TL;DR
This paper introduces a novel framework for approximating graph pattern queries using pre-computed views. It proposes methods to find "upper" and "lower" bound queries that can be answered using existing views, providing approximate answers to complex queries that cannot be directly answered. This approach significantly speeds up query execution while maintaining reasonable accuracy, making it practical for large-scale graph data.
What Problem Does This Paper Address?
Answering complex graph pattern queries (like those used in social network analysis or recommendation systems) directly on large datasets can be computationally expensive. While using pre-computed "views" (smaller, materialized query results) can speed up exact query answering, it's often impossible to answer complex queries exactly with a limited set of views. This paper addresses this gap by proposing a method to find approximate answers. Instead of an exact match, they aim to find two queries: an "upper approximation" that contains all possible answers and a "lower approximation" that is contained within all possible answers. Crucially, both these approximations can be answered using the available views, offering a trade-off between exactness and efficiency. They consider two common graph query semantics: graph simulation and subgraph isomorphism.
Methods
The core of the paper lies in defining and computing "upper" and "lower" approximations of a query $Q$ with respect to a set of views $V$.
- Approximation Definition: An upper approximation $Q_u$ is a query answerable by $V$ such that $Q \subseteq Q_u$, meaning $Q_u$'s answers contain all of $Q$'s answers. A lower approximation $Q_l$ is similarly answerable by $V$ such that $Q_l \subseteq Q$, meaning $Q_l$'s answers are contained within $Q$'s answers. They also define "complete" approximations where the containment is exact.
- Characterizations: The authors provide theoretical characterizations for when such approximations exist and how they relate to query containment and answering using views.
- Algorithms: They develop algorithms for:
- Existence: Determining if upper/lower approximations exist.
- Closest Approximation: Finding the approximations that are "closest" to the original query $Q$ using a defined "closeness" metric based on edge differences. This involves algorithms like
CUAsimfor complete upper approximations andCLAsimfor complete lower approximations. - Answering Approximations: Generating query plans to answer these approximations using only the view data.
- Subgraph Queries: The framework is extended to handle subgraph queries, which have different matching semantics than simulation queries.
Datasets
The experiments were conducted on two real-life graph datasets:
- DBpedia: A knowledge graph with 4.43 million nodes and 8.43 million edges.
- YouTube: A video network with 2.03 million video nodes and 12.22 million directed edges.
The paper does not introduce new benchmark datasets but uses these existing ones to evaluate their proposed methods.
Key Insights and Ideas
- Bridging the Gap: The most significant insight is that even if a complex graph query cannot be answered exactly using available views, it can often be approximated effectively. This opens up possibilities for query processing in scenarios with limited exact answerability.
- Upper and Lower Bounds as a Solution: The concept of finding both an upper and a lower bound query that can be answered by views provides a practical way to bound the true answer set, offering a trade-off between accuracy and computational cost.
- Approximation is Often Necessary: The experimental results highlight that only a small percentage of queries can be answered exactly using views, underscoring the practical need for approximation techniques.
- Complete Approximations are More Accurate: The study shows that "complete" approximations (where the approximation is a subgraph or supergraph of the original query) generally yield higher accuracy than "generic" approximations.
- Combining Approximations Improves Results: Using both the upper and lower approximations together (specifically, the weak F-measure) significantly improves the overall accuracy compared to using either approximation alone.
Key Results
- Effectiveness: The proposed algorithms for finding closest upper and lower approximations are effective. For simulation queries on DBpedia, the F-measure of approximations is consistently above 0.7, and for subgraph queries, it's above 0.6.
- Accuracy: Complete approximations are more accurate than generic ones. For instance, complete approximations achieved an F-measure of 0.89 compared to 0.82 for generic ones on larger subgraph queries.
- Speedup: Querying using approximations with views offers substantial speedups. For simulation queries on YouTube, evaluation time was 80-300 times faster than direct evaluation.
- Efficiency: The algorithms for computing approximations are efficient, taking at most 2.7 seconds for all queries on both datasets, even with all views.
- Answerability vs. Approximation: While only a small percentage of queries were exactly answerable using views (e.g., 12% for simulation queries on DBpedia), a much larger percentage (e.g., 85% for simulation queries on DBpedia) could be approximated.
Limitations and Future Work
- Approximation Quality: While effective, approximations are not exact. The paper acknowledges that the quality of approximation depends on the available views and the query structure.
- Closeness Metric: The "closeness" metric is based on edge differences, which might not always perfectly align with user-perceived similarity.
- Future Work: The authors suggest several directions:
- Studying optimal approximations when views have associated costs.
- Investigating optimal pairs of upper and lower approximations that cover specific parts of queries.
- Extending the framework to other query types, such as relational queries.
- Adapting the techniques for dynamic data graphs.
Summary updated