Abstract

Approximate Nearest Neighbor (ANN) methods such as Lo- cality Sensitive Hashing, Semantic Hashing, and Spectral Hashing, pro- vide computationally efficient procedures for finding ob jects similar to a query ob ject in large datasets. These methods have been successfully applied to search web-scale datasets that can contain millions of images. Unfortunately, the key assumption in these procedures is that ob jects in the dataset lie in a Euclidean space. This assumption is not always valid and poses a challenge for several computer vision applications where data commonly lies in complex non-Euclidean manifolds. In particular, dynamic data such as human activities are commonly represented as distributions over bags of video words or as dynamical systems. In this paper, we propose two new algorithms that extend Spectral Hashing to non-Euclidean spaces. The first method considers the Riemannian ge- ometry of the manifold and performs Spectral Hashing in the tangent space of the manifold at several points. The second method divides the data into subsets and takes advantage of the kernel trick to perform non- Euclidean Spectral Hashing. For a data set of N samples the proposed methods are able to retrieve similar ob jects in as low as O(K ) time com- plexity, where K is the number of clusters in the data. Since K (cid:2) N , our methods are extremely efficient. We test and evaluate our methods on synthetic data generated from the Unit Hypersphere and the Grassmann manifold. Finally, we show promising results on a human action database.