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.展开更多
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.
基金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)算法.通过真实数据进行实验,验证算法的可行性.
