NDLI: Complementary hashing for approximate nearest neighbor search

Content Provider	IEEE Xplore Digital Library
Author	Hao Xu Jingdong Wang Zhu Li Gang Zeng Shipeng Li Nenghai Yu
Copyright Year	2011
Description	Author affiliation: Microsoft Research Asia, China (Jingdong Wang; Shipeng Li) \|\| MOE-MS KeyLab of MCC, University of Science and Technology of China, China (Hao Xu; Nenghai Yu) \|\| Core Networks Research, Huawei Technology, USA (Zhu Li) \|\| Key Laboratory of Machine Perception, Peking University, China (Gang Zeng)
Abstract	Recently, hashing based Approximate Nearest Neighbor (ANN) techniques have been attracting lots of attention in computer vision. The data-dependent hashing methods, e.g., Spectral Hashing, expects better performance than the data-blind counterparts, e.g., Locality Sensitive Hashing (LSH). However, most data-dependent hashing methods only employ a single hash table. When higher recall is desired, they have to retrieve exponentially growing number of hash buckets around the bucket containing the query, which may drag down the precision rapidly. In this paper, we propose a so-called complementary hashing approach, which is able to balance the precision and recall in a more effective way. The key idea is to employ multiple complementary hash tables, which are learned sequentially in a boosting manner, so that, given a query, its true nearest neighbors missed from the active bucket of one hash table are more likely to be found in the active bucket of the next hash table. Compared with LSH that also can exploit multiple hash tables, our approach is more effective to find true NNs, thanks to the complementarity property of the hash tables from our approach. Experimental results on large scale ANN search show that the proposed method significantly improves the performance and outperforms the state-of-the-art.
Starting Page	1631
Ending Page	1638
File Size	237037
Page Count	8
File Format	PDF
ISBN	9781457711015
ISSN	15505499
e-ISBN	9781457711022
DOI	10.1109/ICCV.2011.6126424
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-11-06
Publisher Place	Spain
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Artificial neural networks Boosting Covariance matrix Sparse matrices Databases Redundancy Eigenvalues and eigenfunctions
Content Type	Text
Resource Type	Article
Subject	Computer Vision and Pattern Recognition Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Optimized Product Quantization for Approximate Nearest Neighbor Search

Complementary Projection Hashing

Locally Optimized Product Quantization for Approximate Nearest Neighbor Search

Cartesian K-Means

Jensen-Bregman LogDet Divergence with Application to Efficient Similarity Search for Covariance Matrices

Efficient similarity search for covariance matrices via the Jensen-Bregman LogDet Divergence

Approximate Nearest Subspace Search

Adaptive Object Retrieval with Kernel Reconstructive Hashing

Sparse Convolutional Neural Networks

Complementary hashing for approximate nearest neighbor search

Similar Documents

Optimized Product Quantization for Approximate Nearest Neighbor Search

Complementary Projection Hashing

Locally Optimized Product Quantization for Approximate Nearest Neighbor Search

Cartesian K-Means

Jensen-Bregman LogDet Divergence with Application to Efficient Similarity Search for Covariance Matrices

Efficient similarity search for covariance matrices via the Jensen-Bregman LogDet Divergence

Approximate Nearest Subspace Search

Adaptive Object Retrieval with Kernel Reconstructive Hashing

Sparse Convolutional Neural Networks

Complementary hashing for approximate nearest neighbor search