Abstract
Traditional Locality Sensitive Hashing (LSH) is a cornerstone of efficient similarity search, yet it typically treats data as unstructured sets or vectors. This survey explores the evolution of Hierarchical LSH (HLSH), a paradigm designed to preserve the complex dependencies inherent in sequences, trees, and graphs. By employing recursive or iterative sketching, HLSH provides a computationally efficient, learning-free alternative to deep learning models, maintaining scalability for web-scale datasets while offering theoretical guarantees.
Introduction
In the era of "Big Data," calculating exact similarity between billions of data points is computationally prohibitive. LSH addressed this for flat vectors by using randomized functions to map similar items to the same "buckets" with high probability. However, real-world data is inherently structured: genomic sequences have order, documents have hierarchical chapters, and social networks are defined by complex graph topologies. Traditional LSH "flattens" this data, discarding vital structural context. While deep learning approaches like Graph Neural Networks (GNNs) can capture these relationships, they require massive labeled datasets and significant GPU resources. This survey examines how HLSH bridges this gap by preserving structural information with the speed and scalability of randomized hashing.
Methodological Framework
The core innovation of Hierarchical LSH is the use of recursive or iterative sketching along relational links. These methods are categorized by the data structures they target:
- Trees: Information is propagated from leaf nodes to the root. Each parent node’s hash is a function of its children’s hashes, effectively summarizing the entire subtree.
- Sequences: Methods include parallel approaches using $q$-shingling for local dependencies and serial/streaming approaches that update state incrementally, often incorporating forgetting mechanisms to handle concept drift.
- Graphs: A generalized LSH-based Message Passing framework is employed. Similar to GNNs, it uses MSG (transform), AGG (aggregate), and UPD (update) operations, but instantiates them with fixed, randomized LSH functions like MinHash or SimHash instead of learned weights.
Applications and Real-World Datasets
HLSH has been applied across diverse domains where structure is paramount. Key application areas include document analysis (hierarchical representations of chapters and paragraphs), social network analysis (citation and friendship graphs), bioinformatics (gene sequences and molecular graphs), and healthcare (physiological time-series data).
Key Insights and Performance
HLSH offers several distinct advantages over both traditional hashing and deep learning:
- Learning-Free Efficiency: HLSH requires no training phase, making it significantly faster than neural networks while remaining more expressive than flat LSH. Most algorithms achieve linear or near-linear time complexity ($O(|V|)$ or $O(|E|)$).
- Theoretical Rigor: Unlike "black-box" neural models, many HLSH algorithms provide unbiased estimators for specific similarity measures (e.g., Jaccard or Cosine similarity) with provable error bounds.
- Structural Universality: Sequences and graphs can often be decomposed into tree-like hierarchies, positioning tree-based recursive hashing as a universal building block for structured data analysis.
- Competitive Accuracy: Implementations like the KATH algorithm achieve performance competitive with advanced graph kernels (e.g., Weisfeiler-Lehman) but with drastically reduced computation and storage requirements.
Conclusion and Future Directions
While HLSH provides a powerful tool for large-scale structured data, challenges remain in improving the explainability of hash codes and handling heterogeneous data types (e.g., graphs with multiple node and edge types). A promising future direction involves using LSH not as a replacement for neural networks, but as an acceleration mechanism—for example, by using LSH to sample important parameters or neurons during the training of Large Language Models (LLMs).
Summary updated