Fruited-Forest: A Reachability Querying Method Based on Spanning Tree Modelling of Reduced DAG

Liu Yang, Tingxuan Chen, Junyu Zhang, Jun Long, Zhigang Hu, Victor S. Sheng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationWeb and Big Data - 4th International Joint Conference, APWeb-WAIM 2020, Proceedings
EditorsXin Wang, Rui Zhang, Young-Koo Lee, Le Sun, Yang-Sae Moon
PublisherSpringer Science and Business Media Deutschland GmbH
Pages145-153
Number of pages9
ISBN (Print)9783030602581
DOIs
StatePublished - 2020
Event4th Asia-Pacific Web and Web-Age Information Management, Joint Conference on Web and Big Data, APWeb-WAIM 2020 - Tianjin, China
Duration: Sep 18 2020Sep 20 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12317 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th Asia-Pacific Web and Web-Age Information Management, Joint Conference on Web and Big Data, APWeb-WAIM 2020
Country/TerritoryChina
CityTianjin
Period09/18/2009/20/20

Keywords

  • DAG reduction
  • Fruit-forest
  • Large graph
  • Reachability query
  • Spanning tree

Fingerprint

Dive into the research topics of 'Fruited-Forest: A Reachability Querying Method Based on Spanning Tree Modelling of Reduced DAG'. Together they form a unique fingerprint.

Cite this