TY - GEN

T1 - A lower bound on proximity preservation by space filling curves

AU - Xu, Pan

AU - Tirthapura, Srikanta

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - lower bound

KW - proximity

KW - space filling curve

KW - stretch

UR - http://www.scopus.com/inward/record.url?scp=84866868043&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84866868043&partnerID=8YFLogxK

U2 - 10.1109/IPDPS.2012.118

DO - 10.1109/IPDPS.2012.118

M3 - Conference contribution

AN - SCOPUS:84866868043

SN - 9780769546759

T3 - Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium, IPDPS 2012

SP - 1295

EP - 1305

BT - Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium, IPDPS 2012

T2 - 2012 IEEE 26th International Parallel and Distributed Processing Symposium, IPDPS 2012

Y2 - 21 May 2012 through 25 May 2012

ER -