Dimensional testing for reverse k-nearest neighbor search

Guillaume Casanova, Elias Englmeier, Michael E. Houle, Peer Kröger, Michael Nett, Erich Schubert, Arthur Zimek

    Publikation: Bidrag til tidsskriftKonferenceartikelForskningpeer review

    205 Downloads (Pure)

    Abstrakt

    Given a query object q, reverse k-nearest neighbor (RkNN) search aims to locate those objects of the database that have q among their k-nearest neighbors. In this paper, we propose an approximation method for solving RkNN queries, where the pruning operations and termination tests are guided by a characterization of the intrinsic dimensionality of the data. The method can accommodate any index structure supporting incremental (forward) nearest-neighbor search for the generation and verification of candidates, while avoiding impractically-high preprocessing costs. We also provide experimental evidence that our method significantly outperforms its competitors in terms of the tradeoff between execution time and the quality of the approximation. Our approach thus addresses many of the scalability issues surrounding the use of previous methods in data mining.
    OriginalsprogEngelsk
    TidsskriftProceedings of the VLDB Endowment
    Vol/bind10
    Udgave nummer7
    Sider (fra-til)769-780
    ISSN2150-8097
    DOI
    StatusUdgivet - 2017
    Begivenhed43rd International Conference on Very Large Data Bases - Technical University of Munich, Munich, Tyskland
    Varighed: 28. aug. 20171. sep. 2017
    Konferencens nummer: 43

    Konference

    Konference43rd International Conference on Very Large Data Bases
    Nummer43
    LokationTechnical University of Munich
    Land/OmrådeTyskland
    ByMunich
    Periode28/08/201701/09/2017

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'Dimensional testing for reverse k-nearest neighbor search'. Sammen danner de et unikt fingeraftryk.

    Citationsformater