Optimal Partitioning for Spatial Data

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.