In this paper we study the external memory planar point enclosure problem: Given N axis-parallel rectangles in the piano, construct a data structure on disk (an index) such that all A' 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. Surprisingly, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in <9(logfl N 4-K/B) I/Os, where B is the disk block size. To obtain this bound, Q(N/B1~S) disk blocks are needed for some constant <: > 0. With linear space, the best obtainable query bound is O(og.2N -I-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 n family of structures with matching space and query bounds.
展开▼
