Distributed frameworks are gaining increasingly widespread use in
applications that process large amounts of data. One important example
application is large scale similarity search, for which Locality Sensitive
Hashing (LSH) has emerged as the method of choice, specially when the data is
high-dimensional. At its core, LSH is based on hashing the data points to a
number of buckets such that similar points are more likely to map to the same
buckets. To guarantee high search quality, the LSH scheme needs a rather large
number of hash tables. This entails a large space requirement, and in the
distributed setting, with each query requiring a network call per hash bucket
look up, this also entails a big network load. The Entropy LSH scheme proposed
by Panigrahy significantly reduces the number of required hash tables by
looking up a number of query offsets in addition to the query itself. While
this improves the LSH space requirement, it does not help with (and in fact
worsens) the search network efficiency, as now each query offset requires a
network call. In this paper, focusing on the Euclidian space under $l_2$ norm
and building up on Entropy LSH, we propose the distributed Layered LSH scheme,
and prove that it exponentially decreases the network cost, while maintaining a
good load balance between different machines. Our experiments also verify that
our scheme results in a significant network traffic reduction that brings about
large runtime improvement in real world applications.

本文提出了基于熵局部敏感哈希的分布式分层哈希方案，能够显著减少网络流量，提高实际应用程序的运行效率。