2010 ScalableSimilaritySearchwithOpt

• (He et al., 2010) ⇒ Junfeng He, Wei Liu, and Shih-Fu Chang. (2010). “Scalable Similarity Search with Optimized Kernel Hashing.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835946

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Scalable+similarity+search+with+optimized+kernel+hashing%22+2010
• http://portal.acm.org/citation.cfm?id=1835946&preflayout=flat#citedby

Quotes

Abstract

Scalable similarity search is the core of many large scale learning or data mining applications. Recently, many research results demonstrate that one promising approach is creating compact and efficient hash codes that preserve data similarity. By efficient, we refer to the low correlation (and thus low redundancy) among generated codes. However, most existing hash methods are designed only for vector data. In this paper, we develop a new hashing algorithm to create efficient codes for large scale data of general formats with any kernel function, including kernels on vectors, graphs, sequences, sets and so on. Starting with the idea analogous to spectral hashing, novel formulations and solutions are proposed such that a kernel based hash function can be explicitly represented and optimized, and directly applied to compute compact hash codes for new samples of general formats. Moreover, we incorporate efficient techniques, such as Nystrom approximation, to further reduce time and space complexity for indexing and search, making our algorithm scalable to huge data sets. Another important advantage of our method is the ability to handle diverse types of similarities according to actual task requirements, including both feature similarities and semantic similarities like label consistency. We evaluate our method using both vector and non-vector data sets at a large scale up to 1 million samples. Our comprehensive results show the proposed method outperforms several state-of-the-art approaches for all the tasks, with a significant gain for most tasks.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 ScalableSimilaritySearchwithOpt	Wei Liu Junfeng He Shih-Fu Chang			Scalable Similarity Search with Optimized Kernel Hashing		KDD-2010 Proceedings		10.1145/1835804.1835946		2010