On query processing and optimality using spectral locality-preserving mappings

Mohamed F. Mokbel, Walid G. Aref

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

A locality-preserving mapping (LPM) from the multi-dimensional space into the one-dimensional space is beneficial for many applications (e.g., range queries, nearest-neighbor queries, clustering, and declustering) when multi-dimensional data is placed into one-dimensional storage (e.g., the disk). The idea behind a locality-preserving mapping is to map points that are nearby in the multi-dimensional space into points that are nearby in the one-dimensional space. For the past two decades, fractals (e.g., the Hilbert and Peano space-filling curves) have been considered the natural method for providing a locality-preserving mapping to support efficient answer for range queries and similarity search queries. In this paper, we go beyond the idea of fractals. Instead, we investigate a locality-preserving mapping algorithm (The Spectral LPM) that uses the spectrum of the multi-dimensional space. This paper provably demonstrates how Spectral LPM provides a globally optimal mapping from the multi-dimensional space to the one-dimensional space, and hence outperforms fractals. As an application, in the context of range queries and nearest-neighbor queries, empirical results of the performance of Spectral LPM validate our analysis in comparison with Peano, Hilbert, and Gray fractal mappings.

Original languageEnglish (US)
Pages (from-to)102-121
Number of pages20
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2750
StatePublished - Dec 1 2003

Fingerprint Dive into the research topics of 'On query processing and optimality using spectral locality-preserving mappings'. Together they form a unique fingerprint.

Cite this