2015 · 209 citations · 26 references
ComputingComputer ScienceBig Data AnalyticsData MiningMachine LearningFeature TransformationGraph MiningGraph-based LearningHash FunctionsNearest Neighbor SearchRepresentation LearningApproximate Nearest Neighbor IndexingGraph SimilarityHashingNearest Neighbor MatchingScalable Graph Algorithms
Hashing has been widely used for approximate nearest neighbor (ANN) search in big data applications because of its low storage cost and fast retrieval speed. The goal of hashing is to map the data points from the original space into a binary-code space where the similarity (neighborhood structure) in the original space is preserved. By directly exploiting the similarity to guide the hashing code learning procedure, graph hashing has attracted much attention. However, most existing graph hashing methods cannot achieve satisfactory performance in real applications due to the high complexity for graph modeling. In this paper, we propose a novel method, called scalable graph hashing with feature transformation (SGH), for large-scale graph hashing. Through feature transformation, we can effectively approximate the whole graph without explicitly computing the similarity graph matrix, based on which a sequential learning method is proposed to learn the hash functions in a bitwise manner. Experiments on two datasets with one million data points show that our SGH method can outperform the state-of-the-art methods in terms of both accuracy and scalability.
26
Piotr Indyk, Rajeev Motwani · 1998 · 4.2K citations · Full text
Similarity Search in High Dimensions via Hashing
Aristides Gionis, Piotr Indyk, Rajeev Motwani · 1999 · 3.1K citations
Locality-sensitive hashing scheme based on p-stable distributions
Mayur Datar, Nicole Immorlica, Piotr Indyk et al. · 2004 · 3K citations
Storing and querying ordered XML using a relational database system
Igor Tatarinov, Stratis D. Viglas, Kevin Beyer et al. · 2002 · 2.3K citations
Yair Weiss, Antonio Torralba, Rob Fergus · neural information processing systems · 2008 · 2.1K citations