1. Scaling Hop-Based Reachability Indexing for Fast Graph Pattern Query Processing.
- Author
-
Liang, Ronghua, Zhuge, Hai, Jiang, Xiaorui, Zeng, Qiang, and He, Xiaofei
- Subjects
- *
COMPUTER networks , *SCALABILITY , *GRAPH theory , *QUERYING (Computer science) , *PATTERN recognition systems , *AUTOMATIC data collection systems , *SEMANTIC network analysis , *INFORMATION retrieval - Abstract
Graphs are becoming increasingly dominant in modeling real-life networked data including social and biological networks, the WWW and the Semantic Web, etc. Graph pattern queries are useful for gathering information with expressive semantics from these graph-structured data. Current methods for graph pattern query processing have performance deficiency caused by inefficiencies of the underlying reachability index and costly merge-join operations on huge amounts of tuple-formatted intermediate results. To overcome the above problems, this paper contributes in the following aspects to boost graph pattern query evaluation. First, we propose an improved hop-based reachability indexing scheme 3-Hop* which gains faster reachability query evaluation, less indexing costs and better scalabilities than state-of-the-art hop-based methods. Second, we propose a two-stage node filtering algorithm based on 3-Hop* to answer tree pattern queries more efficiently. Tree pattern queries serve as the underlying facility for graph pattern query evaluation. Furthermore, we use a graph representation of the intermediate results during node filtering and final results enumeration. Experiments on real-life and synthetic datasets demonstrate the effectiveness of the proposed methods. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF