Forest-wise DSH: A Universal Hash Design for Discrete Probability Distributions

EasyChair Preprint 1500

Abstract

In this paper, we consider the problem of classification of $M$ high dimensional queries $y^1,\cdots,y^M\in \mathcal{B}^S$ to $N$ high dimensional classes $x^1,\cdots,x^N\in \mathcal{A}^S$ where $\mathcal{A}$ and $\mathcal{B}$ are discrete alphabets and the probabilistic model that relates data to the classes $\mathbb{P}(x,y)$ is known. This problem has applications in various fields including the database search problem in mass spectrometry. The problem is analogous to the nearest neighbor search problem, where the goal is to find the data point in a database that is the most similar to a query point. The state of the art method for solving an approximate version of the nearest neighbor search problem in high dimensions is locality sensitive hashing (LSH). LSH is based on designing hash functions that map near points to the same buckets with a probability higher than random (far) points. To solve our high dimensional classification problem, we introduce distribution sensitive hashes that map jointly generated pairs $(x,y)\sim \mathbb{P}$ to the same bucket with probability higher than random pairs $x\sim {\mathbb{P}}^x$ and $y\sim {\mathbb{P}}^y$, where $ {\mathbb{P}}^x$ and ${\mathbb{P}}^y$ are the marginal probability distributions of $\mathbb{P}$. We design distribution sensitive hashes using a forest of decision trees and we show that the complexity of search grows with $O(N^{\lambda^*({\mathbb{P}})})$ where $\lambda^*({\mathbb{P}})$ is expressed in an analytical form. We further show that the proposed hashes perform faster than LSH-hamming and Minhash for various probability distributions, in both theory and simulations. Finally, we apply our method to the spectral library search problem in mass spectrometry, and show that it is an order of magnitude faster than the state of the art methods.

Keyphrases: Approximate Nearest Neighbor Search, Forest of decision trees, High dimensional data and classes, Locality Sensitive Hashing

@booklet{EasyChair:1500,
  author    = {Arash Gholamidavoodi and Sean Chang and Hyun Gon Yoo and Mihir Mongia and Hosein Mohimani},
  title     = {Forest-wise DSH: A Universal Hash Design for Discrete Probability Distributions},
  howpublished = {EasyChair Preprint 1500},
  year      = {EasyChair, 2019}}