Scalable network distance browsing in spatial databases
Scalable network distance browsing in spatial databases
复制标题
DOI：
10.1145/1376616.1376623
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
H. Samet;Jagan Sankaranarayanan;H. Alborzi
中科院分区：
文献类型：
--
作者：
H. Samet;Jagan Sankaranarayanan;H. Alborzi
提出了一种利用网络距离以最佳优先方式寻找空间网络中k个最近邻的算法。该算法基于预先计算网络中所有可能顶点之间的最短路径，然后利用编码，该编码利用了从顶点u到所有剩余顶点的最短路径可以基于从u到它们的最短路径上的第一条边被分解为子集的事实。因此，在最坏的情况下，工作量取决于被检查的对象的数量和从q到它们的最短路径上的链接数量，而不是取决于网络中的顶点数量。通过利用它们的空间相干性来减少跟踪子集所需的存储量，所述空间相干性通过最短路径四叉树的帮助来捕获。特别地，在许多大型道路网络上的实验以及理论分析已经表明，存储已经从O（N3）减少到O（N1.5）（即，以等于平方根的数量级）。沿网络沿着的最短路径的预先计算实质上将沿网络计算最短路径沿着的过程与寻找邻居的过程相重叠，并且由此还将查询对象的域S和从中提取邻居的对象的域从空间网络的顶点的域V相重叠。这意味着只要空间网络不变，空间网络中最短路径的算法和底层表示就可以用于不同的对象集。
An algorithm is presented for finding the k nearest neighbors in a spatial network in a best-first manner using network distance. The algorithm is based on precomputing the shortest paths between all possible vertices in the network and then making use of an encoding that takes advantage of the fact that the shortest paths from vertex u to all of the remaining vertices can be decomposed into subsets based on the first edges on the shortest paths to them from u. Thus, in the worst case, the amount of work depends on the number of objects that are examined and the number of links on the shortest paths to them from q, rather than depending on the number of vertices in the network. The amount of storage required to keep track of the subsets is reduced by taking advantage of their spatial coherence which is captured by the aid of a shortest path quadtree. In particular, experiments on a number of large road networks as well as a theoretical analysis have shown that the storage has been reduced from O(N3) to O(N1.5) (i.e., by an order of magnitude equal to the square root). The precomputation of the shortest paths along the network essentially decouples the process of computing shortest paths along the network from that of finding the neighbors, and thereby also decouples the domain S of the query objects and that of the objects from which the neighbors are drawn from the domain V of the vertices of the spatial network. This means that as long as the spatial network is unchanged, the algorithm and underlying representation of the shortest paths in the spatial network can be used with different sets of objects.