Onion curve: A space filling curve with near-optimal clustering

Pan Xu, Cuong Nguyen, Srikanta Tirthapura

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1216-1219
Number of pages4
ISBN (Electronic)9781538655207
DOIs
StatePublished - Oct 24 2018
Externally publishedYes
Event34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, France
Duration: Apr 16 2018Apr 19 2018

Publication series

NameProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018

Other

Other34th IEEE International Conference on Data Engineering, ICDE 2018
Country/TerritoryFrance
CityParis
Period4/16/184/19/18

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Information Systems and Management
  • Hardware and Architecture

Keywords

  • Indexing
  • Query Processing
  • and Optimization

Fingerprint

Dive into the research topics of 'Onion curve: A space filling curve with near-optimal clustering'. Together they form a unique fingerprint.

Cite this