A Dynamic Grid Index for C<i>k</i>NN Queries on Large-Scale Road Networks with Moving Objects
As the Internet of Things devices are deployed on a large scale, location-based services are being increasingly utilized. Among these services, <i>k</i>NN (<i>k</i>-nearest neighbor) queries based on road network constraints have gained importance. This study focuses on the C...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-04-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/13/8/4946 |
| _version_ | 1827746015917113344 |
|---|---|
| author | Kailei Tang Zhiyan Dong Wenxiang Shi Zhongxue Gan |
| author_facet | Kailei Tang Zhiyan Dong Wenxiang Shi Zhongxue Gan |
| author_sort | Kailei Tang |
| collection | DOAJ |
| description | As the Internet of Things devices are deployed on a large scale, location-based services are being increasingly utilized. Among these services, <i>k</i>NN (<i>k</i>-nearest neighbor) queries based on road network constraints have gained importance. This study focuses on the C<i>k</i>NN (continuous <i>k</i>-nearest neighbor) queries for non-uniformly distributed moving objects with large-scale dynamic road network constraints, where C<i>k</i>NN objects are continuously and periodically queried based on their motion evolution. The present C<i>k</i>NN high-concurrency query under the constraints of a super-large road network faces problems, such as high computational cost and low query efficiency. The aim of this study is to ensure high concurrency nearest neighbor query requests while shortening the query response time and reducing global computation costs. To address this issue, we propose the DVTG-Index (Dynamic V-Tree Double-Layer Grid Index), which intelligently adjusts the index granularity by continuously merging and splitting subgraphs as the objects move, thereby filtering unnecessary vertices. Based on DVTG-Index, we further propose the DVTG-C<i>k</i>NN algorithm to calculate the initial <i>k</i>NN query and utilize the existing results to speed up the C<i>k</i>NN query. Finally, extensive experiments on real road networks confirm the superior performance of our proposed method, which has significant practical applications in large-scale dynamic road network constraints with non-uniformly distributed moving objects. |
| first_indexed | 2024-03-11T05:16:35Z |
| format | Article |
| id | doaj.art-0a731f422a0041f29a0256281a8e2b9d |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-11T05:16:35Z |
| publishDate | 2023-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-0a731f422a0041f29a0256281a8e2b9d2023-11-17T18:11:30ZengMDPI AGApplied Sciences2076-34172023-04-01138494610.3390/app13084946A Dynamic Grid Index for C<i>k</i>NN Queries on Large-Scale Road Networks with Moving ObjectsKailei Tang0Zhiyan Dong1Wenxiang Shi2Zhongxue Gan3The Academy for Engineering and Technology, Fudan University, Shanghai 200433, ChinaThe Academy for Engineering and Technology, Fudan University, Shanghai 200433, ChinaThe Academy for Engineering and Technology, Fudan University, Shanghai 200433, ChinaThe Academy for Engineering and Technology, Fudan University, Shanghai 200433, ChinaAs the Internet of Things devices are deployed on a large scale, location-based services are being increasingly utilized. Among these services, <i>k</i>NN (<i>k</i>-nearest neighbor) queries based on road network constraints have gained importance. This study focuses on the C<i>k</i>NN (continuous <i>k</i>-nearest neighbor) queries for non-uniformly distributed moving objects with large-scale dynamic road network constraints, where C<i>k</i>NN objects are continuously and periodically queried based on their motion evolution. The present C<i>k</i>NN high-concurrency query under the constraints of a super-large road network faces problems, such as high computational cost and low query efficiency. The aim of this study is to ensure high concurrency nearest neighbor query requests while shortening the query response time and reducing global computation costs. To address this issue, we propose the DVTG-Index (Dynamic V-Tree Double-Layer Grid Index), which intelligently adjusts the index granularity by continuously merging and splitting subgraphs as the objects move, thereby filtering unnecessary vertices. Based on DVTG-Index, we further propose the DVTG-C<i>k</i>NN algorithm to calculate the initial <i>k</i>NN query and utilize the existing results to speed up the C<i>k</i>NN query. Finally, extensive experiments on real road networks confirm the superior performance of our proposed method, which has significant practical applications in large-scale dynamic road network constraints with non-uniformly distributed moving objects.https://www.mdpi.com/2076-3417/13/8/4946<i>k</i>-nearest neighbor querymoving objectroad network |
| spellingShingle | Kailei Tang Zhiyan Dong Wenxiang Shi Zhongxue Gan A Dynamic Grid Index for C<i>k</i>NN Queries on Large-Scale Road Networks with Moving Objects Applied Sciences <i>k</i>-nearest neighbor query moving object road network |
| title | A Dynamic Grid Index for C<i>k</i>NN Queries on Large-Scale Road Networks with Moving Objects |
| title_full | A Dynamic Grid Index for C<i>k</i>NN Queries on Large-Scale Road Networks with Moving Objects |
| title_fullStr | A Dynamic Grid Index for C<i>k</i>NN Queries on Large-Scale Road Networks with Moving Objects |
| title_full_unstemmed | A Dynamic Grid Index for C<i>k</i>NN Queries on Large-Scale Road Networks with Moving Objects |
| title_short | A Dynamic Grid Index for C<i>k</i>NN Queries on Large-Scale Road Networks with Moving Objects |
| title_sort | dynamic grid index for c i k i nn queries on large scale road networks with moving objects |
| topic | <i>k</i>-nearest neighbor query moving object road network |
| url | https://www.mdpi.com/2076-3417/13/8/4946 |
| work_keys_str_mv | AT kaileitang adynamicgridindexforcikinnqueriesonlargescaleroadnetworkswithmovingobjects AT zhiyandong adynamicgridindexforcikinnqueriesonlargescaleroadnetworkswithmovingobjects AT wenxiangshi adynamicgridindexforcikinnqueriesonlargescaleroadnetworkswithmovingobjects AT zhongxuegan adynamicgridindexforcikinnqueriesonlargescaleroadnetworkswithmovingobjects AT kaileitang dynamicgridindexforcikinnqueriesonlargescaleroadnetworkswithmovingobjects AT zhiyandong dynamicgridindexforcikinnqueriesonlargescaleroadnetworkswithmovingobjects AT wenxiangshi dynamicgridindexforcikinnqueriesonlargescaleroadnetworkswithmovingobjects AT zhongxuegan dynamicgridindexforcikinnqueriesonlargescaleroadnetworkswithmovingobjects |