A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks
K nearest neighbor (kNN) search is an important problem in location-based services (LBS) and has been well studied on static road networks. However, in real world, road networks are often time-dependent; i.e., the time for traveling through a road always changes over time. Most existing methods for...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2019/4829164 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849308398279983104 |
|---|---|
| author | Yajun Yang Hanxiao Li Junhu Wang Qinghua Hu Xin Wang Muxi Leng |
| author_facet | Yajun Yang Hanxiao Li Junhu Wang Qinghua Hu Xin Wang Muxi Leng |
| author_sort | Yajun Yang |
| collection | DOAJ |
| description | K nearest neighbor (kNN) search is an important problem in location-based services (LBS) and has been well studied on static road networks. However, in real world, road networks are often time-dependent; i.e., the time for traveling through a road always changes over time. Most existing methods for kNN query build various indexes maintaining the shortest distances for some pairs of vertices on static road networks. Unfortunately, these methods cannot be used for the time-dependent road networks because the shortest distances always change over time. To address the problem of kNN query on time-dependent road networks, we propose a novel voronoi-based index in this paper. Furthermore, we propose a novel balanced tree, named V-tree, which is a secondary level index on voronoi-based index to make our querying algorithm more efficient. Moreover, we propose an algorithm for preprocessing time-dependent road networks such that the waiting time is not necessary to be considered. We confirm the efficiency of our method through experiments on real-life datasets. |
| format | Article |
| id | doaj-art-05562db63fcf4027b9b05e747bb95bbc |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-05562db63fcf4027b9b05e747bb95bbc2025-08-20T03:54:28ZengWileyComplexity1076-27871099-05262019-01-01201910.1155/2019/48291644829164A Novel Index Method for K Nearest Object Query over Time-Dependent Road NetworksYajun Yang0Hanxiao Li1Junhu Wang2Qinghua Hu3Xin Wang4Muxi Leng5College of Intelligence and Computing, Tianjin University, ChinaCollege of Intelligence and Computing, Tianjin University, ChinaSchool of Information and Communication Technology, Griffith University, AustraliaCollege of Intelligence and Computing, Tianjin University, ChinaCollege of Intelligence and Computing, Tianjin University, ChinaCollege of Intelligence and Computing, Tianjin University, ChinaK nearest neighbor (kNN) search is an important problem in location-based services (LBS) and has been well studied on static road networks. However, in real world, road networks are often time-dependent; i.e., the time for traveling through a road always changes over time. Most existing methods for kNN query build various indexes maintaining the shortest distances for some pairs of vertices on static road networks. Unfortunately, these methods cannot be used for the time-dependent road networks because the shortest distances always change over time. To address the problem of kNN query on time-dependent road networks, we propose a novel voronoi-based index in this paper. Furthermore, we propose a novel balanced tree, named V-tree, which is a secondary level index on voronoi-based index to make our querying algorithm more efficient. Moreover, we propose an algorithm for preprocessing time-dependent road networks such that the waiting time is not necessary to be considered. We confirm the efficiency of our method through experiments on real-life datasets.http://dx.doi.org/10.1155/2019/4829164 |
| spellingShingle | Yajun Yang Hanxiao Li Junhu Wang Qinghua Hu Xin Wang Muxi Leng A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks Complexity |
| title | A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks |
| title_full | A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks |
| title_fullStr | A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks |
| title_full_unstemmed | A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks |
| title_short | A Novel Index Method for K Nearest Object Query over Time-Dependent Road Networks |
| title_sort | novel index method for k nearest object query over time dependent road networks |
| url | http://dx.doi.org/10.1155/2019/4829164 |
| work_keys_str_mv | AT yajunyang anovelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT hanxiaoli anovelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT junhuwang anovelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT qinghuahu anovelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT xinwang anovelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT muxileng anovelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT yajunyang novelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT hanxiaoli novelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT junhuwang novelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT qinghuahu novelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT xinwang novelindexmethodforknearestobjectqueryovertimedependentroadnetworks AT muxileng novelindexmethodforknearestobjectqueryovertimedependentroadnetworks |