  Data similarity (or distance) computation is a fundamental research topic
which fosters a variety of similarity-based machine learning and data mining
applications. In big data analytics, it is impractical to compute the exact
similarity of data instances due to high computational cost. To this end, the
Locality Sensitive Hashing (LSH) technique has been proposed to provide
accurate estimators for various similarity measures between sets or vectors in
an efficient manner without the learning process. Structured data (e.g.,
sequences, trees and graphs), which are composed of elements and relations
between the elements, are commonly seen in the real world, but the traditional
LSH algorithms cannot preserve the structure information represented as
relations between elements. In order to conquer the issue, researchers have
been devoted to the family of the hierarchical LSH algorithms. In this paper,
we explore the present progress of the research into hierarchical LSH from the
following perspectives: 1) Data structures, where we review various
hierarchical LSH algorithms for three typical data structures and uncover their
inherent connections; 2) Applications, where we review the hierarchical LSH
algorithms in multiple application scenarios; 3) Challenges, where we discuss
some potential challenges as future directions.
