Continuous nearestneighbor queries with location

Authors: A Prasad Sistla Ouri Wolfson Bo Xu

Publish Date: 2014/06/10

Volume: 24, Issue: 1, Pages: 25-50

PDF Link

Abstract

In this paper we consider the problem of evaluating the continuous query of finding the k nearest objects with respect to a given point object O q among a set of n moving pointobjects The query returns a sequence of answerpairs namely pairs of the form I S such that I is a time interval and S is the set of objects that are closest to O q during I When there is uncertainty associated with the locations of the moving objects S is the set of all the objects that are possibly the K Nearest Neighbors We analyze the lower bound and the upper bound on the maximum number of answerpairs for the certain case and the uncertain case respectively Then we consider two different types of algorithms The first is offline algorithms that compute a priori all the answerpairs The second type is online algorithms that at any time return the current answerpair We present algorithms for the certain case and the uncertain case respectively and analyze their complexity We experimentally compare different algorithms using a database of 1 million objects derived from realworld GPS tracesThis research was supported in part by the US Department of Transportation National University Rail Center NURAIL Illinois Department of Transportation METSI and National Science Foundation grants IIS1213013 CCF1216096 DGE0549489 IIP1315169 CCF0916438 CNS1035914 CCF1319754 CNS1314485

Keywords: