ETRI-Knowledge Sharing Plaform

KOREAN
논문 검색
Type SCI
Year ~ Keyword

Detail

Journal Article Optimization Technique for Prime Number Labeling of Directed Acyclic Graphs
Cited 0 time in scopus Download 7 time Share share facebook twitter linkedin kakaostory
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
Project Code
16ZS1400, 듀얼모드 배치.쿼리 분석을 제공하는 빅데이터 플랫폼 핵심기술 개발, Won Jongho
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(OT), Prime number labeling, Query Processing, Reachability query, Real-world, processing performance