期刊
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
卷 27, 期 8, 页码 2175-2189出版社
IEEE COMPUTER SOC
DOI: 10.1109/TKDE.2015.2399306
关键词
Single-pair shortest path; KNN search; keyword search; road network; index; spatial databases
类别
资金
- 973 Program of China [2015CB358700, 2011CB302206]
- NSFC [61272090, 61373024, 61422205]
- Tencent
- Huawei
- SAP
- NExT Research Center [WBS: R-252-300-001-490]
- [YETP0105]
- [FDCT/106/2012/A3]
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 vertical bar log vertical bar V vertical bar) where vertical bar V vertical bar 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据