Scaling Group Testing Similarity Search

Ahmet Iscen 1 Laurent Amsaleg 1 Teddy Furon 1
1 LinkMedia - Creating and exploiting explicit links between multimedia fragments
Inria Rennes – Bretagne Atlantique , IRISA-D6 - MEDIA ET INTERACTIONS
Abstract : The large dimensionality of modern image feature vectors, up to thousands of dimensions, is challenging the high dimensional indexing techniques. Traditional approaches fail at returning good quality results within a response time that is usable in practice. However, similarity search techniques inspired by the group testing framework have recently been proposed in an attempt to specifically defeat the curse of dimensionality. Yet, group testing does not scale and fails at indexing very large collections of images because its internal procedures analyze an excessively large fraction of the indexed data collection. This paper identifies these difficulties and proposes extensions to the group testing framework for similarity searches that allow to handle larger collections of feature vectors. We demonstrate that it can return high quality results much faster compared to state-of-the-art group testing strategies when indexing truly high-dimensional features that are indeed hardly indexable with traditional indexing approaches.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01304287
Contributor : Ahmet Iscen <>
Submitted on : Tuesday, April 19, 2016 - 2:58:58 PM
Last modification on : Thursday, February 7, 2019 - 2:34:43 PM
Long-term archiving on : Wednesday, July 20, 2016 - 1:10:01 PM

File

ScalableGroupTesting_hal.pdf
Files produced by the author(s)

Identifiers

Citation

Ahmet Iscen, Laurent Amsaleg, Teddy Furon. Scaling Group Testing Similarity Search. ACM International Conference on Multimedia Retrieval 2016 , Jun 2016, New York, United States. ⟨10.1145/2911996.2912010⟩. ⟨hal-01304287⟩

Share

Metrics

Record views

580

Files downloads

375