• 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.

    Fast l(1)-norm nearest neighbor search using a simple variant of randomized partition tree

    View/Open
    Sinha_2015.pdf (463.6Kb)
    Date
    2015-08-08
    Author
    Sinha, Kaushik
    Metadata
    Show full item record
    Citation
    Sinha, Kaushik. 2015. Fast l(1)-norm nearest neighbor search using a simple variant of randomized partition tree. Procedia Computer Science, vol. 53:pp 64–73, INNS Conference on Big Data 2015 Program San Francisco, CA, USA 8-10 August 2015
    Abstract
    For big data applications, randomized partition trees have recently been shown to be very effective in answering high dimensional nearest neighbor search queries with provable guarantee, when distances are measured using l(2) norm. Unfortunately, if distances are measured using l(1) norm, the same theoretical guarantee does not hold. In this paper, we show that a simple variant of randomized partition tree, which uses a different randomization using 1-stable distribution, can be used to efficiently answer high dimensional nearest neighbors queries when distances are measured using l(1) norm. Experimental evaluations on eight real datasets suggest that the proposed method achieves better l(i)-norm nearest neighbor search accuracy with fewer retrieved data points as compared to locality sensitive hashing.
    Description
    Open Access article. Under a Creative Commons License.
    URI
    http://dx.doi.org/10.1016/j.procs.2015.07.280
    http://hdl.handle.net/10057/11530
    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