Timezone: »
Oral
Locality-Sensitive Binary Codes from Shift-Invariant Kernels
Maxim Raginsky · Svetlana Lazebnik
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 binary strings. We introduce a simple distribution-free encoding scheme based on random projections, such that the expected Hamming distance between the binary 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.
Author Information
Maxim Raginsky (University of Illinois at Urbana-Champaign)
Svetlana Lazebnik (UIUC)
Related Events (a corresponding poster, oral, or spotlight)
-
2009 Poster: Locality-sensitive binary codes from shift-invariant kernels »
Wed. Dec 9th 03:00 -- 07:59 AM Room
More from the Same Authors
-
2021 Poster: Information-theoretic generalization bounds for black-box learning algorithms »
Hrayr Harutyunyan · Maxim Raginsky · Greg Ver Steeg · Aram Galstyan -
2019 Poster: Universal Approximation of Input-Output Maps by Temporal Convolutional Nets »
Joshua Hanson · Maxim Raginsky -
2018 Poster: Minimax Statistical Learning with Wasserstein distances »
Jaeho Lee · Maxim Raginsky -
2018 Spotlight: Minimax Statistical Learning with Wasserstein distances »
Jaeho Lee · Maxim Raginsky -
2017 Poster: Information-theoretic analysis of generalization capability of learning algorithms »
Aolin Xu · Maxim Raginsky -
2017 Spotlight: Information-theoretic analysis of generalization capability of learning algorithms »
Aolin Xu · Maxim Raginsky -
2012 Poster: Angular Quantization based Binary Codes for Fast Similarity Search »
Yunchao Gong · Sanjiv Kumar · Vishal Verma · Svetlana Lazebnik -
2011 Poster: Lower Bounds for Passive and Active Learning »
Maxim Raginsky · Sasha Rakhlin -
2011 Spotlight: Lower Bounds for Passive and Active Learning »
Maxim Raginsky · Sasha Rakhlin -
2010 Workshop: Beyond classification: Machine Learning for next generation Computer Vision challenges »
Craig Saunders · Jakob Verbeek · Svetlana Lazebnik -
2008 Poster: Near-minimax recursive density estimation on the binary hypercube »
Maxim Raginsky · Svetlana Lazebnik · Rebecca Willett · Jorge G Silva -
2008 Spotlight: Near-minimax recursive density estimation on the binary hypercube »
Maxim Raginsky · Svetlana Lazebnik · Rebecca Willett · Jorge G Silva