Table of Content

Open Access iconOpen Access

ARTICLE

An Optimized Labeling Scheme for Reachability Queries

Xian Tang1,*, Ziyang Chen2, Haiyan Zhang3, Xiang Liu1, Yunyu Shi1, Asad Shahzadi4

School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201600, China.
Lixin University of Accounting and Finance, Shanghai 201620, China.
Yanshan University, Qinhuangdao 066004, China.
NCBAE, Lahore 54660, Pakistani.

* Corresponding author: Xian Tang. Email: email.

Computers, Materials & Continua 2018, 55(2), 267-283. https://doi.org/10.3970/cmc.2018.01839

Abstract

Answering reachability queries is one of the fundamental graph operations. Existing approaches either accelerate index construction by constructing an index that covers only partial reachability relationship, which may result in performing cost traversing operation when answering a query; or accelerate query answering by constructing an index covering the complete reachability relationship, which may be inefficient due to comparing the complete node labels. We propose a novel labeling scheme, which covers the complete reachability relationship, to accelerate reachability queries processing. The idea is to decompose the given directed acyclic graph (DAG) G into two subgraphs, G1 and G2. For G1, we propose to use topological labels consisting of two integers to answer all reachability queries. For G2, we construct 2-hop labels as existing methods do to answer queries that cannot be answered by topological labels. The benefits of our method lie in two aspects. On one hand, our method does not need to perform the cost traversing operation when answering queries. On the other hand, our method can quickly answer most queries in constant time without comparing the whole node labels. We confirm the efficiency of our approaches by extensive experimental studies using 20 real datasets.

Keywords


Cite This Article

APA Style
Tang, X., Chen, Z., Zhang, H., Liu, X., Shi, Y. et al. (2018). An optimized labeling scheme for reachability queries. Computers, Materials & Continua, 55(2), 267-283. https://doi.org/10.3970/cmc.2018.01839
Vancouver Style
Tang X, Chen Z, Zhang H, Liu X, Shi Y, Shahzadi A. An optimized labeling scheme for reachability queries. Comput Mater Contin. 2018;55(2):267-283 https://doi.org/10.3970/cmc.2018.01839
IEEE Style
X. Tang, Z. Chen, H. Zhang, X. Liu, Y. Shi, and A. Shahzadi "An Optimized Labeling Scheme for Reachability Queries," Comput. Mater. Contin., vol. 55, no. 2, pp. 267-283. 2018. https://doi.org/10.3970/cmc.2018.01839



cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 1995

    View

  • 1225

    Download

  • 0

    Like

Related articles

Share Link