This work studies the problem of 2-dimensional searching for the 3-sided range query of the form @math in both main and external memory, by considering a variety of input distributions. We present three sets of solutions each of which examines the 3-sided problem in both RAM and I O model respectively. The presented data structures are deterministic and the expectation is with respect to the input distribution.
Moreover, several attempts have been performed to externalize Priority Search Trees, including @cite_11 , @cite_20 , @cite_23 , @cite_16 and @cite_8 , but all of them have not been optimal. The worst case optimal external memory solution (External Priority Search Tree) was presented in @cite_0 . It consumes @math disk blocks, performs 3-sided range queries in @math I Os w.c. and supports updates in @math I Os amortized. This solution poses no assumptions on the input distribution.
@cite_8 @cite_0 @cite_23 @cite_16 @cite_20 @cite_11
2114123275 2043148321 2147935317 2293258084
The authors present a space- and I O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The data structure settles an open problem in databases and I O algorithms by providing the first optimal external-memory solution to the dynamic interval management problem, which is a special case of 2-dimensional range searching and a central problem for object-oriented and temporal databases and for constraint logic programming. The data structure simultaneously uses optimal linear space (that is, O(N B) blocks of disk space) and achieves the optimal O(log sub B N+T B) I O query bound and O(log sub B N) I O update bound, where B is the I O block size and T the number of elements in the answer to a query. The structure is also the first optimal external data structure for a 2-dimensional range searching problem that has worst-case as opposed to amortized update bounds. Part of the data structure uses a novel balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest. In this paper we settle several longstanding open problems in theory of indexability and external orthogonal range searching. In the rst part of the paper, we apply the theory of indexability to the problem of two-dimensional range searching. We show that the special case of 3-sided querying can be solved with constant redundancy and access overhead. From this, we derive indexing schemes for general 4-sided range queries that exhibit an optimal tradeo between redundancy and access overhead. In the second part of the paper, we develop dynamic external memory data structures for the two query types. Our structure for 3-sided queries occupies O(N=B) disk blocks, and it supports insertions and deletions in O(log B N) I Os and queries in O(log B N + T=B) I Os, where B is the disk block size, N is the number of points, and T is the query output size. These bounds are optimal. Our structure for general (4-sided) range searching occupies O (N=B)(log(N=B))= log log B N disk blocks and answers queries in O(log B N + T=B) I Os, which are optimal. It also supports updates in O (log B N)(log(N=B))= log log B N I Os. Center for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC 27708 0129. Supported in part by the U.S. Army Research O ce through MURI grant DAAH04 96 1 0013 and by the National Science Foundation through ESS grant EIA 9870734. Part of this work was done while visiting BRICS, Department of Computer Science, University of Aarhus, Denmark. Email: large@cs.duke.edu. yDepartment of Computer Sciences, University of Texas at Austin, Austin, TX 78712-1188. Email vsam@cs.utexas.edu zCenter for Geometric Computing, Department of Computer Science, Duke University, Box 90129, Durham, NC 27708 0129. Supported in part by the U.S. Army Research O ce through MURI grant DAAH04 96 1 0013 and by the National Science Foundation through grants CCR 9522047 and EIA 9870734. Part of this work was done while visiting BRICS, Department of Computer Science, University of Aarhus, Denmark and I.N.R.I.A., Sophia Antipolis, France. Email: jsv@cs.duke.edu. We propose new succinct representations of ordinal trees and match various space time lower bounds. It is known that any n-node static tree can be represented in 2n p o(n) bits so that a number of operations on the tree can be supported in constant time under the word-RAM model. However, the data structures are complicated and difficult to dynamize. We propose a simple and flexible data structure, called the range min-max tree, that reduces the large number of relevant tree operations considered in the literature to a few primitives that are carried out in constant time on polylog-sized trees. The result is extended to trees of arbitrary size, retaining constant time and reaching 2n p O(n polylog(n)) bits of space. This space is optimal for a core subset of the operations supported and significantly lower than in any previous proposal. For the dynamic case, where insertion deletion (indels) of nodes is allowed, the existing data structures support a very limited set of operations. Our data structure builds on the range min-max tree to achieve 2n p O(n log n) bits of space and O(log n) time for all operations supported in the static scenario, plus indels. We also propose an improved data structure using 2n p O(nlog log n log n) bits and improving the time to the optimal O(log n log log n) for most operations. We extend our support to forests, where whole subtrees can be attached to or detached from others, in time O(log1pe n) for any e > 0. Such operations had not been considered before. Our techniques are of independent interest. An immediate derivation yields an improved solution to range minimum maximum queries where consecutive elements differ by ± 1, achieving n p O(n polylog(n)) bits of space. A second one stores an array of numbers supporting operations sum and search and limited updates, in optimal time O(log n log log n). A third one allows representing dynamic bitmaps and sequences over alphabets of size σ, supporting rank select and indels, within zero-order entropy bounds and time O(log n log σ (log log n)2) for all operations. This time is the optimal O(log n log log n) on bitmaps and polylog-sized alphabets. This improves upon the best existing bounds for entropy-bounded storage of dynamic sequences, compressed full-text self-indexes, and compressed-space construction of the Burrows-Wheeler transform. Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indices, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query e returns the component of T - e containing the vertex sought for, while incurring some known cost c ( e ) . The Tree Search Problem with Non-Uniform Cost is the following: given a tree T on n vertices, each edge having an associated cost, construct a strategy that minimizes the total cost of the identification in the worst case.Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input trees of degree 3 or diameter 6. The best known approximation guarantee was an O ( log ź n log ź log ź log ź n ) -approximation algorithm of (2012) 4.We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an O ( log ź n log ź log ź n ) -approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-hard even when the input tree is a spider of diameter 6, i.e., at most one vertex has degree larger than 2.