University of Minnesota
University Relations

Minnesota Supercomputing Institute

Log out of MyMSI

Research Abstracts Online
January - December 2011

Main TOC ...... Next Abstract

University of Minnesota Twin Cities
College of Science and Engineering
Department of Computer Science and Engineering

PI: Nikolaos P. Papanikolopoulos

Approximate Nearest Neighbors in High-Dimensional Feature Spaces

Nearest Neighbors (NN) is a fundamental operation in many areas of scientific computing, including computer vision, machine learning, robotics and data mining. It is well known that as the dimension of the data increases, the NN task becomes computationally challenging. These researchers are developing a novel NN algorithm for image data. Their algorithm is based on the paradigms of compressive sensing, specifically the dictionary learning facet: exploiting the underlying sparsity in the data. They use a novel tuple representation: Subspace Combination Tuple, in which the data vectors are mapped to tuples of non-zero active basis elements in the learned dictionary. This representation means the data can be indexed via a hash table, thus making NN fast and accurate. Further, they are developing a Multi-Regularization Sparse Coding algorithm to make the hashing robust to image distortions.

Group Member

Anoop Cherian, Graduate Student