Efficient Graph Similarity Search in External Memory
Efficient Graph Similarity Search in External Memory
复制标题
外部存储器中的高效图形相似性搜索
DOI：
10.1109/access.2017.2682107
复制
发表时间：
2017-01-01
期刊：
影响因子：
3.9
通讯作者：
Vitter, Jeffrey Scott
中科院分区：
文献类型：
--
作者：
Chen, Xiaoyang;Huo, Hongwei;Vitter, Jeffrey Scott
许多现实世界的应用程序，例如生物信息学、数据挖掘、模式识别和社交网络分析，都受益于图相似性搜索问题的有效解决方案。现有方法在处理大型图数据库时，例如那些具有数百万或数十亿个图且无法容纳在主内存中的数据库时，可扩展性有限。本文研究外部存储器中图编辑距离约束下的图相似度搜索问题。我们为任意基于 <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>-<inline-formula> <tex-math notation="LaTeX">${gram}$ </tex-math></inline-formula> 的图表示提供了一个有效的框架。具体来说，我们提出了一个以混合布局存储在外部存储器中的 <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>-<italic>gram</italic> 矩阵索引，通过转换 <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>-<italic>gram</italic> 计数过滤器来实现高效的查询处理转化为稀疏矩阵向量乘法问题。此外，我们还通过将全局过滤器转换为二维查询矩形来提高查询性能，这允许我们在缩小的区域中执行查询，从而显着减少实际中的查询 I/O 数量。对真实数据集的大量实验证实：1）我们的方法可以在索引大小和过滤能力方面与最先进的内存方法竞争，并且在处理包括 2500 万个化学结构图的 PubChem 数据集的可扩展性方面优于它们；2）与流行的 <inline-formula> <tex-math notation="LaTeX">$q$ 相比基于 </tex-math></inline-formula>-<italic>gram</italic> 的外部倒排索引，我们的外部索引结构在 PubChem 数据集上需要更少的查询 I/O 数量。
Many real-world applications, such as bioinformatics, data mining, pattern recognition, and social network analysis, benefit from efficient solutions for the graph similarity search problem. Existing methods have limited scalability when they handle the large graph databases, for example, those with millions or billions of graphs that cannot fit in main memory. In this paper, we study the problem of graph similarity search under the graph edit distance constraint in external memory. We present an efficient framework for arbitrary <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>-<inline-formula> <tex-math notation="LaTeX">${gram}$ </tex-math></inline-formula>-based representations of a graph. Specifically, we propose a <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>-<italic>gram</italic> matrix index stored in hybrid layout in external memory to achieve efficient query processing, by converting the <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>-<italic>gram</italic> counting filter into a sparse matrix-vector multiplication problem. Furthermore, we also boost the query performance by transforming the global filter to a 2-D query rectangle, which allows us to perform a query in a reduced region, significantly reducing the number of query I/Os in practice. Extensive experiments on real data sets confirm that 1) our method can compete with the state-of-the-art in-memory methods in index size and filtering ability, and outperform them on scalability of coping with the PubChem data set including 25 million chemical structure graphs and 2) compared with the popular <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula>-<italic>gram</italic>-based external inverted index, our external index structure needs much fewer number of query I/Os on the PubChem data set.