...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Knowledge and Data Engineering >Efficient and Exact Local Search for Random Walk Based Top-K Proximity Query in Large Graphs
【24h】

Efficient and Exact Local Search for Random Walk Based Top-K Proximity Query in Large Graphs

机译：大型图中基于随机游走的Top-K邻近查询的高效且精确的本地搜索

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Top- proximity query in large graphs is a fundamental problem with a wide range of applications. Various random walk based measures have been proposed to measure the proximity between different nodes. Although these measures are effective, efficiently computing them on large graphs is a challenging task. In this paper, we develop an efficient and exact local search method, FLoS (Fast Local Search), for top- proximity query in large graphs. FLoS guarantees the exactness of the solution. Moreover, it can be applied to a variety of commonly used proximity measures. FLoS is based on the property of proximity measures. We show that many measures have no local optimum. Utilizing this property, we introduce several operations to manipulate transition probabilities and develop tight lower and upper bounds on the proximity values. The lower and upper bounds monotonically converge to the exact proximity value when more nodes are visited. We further extend FLoS to measures having local optimum by utilizing relationship among different measures. We perform comprehensive experiments on real and synthetic large graphs to evaluate the efficiency and effectiveness of the proposed method.
机译：大图中的最接近查询是广泛应用中的一个基本问题。已经提出了各种基于随机游动的措施来测量不同节点之间的接近度。尽管这些措施很有效，但是在大型图形上高效地计算它们却是一项艰巨的任务。在本文中，我们开发了一种高效且精确的本地搜索方法FLoS（快速本地搜索），用于大图形中的最接近查询。 FLoS保证了解决方案的准确性。而且，它可以应用于各种常用的接近度测量。 FLoS基于接近度度量的属性。我们表明许多措施没有局部最优。利用此属性，我们引入了几种操作来操纵转移概率，并在接近值上建立严格的上下限。当访问更多节点时，下限和上限单调收敛到确切的接近值。通过利用不同度量之间的关系，我们进一步将FLoS扩展到具有局部最优的度量。我们对真实和合成的大图进行综合实验，以评估该方法的效率和有效性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号