Efficiently answering reachability queries on very large directed graphs

No abstract is available for this paper.

• Publication year

  2008

• Venue

  SIGMOD Conference

• Publication date

  2008-06-09

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1145/1376616.1376677
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Fast and practical indexing and querying of very large graphs

  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
• Stack-based Algorithms for Pattern Matching on DAGs

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

  2004influential reference
• Reachability and distance queries via 2-hop labels

  2002cited by this paper
• Computational geometry: algorithms and applications

  1997influential reference
• Computational geometry: algorithms and applications, 3rd Edition

  1997influential reference
• Introduction to algorithms

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

  1990cited by this paper
• Efficient management of transitive relationships in large data and knowledge bases

  1989cited by this paper
• An Improved Algorithm for Transitive Closure on Acyclic Digraphs

  1986cited by this paper
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

  1986cited by this paper
• On the Vector Representation of the Reachability in Planar Directed Graphs

  1975cited by this paper

• Reachability-state encoding: bridging tradeoffs between the minimal storage and the fastest query for reachability query

  2026cites this paper
• TDS: fast answering reachability queries with hierarchical traversal trees

  2025cites this paper
• Preserving K-Connectivity in Dynamic Graphs

  2025cites this paper
• Parameter Invariance Analysis of Moment Equations Using Dulmage-Mendelsohn Decomposition

  2025cites this paper
• Fast Answering Pattern-Constrained Reachability Queries with Two-Dimensional Reachability Index

  2025cites this paper
• Efficient k-step Weighted Reachability Queries Processing Algorithms

  2025cites this paper
• On Querying Historical Connectivity in Large-scale Temporal Graphs

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

  2024cites this paper
• ActiveReach: an active learning framework for approximate reachability query answering in large-scale graphs

  2024cites this paper
• POLIGRAS: Policy-based Graph Summarization

  2024cites this paper
• On Querying Historical Connectivity in Temporal Graphs

  2024cites this paper
• Parameterized Linear Time Transitive Closure

  2024cites this paper
• Efficient k-step Weighted Reachability Query Processing Algorithms

  2024cites this paper
• Fast Reachability Using DAG Decomposition

  2023cites this paper
• HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs

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

  2023cites this paper
• Indexing Techniques for Graph Reachability Queries

  2023influential citation
• Efficient and Effective Directed Minimum Spanning Tree Queries

  2023cites this paper
• Evaluation of Reachability Queries Based on Recursive DAG Decomposition

  2023cites this paper
• Answering reachability queries with ordered label constraints over labeled graphs

  2023cites this paper
• IFCA: Index-Free Community-Aware Reachability Processing Over Large Dynamic Graphs

  2023cites this paper
• A Hierarchical Contraction Scheme for Querying Big Graphs

  2022cites this paper
• Fast and Practical DAG Decomposition with Reachability Applications

  2022cites this paper
• DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs

  2022cites this paper
• Reachability Labeling for Distributed Graphs

  2022cites this paper
• A Reachability Index for Recursive Label-Concatenated Graph Queries

  2022cites this paper
• Efficient Reachability Query with Extreme Labeling Filter

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

  2022cites this paper
• Preference Queries over Taxonomic Domains

  2021cites this paper
• GOMS: Large‐scale ontology management system using graph databases

  2021cites this paper
• Span-reachability querying in large temporal graphs

  2021cites this paper
• An Index for Single Source All Destinations Distance Queries in Temporal Graphs

  2021cites this paper
• Making graphs compact by lossless contraction

  2021cites this paper
• Graph Indexing for Efficient Evaluation of Label-constrained Reachability Queries

  2021cites this paper
• Faster Reachability in Static Graphs

  2020cites this paper
• Graph Reachability on Parallel Many-Core Architectures

  2020cites this paper
• Efficiently Answering Span-Reachability Queries in Large Temporal Graphs

  2020cites this paper
• A Parallel Many-core CUDA-based Graph Labeling Computation

  2020cites this paper
• CPOI: A Compact Method to Archive Versioned RDF Triple-Sets

  2019cites this paper
• An efficient reachability query based pruning algorithm in e-health scenario

  2019cites this paper
• Implicit Landmark Path Indexing for Bounded Label Constrained Reachable Paths

  2019cites this paper
• Bachelorarbeit Dynamic All-Pairs Reachability on Partitioned Graphs

  2019cites this paper
• Efficient distributed reachability querying of massive temporal graphs

  2019cites this paper
• A TSGP-Based Tip Search Optimization Algorithm

  2019cites this paper
• Labeled graph sketches: Keeping up with real-time graph streams

  2019cites this paper
• Modular Decomposition-Based Graph Compression for Fast Reachability Detection

  2019cites this paper
• Reachability in Large Graphs Using Bloom Filters

  2019cites this paper
• DBL : Reachability Queries on Dynamic Graphs Technical Report

  2019cites this paper
• Multi-level Graph Compression for Fast Reachability Detection

  2019cites this paper
• Accelerating reachability query processing based on DAG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{DAG}$$\

  2018cites this paper
• Query Processing on Attributed Graphs

  2018cites this paper
• Storage, processing and analysis of large evolving graphs

  2018cites this paper
• A BFS-Based Pruning Algorithm for Disease-Symptom Knowledge Graph Database

  2018cites this paper
• MGTag: a Multi-Dimensional Graph Labeling Scheme for Fast Reachability Queries

  2018cites this paper
• The Space-Efficient Core of Vadalog

  2018cites this paper
• Large-Scale Ontology Matching

  2018cites this paper
• Min-Forest: Fast Reachability Indexing Approach for Large-Scale Graphs on Spark Platform

  2018cites this paper
• Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations

  2018cites this paper
• Edge Influence Computation in Dynamic Graphs

  2017cites this paper
• Real-Time Targeted-Influence Queries over Large Graphs

  2017cites this paper
• DAG Reduction: Fast Answering Reachability Queries

  2017cites this paper
• HD-GDD: high dimensional graph dominance drawing approach for reachability query

  2017cites this paper
• All-Pairs 2-Reachability in O(n^w log n) Time

  2017cites this paper
• Reachability Querying: Can It Be Even Faster?

  2017influential citation
• Scalable Algorithms for Mining Graphs and Social Networks via Sampling

  2017cites this paper
• BFSI-B: An improved K-hop graph reachability queries for cyber-physical systems

  2017cites this paper
• Indexing Public-Private Graphs

  2017cites this paper
• DistR: A Distributed Method for the Reachability Query over Large Uncertain Graphs

  2016cites this paper
• A Greedy Approach to Answer Reachability Queries on DAGs

  2016cites this paper
• Para-G: Path pattern query processing on large graphs

  2016cites this paper
• GeoReach: An Efficient Approach for Evaluating Graph Reachability Queries with Spatial Range Predicates

  2016cites this paper
• All-Pairs $2$-reachability in Õ(nω) Time

  2016cites this paper
• Answering Reachability Queries on Incrementally Updated Graphs by Hierarchical Labeling Schema

  2016influential citation
• Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs

  2016cites this paper
• All-Pairs 2-Reachability in $\mathcal{O}(n^{\omega}\log n)$ Time

  2016cites this paper
• Efficient index structures for reachability and shortest path queries

  2016cites this paper
• Query Processing and Optimization in Graph Databases

  2015influential citation
• Giga-scale exhaustive points-to analysis for Java in under a minute

  2015cites this paper
• A Reachability Query Method Based on Labeling Index on Large-Scale Graphs

  2015cites this paper
• TopCom: Index for Shortest Distance Query in Directed Graph

  2015cites this paper
• Microblog Entity Linking with Social Temporal Context

  2015cites this paper
• TimeReach: Historical Reachability Queries on Evolving Graphs

  2015cites this paper
• A Framework for Computing on Large Dynamic Graphs

  2015cites this paper
• A Case Study on the Use of Semantic Web Technologies for Learner Guidance

  2015cites this paper
• Zip: An Algorithm Based on Loser Tree for Common Contacts Searching in Large Graphs

  2015cites this paper
• Algorithmic building blocks for relationship analysis over large graphs

  2015cites this paper
• The Graph Pattern Matching Problem through Parameterized Matching

  2015cites this paper
• Mining and Managing Large-Scale Temporal Graphs

  2015cites this paper
• K-Reach Query Processing Based on Graph Compression

  2014cites this paper
• Stream Querying and Reasoning on Social Data

  2014cites this paper
• Path Pattern Query Processing on Large Graphs

  2014cites this paper
• Reachability querying: an independent permutation labeling approach

  2014influential citation
• Curating the Specificity of Ontological Descriptions under Ontology Evolution

  2014cites this paper
• PReaCH: A Fast Lightweight Reachability Index Using Pruning and Contraction Hierarchies

  2014cites this paper
• Estimating pairwise distances in large graphs

  2014cites this paper
• Reachability Queries in Very Large Graphs: A Fast Refined Online Search Approach

  2014cites this paper
• Shortest-path queries in static networks

  2014cites this paper
• Reachability queries on large dynamic graphs: a total order approach

  2014cites this paper
• Scaling Hop-Based Reachability Indexing for Fast Graph Pattern Query Processing

  2014cites this paper
• Efficient processing of label-constraint reachability queries in large graphs

  2014cites this paper