Abstract
Optimal Partitioning for Spatial Data
by: Hakan Ferhatosmanoglu, Divyakant Agrawal, Amr El Abbadi
Abstract:
It is desirable to design partitioning techniques that minimizethe I/O time incurred during query execution in spatial databases. Inthis paper, we explore optimal partitioning techniques for spatialdata for different types of queries. In particular, we show thathexagonal partitioning has optimal I/O cost for circular queriescompared to all possible non-overlapping partitioning techniques thatuse convex regions. For rectangular queries, we show that although forthe special case when queries are rectilinear, rectangular gridpartitioning gives superior performance, hexagonal partitioning hasoverall better I/O cost for a general class of range queries. We alsodiscuss storage and retrieval techniques for hexagonal partitioningusing current techniques for rectangular grid partitioning.
Keywords:
partitioning, I/O optimality, range query, hexagonal partitioning, spatial data
Date:
December 2000
Document: 2000-25
