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 1. 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. |
Year | DOI | Venue |
---|---|---|
2000 | 10.1007/3-540-46564-2_1 | FoIKS |
Keywords | Field | DocType |
low discrepancy allocation,concurrent retrieval,different storage device,geographically referenced information,latin square,distinct label,o device,certain condition,retrieving information,query rectangle,present paper construction,two-dimensional data,lower bound,region of interest | Division (mathematics),Upper and lower bounds,Computer science,Rectangle,Algorithm,Theoretical computer science,Digital library,Data allocation,Tile | Conference |
Volume | ISSN | ISBN |
1762 | 0302-9743 | 3-540-67100-5 |
Citations | PageRank | References |
3 | 0.54 | 8 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Richard P. Anstee | 1 | 210 | 51.95 |
János Demetrovics | 2 | 414 | 163.60 |
Gyula O. H. Katona | 3 | 264 | 66.44 |
Attila Sali | 4 | 166 | 24.30 |