Campus Units
Computer Science, Electrical and Computer Engineering
Document Type
Article
Publication Date
2018
Journal or Book Title
arXiv
Abstract
Space filling curves (SFCs) are widely used in the design of indexes for spatial and temporal data. Clustering is a key metric for an SFC, that measures how well the curve preserves locality in moving from higher dimensions to a single dimension. We present the onion curve, an SFC whose clustering performance is provably close to optimal for cube and nearcube shaped query sets, irrespective of the side length of the query. We show that in contrast, the clustering performance of the widely used Hilbert curve can be far from optimal, even for cube-shaped queries. Since the clustering performance of an SFC is critical to the efficiency of multi-dimensional indexes based on the SFC, the onion curve can deliver improved performance for data structures involving multi-dimensional data.
Language
en
File Format
application/pdf
Recommended Citation
Xu, Pan; Nguyen, Cuong; and Tirthapura, Srikanta, "Onion Curve: A Space Filling Curve with Near-Optimal Clustering" (2018). Electrical and Computer Engineering Publications. 174.
https://lib.dr.iastate.edu/ece_pubs/174
Comments
This is a manuscript of the article Xu, Pan, Cuong Nguyen, and Srikanta Tirthapura. "Onion Curve: A Space Filling Curve with Near-Optimal Clustering." arXiv preprint arXiv:1801.07399 (2018). Posted with permission.