Show simple item record

dc.contributor.authorKeivani, Omid
dc.contributor.authorSinha, Kaushik
dc.identifier.citationKeivani, Omid; Sinha, Kaushik. 2021. Random projection-based auxiliary information can improve tree-based nearest neighbor search. Information Sciences, vol. 546:pp 526-542en_US
dc.descriptionClick on the DOI link to access the article (may not be free).en_US
dc.description.abstractNearest neighbor search using random projection trees has recently been shown to achieve superior performance, in terms of better accuracy while retrieving less number of data points, compared to locality sensitive hashing based methods. However, to achieve acceptable nearest neighbor search accuracy for large scale applications, where number of data points and/or number of features can be very large, it requires users to maintain, store and search through large number of such independent random projection trees, which may be undesirable for many practical applications. To address this issue, in this paper we present different search strategies to improve nearest neighbor search performance of a single random projection tree. Our approach exploits properties of single and multiple random projections, which allows us to store meaningful auxiliary information at internal nodes of a random projection tree as well as to design priority functions to guide the search process that results in improved nearest neighbor search performance. Empirical results on multiple real world datasets show that our proposed method significantly improves nearest neighbor search accuracy of a single tree compared to baseline methods.en_US
dc.relation.ispartofseriesInformation Sciences;v.546
dc.subjectNearest neighbor searchen_US
dc.subjectRandom projection treeen_US
dc.subjectAuxiliary informationen_US
dc.subjectPriority functionen_US
dc.titleRandom projection-based auxiliary information can improve tree-based nearest neighbor searchen_US
dc.rights.holder© 2020 Elsevier Inc.en_US

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record