Semi-Supervised SimHash for Efficient Document Similarity Search

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 93–101, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Semi-Supervised SimHash for Efficient Document Similarity Search Qixia Jiang and Maosong Sun State Key Laboratory on Intelligent Technology and Systems Tsinghua National Laboratory for Information Science and Technology Department of Computer Sci. and Tech., Tsinghua University, Beijing 100084, China qixia.jiang@gmail.com, sms@tsinghua.edu.cn Abstract Searching documents that are similar to a query document is an important component in modern information retrieval. Some ex- isting hashing methods can be used for effi- cient document similarity search. However, unsupervised hashing methods cannot incor- porate prior knowledge for better hashing. Although some supervised hashing methods can derive effective hash functions from prior knowledge, they are either computationally expensive or poorly discriminative. This pa- per proposes a novel (semi-)supervised hash- ing method named Semi-Supervised SimHash (S3H) for high-dimensional data similarity search. The basic idea of S3H is to learn the optimal feature weights from prior knowledge to relocate the data such that similar data have similar hash codes. We evaluate our method with several state-of-the-art methods on two large datasets. All the results show that our method gets the best performance. 1 Introduction Document Similarity Search (DSS) is to find sim- ilar documents to a query doc in a text corpus or on the web. It is an important component in mod- ern information retrieval since DSS can improve the traditional search engines and user experience (Wan et al., 2008; Dean et al., 1999). Traditional search engines accept several terms submitted by a user as a query and return a set of docs that are rele- vant to the query. However, for those users who are not search experts, it is always difficult to ac- curately specify some query terms to express their search purposes. Unlike short-query based search, DSS queries by a full (long) document, which allows users to directly submit a page or a document to the search engines as the description of their informa- tion needs. Meanwhile, the explosion of information has brought great challenges to traditional methods. For example, Inverted List (IL) which is a primary key-term access method would return a very large set of docs for a query document, which leads to the time-consuming post-processing. Therefore, a new effective algorithm is required. Hashing methods can perform highly efficient but approximate similarity search, and have gained great success in many applications such as Content-Based Image Retrieval (CBIR) (Ke et al., 2004; Kulis et al., 2009b), near-duplicate data detection (Ke et al., 2004; Manku et al., 2007; Costa et al., 2010), etc. Hashing methods project high-dimensional ob- jects to compact binary codes called fingerprints and make similar fingerprints for similar objects. The similarity search in the Hamming space1 is much more efficient than in the original attribute space (Manku et al., 2007). Recently, several hashing methods have been pro- posed. Specifically, SimHash (SH) (Charikar M.S., 2002) uses random projections to hash data. Al- though it works well with …

Content truncated to 500 words