Optimal Allocation of Two-Dimensional Data

Efficient browsing and retrieval of geographically referenced informationrequires the allocation of data on different storage devices for concurrentretrieval. By dividing a two dimensional space into tiles, a system can allowusers to specify regions of interest using a query rectangle and thenretrieving all information related to tiles overlapping with the query. Inthis paper, we derive the necessary and sufficient conditions for strictlyoptimal allocations of two-dimensional data. These methods, when they exist,guarantee that for any query, the minimum number of tiles are assigned the samestorage device, and hence ensures maximal retrieval concurrency.