On two-dimensional indexability and optimal range search indexing

摘要: In this paper we settle several longstanding open problems in theory of indexability and external orthogonal range searching. the rst part paper, apply to problem two-dimensional We show that special case 3-sided querying can be solved with constant redundancy access overhead. From this, derive indexing schemes for general 4-sided queries exhibit an optimal tradeo between second develop dynamic memory data structures two query types. Our structure occupies O(N=B) disk blocks, it supports insertions deletions O(log B N) I/Os N + T=B) I/Os, where is block size, number points, T output size. These bounds are optimal. (4-sided) searching O (N=B)(log(N=B))= log blocks answers which It also updates (log N)(log(N=B))= I/Os. Center Geometric Computing, Department Computer Science, Duke University, Box 90129, Durham, NC 27708{0129. Supported by U.S. Army Research ce through MURI grant DAAH04{96{1{0013 National Science Foundation ESS EIA{9870734. Part work was done while visiting BRICS, University Aarhus, Denmark. Email: large@cs.duke.edu. yDepartment Sciences, Texas at Austin, TX 78712-1188. Email vsam@cs.utexas.edu zCenter grants CCR{9522047 Denmark I.N.R.I.A., Sophia Antipolis, France. jsv@cs.duke.edu.