Answer-pairs and processing of continuous nearest-neighbor queries Conference

Sistla, AP, Wolfson, O, Xu, B et al. (2011). Answer-pairs and processing of continuous nearest-neighbor queries . 16-24. 10.1145/1998476.1998481

cited authors

  • Sistla, AP; Wolfson, O; Xu, B; Rishe, N

authors

abstract

  • We consider the problem of evaluating the continuous query of finding the k nearest objects with respect to a given moving point-object Oq among a set of n moving point-objects. The query returns a sequence of answer-pairs, 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 Oq during I. Existing work on this problem lacks complexity analysis due to limited understanding of the maximum number of answer-pairs. In this paper we analyze the lower bound and the upper bound on the maximum number of answer-pairs. Then we consider two different types of algorithms. The first is off-line algorithms that compute a priori all the answer-pairs. The second type is on-line algorithms that at any time return the current answer-pair. We present the algorithms and analyze their complexity using the maximum number of answer-pairs. © 2011 ACM.

publication date

  • July 28, 2011

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 13

start page

  • 16

end page

  • 24