Journal of Northeastern University Natural Science ›› 2020, Vol. 41 ›› Issue (7): 913-919.DOI: 10.12068/j.issn.1005-3026.2020.07.001

• Information & Control •     Next Articles

Moving k Nearest Neighbor Query with Spatial Diversity Constraints

XU Hong-fei, GU Yu, YU Ge   

  1. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China.
  • Received:2019-06-01 Revised:2019-06-01 Online:2020-07-15 Published:2020-07-15
  • Contact: YU Ge
  • About author:-
  • Supported by:
    -

Abstract: A new type of queries, named moving k nearest neighbor query with spatial diversity constraints(SDC-MkNN), was proposed.When the query object is moving, this type of queries can continuously return the k nearest neighbors, and any two of the returned objects are satisfied with the spatial diversity constraints, which means the spatial distance between any two of the returned objects must be larger than the distance threshold.Based on the safe region technique, two algorithms were proposed to increase the query efficiency by reducing the frequency of the recomputation of query results.One is an exact algorithm(EA), which can continuously return exact query results, and the other is an approximate algorithm(ρAA), which can continuously return approximate query results with exact bounds.The proposed algorithms were verified by extensive experiments on a real dataset.The results confirm the superiority of the proposed algorithms over the baseline algorithm.

Key words: moving k nearest neighbor query, spatial diversity, safe region, location-based service, query processing algorithms

CLC Number: