Can I read Constrained Reverse Nearest Neighbor Search on Mobile Objects on EtoBox?

Constrained Reverse Nearest Neighbor Search on Mobile Objects by Tobias Emrich; Hans-Peter Kriegel; Peer Kröger; Matthias Renz; Andreas Züfle is a scholarly article available to read on EtoBox.

What is Constrained Reverse Nearest Neighbor Search on Mobile Objects about?

In this paper, we formalize the novel concept of Constrained Reverse k-Nearest Neighbor (CRkNN) search on mobile objects (clients) performed at a central server. The CRkNN query computes for a given query object q the set RkNN(q) of objects having q as one of their k-nearest neighbors, iff the result set exceeds a specific threshold m, i.e. CardRkN N q)) ≥ m. Otherwise, the query reports an empty result. In our setting, the positions of the query object and database objects are approximated by minimal bounding rectangles that depend on the last reported location of the object, as well as on the time that has been passed since the object reported its recent exact location. We propose an approach that minimizes the amount of communication between clients and central server by using the approximation of the positions to identify true hits and true drops. We present a multi-step filter/refinement framework that uses a novel refinement heuristic to minimize the number of objects that are required to provide their exact location. Our solution does not assume any preprocessing steps which makes it applicable for dynamic environments where updates of the database frequently occur. Experi

Author

Tobias Emrich; Hans-Peter Kriegel; Peer Kröger; Matthias Renz; Andreas Züfle

Publisher

ACM

Published

2009

Language

EN