상세정보
학술지
Optimization Technique for Prime Number Labeling of Directed Acyclic Graphs
Cited 0 time in 
Download 3 time
Share 
Download 3 time
Share
- 저자
- 안진현, 임동혁, 이태휘, 김홍기
- 발행일
- 201702
- 출처
- Journal of Theoretical and Applied Information Technology, v.95 no.3, pp.645-653
- ISSN
- 1992-8645
- 출판사
- Asian Research Publication Network
- 초록
- 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 제안 키워드
- Data structure, Directed acyclic graphs, Division operation, Existing Approaches, Labeling scheme, Optimization techniques(OT), Prime number labeling, Query Processing, Reachability query, Real-world, processing performance