A Continuous k-Nearest Neighbor Query Method for Moving Data in Obstructed Spaces
For the nearest neighbor query problem of continuous moving objects in spatio-temporal databases, the COpKNN (continuous obstructed possible k-nearest neighbor) query is proposed: in a two-dimensional space, given a moving query point q, a set of moving query object sets P and a set of polygonal obs...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Harbin University of Science and Technology Publications
2018-06-01
|
| Series: | Journal of Harbin University of Science and Technology |
| Subjects: | |
| Online Access: | https://hlgxb.hrbust.edu.cn/#/digest?ArticleID=1530 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849228541499015168 |
|---|---|
| author | WAN Jing TANG Bei-bei HE Yun-bin Li Song |
| author_facet | WAN Jing TANG Bei-bei HE Yun-bin Li Song |
| author_sort | WAN Jing |
| collection | DOAJ |
| description | For the nearest neighbor query problem of continuous moving objects in spatio-temporal databases, the COpKNN (continuous obstructed possible k-nearest neighbor) query is proposed: in a two-dimensional space, given a moving query point q, a set of moving query object sets P and a set of polygonal obstacle sets O, based on the concept of obstacle distance, all possible k nearest neighbor sets of q are queried. Due to the uncertainty of the moving objects themselves and the existence of obstacles in real life, the existing query methods are no longer applicable to COpKNN queries. The COpKNN query includes three sub-processes: based on the concepts of visibility graph, R-tree and heap sort, a method for calculating the obstacle distance between two points (greater than or equal to the Euclidean distance) is given; based on the R-tree query method, all possible k nearest neighbor result sets of q within the user-given time period (preliminary results, also called candidate sets) are found; the k nearest neighbor result set is pruned by using Mindist(E,q) and the candidate set update algorithm UpdataC(pn) to obtain a more accurate k nearest neighbor result set. The experimental data set and obstacle set both use real data sets. Theoretical research and experimental results show that this method has good efficiency. |
| format | Article |
| id | doaj-art-ce82ecce7e3b4591ae08a0067cd64e84 |
| institution | Kabale University |
| issn | 1007-2683 |
| language | zho |
| publishDate | 2018-06-01 |
| publisher | Harbin University of Science and Technology Publications |
| record_format | Article |
| series | Journal of Harbin University of Science and Technology |
| spelling | doaj-art-ce82ecce7e3b4591ae08a0067cd64e842025-08-23T01:17:55ZzhoHarbin University of Science and Technology PublicationsJournal of Harbin University of Science and Technology1007-26832018-06-012303445010.15938/j.jhust.2018.03.008A Continuous k-Nearest Neighbor Query Method for Moving Data in Obstructed SpacesWAN Jing0TANG Bei-bei1HE Yun-bin2Li Song3School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,ChinaSchool of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,ChinaSchool of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,ChinaSchool of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,ChinaFor the nearest neighbor query problem of continuous moving objects in spatio-temporal databases, the COpKNN (continuous obstructed possible k-nearest neighbor) query is proposed: in a two-dimensional space, given a moving query point q, a set of moving query object sets P and a set of polygonal obstacle sets O, based on the concept of obstacle distance, all possible k nearest neighbor sets of q are queried. Due to the uncertainty of the moving objects themselves and the existence of obstacles in real life, the existing query methods are no longer applicable to COpKNN queries. The COpKNN query includes three sub-processes: based on the concepts of visibility graph, R-tree and heap sort, a method for calculating the obstacle distance between two points (greater than or equal to the Euclidean distance) is given; based on the R-tree query method, all possible k nearest neighbor result sets of q within the user-given time period (preliminary results, also called candidate sets) are found; the k nearest neighbor result set is pruned by using Mindist(E,q) and the candidate set update algorithm UpdataC(pn) to obtain a more accurate k nearest neighbor result set. The experimental data set and obstacle set both use real data sets. Theoretical research and experimental results show that this method has good efficiency.https://hlgxb.hrbust.edu.cn/#/digest?ArticleID=1530r-treeknearest neighbor queryuncertaintyvisibilityobstructed distance |
| spellingShingle | WAN Jing TANG Bei-bei HE Yun-bin Li Song A Continuous k-Nearest Neighbor Query Method for Moving Data in Obstructed Spaces Journal of Harbin University of Science and Technology r-tree knearest neighbor query uncertainty visibility obstructed distance |
| title | A Continuous k-Nearest Neighbor Query Method for Moving Data in Obstructed Spaces |
| title_full | A Continuous k-Nearest Neighbor Query Method for Moving Data in Obstructed Spaces |
| title_fullStr | A Continuous k-Nearest Neighbor Query Method for Moving Data in Obstructed Spaces |
| title_full_unstemmed | A Continuous k-Nearest Neighbor Query Method for Moving Data in Obstructed Spaces |
| title_short | A Continuous k-Nearest Neighbor Query Method for Moving Data in Obstructed Spaces |
| title_sort | continuous k nearest neighbor query method for moving data in obstructed spaces |
| topic | r-tree knearest neighbor query uncertainty visibility obstructed distance |
| url | https://hlgxb.hrbust.edu.cn/#/digest?ArticleID=1530 |
| work_keys_str_mv | AT wanjing acontinuousknearestneighborquerymethodformovingdatainobstructedspaces AT tangbeibei acontinuousknearestneighborquerymethodformovingdatainobstructedspaces AT heyunbin acontinuousknearestneighborquerymethodformovingdatainobstructedspaces AT lisong acontinuousknearestneighborquerymethodformovingdatainobstructedspaces AT wanjing continuousknearestneighborquerymethodformovingdatainobstructedspaces AT tangbeibei continuousknearestneighborquerymethodformovingdatainobstructedspaces AT heyunbin continuousknearestneighborquerymethodformovingdatainobstructedspaces AT lisong continuousknearestneighborquerymethodformovingdatainobstructedspaces |