This paper introduces a new proximity graph, called the @math -Semi-Yao graph ( @math -SYG), on a set @math of points in @math , which is a supergraph of the @math -nearest neighbor graph ( @math -NNG) of @math . We provide a kinetic data structure (KDS) to maintain the @math -SYG on moving points, where the trajectory of each point is a polynomial function whose degree is bounded by some constant. Our technique gives the first KDS for the theta graph ( , @math -SYG) in @math . It generalizes and improves on previous work on maintaining the theta graph in @math . As an application, we use the kinetic @math -SYG to provide the first KDS for maintenance of all the @math -nearest neighbors in @math , for any @math . Previous works considered the @math case only. Our KDS for all the @math -nearest neighbors is deterministic. The best previous KDS for all the @math -nearest neighbors in @math is randomized. Our structure and analysis are simpler and improve on this work for the @math case. We also provide a KDS for all the @math -nearest neighbors, which in fact gives better performance than previous KDS's for maintenance of all the exact @math -nearest neighbors. As another application, we present the first KDS for answering reverse @math -nearest neighbor queries on moving points in @math , for any @math .
The reverse @math -nearest neighbor queries for a set of continuously moving objects has attracted the attention of the database community (see @cite_30 and references therein). To our knowledge there is no previous solution to the kinetic problem in the literature.
@cite_30
2142410337
In this paper, we study the problem of continuous monitoring of reverse k nearest neighbors queries in Euclidean space as well as in spatial networks. Existing techniques are sensitive toward objects and queries movement. For example, the results of a query are to be recomputed whenever the query changes its location. We present a framework for continuous reverse k nearest neighbor (RkNN) queries by assigning each object and query with a safe region such that the expensive recomputation is not required as long as the query and objects remain in their respective safe regions. This significantly improves the computation cost. As a byproduct, our framework also reduces the communication cost in client---server architectures because an object does not report its location to the server unless it leaves its safe region or the server sends a location update request. We also conduct a rigid cost analysis for our Euclidean space RkNN algorithm. We show that our techniques can also be applied to answer bichromatic RkNN queries in Euclidean space as well as in spatial networks. Furthermore, we show that our techniques can be extended for the spatial networks that are represented by directed graphs. The extensive experiments demonstrate that our techniques outperform the existing techniques by an order of magnitude in terms of computation cost and communication cost.