Campus Units

Electrical and Computer Engineering, Computer Science, Industrial and Manufacturing Systems Engineering

Document Type

Conference Proceeding

Conference

2012 IEEE 26th International Parallel & Distributed Processing Symposium (IPDPS)

Publication Version

Accepted Manuscript

Link to Published Version

https://doi.org/10.1109/IPDPS.2012.118

Publication Date

2012

Journal or Book Title

2012 IEEE 26th International Parallel & Distributed Processing Symposium (IPDPS)

First Page

1295

Last Page

1305

DOI

10.1109/IPDPS.2012.118

Conference Date

May 21-25, 2012

City

Shanghai, China

Abstract

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, which measure the extent to which an SFC preserves proximity. We first show a powerful negative result, that there is an inherent lower bound on the stretch of any SFC. We then show that the stretch of the commonly used Z curve is within a factor of 1.5 from the optimal, irrespective of the number of dimensions. Further we show that a very simple SFC also achieves the same stretch as the Z curve. Our results apply to SFCs in any dimension d such that d is a constant.

Comments

This is a manuscript of a proceeding published as Xu, Pan, and Srikanta Tirthapura. "A lower bound on proximity preservation by space filling curves." 2012 IEEE 26th International Parallel & Distributed Processing Symposium (IPDPS), (2012):1295-1305. DOI: 10.1109/IPDPS.2012.118. Posted with permission.

Rights

Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Copyright Owner

IEEE

Language

en

File Format

application/pdf

Published Version

Share

Article Location

 
COinS