Finding RkNN by compressed straightforward index
Yanmin Luo, Canhong Lian, Jianquan Liu, Hanxiong Chen · 2008
Reverse Nearest Neighbo ..(RNN) query now is one of the important queries in spatial database and data mining. Reverse k Nearest Neighbor(RkNN) is the extendibility of RNN. Given a set V of objects and a query object q, an RkNN query returns a subset of V such that each element of the subset has q as its kNN member according to a certain similarity metric. Early methods pre-compute NN of each data objects and find RNN. Recent methods introduce index based on the mutual distance between two objects. Chen brought forward a method[1] which can find RkNN for any k straightforwardly with constant running cost. The method builds an index block for each object pi of V which stores the pre-computed distances from pi to each other object of V in ascending order. It can be applied to any RkNN searches whenever the mutual distance between objects can be figured out, and does not require the triangle inequality. ..But the distance values in index block is storage-consuming and redundancy. In this paper, we propose an efficient method to compress the index block. Our method uses just the necessary bits to store the mutual distance between objects hence reduces the redundancy to the lowermost level. We evaluate the efficiency and effectiveness of the proposed method.