Academic
Publications
Locality-Sensitive Binary Codes from Shift-Invariant Kernels

Locality-Sensitive Binary Codes from Shift-Invariant Kernels,Maxim Raginsky,Svetlana Lazebnik

Locality-Sensitive Binary Codes from Shift-Invariant Kernels   (Citations: 15)
BibTex | RIS | RefWorks Download
This paper addresses the problem of designing binary codes for high-dimensional data such that vectors that are similar in the original space map to similar bi- nary strings. We introduce a simple distribution-free 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 shift-invariant 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 state-of-the-art method, spectral hashing.
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.
    • ...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, similarity-sensitive hashing (SSH) or localitysensitive hashing [9], [10], [14], [11], [12] algorithms seek to find an efficient binary representation of high-dimensional data maintaining their similarity in the new space...

    Christoph Strechaet al. LDAHash: Improved Matching with Smaller Descriptors

    • ...Recently, a lot of research efforts have been conducted on finding good hashing functions, by using metric learning-like techniques, including optimized kernel hashing [11], learned metrics [12], learnt binary reconstruction [15], kernelized LSH [16], and shift kernel hashing [22], semi-supervised hashing [31], spectral hashing [32]...

    Jingdong Wanget al. Query-driven 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 Sanchezet al. High-dimensional signature compression for large-scale 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 non-vectors, but they all need a Mercer kernel function...

    Junfeng Heet 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 similarity-preserving binary codes for representing large-scale image collections [12, 16, 18, 19, 20, 21]...
    • ...Raginsky and Lazebnik [12] have proposed a distribution-free method based on the random features mapping for shift-invariant kernels [13]...
    • ...This approach, dubbed iterative quantization (ITQ) has connections to the orthogonal Procrustes problem [15] and to eigenvector discretization for multi-class 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 shift-invariant 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 Gonget al. Iterative quantization: A procrustean approach to learning binary code...

Sort by: