PReaCH: A Fast Lightweight Reachability Index Using Pruning and Contraction Hierarchies

We develop the data structure PReaCH (for Pruned Reachability Contraction Hierarchies) which supports reachability queries in a directed graph. PReaCH adapts the contraction hierarchy speedup techniques for shortest path queries to the reachability setting. The resulting approach is surprisingly simple and guarantees linear space and near linear preprocessing time. Orthogonally to that, we improve existing pruning techniques for the search by gathering more information from a single DFS-traversal of the graph. In particular, we show that more classes of node numberings can be used to obtain strong pruning information.

• Publication year

  2014

• Venue

  Embedded Systems and Applications

• Publication date

  2014-04-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-662-44777-2_58arXiv 1404.4465
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Route Planning in Transportation Networks

  2015influential reference
• Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths

  2013influential reference
• Simple, Fast, and Scalable Reachability Oracle

  2013cited by this paper
• On fast parallel detection of strongly connected components (SCC) in small-world graphs

  2013cited by this paper
• FERRARI: Flexible and efficient reachability range assignment for graph indexing

  2013cited by this paper
• TF-Label: a topological-folding labeling scheme for reachability querying in a large graph

  2013cited by this paper
• Exact Routing in Large Road Networks Using Contraction Hierarchies

  2012influential reference
• SCARAB: scaling reachability computation on large graphs

  2012cited by this paper
• A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks

  2011cited by this paper
• Path-tree: An efficient reachability indexing scheme for large directed graphs

  2011cited by this paper
• GRAIL: a scalable index for reachability queries in very large graphs

  2011influential reference
• A memory efficient reachability data structure through bit vector compression

  2011cited by this paper
• Introducing the Graph 500

  2010cited by this paper
• 3-HOP: a high-compression indexing scheme for reachability query

  2009cited by this paper
• Fast computing reachability labelings for large graphs with high compression rate

  2008cited by this paper
• An Efficient Algorithm for Answering Graph Reachability Queries

  2008cited by this paper
• Efficiently answering reachability queries on very large directed graphs

  2008cited by this paper
• Fast and practical indexing and querying of very large graphs

  2007cited by this paper
• Dynamic Highway-Node Routing

  2007cited by this paper
• Fast Routing in Road Networks with Transit Nodes

  2007cited by this paper
• Dual Labeling: Answering Graph Reachability Queries in Constant Time

  2006cited by this paper
• Fast Computation of Reachability Labeling for Large Graphs

  2006cited by this paper
• A simple recursive numerical method for Bermudan option pricing under Lévy processes

  2006cited by this paper
• Stack-based Algorithms for Pattern Matching on DAGs

  2005cited by this paper
• HOPI: An Efficient Connection Index for Complex XML Document Collections

  2004cited by this paper
• Reachability and distance queries via 2-hop labels

  2002cited by this paper
• Resource Description Framework (RDF) Model and Syntax Specification

  2002cited by this paper
• Fast priority queues for cached memory

  1999cited by this paper
• A Query Language for XML

  1999cited by this paper
• RegulonDB: a database on transcriptional regulation in Escherichia coli

  1998cited by this paper
• Introduction to algorithms

  1996cited by this paper
• Bounded Ordered Dictionaries in O(log log N) Time and O(n) Space

  1990cited by this paper
• A compression technique to materialize transitive closure

  1990cited by this paper
• Preserving order in a forest in less than logarithmic time

  1975cited by this paper

• MLRQ: an efficient labeling scheme for reachability queries on reduced DAGs

  2025cites this paper
• Minimum Strongly Connected Subgraph Collection in Dynamic Graphs

  2024cites this paper
• GA-Based Multipopulation Synergistic Gene Screening Strategy on Critical Nodes Detection

  2024cites this paper
• Indexing Techniques for Graph Reachability Queries

  2023cites this paper
• An Overview of Reachability Indexes on Graphs

  2023cites this paper
• O’Reach: Even Faster Reachability in Large Graphs

  2022influential citation
• Reachability and Top-k Reachability Queries with Transfer Decay

  2021cites this paper
• Faster Reachability in Static Graphs

  2020influential citation
• Fully Dynamic Single-Source Reachability in Practice: An Experimental Study

  2019cites this paper
• Markov fundamental tensor and its applications to network analysis

  2019cites this paper
• Random Walk Fundamental Tensor and its Applications to Network Analysis

  2018cites this paper
• Efficient Processing of Reachability Queries with Meetings

  2017cites this paper
• Efficient top-k shortest path query processing in sparse graph databases

  2017cites this paper
• Indexing Public-Private Graphs

  2017cites this paper
• A Survey on Methods and Systems for Graph Compression

  2015cites this paper
• Public Transit Labeling

  2015cites this paper
• RICC: Fast Reachability Query Processing on Large Spatiotemporal Datasets

  2015cites this paper