Approximate Shortest Distance Computing: A Query-Dependent Local Landmark Scheme
Approximate Shortest Distance Computing: A Query-Dependent Local Landmark Scheme
复制标题
DOI：
10.1109/icde.2012.53
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
Miao Qiao;Hong Cheng;Lijun Chang;J. Yu
中科院分区：
文献类型：
--
作者：
Miao Qiao;Hong Cheng;Lijun Chang;J. Yu
节点间最短距离查询是大规模网络中的一项基本操作。文献中的大多数现有方法采用地标嵌入方法，该方法选择一组图节点作为地标，并计算从每个地标到所有节点的最短距离作为嵌入。为了处理两个节点之间的最短距离查询，使用预先计算的从地标到查询节点的距离来基于三角不等式计算近似最短距离。在本文中，我们分析了在地标嵌入方法中影响距离估计精度的因素。特别是，我们发现，一个全球性的选择，查询独立的地标集加上三角测量的距离估计引入了一个大的相对误差，特别是附近的查询节点。为了解决这个问题，我们提出了一个查询相关的本地地标计划，它确定了一个本地地标接近特定的查询节点，并提供了一个更准确的距离估计比传统的全球地标的方法。具体地说，本地地标被定义为最短路径树中的两个查询节点的最小共同祖先在一个全局地标。我们提出了有效的本地地标索引和检索技术，这是至关重要的，以实现低离线索引的复杂性和在线查询的复杂性。提出了图压缩和图在线搜索两种优化技术，以进一步减小索引大小，提高查询精度。我们在大规模社交网络和道路网络上的实验结果表明，与全局地标嵌入相比，局部地标方案显着降低了最短距离估计误差。
Shortest distance query between two nodes is a fundamental operation in large-scale networks. Most existing methods in the literature take a landmark embedding approach, which selects a set of graph nodes as landmarks and computes the shortest distances from each landmark to all nodes as an embedding. To handle a shortest distance query between two nodes, the precomputed distances from the landmarks to the query nodes are used to compute an approximate shortest distance based on the triangle inequality. In this paper, we analyze the factors that affect the accuracy of the distance estimation in the landmark embedding approach. In particular we find that a globally selected, query-independent landmark set plus the triangulation based distance estimation introduces a large relative error, especially for nearby query nodes. To address this issue, we propose a query-dependent local landmark scheme, which identifies a local landmark close to the specific query nodes and provides a more accurate distance estimation than the traditional global landmark approach. Specifically, a local landmark is defined as the least common ancestor of the two query nodes in the shortest path tree rooted at a global landmark. We propose efficient local landmark indexing and retrieval techniques, which are crucial to achieve low offline indexing complexity and online query complexity. Two optimization techniques on graph compression and graph online search are also proposed, with the goal to further reduce index size and improve query accuracy. Our experimental results on large-scale social networks and road networks demonstrate that the local landmark scheme reduces the shortest distance estimation error significantly when compared with global landmark embedding.