Practical Hash Functions For Similarity Estimation And Dimensionality Reduction

Abstract

Hashing is a basic tool for dimensionality reduction employed in several aspects of machine learning. However, the perfomance analysis is often carried out under the abstract assumption that a truly random unit cost hash function is used, without concern for which concrete hash function is employed. The concrete hash function may work fine on sufficiently random input. The question is if it can be trusted in the real world when faced with more structured input. In this paper we focus on two prominent applications of hashing, namely similarity estimation with the one permutation hashing (OPH) scheme of Li et al. [NIPS'12] and feature hashing (FH) of Weinberger et al. [ICML'09], both of which have found numerous applications, i.e. in approximate near-neighbour search with LSH and large-scale classification with SVM. We consider mixed tabulation hashing of Dahlgaard et al.[FOCS'15] which was proved to perform like a truly random hash function in many applications, including OPH. Here

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keydahlgaard2017practical

Related papers

• Robust Hashing For Multi-view Data: Jointly Learning Low-rank Kernelized Similarity Consensus And Hash Functions (2016)11.19
• Improving Similarity Search With High-dimensional Locality-sensitive Hashing (2018)0.00
• Sharing Hash Codes For Multiple Purposes (2016)0.00
• Probminhash -- A Class Of Locality-sensitive Hash Algorithms For The (probability) Jaccard Similarity (2019)9.92
• Distance-sensitive Hashing (2017)8.82
• LOH And Behold: Web-scale Visual Search, Recommendation And Clustering Using Locally Optimized Hashing (2016)4.52
• Learning To Hash With Semantic Similarity Metrics And Empirical KL Divergence (2020)0.00
• Hierarchical Locality Sensitive Hashing For Structured Data: A Survey (2022)0.00