Low discrepancy allocation of two-dimensional data

TitleLow discrepancy allocation of two-dimensional data
Publication TypeConference Paper
AuthorsAnstee, R., J. Demetrovics, G. O. H. Katona, and A. Sali
Year2000
Pages1 - 12
Conference NameFoundations of Information and Knowledge Systems
PublisherSpringer
Place of PublicationBerlin
Languageeng
ISBN Number0302-97433540671005
Notes

Low discrepancy allocation of two-dimensional data;

Abstract

Fast browsing and retrieval of geographically referenced information requires the allocation of data on different storage devices for concurrent retrieval. By dividing the two-dimensional space into tiles, a system can allow users to specify regions of interest using a query rectangle and then retrieving information related to tiles covered by the query. Suppose that there are m I/O devices. A tile is labeled by i if the data corresponding to this area is stored in the ith I/O device. A labeling is efficient if the difference of the numbers of occurrences of distinct labels in any given rectangle is small. Except for some simple cases this discrepancy exceeds i. In the present paper constructions are given to make this discrepancy small relative to m. The constructions use latin squares and a lower bound is given, which shows that the constructions are best possible under certain conditions.