Space-Filling Curves for Query Processing


Given a query Q, a one-dimensional index structure I(e.g., B-tree), and a set of D dimensional points, a space-filling curve S is used to map the D dimensional points into a set of one-dimensional points that can be indexed through I for an efficient execution of query Q. The main idea is that space-filling curves are used as a way of mapping the multi-dimensional space into the one-dimensional space such that existing onedimensional query processing and indexing techniques can be applied.


Distance-preserving, mapping, Locality-preserving mapping, Multi-dimensional mapping, Linearization

Date of this Version



Encyclopedia of Database Systems , 2009, Part 19, 2675-2680