HAL - INRIA :: [inria-00548629, version 1] Searching with expectations

inria-00548629, version 1

Searching with expectations

Harsimrat Sandhawalia ^1, 2, Hervé Jégou ()^a^, 3

IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP '10) (2010) 1242--1245

Abstract: Handling large amounts of data, such as large image databases, requires the use of approximate nearest neighbor search techniques. Recently, Hamming embedding methods such as spectral hashing have addressed the problem of obtaining compact binary codes optimizing the trade-off between the memory usage and the probability of retrieving the true nearest neighbors. In this paper, we formulate the problem of generating compact signatures as a rate-distortion problem. In the spirit of source coding algorithms, we aim at minimizing the reconstruction error on the squared distances with a constraint on the memory usage. The vectors are ranked based on the distance estimates to the query vector. Experiments on image descriptors show a significant improvement over spectral hashing.

a – INRIA
1: Laboratoire Jean Kuntzmann (LJK)
CNRS : UMR5224 – Université Joseph Fourier - Grenoble I – Université Pierre Mendès-France - Grenoble II – Institut Polytechnique de Grenoble - Grenoble Institute of Technology
2: LEAR (INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann)
CNRS : FR71 – CNRS : UMR5527 – INRIA – Laboratoire Jean Kuntzmann – Université Joseph Fourier - Grenoble I – Institut National Polytechnique de Grenoble (INPG)
3: TEXMEX (INRIA - IRISA)
CNRS : UMR6074 – INRIA – INSA Rennes – Université de Rennes 1

inria-00548629, version 1
http://hal.inria.fr/inria-00548629
oai:hal.inria.fr:inria-00548629
From: Hervé Jégou <>
Submitted for: Laure BENAC <>
Submitted on: Monday, 20 December 2010 10:21:36
Updated on: Monday, 10 January 2011 14:24:44

See detailed view

Associated documents

PDF :

DOI: 10.1109/ICASSP.2010.5495403

Full text from publisher

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00548629"><analytic>
<author><persName><forename>Harsimrat</forename><surname>Sandhawalia</surname></persName>
<affiliation>
<orgName type="laboratory">LJK</orgName>
<orgName type="team">Laboratoire Jean Kuntzmann</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5224</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Université Pierre Mendès-France - Grenoble II</orgName>
<orgName type="institution">Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann</orgName>
<orgName type="team">LEAR</orgName>
<country>FR</country>
<orgName type="institution">CNRS : FR71</orgName>
<orgName type="institution">CNRS : UMR5527</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Laboratoire Jean Kuntzmann</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Institut National Polytechnique de Grenoble (INPG)</orgName>
</affiliation>
</author>
<author><persName><forename>Hervé</forename><surname>Jégou</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA - IRISA</orgName>
<orgName type="team">TEXMEX</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6074</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">INSA Rennes</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<title type="main" level="a">Searching with expectations</title></analytic><monogr><meeting>IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP '10)</meeting><imprint><publisher>IEEE Signal Processing Society</publisher><pubPlace><settlement>Dallas</settlement><country>United States</country></pubPlace><biblScope type="publicationDate">2010-00-00</biblScope><biblScope type="pp">1242--1245</biblScope></imprint></monogr><idno type="doi">10.1109/ICASSP.2010.5495403</idno><idno type="HALid">http://hal.inria.fr/inria-00548629</idno><idno type="HALFile">http://hal.inria.fr/inria-00548629/PDF/searching_with_expectations.pdf</idno></biblStruct>
</listBibl>
</listBibl>