Fetching the paper…

Reading the bibliography…

2011

Anti-sparse coding for approximate nearest neighbor search

Jégou, Hervé, Furon, Teddy, Fuchs, Jean-Jacques

Original
PDF
Post on X

Understand

This paper proposes a binarization scheme for vectors of high dimension based on the recent concept of anti-sparse coding, and shows its excellent performance for approximate nearest neighbor search.

Unlike other binarization schemes, this framework allows, up to a scaling factor, the explicit reconstruction from the binary representation of the original vector.
The paper also shows that random projections which are used in Locality Sensitive Hashing algorithms, are significantly outperformed by regular frames for both synthetic and real data if the number of bits exceeds the vector dimensionality, i.e., when high precision is required.

Anti-sparse coding for approximate nearest neighbor search · Around

Built on

“Least angle regression,”
B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, · 2004
Earlier work this paper cites.
“Distinctive image features from scale-invariant keypoints,”
D. Lowe, · 2004
Earlier work this paper cites.
“Near-optimal hashing algorithms for near neighbor problem in high dimensions,”
A. Andoni and P. Indyk, · 2006
Earlier work this paper cites.
“Video copy detection: a comparative study,”
J. Law-To, L. Chen, A. Joly, I. Laptev, O. Buisson, V. Gouet-Brunet, N. Boujemaa, and F. Stentiford, · 2007
Earlier work this paper cites.

Similar

“Content-based music information retrieval: Current directions and future challenges,”
M. A. Casey, R. Veltkamp, M. Goto, M. Leman, C. Rhodes, and M. Slaney, · 2008
Cited alongside, same era.
“Small codes and large databases for recognition,”
A. Torralba, R. Fergus, and Y. Weiss, · 2008
Cited alongside, same era.
“Spectral hashing,”
Y. Weiss, A. Torralba, and R. Fergus, · 2008
Cited alongside, same era.
“Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces,”
W. Dong, M. Charikar, and K. Li, · 2008
Cited alongside, same era.

Then

“Improving bag-of-features for large scale image search,”
H. Jégou, M. Douze, and C. Schmid, · 2010
Later among the works it cites.
“Searching in one billion vectors: re-rank with source coding,”
H. Jégou, R. Tavenard, M. Douze, and L. Amsaleg, · 2011
Closest in time.
“Product quantization for nearest neighbor search,”
H. Jégou, M. Douze, and C. Schmid, · 2011
Closest in time.
“Spread representations,”
J-J. Fuchs, · 2011
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…