Top-K Nearest Keyword Search on Large Graphs
Top-K Nearest Keyword Search on Large Graphs
复制标题
DOI：
10.14778/2536206.2536217
复制
发表时间：
2013-08
期刊：
影响因子：
--
通讯作者：
Miao Qiao;Lu Qin;Hong Cheng;J. Yu;Wentao Tian
中科院分区：
文献类型：
--
作者：
Miao Qiao;Lu Qin;Hong Cheng;J. Yu;Wentao Tian
现在出现的网络在节点上有标签或文本内容是很常见的。在这样的网络上，我们研究了top-k最近的关键字（k-NK）搜索问题。在被建模为无向图的网络G中，每个节点都与零个或多个关键字相连，并且每个边都被分配了衡量其长度的权重。给定G中的查询节点q和关键字λ，k-NK查询寻找包含λ且最接近q的k个节点。k-NK不仅可以作为独立的查询，而且可以作为解决复杂图形模式匹配问题的构建块。准确的k-NK结果的关键是图中精确的最短距离估计。基于最新的距离预言技术，我们建立了一个最短路径树的距离预言和使用树的距离作为一个更准确的估计。通过这种表示，图上的原始k-NK查询可以简化为在一组树上回答查询，然后组装从树中获得的结果。我们提出了两个有效的算法来报告一棵树上的确切的k-NK结果。一个是针对用户感兴趣的少量结果节点的场景优化查询时间。另一个有效地处理任意大k的k-NK查询。在从树上的k-NK结果获得图上的k-NK结果时，提出了一种全局存储技术，以进一步减少索引大小和查询时间。大量的实验结果符合我们的理论研究结果，并证明了我们的k-NK算法的有效性和效率的大型真实的图。
It is quite common for networks emerging nowadays to have labels or textual contents on the nodes. On such networks, we study the problem of top-k nearest keyword (k-NK) search. In a network G modeled as an undirected graph, each node is attached with zero or more keywords, and each edge is assigned with a weight measuring its length. Given a query node q in G and a keyword λ, a k-NK query seeks k nodes which contain λ and are nearest to q. k-NK is not only useful as a stand-alone query but also as a building block for tackling complex graph pattern matching problems. The key to an accurate k-NK result is a precise shortest distance estimation in a graph. Based on the latest distance oracle technique, we build a shortest path tree for a distance oracle and use the tree distance as a more accurate estimation. With such representation, the original k-NK query on a graph can be reduced to answering the query on a set of trees and then assembling the results obtained from the trees. We propose two efficient algorithms to report the exact k-NK result on a tree. One is query time optimized for a scenario when a small number of result nodes are of interest to users. The other handles k-NK queries for an arbitrarily large k efficiently. In obtaining a k-NK result on a graph from that on trees, a global storage technique is proposed to further reduce the index size and the query time. Extensive experimental results conform with our theoretical findings, and demonstrate the effectiveness and efficiency of our k-NK algorithms on large real graphs.