Query Optimization of Distributed Pattern Matching

Provided by: Yale University
Topic: Data Management
Format: PDF
Greedy algorithms for subgraph pattern matching operations are often sufficient when the graph data set can be held in memory on a single machine. However, as graph data sets increasingly expand and require external storage and partitioning across a cluster of machines, more sophisticated query optimization techniques become critical to avoid explosions in query latency. In this paper, the authors introduce several query optimization techniques for distributed graph pattern matching. These techniques include a system-R style dynamic programming-based optimization algorithm that considers both linear and bushy plans, s cycle detection-based algorithm that leverages cycles to reduce intermediate result set sizes and a computation reusing technique that eliminates redundant query execution and data transfer over the network.

Find By Topic