Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Ahmet Iscen Connect in order to contact the contributor
Submitted on : Tuesday, April 19, 2016 - 2:58:58 PM
Last modification on : Wednesday, November 3, 2021 - 6:05:32 AM
Long-term archiving on: : Wednesday, July 20, 2016 - 1:10:01 PM


Files produced by the author(s)



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⟩



Les métriques sont temporairement indisponibles