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!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1007-2683 |