A group testing framework for similarity search in high-dimensional spaces

This paper introduces a group testing framework for detecting large similarities between high-dimensional vectors, such as descriptors used in state-of-the-art description of multimedia documents. At the crossroad of multimedia information retrieval and signal processing, we produce a set of group representations that jointly encode several vectors into a single one, in the spirit of group testing a By comparing a query vector to several of the diate representations, we screen the large value the similarities between the query and all the ve fraction of the cost of exhaustive similarity calcu Unlike concurrent indexing methods that suffe curse of dimensionality, our method exploits the of high-dimensional spaces. It therefore complem strategies for approximate nearest neighbor sear Our preliminary experiments demonstrate th of group testing for searching large databases of objects represented by vectors. We obtain a larg ment in terms of the theoretical complexity, at t small or negligible decrease of accuracy. We hop preliminary work will pave the way to subsequen multimedia retrieval with limited resources.EI