Show simple item record

dc.contributor.authorSinha, Kaushik
dc.date.accessioned2015-09-18T18:19:17Z
dc.date.available2015-09-18T18:19:17Z
dc.date.issued2015-08-08
dc.identifier.citationSinha, 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 2015en_US
dc.identifier.issn1877-0509
dc.identifier.otherWOS:000360311000008
dc.identifier.urihttp://dx.doi.org/10.1016/j.procs.2015.07.280
dc.identifier.urihttp://hdl.handle.net/10057/11530
dc.descriptionOpen Access article. Under a Creative Commons License.en_US
dc.description.abstractFor 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.en_US
dc.language.isoen_USen_US
dc.publisherElsevier B.V.en_US
dc.relation.ispartofseriesProcedia Computer Science;v.53
dc.subjectNearest neighbor searchen_US
dc.subjectBig dataen_US
dc.subjectRandomized partition treeen_US
dc.titleFast l(1)-norm nearest neighbor search using a simple variant of randomized partition treeen_US
dc.typeConference paperen_US
dc.rights.holderCopyright The Authors. Published by Elsevier B.V.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record