Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

On two-dimensional indexability and optimal range search indexing

Samoladas Vasilis, Lars Arge

Full record


URI: http://purl.tuc.gr/dl/dias/61B2ED50-7E4D-4E26-908D-B964305F5156
Year 1999
Type of Item Conference Full Paper
License
Details
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

Summary

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.

Services

Statistics