ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

논문 검색
구분 SCI
연도 ~ 키워드

상세정보

학술지 Optimization Technique for Prime Number Labeling of Directed Acyclic Graphs
Cited 0 time in scopus Download 5 time Share share facebook twitter linkedin kakaostory
저자
안진현, 임동혁, 이태휘, 김홍기
발행일
201702
출처
Journal of Theoretical and Applied Information Technology, v.95 no.3, pp.645-653
ISSN
1992-8645
출판사
Asian Research Publication Network
협약과제
16ZS1400, 듀얼모드 배치.쿼리 분석을 제공하는 빅데이터 플랫폼 핵심기술 개발, 원종호
초록
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