• Login
    View Item 
    •   Shocker Open Access Repository Home
    • Engineering
    • Electrical Engineering and Computer Science
    • EECS Faculty Scholarship
    • EECS Research Publications
    • View Item
    •   Shocker Open Access Repository Home
    • Engineering
    • Electrical Engineering and Computer Science
    • EECS Faculty Scholarship
    • EECS Research Publications
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Randomized partition trees for nearest neighbor search

    Date
    2015-05
    Author
    Dasgupta, Sanjoy
    Sinha, Kaushik
    Metadata
    Show full item record
    Citation
    Dasgupta, Sanjoy; Sinha, Kaushik. Dasgupta, Sanjoy; Sinha, Kaushik. 2015. Randomized partition trees for nearest neighbor search. Algorithmica, May 2015:vol. 72:no. 1:pp 237-263
    Abstract
    The -d tree was one of the first spatial data structures proposed for nearest neighbor search. Its efficacy is diminished in high-dimensional spaces, but several variants, with randomization and overlapping cells, have proved to be successful in practice. We analyze three such schemes. We show that the probability that they fail to find the nearest neighbor, for any data set and any query point, is directly related to a simple potential function that captures the difficulty of the point configuration. We then bound this potential function in several situations of interest: when the data are drawn from a doubling measure; when the data and query distributions are identical and are supported on a set of bounded doubling dimension; and when the data are documents from a topic model.
    Description
    Click on the DOI link to access the article (may not be free).
    URI
    http://dx.doi.org/10.1007/s00453-014-9885-5
    http://hdl.handle.net/10057/11260
    Collections
    • EECS Research Publications

    Browse

    All of Shocker Open Access RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsBy TypeThis CollectionBy Issue DateAuthorsTitlesSubjectsBy Type

    My Account

    LoginRegister

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    DSpace software copyright © 2002-2021  DuraSpace
    Contact Us | Send Feedback
    DSpace Express is a service operated by 
    Atmire NV