Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures

Deepak Padmanabhan, Prasad Deshpande

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


A RkNN query returns all objects whose nearest k neighbors
contain the query object. In this paper, we 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. We outline real world cases
that motivate RkNN processing in such scenarios. We consider
the AL-Tree index and its applicability in RkNN query
processing. We develop an approach that exploits the group
level reasoning enabled by the AL-Tree in RkNN processing.
We evaluate our approach against a Naive approach
that performs sequential scans on contiguous data and an
improved block-based approach that we provide. We use
real-world datasets and synthetic data with varying characteristics
for our experiments. This extensive empirical
evaluation shows that our approach is better than existing
methods in terms of computational and disk access costs,
leading to significantly better response times.
Original languageEnglish
Pages (from-to)1243-1254
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number1
Publication statusPublished - 2010


Dive into the research topics of 'Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures'. Together they form a unique fingerprint.

Cite this