Efficiently Indexing Large Sparse Graphs for Similarity Search
Efficiently Indexing Large Sparse Graphs for Similarity Search
复制标题
高效索引大型稀疏图以进行相似性搜索
DOI：
10.1109/tkde.2010.28
复制
发表时间：
2012-03-01
影响因子：
8.9
通讯作者：
Yu, Ge
中科院分区：
文献类型：
--
作者：
Wang, Guoren;Wang, Bin;Yu, Ge
图结构是对蛋白质相互作用网络、化合物、知识查询推理系统、道路网络等结构复杂的无模式数据建模的重要手段。本文研究了大型稀疏图集上相似性搜索的索引结构，并引入Q-Gram思想，提出了一种高效的索引机制。通过将图分解为小的gram（由κ-Adjacent Tree模式组织）并在这些κ-Adjacent Tree模式上配对，可以计算它们的编辑距离的下界估计以用于候选过滤。此外，我们还开发了一系列的倒排索引构建和在线查询处理技术。通过在精确编辑距离计算之前构建查询图的候选集，可以大大减少需要进行精确匹配的图的数量。在真实的数据集和合成数据集上进行了大量的实验，结果表明了所提出的索引机制的有效性和效率。
The graph structure is a very important means to model schemaless data with complicated structures, such as protein-protein interaction networks, chemical compounds, knowledge query inferring systems, and road networks. This paper focuses on the index structure for similarity search on a set of large sparse graphs and proposes an efficient indexing mechanism by introducing the Q-Gram idea. By decomposing graphs to small grams (organized by κ-Adjacent Tree patterns) and pairing-up on those κ-Adjacent Tree patterns, the lower bound estimation of their edit distance can be calculated for candidate filtering. Furthermore, we have developed a series of techniques for inverted index construction and online query processing. By building the candidate set for the query graph before the exact edit distance calculation, the number of graphs need to proceed into exact matching can be greatly reduced. Extensive experiments on real and synthetic data sets have been conducted to show the effectiveness and efficiency of the proposed indexing mechanism.