@inproceedings{3964b0d68913482d8b4aa29aa204a10d,
title = "Fruited-Forest: A Reachability Querying Method Based on Spanning Tree Modelling of Reduced DAG",
abstract = "A reachability query is a fundamental graph operation in real graph applications, which answers whether a node can reach another node through a path in a graph. However, the increasingly large amounts of real graph data make it more challenging for query efficiency and scalability. In this paper, we propose a Fruited-Forest (FF) approach to accelerate reachability queries in large graphs by constructing four kinds of fruited-forests from a reduced DAG in different traversal orders. We build different binary-label schemes for the four kinds of fruited-forests to cover reachability between nodes as much as possible, and create a corresponding index for the deleted edges which are deleted during the construction of fruited-forests. Our experimental results on 18 large real graph datasets show that our FF approach requires less index construct time and a smaller index size, which is more scalable to answer reachability queries compared with other existing works.",
keywords = "DAG reduction, Fruit-forest, Large graph, Reachability query, Spanning tree",
author = "Liu Yang and Tingxuan Chen and Junyu Zhang and Jun Long and Zhigang Hu and Sheng, {Victor S.}",
note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; null ; Conference date: 18-09-2020 Through 20-09-2020",
year = "2020",
doi = "10.1007/978-3-030-60259-8_11",
language = "English",
isbn = "9783030602581",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "145--153",
editor = "Xin Wang and Rui Zhang and Young-Koo Lee and Le Sun and Yang-Sae Moon",
booktitle = "Web and Big Data - 4th International Joint Conference, APWeb-WAIM 2020, Proceedings",
}