ISBN:  Unavailable

Category: Unavailable

Page count: 11

Abstract: "In this paper, we describe a new technique for solving a variety of query-retrieval problems in optimal time with optimal or near-optimal space. In particular, we use the technique to construct algorithms and data structures for circular range searching, half-space range searching, and computing k-nearest neighbors in a variety of metrics. For each problem and each query, the response to the query is provided in O(k) or O(k + log n) time where k is the size of the response and n is the size of the problem. (E.g., for the n-point k-nearest neighbors problem, the k-nearest neighbors of any query point are provided in O(K + log n) steps.).