Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Gaussian Kernel
Hamming Distance
High Dimensional Data
Random Projection
Space Mapping
Theoretical Analysis
Shift Invariant
Related Publications
(1)
Nearoptimal hashing algorithms for approximate nearest neighbor in high dimensions
Subscribe
Academic
Publications
LocalitySensitive Binary Codes from ShiftInvariant Kernels
LocalitySensitive Binary Codes from ShiftInvariant Kernels,Maxim Raginsky,Svetlana Lazebnik
Edit
LocalitySensitive Binary Codes from ShiftInvariant Kernels
(
Citations: 15
)
BibTex

RIS

RefWorks
Download
Maxim Raginsky
,
Svetlana Lazebnik
This paper addresses the problem of designing binary codes for highdimensional data such that vectors that are similar in the original space map to similar bi nary strings. We introduce a simple distributionfree encoding scheme based on random projections, such that the expected
Hamming distance
between the bi nary codes of two vectors is related to the value of a shiftinvariant kernel (e.g., a Gaussian kernel) between the vectors. We present a full
theoretical analysis
of the convergence properties of the proposed scheme, and report favorable experimental performance as compared to a recent stateoftheart method, spectral hashing.
Conference:
Neural Information Processing Systems  NIPS
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
books.nips.cc
)
(
people.ee.duke.edu
)
Citation Context
(13)
...Another class [9], [10], [11], [
12
] takes advantage of training data to learn short binary codes whose distances are small for positive training pairs and large for others...
...In particular, similaritysensitive hashing (SSH) or localitysensitive hashing [9], [10], [14], [11], [
12
] algorithms seek to find an efficient binary representation of highdimensional data maintaining their similarity in the new space...
Christoph Strecha
,
et al.
LDAHash: Improved Matching with Smaller Descriptors
...Recently, a lot of research efforts have been conducted on finding good hashing functions, by using metric learninglike techniques, including optimized kernel hashing [11], learned metrics [12], learnt binary reconstruction [15], kernelized LSH [16], and shift kernel hashing [
22
], semisupervised hashing [31], spectral hashing [32]...
Jingdong Wang
,
et al.
Querydriven iterated neighborhood graph search for scalable visual in...
...as many subsequent ones [34, 12,
23
, 5, 14] focused on small image signatures (typically GIST or BOV) with a few hundreds or a few thousands of dimensions...
...For instance, [
23
] requires dense projections and [34, 5, 14] require a global PCA...
Jorge Sanchez
,
et al.
Highdimensional signature compression for largescale image classific...
...Recent works [1, 2, 3, 5, 6, 11, 10, 8, 13,
14
, 12, 17], have reported interesting results in finding approximate solutions over large data sets...
...Recently, many hash coding based algorithms have been proposed to handle similarity search of high dimensional data [3, 5, 6, 11, 10, 8, 13,
14
, 12, 17]...
...Though several recent previous kernel hashing methods, e.g.,[13,
14
, 12] have discussed hashing for nonvectors, but they all need a Mercer kernel function...
Junfeng He
,
et al.
Compact hashing with joint optimization of search accuracy and time
...Recently, the vision community has devoted a lot of attention to the problem of learning similaritypreserving binary codes for representing largescale image collections [
12
, 16, 18, 19, 20, 21]...
...Raginsky and Lazebnik [
12
] have proposed a distributionfree method based on the random features mapping for shiftinvariant kernels [13]...
...This approach, dubbed iterative quantization (ITQ) has connections to the orthogonal Procrustes problem [15] and to eigenvector discretization for multiclass spectral partitioning [22], and in our experiments it outperforms the methods of [
12
, 19, 21]...
...We follow two evaluation protocols widely used in recent papers [
12
, 19, 21]...
...As in [
12
], a nominal threshold of the average distance to the 50th nearest neighbor is used to determine whether a database point returned for a given query is considered a true positive...
...2. SKLSH [
12
]: This method is based on the random features mapping for approximating shiftinvariant kernels [13]...
...In [
12
], this method is reported to outperform SH for code sizes larger than 64 bits...
...We use a Gaussian kernel with bandwidth set to the average distance to the 50th nearest neighbor as in [
12
]...
Yunchao Gong
,
et al.
Iterative quantization: A procrustean approach to learning binary code...
References
(16)
Nearoptimal hashing algorithms for approximate nearest neighbor in high dimensions
(
Citations: 104
)
Alexandr Andoni
,
Piotr Indyk
Journal:
Communications of The ACM  CACM
, vol. 51, no. 1, pp. 117122, 2008
Random projection trees and low dimensional manifolds
(
Citations: 30
)
Sanjoy Dasgupta
,
Yoav Freund
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 537546, 2008
An elementary proof of a theorem of Johnson and Lindenstrauss
(
Citations: 74
)
Sanjoy Dasgupta
,
Anupam Gupta
Journal:
Random Structures and Algorithms  RSA
, vol. 22, no. 1, pp. 6065, 2003
Nearestneighborpreserving embeddings
(
Citations: 28
)
Piotr Indyk
,
Assaf Naor
Journal:
ACM Transactions on Algorithms  TALG
, vol. 3, no. 3, pp. 31es, 2007
Modeling the Shape of the Scene: A Holistic Representation of the Spatial Envelope
(
Citations: 662
)
Aude Oliva
,
Antonio B. Torralba
Journal:
International Journal of Computer Vision  IJCV
, vol. 42, no. 3, pp. 145175, 2001
Sort by:
Citations
(15)
LDAHash: Improved Matching with Smaller Descriptors
(
Citations: 2
)
Christoph Strecha
,
Alexander M. Bronstein
,
Michael M. Bronstein
,
Pascal Fua
Journal:
IEEE Transactions on Pattern Analysis and Machine Intelligence  PAMI
, vol. 34, no. 1, pp. 6678, 2012
Querydriven iterated neighborhood graph search for scalable visual indexing
Jingdong Wang
,
XianSheng Hua
,
Shipeng Li
Published in 2012.
Highdimensional signature compression for largescale image classification
(
Citations: 1
)
Jorge Sanchez
,
Florent Perronnin
Conference:
Computer Vision and Pattern Recognition  CVPR
, pp. 16651672, 2011
Compact hashing with joint optimization of search accuracy and time
Junfeng He
,
ShihFu Chang
,
Regunathan Radhakrishnan
,
Claus Bauer
Conference:
Computer Vision and Pattern Recognition  CVPR
, pp. 753760, 2011
Iterative quantization: A procrustean approach to learning binary codes
Yunchao Gong
,
Svetlana Lazebnik
Conference:
Computer Vision and Pattern Recognition  CVPR
, pp. 817824, 2011