More Like this

1. Learning to Hash Robustly, Guaranteed

   Andoni, Alexandr; Beaglehole, Daniel (July 2022, International Conference on Machine Learning)

   The indexing algorithms for the high-dimensional nearest neighbor search (NNS) with the best worst-case guarantees are based on the randomized Locality Sensitive Hashing (LSH), and its derivatives. In practice, many heuristic approaches exist to "learn" the best indexing method in order to speed-up NNS, crucially adapting to the structure of the given dataset. Oftentimes, these heuristics outperform the LSH-based algorithms on real datasets, but, almost always, come at the cost of losing the guarantees of either correctness or robust performance on adversarial queries, or apply to datasets with an assumed extra structure/model. In this paper, we design an NNS algorithm for the Hamming space that has worst-case guarantees essentially matching that of theoretical algorithms, while optimizing the hashing to the structure of the dataset (think instance-optimal algorithms) for performance on the minimum-performing query. We evaluate the algorithm's ability to optimize for a given dataset both theoretically and practically. On the theoretical side, we exhibit a natural setting (dataset model) where our algorithm is much better than the standard theoretical one. On the practical side, we run experiments that show that our algorithm has a 1.8x and 2.1x better recall on the worst-performing queries to the MNIST and ImageNet datasets. https://arxiv.org/abs/2108.05433 

   more » « less
2. Learning to Hash Robustly, Guaranteed

   Andoni, Alexandr; Beaglehole, Daniel (January 2022, Proceedings of the 39th International Conference on Machine Learning)
3. History-Independent Concurrent Hash Tables

   https://doi.org/10.1145/3717823.3718283  

   Attiya, Hagit; Bender, Michael A; Farach-Colton, Martín; Oshman, Rotem; Schiller, Noa (June 2025, ACM)
4. Can Learned Models Replace Hash Functions?

   https://doi.org/10.14778/3570690.3570702  

   Sabek, Ibrahim; Vaidya, Kapil; Horn, Dominik; Kipf, Andreas; Mitzenmacher, Michael; Kraska, Tim (November 2022, Proceedings of the VLDB Endowment)

   Hashing is a fundamental operation in database management, playing a key role in the implementation of numerous core database data structures and algorithms. Traditional hash functions aim to mimic a function that maps a key to a random value, which can result in collisions, where multiple keys are mapped to the same value. There are many well-known schemes like chaining, probing, and cuckoo hashing to handle collisions. In this work, we aim to study if using learned models instead of traditional hash functions can reduce collisions and whether such a reduction translates to improved performance, particularly for indexing and joins. We show that learned models reduce collisions in some cases, which depend on how the data is distributed. To evaluate the effectiveness of learned models as hash function, we test them with bucket chaining, linear probing, and cuckoo hash tables. We find that learned models can (1) yield a 1.4x lower probe latency, and (2) reduce the non-partitioned hash join runtime with 28% over the next best baseline for certain datasets. On the other hand, if the data distribution is not suitable, we either do not see gains or see worse performance. In summary, we find that learned models can indeed outperform hash functions, but only for certain data distributions. 

   more » « less
5. Analyzing and Implementing GPU Hash Tables

   https://doi.org/10.1137/1.9781611977578.ch3  

   Awad, Muhammad A.; Ashkiani, Saman; Porumbescu, Serban D.; Farach-Colton, Martín; Owens, John D. (January 2023, SIAM Symposium on Algorithmic Principles of Computer Systems)

   We revisit the problem of building static hash tables on the GPU and present an efficient implementation of bucketed hash tables. By decoupling the probing scheme from the hash table in-memory representation, we offer an implementation where the number of probes and the bucket size are the only factors limiting performance. Our analysis sweeps through the hash table parameter space for two probing schemes: cuckoo and iceberg hashing. We show that a bucketed cuckoo hash table (BCHT) that uses three hash functions outperforms alternative methods that use iceberg hashing and a cuckoo hash table that uses a bucket size of one. At load factors as high as 0.99, BCHT enjoys an average probe count of 1.43 during insertion. Using three hash functions only, positive and negative queries require at most 1.39 and 2.8 average probes per key, respectively. 

   more » « less