DET-LSH

Category: Research Papers & Surveys
Brand: arXiv
Source: Paper PDF
Code & Artifacts: GitHub – WeiJiuQi/DET-LSH

Overview

DET-LSH is a locality-sensitive hashing (LSH) scheme designed for approximate nearest neighbor (ANN) search in high-dimensional Euclidean spaces. It introduces a Dynamic Encoding Tree (DE-Tree) structure to accelerate both indexing and querying, with a focus on improving indexing efficiency—an aspect often underemphasized in traditional LSH-based methods.

Key Concepts

• Approximate Nearest Neighbor (ANN) Search: Targets efficient retrieval of points whose distances to a query are within a factor (c) of the true nearest neighbor distance in high-dimensional spaces.
• Locality-Sensitive Hashing (LSH): A hashing framework that increases collision probability for nearby points to enable sublinear-time ANN search.

Features

Dynamic Encoding Tree (DE-Tree)

• Encoding-based index tree designed specifically for ANN tasks.
• Focuses on improving indexing efficiency rather than only query-time optimizations.
• Avoids directly partitioning the raw multi-dimensional space, mitigating performance degradation as dimensionality increases.
• Supports efficient range queries based on Euclidean distance.

DET-LSH Scheme

• Builds multiple independent DE-Tree indexes over the data.
• Employs a novel query strategy that:
  • Performs range queries across multiple DE-Trees.
  • Reduces the probability of missing exact nearest neighbor points, thereby improving recall and overall query accuracy.
• Designed as a general LSH-based framework that can be used to inspire or implement vector indexing components in vector databases.

Theoretical Properties

• Provides probabilistic guarantees on query accuracy, in line with classical LSH theory.
• Formally analyzed within the approximate nearest neighbor ((c)-ANN) framework for Euclidean distance.

Performance Characteristics

• Targets high-dimensional Euclidean spaces where the curse of dimensionality makes exact NN search impractical.
• Experimental results on real-world datasets (as reported in the paper):
  • Up to 6× speedup in indexing time compared to state-of-the-art LSH-based methods.
  • Up to .