Spatial Partitioning using Hilbert Space Filling Curve for Spatial Query Optimization


The KIPS Transactions:PartD, Vol. 11, No. 1, pp. 23-30, Feb. 2004
10.3745/KIPSTD.2004.11.1.23,   PDF Download:

Abstract

In order to approximate the spatial query result size we partition the input rectangles into subsets and estimate the query result size based on the partioned spatial area. In this paper we examine query result size estimation in skewed data. We examine the existing spatial partitioning techniques such as equi-area and equi-count partitioning, which are analogous to the equi-width and equi-height histograms used in relational databases, and examine the other partitioning techniques based on spatial indexing. In this paper we propose a new spatial partitioning technique based on the Hillbert space filling curve. We present a detailed experimental evaluation comparing the proposed technique and the existing techniques using synthetic as well as real-life datasets. The experiments showed that the proposed partitioning technique based on the Hillbert space filling curve achieves better query result size estimation than the existing techniques for space query size, bucket numbers, skewed data, and spatial data size.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
H. H. Gyu and K. H. Gug, "Spatial Partitioning using Hilbert Space Filling Curve for Spatial Query Optimization," The KIPS Transactions:PartD, vol. 11, no. 1, pp. 23-30, 2004. DOI: 10.3745/KIPSTD.2004.11.1.23.

[ACM Style]
Hwang Hwan Gyu and Kim Hyeon Gug. 2004. Spatial Partitioning using Hilbert Space Filling Curve for Spatial Query Optimization. The KIPS Transactions:PartD, 11, 1, (2004), 23-30. DOI: 10.3745/KIPSTD.2004.11.1.23.