A meta-indexing method for fast probably approximately correct nearest neighbor searches
EntityUAM. Departamento de Ingeniería Informática
10.1007/s11042-022-12690-wMultimedia Tools and Applications 22.15 (2022):
ISSN1380-7501 (print); 1573-7721 (online)
Funded byOpen Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature
SubjectsApproximate nearest neighbor; Approximate search; Curse of dimensionality; Error modeling; Indexing; Multimedia data base; Informática
Rights© The author(s)
Esta obra está bajo una Licencia Creative Commons Atribución 4.0 Internacional.
In this paper we present an indexing method for probably approximately correct nearest neighbor queries in high dimensional spaces capable of improving the performance of any index whose performance degrades with the increased dimensionality of the query space. The basic idea of the method is quite simple: we use SVD to concentrate the variance of the inter-element distance in a lower dimensional space, Ξ. We do a nearest neighbor query in this space and then we “peek” forward from the nearest neighbor by gathering all the elements whose distance from the query is less than dΞ(1+ζσΞ2), where dΞ is the distance from the nearest neighbor in Ξ, σΞ2 is the variance of the data in Ξ, and ζ a parameter. All the data thus collected form a tentative set T, in which we do a scan using the complete feature space to find the point closest to the query. The advantages of the method are that (1) it can be built on top of virtually any indexing method and (2) we can build a model of the distribution of the error precise enough to allow designing a compromise between error and speed. We show the improvement that we can obtain using data from the SUN data base
Google Scholar:Santini, Simone
This item appears in the following Collection(s)
Showing items related by title, author, creator and subject.