.png){kind=icon}
返回
Scaling Hop-Based Reachability Indexing for Fast Graph Pattern Query Processing
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2014.2310207.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Graph pattern query processing
two-stage node filtering
reachability indexing
3-Hop* labeling
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
10.4
论文数:
6.9K
被引数:
3.2W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容