Adapting Prime Number Labeling Scheme for Directed Acyclic Graphs Export

@incollection{wu2006, abstract = {Directed Acyclic Graph(DAG) could be used for modeling subsumption hierarchies. Several labeling schemes have been proposed or tailored for indexing DAG in order to efficiently explore relationships in such hierarchy. However few of them can satisfy all the requirements in response time, space, and effect of updates simultaneously. In this paper, the prime number labeling scheme is extended for DAG. The scheme invests intrinsic mapping between integer divisibility and subsumption hierarchy, which simplifies the transitive closure computations and diminishes storage redundancy, as well as inherits the dynamic labeling ability from original scheme. Performance is further improved by introducing some optimization techniques. Our extensive experimental results show that prime number labeling scheme for DAG outperforms interval-based and prefix-based labeling schemes in most cases.}, author = {Wu, Gang and Zhang, Kuo and Liu, Can and Li, Juanzi}, citeulike-article-id = {2405743}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/11733836_56}, doi = {10.1007/11733836_56}, journal = {Database Systems for Advanced Applications}, keywords = {db, eswc08, graph, graph-db, pragmatic, rdf}, pages = {787--796}, posted-at = {2008-02-21 09:12:44}, priority = {2}, title = {Adapting Prime Number Labeling Scheme for Directed Acyclic Graphs}, url = {http://dx.doi.org/10.1007/11733836_56}, year = {2006} }

TY - CHAP ID - wu2006 L3 - citeulike-article-id:2405743 N2 - Directed Acyclic Graph(DAG) could be used for modeling subsumption hierarchies. Several labeling schemes have been proposed or tailored for indexing DAG in order to efficiently explore relationships in such hierarchy. However few of them can satisfy all the requirements in response time, space, and effect of updates simultaneously. In this paper, the prime number labeling scheme is extended for DAG. The scheme invests intrinsic mapping between integer divisibility and subsumption hierarchy, which simplifies the transitive closure computations and diminishes storage redundancy, as well as inherits the dynamic labeling ability from original scheme. Performance is further improved by introducing some optimization techniques. Our extensive experimental results show that prime number labeling scheme for DAG outperforms interval-based and prefix-based labeling schemes in most cases. JF - Database Systems for Advanced Applications EP - 796 TI - Adapting Prime Number Labeling Scheme for Directed Acyclic Graphs SP - 787 KW - db KW - eswc08 KW - graph KW - graph-db KW - pragmatic KW - rdf AU - Wu, Gang AU - Zhang, Kuo AU - Liu, Can AU - Li, Juanzi PY - 2006/// UR - http://dx.doi.org/10.1007/11733836_56 ER -