Share Email Print

Proceedings Paper

Evaluation of strategies for multiple sphere queries with local image descriptors
Author(s): Nouha Bouteldja; Valérie Gouet-Brunet; Michel Scholl
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

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.

Paper Details

Date Published: 16 January 2006
PDF: 12 pages
Proc. SPIE 6073, Multimedia Content Analysis, Management, and Retrieval 2006, 60730A (16 January 2006); doi: 10.1117/12.650657
Show Author Affiliations
Nouha Bouteldja, CEDRIC/CNAM (France)
Valérie Gouet-Brunet, CEDRIC/CNAM (France)
Michel Scholl, CEDRIC/CNAM (France)

Published in SPIE Proceedings Vol. 6073:
Multimedia Content Analysis, Management, and Retrieval 2006
Edward Y. Chang; Alan Hanjalic; Nicu Sebe, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?