G-Tree: An Efficient and Scalable Index for Spatial Search on Road Networks
G-Tree: An Efficient and Scalable Index for Spatial Search on Road Networks
复制标题
G-Tree：用于道路网络空间搜索的高效且可扩展的索引
DOI：
10.1109/tkde.2015.2399306
复制
发表时间：
2015-08
期刊：
影响因子：
--
通讯作者：
Kian-lee Tan
中科院分区：
文献类型：
--
作者：
Ruicheng Hong;Guoliang Li;Lizhu Zhou;Kian-lee Tan
近几十年来，我们见证了基于位置的系统的迅速普及。基于位置的道路网络查询主要有三种类型：单对最短路径查询、k近邻查询和基于关键字的k近邻查询。受R-tree的启发，我们提出了一种高度平衡且可扩展的索引，即G-tree，以有效地支持这些查询。G-tree的空间复杂度为O（|V|日志|V|），其中|V|是道路网络中的顶点数。与以前的作品，分别支持这些查询，G树支持所有这些查询在一个框架。这个框架的基础是一个基于装配的方法来计算两个顶点之间的最短路径距离。基于组装的方法，高效的搜索算法来回答kNN查询和基于关键字的kNN查询。实验结果表明，G树在理论和实践上都优于现有的方法。
In the recent decades, we have witnessed the rapidly growing popularity of location-based systems. Three types of location-based queries on road networks, single-pair shortest path query, k nearest neighbor (kNN) query, and keyword-based kNN query, are widely used in location-based systems. Inspired by R-tree, we propose a height-balanced and scalable index, namely G-tree, to efficiently support these queries. The space complexity of G-tree is O(|V|log|V|) where |V| is the number of vertices in the road network. Unlike previous works that support these queries separately, G-tree supports all these queries within one framework. The basis for this framework is an assembly-based method to calculate the shortest-path distances between two vertices. Based on the assembly-based method, efficient search algorithms to answer kNN queries and keyword-based kNN queries are developed. Experiment results show G-tree's theoretical and practical superiority over existing methods.
登录
查看更多内容
DOI：
10.1109/69.687976
发表时间：
1998-05
期刊：
IEEE Trans. Knowl. Data Eng.
影响因子：
--
作者：
N. Jing;Yun-Wu Huang;Elke A. Rundensteiner
通讯作者：
N. Jing;Yun-Wu Huang;Elke A. Rundensteiner
DOI：
10.1145/956676.956677
发表时间：
2003-11
期刊：
--
影响因子：
--
作者：
Christian S. Jensen;Jan Kolárvr;T. Pedersen;Igor Timko
通讯作者：
Christian S. Jensen;Jan Kolárvr;T. Pedersen;Igor Timko
影响因子：
4
作者：
Jagan Sankaranarayanan;H. Alborzi;H. Samet
通讯作者：
Jagan Sankaranarayanan;H. Alborzi;H. Samet
DOI：
--
发表时间：
2006-09
期刊：
--
影响因子：
--
作者：
Haibo Hu;Lee;V. Lee
通讯作者：
Haibo Hu;Lee;V. Lee
DOI：
10.1145/1376616.1376623
发表时间：
2008-06
期刊：
--
影响因子：
--
作者：
H. Samet;Jagan Sankaranarayanan;H. Alborzi
通讯作者：
H. Samet;Jagan Sankaranarayanan;H. Alborzi