Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates

摘要

In recent years there has been an increasing interest in databases of moving objects where the motion and extent of objects are represented as a function of time. The focus of this paper is on the maintenance of continuous κ-nearest neighbor (κ-NN) queries on moving points when updates are allowed. Updates change the functions describing the motion of the points, causing pending events to change. Events are processed to keep the query result consistent as points move. It is shown that the cost of maintaining a continuous κ-NN query result for moving points represented in this way can be significantly reduced with a modest increase in the number of events processed in the presence of updates. This is achieved by introducing a continuous within query to filter the number of objects that must be taken into account when maintaining a Continuous κ-NN query. This new approach is presented and compared with other recent work. Experimental results are presented showing the utility of this approach.