Evaluation of strategies for multiple sphere queries with local image descriptors

Nouha Bouteldja; Valérie Gouet-Brunet; Michel Scholl

doi:10.1117/12.650657

16 January 2006 Evaluation of strategies for multiple sphere queries with local image descriptors

Nouha Bouteldja, Valérie Gouet-Brunet, Michel Scholl

Proceedings Volume 6073, Multimedia Content Analysis, Management, and Retrieval 2006; 60730A (2006) https://doi.org/10.1117/12.650657
Event: Electronic Imaging 2006, 2006, San Jose, California, United States

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 A_i,iε1,m} where A_i is the set of points within a sphere of center query point p_i,iε{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.

Citation Download Citation

Nouha Bouteldja, Valérie Gouet-Brunet, and 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); https://doi.org/10.1117/12.650657

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available