Dimensionality reduction for dimension-specific search

Zi Huang, Heng Tao Shen, Xiaofang Zhou, Dawei Song, Stefan M. Rüger

Abstract

Dimensionality reduction plays an important role in efficient similarity search, which is often based on k-nearest neighbor (k-NN) queries over a high-dimensional feature space. In this paper, we introduce a novel type of k-NN query, namely conditional k-NN (ck-NN), which considers dimension-specific constraint in addition to the inter-point distances. However, existing dimensionality reduction methods are not applicable to this new type of queries. We propose a novel Mean-Std (standard deviation) guided Dimensionality Reduction (MSDR) to support a pruning based efficient ck-NN query processing strategy. Our preliminary experimental results on 3D protein structure data demonstrate that the MSDR method is promising.
BibTeX
@inproceedings{huang2007dimensionality,
  author = {Zi Huang and Heng Tao Shen and Xiaofang Zhou and Dawei Song and Stefan M. Rüger},
  title = {{Dimensionality reduction for dimension-specific search}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2007},
  doi = {10.1145/1277741.1277940},
}

Loading related content...

Figure