Το έργο με τίτλο Optimal external memory planar point enclosure από τον/τους δημιουργό/ούς Samoladas Vasilis, Lars Arge, Ke Yi διατίθεται με την άδεια Creative Commons Αναφορά Δημιουργού 4.0 Διεθνές
Βιβλιογραφική Αναφορά
L. 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.pdf
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.