A pinboard by
Sepehr Eghbali

PhD candidate, University of Waterloo


Our goal is to find the points in a database that are the closest to a given query point.

Many of the current large-scale datasets consist of high dimension vectors. For example, in multimedia applications, each image can be described by the features of various aspects of visual content like color, shape and objects. In addition to the huge volume of current datasets, the velocity of arrival (e.g. stream of video) and the large variety of heterogeneity 1(e.g. image, text, audio) of current datasets are unprecedented. In the context of retrieval algorithms for massive dataset, the most computationally demanding part often consists of searching for the most similar matches to the one or a set of query vectors. This task, referred to as the Nearest Neighbour (NN) matching, has a wide range of applications in many fields such as data mining, information retrieval, machine learning and computer vision. The simplest exact solution is to compare each query vector with all items in the dataset. However, this approach is not scalable for large-scale datasets. Applying the traditional exact search techniques on today’s large scale datasets can incur intolerable space and computational costs. Tackling the aforementioned problems have set the goals of our research. We aim at solving the approximate nearest neighbour problem with efficient time and space complexity such that even a single machine can perform large-scale nearest neighbours search. However, this comes at the cost of allowing the answers to be approximate rather than exact which is shown to be enough and useful in many applications.


Spherical hashing: binary code embedding with hyperspheres.

Abstract: Many binary code embedding schemes have been actively studied recently, since they can provide efficient similarity search, and compact data representations suitable for handling large scale image databases. Existing binary code embedding techniques encode high-dimensional data by using hyperplane-based hashing functions. In this paper we propose a novel hypersphere-based hashing function, spherical hashing, to map more spatially coherent data points into a binary code compared to hyperplane-based hashing functions. We also propose a new binary code distance function, spherical Hamming distance, tailored for our hypersphere-based binary coding scheme, and design an efficient iterative optimization process to achieve both balanced partitioning for each hash function and independence between hashing functions. Furthermore, we generalize spherical hashing to support various similarity measures defined by kernel functions. Our extensive experiments show that our spherical hashing technique significantly outperforms state-of-the-art techniques based on hyperplanes across various benchmarks with sizes ranging from one to 75 million of GIST, BoW and VLAD descriptors. The performance gains are consistent and large, up to 100 percent improvements over the second best method among tested methods. These results confirm the unique merits of using hyperspheres to encode proximity regions in high-dimensional spaces. Finally, our method is intuitive and easy to implement.

Pub.: 07 Oct '15, Pinned: 24 Aug '17