@inproceedings{4d3d97ee27cc4431a1859dd36a1627fa,
title = "Onion curve: A space filling curve with near-optimal clustering",
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 mapping from higher dimensions to a single dimension. We present the onion curve, an SFC whose clustering performance is provably close to the optimal for cube and near-cube shaped query sets. 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 clustering performance is critical to the efficiency of multi-dimensional indexes based on the SFC, the onion curve can deliver improved performance for data structures for multi-dimensional data.",
keywords = "Indexing, Query Processing, and Optimization",
author = "Pan Xu and Cuong Nguyen and Srikanta Tirthapura",
note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 34th IEEE International Conference on Data Engineering, ICDE 2018 ; Conference date: 16-04-2018 Through 19-04-2018",
year = "2018",
month = oct,
day = "24",
doi = "10.1109/ICDE.2018.00119",
language = "English (US)",
series = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "1216--1219",
booktitle = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",
address = "United States",
}