Name
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11733836_56 | DASFAA |
Keywords | Field | DocType |
extensive experimental result,acyclic graph,response time,optimization technique,intrinsic mapping,indexing dag,prime number,original scheme,integer divisibility,subsumption hierarchy,directed acyclic graph,transitive closure,indexation,satisfiability | Integer,Prime number,Divisibility rule,Computer science,Algorithm,Directed graph,Search engine indexing,Directed acyclic graph,Redundancy (engineering),Transitive closure | Conference |
Volume | ISSN | ISBN |
3882 | 0302-9743 | 3-540-33337-1 |
Citations | PageRank | References |
13 | 0.77 | 7 |
Authors | ||
4 | ||