Title

Subspace Projection: A Unified Framework For A Class Of Partition-Based Dimension Reduction Techniques

Keywords

Dimension partition; Dimensionality reduction; Multidimensional indexing; Similarity search; SubSpace Projection

Abstract

Similarity search in high dimensional space is a nontrivial problem due to the so-called curse of dimensionality. Recent techniques such as Piecewise Aggregate Approximation (PAA), Segmented Means (SMEAN) and Mean-Standard deviation (MS) prove to be very effective in reducing data dimensionality by partitioning dimensions into subsets and extracting aggregate values from each dimension subset. These partition-based techniques have many advantages including very efficient multi-phased approximation while being simple to implement. They, however, are not adaptive to the different characteristics of data in diverse applications. We propose SubSpace Projection (SSP) as a unified framework for these partition-based techniques. SSP projects data onto subspaces and computes a fixed number of salient features with respect to a reference vector. A study of the relationships between query selectivity and the corresponding space partitioning schemes uncovers indicators that can be used to predict the performance of the partitioning configuration. Accordingly, we design a greedy algorithm to efficiently determine a good partitioning of the data dimensions. The results of our extensive experiments indicate that the proposed method consistently outperforms state-of-the-art techniques. © 2008 Elsevier Inc. All rights reserved.

Publication Date

4-15-2009

Publication Title

Information Sciences

Volume

179

Issue

9

Number of Pages

1234-1248

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.ins.2008.12.004

Socpus ID

60349131432 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/60349131432

This document is currently not available here.

Share

COinS