Research Projects

This proposal focuses on the similarity search problem formally known as the approximate nearest neighbour search (c-ANN) problem. Given a data set of n points and a query point q, in the c-ANN problem, the task is to return a point within some constant (c more than 1) times the distance of query q to its actual nearest neighbour. This problem is a fundamental subroutine in several data science applications such as building recommendation engines, duplicate detection, clustering, audio/video fingerprinting, gene expression similarity identification, genome-wide association study, frequent itemset mining, etc. The c-ANN problem has been well-studied in literature, and several practical algorithms are known. One of the classical algorithms for this problem is due to Indyk and Motwani, popularly known as ``locality sensitive hashing (LSH)", which gives a provable sublinear time algorithm for the c-ANN problem. LSH functions have been studied for different similarity/distance measures, such as cosine similarity, Euclidean distance, hamming distance, and Jaccard similarity. In this proposal, we focus on LSH for real-valued vectors over Euclidean distance, cosine similarity and inner product. We note that the existing LSH algorithms don’t exploit the underlying distributional properties that exist in several real-life data matrices. One such important property is that the rank of real-life data matrices is small. Furthermore, several real-life data matrices are sparse - the number of non-zero entries is much smaller in comparison to the zero entries. We believe that such distributional parties can be exploited carefully and can potentially lead to time/space efficient and accurate LSH algorithms. This is the proposal's main objective, and we aim to design such LSH algorithms, theoretically analyze them for correctness and efficiency, and empirically validate them on several real-life datasets. LSH algorithm can be viewed as projecting the input data matrix on a random projection matrix (whose entries are sampled from Gaussian distribution) and then discretizing the entries (called hashcodes) of the resultant product matrix. For a pair of data points, the probability that their hash code is the same is monotonic to their pairwise similarity. Our primary key approach is to propose improved construction of random projection matrices that exploit the distributional properties of input matrices. This can be potentially achieved by adapting improved variants of random projection matrices such as fast JL transform, circulant, and Toeplitz matrices and tailoring them with the distributional properties of the input matrix. Building on this random projection matrix, improved LSH hash functions can be designed. LSH algorithms have been crucially used in several data science applications. Our proposed algorithm will significantly benefit all these applications by reducing their computational complexity while simultaneously offering better accuracy.