期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2017
卷号：95
期号：3
出版社：Journal of Theoretical and Applied
摘要：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.
关键词：Directed Acyclic Graph; DAG; Prime Number Labeling; Label Assignment Order; Label Size
