Date Added: Oct 2009
A RkNN query returns all objects whose nearest k neighbors contain the query object. In this paper, the authors consider RkNN query processing in the case where the distances between attribute values are not necessarily metric. Dissimilarities between objects could then be a monotonic aggregate of dissimilarities between their values, such aggregation functions being specified at query time. They outline real world cases that motivate RkNN processing in such scenarios. They consider the AL-Tree index and its applicability in RkNN query processing. They develop an approach that exploits the group level reasoning enabled by the AL-Tree in RkNN processing.