Evaluation of strategies for multiple sphere queries with local image descriptors
Lists
Only you see this
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 <i>m</i> query points (a multiple query): we want to efficiently find the sequence <i>A</i><sub><i>i</i>,<i>i</i>ε1,<i>m</i>}</sub> where <i>A<sub>i</sub></i> is the set of points within a sphere of center query point p<sub><i>i</i>,<i>iε</i>{1,<i>m</i>}</sub> and radius <i>ε</i> (a sphere query). It has been argued that beyond a rather small dimension (<i>d</i> ⩾ 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 <i>m</i> 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.
BibTeX
@inproceedings{bouteldja2006evaluation,
author = {Nouha Bouteldja and Valérie Gouet-Brunet and Micheł Scholl},
title = {{Evaluation of strategies for multiple sphere queries with local image descriptors}},
booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
year = {2006},
doi = {10.1117/12.650657},
}Loading related content...