Locality sensitive hashing (LSH) is a widely practiced c-approximate nearest neighbor(c-ANN) search algorithm in high dimensional spaces. The state-of-the-art LSH based algorithm searches an unbounded and irregular space to identify candidates, which jeopardizes the efficiency. To address this issue, we introduce the concept of virtual hypersphere partitioning. The core idea is to impose a virtual hypersphere, centered at the query, in the original feature space and only examine points inside the hypersphere. The search space of a hypersphere is isotropic and bounded, and thus more efficient than the existing one. In practice, we use multiple physical hyperspheres with different radii in corresponding projection subspaces to emulate the single virtual hypersphere. We also developed a principled method to compute the hypersphere radii for given success probability. Based on virtual hypersphere partitioning, we propose a novel disk-based indexing and searching scheme VHP to answer c-ANN queries. In the indexing phase, VHP stores LSH projections with independent B+-trees. To process a query, VHP keeps increasing the radii of physical hyperspheres coordinately, which in effect amounts to enlarging the virtual hypersphere, to accommodate more candidates until the success probability is met. Rigorous theoretical analysis shows that the proposed algorithm supports c-ANN search for arbitrarily small c >= 1 with probability guarantee. Extensive experiments on a variety of datasets, including the billion-scale ones, demonstrate that VHP could achieve different tradeoffs between efficiency and accuracy, and achieves up to 2x speedup in running time over the state-of-the-art methods.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning


    Beteiligte:
    Lu, Kejing (Autor:in) / Wang, Hongya (Autor:in) / Wang, Wei (Autor:in) / Kudo, Mineichi (Autor:in)


    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Schlagwörter :

    Klassifikation :

    DDC:    004 / 629




    Nearest neighbor search for relevance feedback

    Tesic, J. / Manjunath, B.S. | IEEE | 2003


    Nearest Neighbor Search for Relevance Feedback

    Tesic, J. / Manjunath, B. / IEEE | British Library Conference Proceedings | 2003


    Fast nearest-neighbor search algorithm [2669-11]

    Darwish, A. M. / SPIE | British Library Conference Proceedings | 1996


    Kernelized pyramid nearest-neighbor search for object categorization

    Cheng, H. | British Library Online Contents | 2014


    Efficient Nearest Neighbor Search on Metric Time Series

    Schäfer, Jörg Peter | Deutsches Zentrum für Luft- und Raumfahrt (DLR) | 2022

    Freier Zugriff