Top-k subgraph matching query in a large graph
Top-k subgraph matching query in a large graph
复制标题
DOI：
10.1145/1316874.1316897
复制
发表时间：
2007-11
期刊：
影响因子：
--
通讯作者：
Lei Zou;Lei Chen;Yansheng Lu
中科院分区：
文献类型：
--
作者：
Lei Zou;Lei Chen;Yansheng Lu
近年来，子图搜索由于其广泛的应用，引起了数据库和数据挖掘领域的广泛关注。子图搜索的定义如下：给定一个查询图Q，我们报告数据库中所有包含Q的数据图。然而，在单个大图中进行子图搜索的工作还很少，它已经在生物网络和社会网络等许多应用中得到了应用。本文研究top-k子图匹配查询问题，其定义如下：给定一个查询图Q，我们根据得分函数在一个大型数据图G中定位它的top-k匹配。得分函数被定义为Q中的一个顶点与G中的匹配顶点之间的两两相似度之和。具体地，我们首先设计了一棵平衡树(即G-树)来索引大数据图。然后，在G-Tree的基础上，提出了一种高效的查询算法--排序匹配算法。我们的大量实验结果表明，由于剪枝策略的有效性，对于一个最多20个顶点的查询，我们可以在不到10秒的时间内找到100K个顶点的大型数据图中的前100个匹配。此外，我们的方法比替代方法的性能高出一个数量级。
Recently, due to its wide applications, subgraph search has attracted a lot of attention from database and data mining community. Sub-graph search is defined as follows: given a query graph Q, we report all data graphs containing Q in the database. However, there is little work about sub-graph search in a single large graph, which has been used in many applications, such as biological network and social network. In this paper, we address top-k sub-graph matching query problem, which is defined as follows: given a query graph Q, we locate top-k matchings of Q in a large data graph G according to a score function. The score function is defined as the sum of the pairwise similarity between a vertex in Q and its matching vertex in G. Specifically, we first design a balanced tree (that is G-Tree) to index the large data graph. Then, based on G-Tree, we propose an efficient query algorithm (that is Ranked Matching algorithm). Our extensive experiment results show that, due to efficiency of pruning strategy, given a query with up to 20 vertices, we can locate the top-100 matchings in less than 10 seconds in a large data graph with 100K vertices. Furthermore, our approach outperforms the alternative method by orders of magnitude.