Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/61B2ED50-7E4D-4E26-908D-B964305F5156 | ||
| Year | 1999 | ||
| Type of Item | Conference Full Paper | ||
| License |
|
||
| Bibliographic Citation | L. Arge, V. Samoladas, J. S. Vitterz .(1999).On two-dimensional indexability and optimal range search indexing.Presented at Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems.[online].Available:http://www.cs.au.dk/~large/Papers/rangepods99.pdf | ||
| Appears in Collections |
In this paper we settle several longstanding open problems intheory of indexability and external orthogonal range searching In the rst part of the paper we apply the theory ofindexability to the problem of twodimensional range searching We show that the special case of sided querying canbe solved with constant redundancy and access overheadFrom this we derive indexing schemes for general sidedrange queries that exhibit an optimal tradeo between redundancy and access overhead.
Copyright © DIAS 2013
