@inproceedings{890d94598fa54dac85eae9aa824a0a7e,
title = "Spectral hashing",
abstract = "Semantic hashing[1] seeks compact binary codes of data-points so that the Hamming distance between codewords correlates with semantic similarity. In this paper, we show that the problem of finding a best code for a given dataset is closely related to the problem of graph partitioning and can be shown to be NP hard. By relaxing the original problem, we obtain a spectral method whose solutions are simply a subset of thresholded eigen- vectors of the graph Laplacian. By utilizing recent results on convergence of graph Laplacian eigenvectors to the Laplace-Beltrami eigenfunctions of manifolds, we show how to efficiently calculate the code of a novel data- point. Taken together, both learning the code and applying it to a novel point are extremely simple. Our experiments show that our codes outper- form the state-of-the art.",
author = "Yair Weiss and Antonio Torralba and Rob Fergus",
year = "2009",
language = "English (US)",
isbn = "9781605609492",
series = "Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference",
publisher = "Neural Information Processing Systems",
pages = "1753--1760",
booktitle = "Advances in Neural Information Processing Systems 21 - Proceedings of the 2008 Conference",
note = "22nd Annual Conference on Neural Information Processing Systems, NIPS 2008 ; Conference date: 08-12-2008 Through 11-12-2008",
}