Distance indexing on road networks
Distance indexing on road networks
复制标题
DOI：
--
复制
发表时间：
2006-09
期刊：
影响因子：
--
通讯作者：
Haibo Hu;Lee;V. Lee
中科院分区：
文献类型：
--
作者：
Haibo Hu;Lee;V. Lee
空间网络数据库(SNDB)上的KNN和连续KNN查询的处理是近年来研究的热点。然而，对于公路网与欧氏空间最根本的区别--网络距离的计算缺乏系统的研究。由于在线Dijkstra算法被证明只在短距离下是有效的，我们提出了一个高效的索引，称为距离签名，用于长距离的距离计算和查询处理。距离签名将对象和网络节点之间的距离离散化成类别，然后对这些类别进行编码。为了最大限度地减少存储和搜索开销，基于简化的网络拓扑结构，我们提出了最优类别划分以及签名的编码和压缩算法。通过数学分析和实验研究表明，该签名索引对于各种数据分布、查询工作量、参数设置和网络更新都是有效和健壮的。
The processing of kNN and continuous kNN queries on spatial network databases (SNDB) has been intensively studied recently. However, there is a lack of systematic study on the computation of network distances, which is the most fundamental difference between a road network and a Euclidean space. Since the online Dijkstra's algorithm has been shown to be efficient only for short distances, we propose an efficient index, called distance signature, for distance computation and query processing over long distances. Distance signature discretizes the distances between objects and network nodes into categories and then encodes these categories. To minimize the storage and search costs, we present the optimal category partition, and the encoding and compression algorithms for the signatures, based on a simplified network topology. By mathematical analysis and experimental study, we showed that the signature index is efficient and robust for various data distributions, query workloads, parameter settings and network updates.