VDeH: Voronoi Diagram Encoded Hashing for Effective and Efficient Similarity Search, Applicable to Different Types of Databases

Abstract

The goal of learning to hash (L2H) is to derive data-dependent hash functions from a given data distribution to map data from the input space to a binary coding space. Despite the success of L2H, two observations have cast doubt on the source of its power, i.e., learning. First, a recent study shows that a version of locality-sensitive hashing without learning can achieve comparable accuracy to L2H methods with less time cost. Second, existing L2H methods are constrained to only three types of hash functions: thresholding, hyperspheres, and hyperplanes. In this paper, we identify Voronoi diagrams as a superior alternative for hashing, as they naturally possess three key properties, i.e., full space coverage, entropy maximization, and bit independence, that existing methods must acquire through complex learning. This insight leads us to propose Voronoi Diagram Encoded Hashing (VDeH), a simple and efficient no-learning approach. VDeH constructs hash functions directly from data-driven Voronoi partitions and leverages a simple encoding scheme to generate mutually independent binary bits. The no-learning and data-dependent nature of VDeH makes it an ideal and highly effective plug-and-play component for similarity search, not only in standard vector databases but also for complex data objects such as trajectories and graphs. For complex data objects, VDeH enables a straightforward two-stage process: an appropriate embedding method first maps the data into a vector space, after which VDeH efficiently generates binary hash codes to accelerate retrieval. Comprehensive experiments on multiple large-scale public benchmarks (consisting of databases of vectors, graphs, and trajectories) demonstrate that VDeH significantly outperforms state-of-the-art hashing methods in both retrieval accuracy and computational efficiency, establishing it as a versatile, efficient, and high-performance solution for similarity search across diverse data domains.