Spectral Hashing
Semantic hashing seeks compact binary codes of datapoints so that the Hamming distance between codewords correlates with semantic similarity. Hinton et al. used a clever implementation of autoencoders to find such codes. 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 thresh- olded eigenvectors of the graph Laplacian. By utilizing recent results on convergence of graph Laplacian eigenvectors to the Laplace-Beltrami eigen- functions of manifolds, we show how to efficiently calculate the code of a novel datapoint. Taken together, both learning the code and applying it to a novel point are extremely simple. Our experiments show that our codes significantly outperform the state-of-the art.
Code (0)
등록된 구현이 없습니다.
Tasks
graph partitioningSemantic SimilaritySemantic Textual SimilaritySimilar Papers 제목 키워드 기반
Unsupervised Deep Cross-modality Spectral Hashing
This paper presents a novel framework, namely Deep Cross-modality Spectral Hashing (DCSH), to tackle the unsupervised learning problem of binary hash codes for efficient cross-modal retrieval. The framework is a two-step…
Cross-Modal RetrievalRetrievalWord EmbeddingsA non-alternating graph hashing algorithm for large scale image search
In the era of big data, methods for improving memory and computational efficiency have become crucial for successful deployment of technologies. Hashing is one of the most effective approaches to deal with computational …
Computational EfficiencyImage RetrievalRetrievalSpectral Toolkit of Algorithms for Graphs: Technical Report (2)
Spectral Toolkit of Algorithms for Graphs (STAG) is an open-source library for efficient graph algorithms. This technical report presents the newly implemented component on locality sensitive hashing, kernel density esti…
ClusteringDensity EstimationLearning to Hash with Binary Reconstructive Embeddings
Fast retrieval methods are increasingly critical for many large-scale analysis tasks, and there have been several recent methods that attempt to learn hash functions for fast and accurate nearest neighbor searches. In t…
RetrievalAn NMF Perspective on Binary Hashing
The pervasiveness of massive data repositories has led to much interest in efficient methods for indexing, search, and retrieval. For image data, a rapidly developing body of work for these applications shows impressive …
GPUQuantizationRetrieval