BROWSE
Detail
Journal Article
Efficiently Answering Reachability Queries for Tree-Structured Data in Repetitive Prime Number Labeling Schemes
- Authors
- Jinhyun Ahn, Taewhi Lee, Dong-Hyuk Im
- Issue Date
- 2018-05
- Citation
- Applied Sciences, v.8, no.5, pp.1-9
- ISSN
- 2076-3417
- Publisher
- MDPI AG
- Language
- English
- Type
- Journal Article
- Project Code
- 17HS7600, Development of an Unified Data Engineering Technology for Large-scale Transaction Processing and Real-time Complex Analytics, Chang Soo Kim
- Abstract
- Reachability queries plays a crucial role in accessing relationships between nodes in tree-structured data. Previous studies have proposed prime number labeling schemes that answer reachability queries using arithmetic operations. However, the prime numbers in these schemes can become very large when a tree contains a considerable number of nodes; thus, it is not scalable. Recently, a repetitive prime number labeling scheme that reduces space requirements was proposed. Unfortunately, it suffers from slow query processing, owing to the complexity of its reachability test. In this paper, we propose a more efficient method for answering reachability queries in a repetitive prime number labeling scheme. The results of experiments using real-world XML datasets show that our approach reduces reachability query processing times.
- KSP Keywords
- Arithmetic operations, Labeling scheme, Prime number labeling, Query Processing, Reachability query, Real-world, Space requirements, Tree-Structured Data
This work is distributed under the term of Creative Commons License (CCL)
(CC BY)
(CC BY)
