Repository files navigation

Code accompanying ourpaperImproving Similarity Search with High-dimensional Locality sensitive hashing

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 byDasgupta et. al.. NamedDenseFly, 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 originalFlyHash as well as the proposedDenseFly algorithms. In particular, we show thatFlyHash preserves rank similarity under anyLp norm and thatDenseFly approximates aSimHash in very high dimensions at a much lower computational cost. (Lemmas 1 and 2)
3. We develop a multi-probe binning scheme forFlyHash andDenseFly 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 dimensionalFly orDenseFly hashes. Thus, the multi-probe versions ofFlyHash andDenseFly result in a significant increase in mAP scores for a given query time. (figure 4)

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