Unsupervised multi-index semantic hashing

Christian Hansen, Casper Hansen, Jakob Grue Simonsen, Stephen Alstrup, Christina Lioma

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

6 Citations (Scopus)
17 Downloads (Pure)

Abstract

Semantic hashing represents documents as compact binary vectors (hash codes) and allows both efficient and effective similarity search in large-scale information retrieval. The state of the art has primarily focused on learning hash codes that improve similarity search effectiveness, while assuming a brute-force linear scan strategy for searching over all the hash codes, even though much faster alternatives exist. One such alternative is multi-index hashing, an approach that constructs a smaller candidate set to search over, which depending on the distribution of the hash codes can lead to sub-linear search time. In this work, we propose Multi-Index Semantic Hashing (MISH), an unsupervised hashing model that learns hash codes that are both effective and highly efficient by being optimized for multi-index hashing. We derive novel training objectives, which enable to learn hash codes that reduce the candidate sets produced by multi-index hashing, while being end-to-end trainable. In fact, our proposed training objectives are model agnostic, i.e., not tied to how the hash codes are generated specifically in MISH, and are straight-forward to include in existing and future semantic hashing models. We experimentally compare MISH to state-of-the-art semantic hashing baselines in the task of document similarity search. We find that even though multi-index hashing also improves the efficiency of the baselines compared to a linear scan, they are still upwards of 33% slower than MISH, while MISH is still able to obtain state-of-the-art effectiveness.

Original languageEnglish
Title of host publicationThe Web Conference 2021 - Proceedings of the World Wide Web Conference, WWW 2021
PublisherAssociation for Computing Machinery, Inc
Publication date2021
Pages2879-2889
ISBN (Electronic)9781450383127
DOIs
Publication statusPublished - 2021
Event2021 World Wide Web Conference, WWW 2021 - Ljubljana, Slovenia
Duration: 19 Apr 202123 Apr 2021

Conference

Conference2021 World Wide Web Conference, WWW 2021
Country/TerritorySlovenia
CityLjubljana
Period19/04/202123/04/2021
SponsorAmazon, et al., Facebook, FINVOLUTION, Microsoft Research, Pinterest
SeriesThe Web Conference 2021 - Proceedings of the World Wide Web Conference, WWW 2021

Bibliographical note

Publisher Copyright:
© 2021 ACM.

Keywords

  • Multi-index hashing
  • Semantic hashing
  • Similarity search

Cite this