Performance Guarantees for Distributed Reachability Queries

Yinghui Wu, Wenfei Fan, Xin Wang, Yinghui Wu 0001arXiv 2012 · arXiv

Abstract

Distributed graph processing is essential for handling massive datasets like social networks and web graphs. However, traditional methods often suffer from high network overhead and lack performance guarantees. This paper presents a framework for answering reachability, bounded reachability, and regular reachability queries on distributed graphs using partial evaluation. By visiting each site only once and minimizing data transfer, the proposed approach ensures that network traffic remains independent of the total graph size, offering significant speedups over iterative message-passing models.

Introduction: The Challenge of Geo-Distributed Graphs

In modern data architectures, massive graphs are frequently partitioned across multiple data centers (DCs) to optimize for latency, storage, and privacy. Querying these fragmented graphs—for instance, determining if a path exists between two users in a global social network—presents a significant challenge.

Distributed graph fragmentation and reachability query example.

Traditional distributed query processing typically follows one of two paradigms:

  1. Data Shipping: Centralizing all fragments at a single node. This is often infeasible due to the sheer volume of data and strict privacy regulations.
  2. Iterative Message Passing: Systems like Pregel execute computation locally but require multiple rounds of synchronization between servers. This leads to high network overhead and unpredictable completion times for complex queries.

Methodology: Partial Evaluation and Assembly

The core of this research is the application of partial evaluation to graph reachability. Instead of an iterative search, the process is divided into three distinct phases:

  1. Query Distribution: A central coordinator broadcasts the query to all participating sites simultaneously.
  2. Local Partial Evaluation: Each site evaluates the query against its local data fragment. Edges that cross into other fragments are treated as symbolic variables. The output of this step is a partial answer—a set of Boolean equations representing reachability within the fragment's boundaries.
  3. Global Assembly: The coordinator collects these compact Boolean formulas and constructs a "dependency graph." Solving this significantly smaller graph provides the final answer for the entire distributed system.
The partial evaluation framework: distributing queries, local evaluation, and assembling partial answers.

This architecture ensures a "single visit" guarantee: each site is accessed exactly once per query, drastically reducing the communication overhead typical of iterative models. Furthermore, the logic is designed to be compatible with parallel frameworks like MapReduce.

Experimental Evaluation

The authors tested their algorithms on a diverse set of real-world and synthetic datasets, ranging from social networks (LiveJournal, YouTube) to web graphs (BerkStan) and product co-purchasing networks (Amazon). Synthetic graphs were scaled up to 36 million nodes and 360 million edges to test the limits of the system.

Key Insights

  • Traffic Independence: Network traffic is determined by the number of "cross-edges" between fragments and the query complexity, rather than the total number of nodes in the graph.
  • Efficiency: On the Amazon dataset, the proposed disReach algorithm outperformed traditional distributed BFS by a factor of 16, completing in just 6% of the time.
  • Scalability: Regular reachability queries (matching path patterns) on a graph with 1.5 million nodes were resolved in approximately 16 seconds.
  • Minimal Overhead: Data transferred during the query process averaged only 11% of the total graph size, compared to the 100% required by centralized shipping methods.

Conclusion and Future Directions

By leveraging partial evaluation, this framework provides robust performance guarantees for distributed reachability queries. It effectively decouples local computation from global coordination, making it highly suitable for massive, geo-distributed datasets.

While the current work handles reachability with node repetition efficiently, finding "simple paths" (no repeated nodes) remains an NP-complete challenge. Future research aims to extend this partial evaluation approach to more complex graph pattern matching and to develop incremental computation techniques for dynamic graphs that evolve in real-time.

Summary updated

BibTeX
@misc{wu2012performance,
  author = {Yinghui Wu and Wenfei Fan and Xin Wang and Yinghui Wu},
  title = {{Performance Guarantees for Distributed Reachability Queries}},
  year = {2012},
  eprint = {1208.0091},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1208.0091},
}
Figure