Campus Units

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

Document Type

Conference Proceeding


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

Publication Version

Accepted Manuscript

Link to Published Version

Publication Date


Journal or Book Title

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

First Page


Last Page




Conference Date

May 21-25, 2012


Shanghai, China


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.


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.


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




File Format


Published Version


Article Location