Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures

    Research output: Contribution to journalArticle


    View graph of relations

    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
    Number of pages12
    Pages (from-to)1243-1254
    JournalProceedings of the VLDB Endowment
    Journal publication date2010
    Issue number1
    Publication statusPublished - 2010

    ID: 17792610