BROWSE
Detail
Journal Article
Optimization Technique for Prime Number Labeling of Directed Acyclic Graphs
Cited 0 time in 
Share 
Share
- Authors
- Jinhyun Ahn, Dong-Hyuk Im, Taewhi Lee, Hong-Gee Kim
- Issue Date
- 2017-02
- Citation
- Journal of Theoretical and Applied Information Technology, v.95, no.3, pp.645-653
- ISSN
- 1992-8645
- Publisher
- Asian Research Publication Network
- Language
- English
- Type
- Journal Article
- Abstract
- Directed Acyclic Graphs (DAGs) are widely used data structures. Labeling schemes have been proposed to accelerate reachability query processing over DAGs. Among such schemas, prime number labeling has attracted researchers because of its simplicity: a division operation is sufficient for answering reachability queries. However, the limitation of existing prime number labeling algorithms is that they generate huge label sizes. Minimizing the label size is an important issue because query-processing performance depends on it. In this paper, we propose techniques for generating prime number labels that are much smaller than those made by existing algorithms. In order to reduce the overall label size, some heuristics are suggested for sorting the vertices to which prime numbers are assigned. Experiments over real-world and synthetic DAG datasets show that the proposed approach produces smaller labels than existing approaches, and the labeling time is also reduced.
- KSP Keywords
- Data structure, Directed acyclic graphs, Division operation, Existing Approaches, Labeling scheme, Optimization techniques, Prime number labeling, Query processing, Reachability query, Real-world, processing performance