Skip to content

An implementation of efficient LSH inspired by fruit fly brain

License

Notifications You must be signed in to change notification settings

dataplayer12/Fly-LSH

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

33 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Build status

Paper

Code accompanying our paper Improving Similarity Search with High-dimensional Locality sensitive hashing

Summary

We make three important contributions:

  1. We present a new data independent approximate nearest neighbor (ANN) search algorithm inspired by the fruit fly olfactory circuit introduced by Dasgupta et. al.. Named DenseFly, the proposed algorithm performs significantly better than several existing data independent algorithms on six benchmark datasets. (figures 2 and 3)
  2. We prove several theoretical results about the original FlyHash as well as the proposed DenseFly algorithms. In particular, we show that FlyHash preserves rank similarity under any Lp norm and that DenseFly approximates a SimHash in very high dimensions at a much lower computational cost. (Lemmas 1 and 2)
  3. We develop a multi-probe binning scheme for FlyHash and DenseFly algorithms, which are indispensable for practical applications of ANN algorithms. Remarkably, the proposed multi-probe binning scheme does not require additional computation over and above those used to create the high dimensional Fly or DenseFly hashes. Thus, the multi-probe versions of FlyHash and DenseFly result in a significant increase in mAP scores for a given query time. (figure 4)

Code

The code for all the new algorithms described are present in one large file. Helper scripts to compare different algorithms will be added soon.

Releases

No releases published

Packages

No packages published

Languages