Open Access. Powered by Scholars. Published by Universities.®

Operations Research, Systems Engineering and Industrial Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

Series

Computer Sciences

Electrical and Computer Engineering Conference Papers, Posters and Presentations

Articles 1 - 1 of 1

Full-Text Articles in Operations Research, Systems Engineering and Industrial Engineering

A Lower Bound On Proximity Preservation By Space Filling Curves, Pan Xu, Srikanta Tirthapura Jan 2012

A Lower Bound On Proximity Preservation By Space Filling Curves, Pan Xu, Srikanta Tirthapura

Electrical and Computer Engineering Conference Papers, Posters and Presentations

Abstract: A space filling curve (SFC) is a proximity preserving mapping from a high dimensional space to a single dimensional space. SFCs have been used extensively in dealing with multi-dimensional data in parallel computing, scientific computing, and databases. The general goal of an SFC is that points that are close to each other in high-dimensional space are also close to each other in the single dimensional space. While SFCs have been used widely, the extent to which proximity can be preserved by an SFC is not precisely understood yet. We consider natural metrics, including the "nearest-neighbor stretch" of an SFC ...