Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures

A RkNN query returns all objects whose nearest k neighbors<br/>contain the query object. In this paper, we consider RkNN<br/>query processing in the case where the distances between<br/>attribute values are not necessarily metric. Dissimilarities<br/>between objects could then be a monotonic aggregate of dissimilarities<br/>between their values, such aggregation functions<br/>being specified at query time. We outline real world cases<br/>that motivate RkNN processing in such scenarios. We consider<br/>the AL-Tree index and its applicability in RkNN query<br/>processing. We develop an approach that exploits the group<br/>level reasoning enabled by the AL-Tree in RkNN processing.<br/>We evaluate our approach against a Naive approach<br/>that performs sequential scans on contiguous data and an<br/>improved block-based approach that we provide. We use<br/>real-world datasets and synthetic data with varying characteristics<br/>for our experiments. This extensive empirical<br/>evaluation shows that our approach is better than existing<br/>methods in terms of computational and disk access costs,<br/>leading to significantly better response times.