Fast Near Neighbor Search in High-Dimensional Binary Data.

Anshumali Shrivastava, Ping LiECML/PKDD 2012 · OpenReview

Abstract

Numerous applications in search, databases, machine learning, and computer vision, can benefit from efficient algorithms for near neighbor search. This paper proposes a simple framework for fast near neighbor search in high-dimensional binary data, which are common in practice (e.g., text). We develop a very simple and effective strategy for sub-linear time near neighbor search, by creating hash tables directly using the bits generated by b-bit minwise hashing. The advantages of our method are demonstrated through thorough comparisons with two strong baselines: spectral hashing and sign (1-bit) random projections.
BibTeX
@inproceedings{shrivastava2012fast,
  author = {Anshumali Shrivastava and Ping Li},
  title = {{Fast Near Neighbor Search in High-Dimensional Binary Data.}},
  booktitle = {ECML/PKDD},
  year = {2012},
  url = {https://openreview.net/forum?id=r9LD5Dd1tCh1},
}

Loading related content...

Figure