Spectral LPM: an optimal locality-preserving mapping using the spectral (not fractal) order

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. The idea behind a locality-preserving mapping is to map points that are nearby in the multidimensional space into points that are...

Full description

Saved in:
Bibliographic Details
Main Authors: Mokbel, M.F., Aref, W.G., Grama, A.
Format: Conference Proceeding
Language:English
Subjects:
Clustering algorithms
Cranes
Data engineering
Eigenvalues and eigenfunctions
Fractals
Geographic Information Systems
Hilbert space
Multidimensional systems
Partitioning algorithms
Spatial databases
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. The idea behind a locality-preserving mapping is to map points that are nearby in the multidimensional space into points that are nearby in the one-dimensional space. We argue against the use of fractals in locality-preserving mapping algorithms, and present examples with experimental evidence to show why fractals produce poor locality-preserving mappings. In addition, we propose an optimal locality-preserving mapping algorithm, termed the spectral locality-preserving mapping algorithm (Spectral LPM, for short), that makes use of the spectrum of the multidimensional space. We give a mathematical proof for the optimality of Spectral LPM, and also demonstrate its practical use.
DOI:10.1109/ICDE.2003.1260840