Here's a good one I read the other day. Optimal Partitioning for Efficient I/O in Spatial Databases "It is desirable to design partitioning techniques that mi

Here's a good one I read the other day. Optimal Partitioning for Efficient I/O in Spatial Databases "It is desirable to design partitioning techniques that minimize the I/O time incurred during query execution in spatial databases. In this paper, we explore optimal partitioning techniques for spatial data for different types of queries, and develop multi-disk allocation techniques that maximize the degree of I/O parallelism obtained during the retrieval. We show that hexagonal partitioning has optimal I/O cost for circular queries compared to all possible non-overlapping partitioning techniques that use convex regions. For rectangular queries, we show that although for the special case when queries are rectilinear, rectangular grid partitioning gives superior performance, hexagonal partitioning has overall better I/O cost for a general class of range queries. We then discuss parallel storage and retrieval techniques for hexagonal partitioning using current techniques for rectangular grid partitioning." http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.8088 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.8...