Institutional Repository
Technical University of Crete
EN  |  EL



My Space

Optimal external memory planar point enclosure

Samoladas Vasilis, Lars Arge, Ke Yi

Full record

Year 2004
Type of Item Conference Full Paper
Bibliographic Citation L. Arge, V. Samoladas, K. Yi .(2004).Optimal external memory planar point enclosure.Presented at 12th Annual European Symposium.[online].Available:
Appears in Collections


In 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.