Finding RkNN by Compressed Straightforward Index
Reverse Nearest Neighbor(RNN) query now is oneof the important queries in spatial database and datamining. Reverse k Nearest Neighbor(RkNN) is theextendibility of RNN. Given a set V of objects and aquery object q, an RkNN query returns a subset of Vsuch that each element of the subset has q as its kNNmember according to a certain similarity metric. Earlymethods pre-compute NN of each data objects and findRNN. Recent methods introduce index based on themutual distance between two objects. Chen broughtforward a methodI which can find RkNN for any kstraightforwardly with constant running cost. Themethod builds an index block for each object pi of Vwhich stores the pre-computed distances from pi toeach other object of V in ascending order. It can beapplied to any RkNN searches whenever the mutualdistance between objects can be figured out, and doesnot require the triangle inequality. But the distancevalues in index block is storage-consuming andredundancy. In this paper, we propose an efficientmethod to compress the index block. Our method usesjust the necessary bits to store the mutual distancebetween objects hence reduces the redundancy to thelowermost level. We evaluate the efficiency andeffectiveness of the proposed method.
Yanmin Luo Canhong Lian Jianquan Liu Hanxiong Chen
Dept.Computer Science HuaQiao University,Fujian,China Dept.Computer Science University of Tsukuba,Japan
国际会议
厦门
英文
279-284
2008-11-17（万方平台首次上网日期，不代表论文的发表时间）