Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

1-2011

Abstract

Efficient nearest neighbor (NN) search techniques for highdimensional data are crucial to content-based image retrieval (CBIR). Traditional data structures (e.g., kd-tree) usually are only efficient for low dimensional data, but often perform no better than a simple exhaustive linear search when the number of dimensions is large enough. Recently, approximate NN search techniques have been proposed for high-dimensional search, such as Locality-Sensitive Hashing (LSH), which adopts some random projection approach. Motivated by similar idea, in this paper, we propose a new high dimensional NN search method, called Randomly Projected kd-Trees (RP-kd-Trees), which is to project data points into a lower-dimensional space so as to exploit the advantage of multiple kd-trees over low-dimensional data. Based on the proposed framework, we present an enhanced RP-kd-Trees scheme by applying distance metric learning techniques. We conducted extensive empirical studies on CBIR, which showed that our technique achieved faster search performance with better retrieval quality than regular LSH algorithms.

Discipline

Computer Sciences | Databases and Information Systems

Publication

Advances in Multimedia Modeling: 17th International Multimedia Modeling Conference, MMM 2011, Taipei, Taiwan, January 5-7, 2011, Proceedings, Part II

Volume

6524

First Page

371

Last Page

382

ISBN

9783642178283

Identifier

10.1007/978-3-642-17829-0_35

Publisher

Springer Verlag

City or Country

Berlin

Additional URL

http://dx.doi.org/10.1007/978-3-642-17829-0_35

Download

Share

COinS