Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road Networks
A reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k closest points. In recent years, considerable research has been conducted into monitoring reverse k nearest neighbor queries. In this paper, we study the problem of continuous reverse nearest neighb...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2016-12-01
|
| Series: | ISPRS International Journal of Geo-Information |
| Subjects: | |
| Online Access: | http://www.mdpi.com/2220-9964/5/12/247 |
| _version_ | 1828541559186915328 |
|---|---|
| author | Muhammad Attique Hyung-Ju Cho Rize Jin Tae-Sun Chung |
| author_facet | Muhammad Attique Hyung-Ju Cho Rize Jin Tae-Sun Chung |
| author_sort | Muhammad Attique |
| collection | DOAJ |
| description | A reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k closest points. In recent years, considerable research has been conducted into monitoring reverse k nearest neighbor queries. In this paper, we study the problem of continuous reverse nearest neighbor queries where both the query object q and data objects are moving. Existing state-of-the-art techniques are sensitive towards the movement of data objects, e.g., a candidate object must be verified whenever it changes its location. Further, insufficient attention has been given to the monitoring of RNN queries in dynamic road networks where the network weight changes depending on the traffic conditions. In this paper, we address these problems by proposing a new safe exit-based algorithm called CORE-X for efficiently computing the safe exit points of both query and data objects. The safe exit point of an object indicates the point at which its safe region and non-safe region meet, thus a set of safe exit points represents the border of the safe region. Within the safe region, the query result remains unchanged provided the query and data objects remain inside their respective safe regions. The results of extensive experiments conducted using real road maps indicate that the proposed algorithm significantly reduces communication and computation costs compared to the state-of-the-art algorithm. |
| first_indexed | 2024-12-12T01:41:34Z |
| format | Article |
| id | doaj.art-e534cdb7e82644fbb82c78b3a79a4cd5 |
| institution | Directory Open Access Journal |
| issn | 2220-9964 |
| language | English |
| last_indexed | 2024-12-12T01:41:34Z |
| publishDate | 2016-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | ISPRS International Journal of Geo-Information |
| spelling | doaj.art-e534cdb7e82644fbb82c78b3a79a4cd52022-12-22T00:42:42ZengMDPI AGISPRS International Journal of Geo-Information2220-99642016-12-0151224710.3390/ijgi5120247ijgi5120247Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road NetworksMuhammad Attique0Hyung-Ju Cho1Rize Jin2Tae-Sun Chung3Department of Computer Engineering, Ajou University, Suwon 16499, KoreaDepartment of Software, Kyungpook National University, Sangju-si 37224, KoreaDepartment of Computer Engineering, Ajou University, Suwon 16499, KoreaDepartment of Computer Engineering, Ajou University, Suwon 16499, KoreaA reverse k nearest neighbor (RkNN) query retrieves all the data points that have q as one of their k closest points. In recent years, considerable research has been conducted into monitoring reverse k nearest neighbor queries. In this paper, we study the problem of continuous reverse nearest neighbor queries where both the query object q and data objects are moving. Existing state-of-the-art techniques are sensitive towards the movement of data objects, e.g., a candidate object must be verified whenever it changes its location. Further, insufficient attention has been given to the monitoring of RNN queries in dynamic road networks where the network weight changes depending on the traffic conditions. In this paper, we address these problems by proposing a new safe exit-based algorithm called CORE-X for efficiently computing the safe exit points of both query and data objects. The safe exit point of an object indicates the point at which its safe region and non-safe region meet, thus a set of safe exit points represents the border of the safe region. Within the safe region, the query result remains unchanged provided the query and data objects remain inside their respective safe regions. The results of extensive experiments conducted using real road maps indicate that the proposed algorithm significantly reduces communication and computation costs compared to the state-of-the-art algorithm.http://www.mdpi.com/2220-9964/5/12/247continuous monitoringlocation-based applicationsreverse nearest neighbor querysafe exit algorithmmobile computingroad network |
| spellingShingle | Muhammad Attique Hyung-Ju Cho Rize Jin Tae-Sun Chung Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road Networks ISPRS International Journal of Geo-Information continuous monitoring location-based applications reverse nearest neighbor query safe exit algorithm mobile computing road network |
| title | Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road Networks |
| title_full | Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road Networks |
| title_fullStr | Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road Networks |
| title_full_unstemmed | Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road Networks |
| title_short | Efficient Processing of Continuous Reverse k Nearest Neighbor on Moving Objects in Road Networks |
| title_sort | efficient processing of continuous reverse k nearest neighbor on moving objects in road networks |
| topic | continuous monitoring location-based applications reverse nearest neighbor query safe exit algorithm mobile computing road network |
| url | http://www.mdpi.com/2220-9964/5/12/247 |
| work_keys_str_mv | AT muhammadattique efficientprocessingofcontinuousreverseknearestneighboronmovingobjectsinroadnetworks AT hyungjucho efficientprocessingofcontinuousreverseknearestneighboronmovingobjectsinroadnetworks AT rizejin efficientprocessingofcontinuousreverseknearestneighboronmovingobjectsinroadnetworks AT taesunchung efficientprocessingofcontinuousreverseknearestneighboronmovingobjectsinroadnetworks |