A novel technique called the bitmap lattice index(BLI) is proposed, which combines the advantages of a wireless broadcasting environment with a road network. Existing road networks are based on the on-demand method: a...A novel technique called the bitmap lattice index(BLI) is proposed, which combines the advantages of a wireless broadcasting environment with a road network. Existing road networks are based on the on-demand method: a server's workload increases as the query request increases when a server sends a client information. To solve this problem, we propose the BLI. The BLI denotes an object and a node as 0 and 1 in the Hilbert curve(HC) map. The BLI can identify the position of a node and an object through bit information; it can also reduce the broadcasting frequency of a server by reducing the size of the index, thereby decreasing the access latency and query processing times. Moreover, the BLI is highly effective for data filtering, as it can identify the positions of both an object and a node. In a road network, if filtering is done via the Euclidean distance, it may result in an error. To prevent this, we add another validation procedure. The experiment is conducted by applying the BLI to kNN query, and the technique is assessed by a performance evaluation experiment.展开更多
Nowadays,location-based services are widely used,requiring instant responses to a large volume of multiple spatial queries over massive road networks,i.e.,single-pair shortest path(SPSP)query,k-nearest neighbor(kNN)qu...Nowadays,location-based services are widely used,requiring instant responses to a large volume of multiple spatial queries over massive road networks,i.e.,single-pair shortest path(SPSP)query,k-nearest neighbor(kNN)query,and range query.Creating index-based structure for each kind of query is costly,hence it is important to handle multiple spatial queries within one efficient structure.Partition-based hierarchical approaches show promising potential to meet the requirement.However,existing approaches require large search space on massive road networks especially for long-distance queries,which is inefficient and hard to scale.To overcome the drawbacks,we propose the shortcut-enhanced graph hierarchy tree(SCG-tree),which leverages shortcuts to effectively prune the search space over a hierarchical structure.With the SCG-tree,a pruned shortcut-based method is designed to answer SPSP query,and a two-phase expansion strategy is proposed to leverage shortcuts for kNN and range queries.Theoretical analyses show the superiority of proposed shortcut-based query algorithms.Extensive experiments demonstrate that our approach can achieve three times speedup for kNN query and an order of magnitude speedup for SPSP and range queries over existing methods on real road networks that scale up to 24 million nodes and 58 million edges.展开更多
An aggregate nearest neighbor （ANN） query returns a point of interest （POI） that minimizes an aggregate function for multiple query points. In this paper, we propose an e？cient approach to tackle ANN queries in r...An aggregate nearest neighbor （ANN） query returns a point of interest （POI） that minimizes an aggregate function for multiple query points. In this paper, we propose an e？cient approach to tackle ANN queries in road networks. Our approach consists of two phases： searching phase and pruning phase. In particular, we first continuously compute the nearest neighbors （NNs） for each query point in some specific order to obtain the candidate POIs until all query points find a common POI. Second, we filter out the unqualified POIs based on the pruning strategy for a given aggregate function. The two-phase process is repeated until there remains only one candidate POI, and the remained one is returned as the final result. In addition, we discuss the partition strategies for query points and the approximate ANN query for the case where the number of query points is huge. Extensive experiments using real datasets demonstrate that our proposed approach outperforms its competitors significantly in most cases.展开更多
空间资源的索引查询广泛应用在多个位置服务平台上(Google地图、百度地图等),基于欧氏空间或者普通网络图的资源查询算法对于实际道路情况考虑不完全,影响实际应用效果.在已有工作基础上,提出改进的实际道路网络模型,并设计以边为引导...空间资源的索引查询广泛应用在多个位置服务平台上(Google地图、百度地图等),基于欧氏空间或者普通网络图的资源查询算法对于实际道路情况考虑不完全,影响实际应用效果.在已有工作基础上,提出改进的实际道路网络模型,并设计以边为引导的查询(directed from edge,DFE)算法、以点为引导的查询(directed from point,DFP)算法和结合IR-tree的改进查询(IR-tree query,IR-TQ)算法.通过真实数据进行实验,验证算法的可行性.展开更多
基金supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (NRF2013R1A1A1004593, 2013R1A1A1A05012348)
文摘A novel technique called the bitmap lattice index(BLI) is proposed, which combines the advantages of a wireless broadcasting environment with a road network. Existing road networks are based on the on-demand method: a server's workload increases as the query request increases when a server sends a client information. To solve this problem, we propose the BLI. The BLI denotes an object and a node as 0 and 1 in the Hilbert curve(HC) map. The BLI can identify the position of a node and an object through bit information; it can also reduce the broadcasting frequency of a server by reducing the size of the index, thereby decreasing the access latency and query processing times. Moreover, the BLI is highly effective for data filtering, as it can identify the positions of both an object and a node. In a road network, if filtering is done via the Euclidean distance, it may result in an error. To prevent this, we add another validation procedure. The experiment is conducted by applying the BLI to kNN query, and the technique is assessed by a performance evaluation experiment.
基金supported by the Frontier Technology R&D Project of Jiangsu(BF2024059)the National Natural Science Foundation of China(Grant No.6240071854)+1 种基金the Natural Science Foundation of Jiangsu Province(BK20241381)the Jiangsu Association for Science and Technology Youth Science and Technology Talent Support Project(JSTJ-2023-XH055).
文摘Nowadays,location-based services are widely used,requiring instant responses to a large volume of multiple spatial queries over massive road networks,i.e.,single-pair shortest path(SPSP)query,k-nearest neighbor(kNN)query,and range query.Creating index-based structure for each kind of query is costly,hence it is important to handle multiple spatial queries within one efficient structure.Partition-based hierarchical approaches show promising potential to meet the requirement.However,existing approaches require large search space on massive road networks especially for long-distance queries,which is inefficient and hard to scale.To overcome the drawbacks,we propose the shortcut-enhanced graph hierarchy tree(SCG-tree),which leverages shortcuts to effectively prune the search space over a hierarchical structure.With the SCG-tree,a pruned shortcut-based method is designed to answer SPSP query,and a two-phase expansion strategy is proposed to leverage shortcuts for kNN and range queries.Theoretical analyses show the superiority of proposed shortcut-based query algorithms.Extensive experiments demonstrate that our approach can achieve three times speedup for kNN query and an order of magnitude speedup for SPSP and range queries over existing methods on real road networks that scale up to 24 million nodes and 58 million edges.
基金This research is supported in part by the Shanghai Natural Science Foundation of China under Grant No. 14ZR1403100, the Shanghai Science and Technology Development Funds of China under Grant Nos. 13dz2260200 and 13511504300, and the National Natural Science Foundation of China under Grant No. 61073001.
文摘An aggregate nearest neighbor （ANN） query returns a point of interest （POI） that minimizes an aggregate function for multiple query points. In this paper, we propose an e？cient approach to tackle ANN queries in road networks. Our approach consists of two phases： searching phase and pruning phase. In particular, we first continuously compute the nearest neighbors （NNs） for each query point in some specific order to obtain the candidate POIs until all query points find a common POI. Second, we filter out the unqualified POIs based on the pruning strategy for a given aggregate function. The two-phase process is repeated until there remains only one candidate POI, and the remained one is returned as the final result. In addition, we discuss the partition strategies for query points and the approximate ANN query for the case where the number of query points is huge. Extensive experiments using real datasets demonstrate that our proposed approach outperforms its competitors significantly in most cases.
文摘空间资源的索引查询广泛应用在多个位置服务平台上(Google地图、百度地图等),基于欧氏空间或者普通网络图的资源查询算法对于实际道路情况考虑不完全,影响实际应用效果.在已有工作基础上,提出改进的实际道路网络模型,并设计以边为引导的查询(directed from edge,DFE)算法、以点为引导的查询(directed from point,DFP)算法和结合IR-tree的改进查询(IR-tree query,IR-TQ)算法.通过真实数据进行实验,验证算法的可行性.
