16 January 2006 Evaluation of strategies for multiple sphere queries with local image descriptors
Author Affiliations +
In this paper, we are interested in the fast retrieval, in a large collection of points in high-dimensional space, of points close to a set of m query points (a multiple query): we want to efficiently find the sequence Ai,iε1,m} where Ai is the set of points within a sphere of center query point pi,{1,m} and radius ε (a sphere query). It has been argued that beyond a rather small dimension (d ⩾ 10) for such sphere queries as well as for other similarity queries, sequentially scanning the collection of points is faster than crossing a tree structure indexing the collection (the so-called curse of dimensionality phenomenon). Our first contribution is to experimentally assess whether the curse of dimensionality is reached with various points distributions. We compare the performance of a single sphere query when the collection is indexed by a tree structure (an SR-tree in our experiments) to that of a sequential scan. The second objective of this paper is to propose and evaluate several algorithms for multiple queries in a collection of points indexed by a tree structure. We compare the performance of these algorithms to that of a naive one consisting in sequentially running the m queries. This study is applied to content-based image retrieval where images are described by local descriptors based on points of interest. Such descriptors involve a relatively small dimension (8 to 30) justifying that the collection of points be indexed by a tree structure; similarity search with local descriptors implies multiple sphere queries that are usually time expensive, justifying the proposal of new strategies.
© (2006) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Nouha Bouteldja, Nouha Bouteldja, Valérie Gouet-Brunet, Valérie Gouet-Brunet, Michel Scholl, Michel Scholl, } "Evaluation of strategies for multiple sphere queries with local image descriptors", Proc. SPIE 6073, Multimedia Content Analysis, Management, and Retrieval 2006, 60730A (16 January 2006); doi: 10.1117/12.650657; https://doi.org/10.1117/12.650657

Back to Top