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

Search

Browse

My Space

Optimal external memory planar point enclosure

Samoladas Vasilis, Lars Arge, Ke Yi

Simple record

URIhttp://purl.tuc.gr/dl/dias/9648C742-BA07-43D3-8EFD-AB2B212C0CB0-
Identifierhttps://www.cse.ust.hk/~yike/enclosure/esa04.pdf-
Languageen-
Extent12 pagesen
TitleOptimal external memory planar point enclosureen
CreatorSamoladas Vasilisen
CreatorΣαμολαδας Βασιληςel
CreatorLars Argeen
CreatorKe Yi en
Content SummaryIn this paper we study the external memory planar point en- closure problem: Given N axis-parallel rectangles in the plane, construct a data structure on disk (an index) such that all K rectangles containing a query point can be reported I/O-efficiently. This problem has important applications in e.g. spatial and temporal databases, and is dual to the important and well-studied orthogonal range searching problem. Surpris- ingly, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in O(logB N + K/B) I/Os, where B is the disk block size. To obtain this bound, Ω(N/B1−ε) disk blocks are needed for some constant ε > 0. With linear space, the best obtainable query bound is O(log2 N + K/B). To show this we prove a general lower bound on the tradeoff between the size of the data structure and its query cost. We also develop a family of structures with matching space and query bounds.el
Type of ItemΠλήρης Δημοσίευση σε Συνέδριοel
Type of ItemConference Full Paperen
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2015-10-17-
Date of Publication2004-
Bibliographic CitationL. Arge, V. Samoladas, K. Yi .(2004).Optimal external memory planar point enclosure.Presented at 12th Annual European Symposium.[online].Available: https://www.cse.ust.hk/~yike/enclosure/esa04.pdfen

Services

Statistics

 

Copyright © DIAS 2013