We use a novel decomposition to create succinct data structures – supporting a wide range of operations on static trees in constant time – for a variety tree classes, extending results of Munro, Nicholson, Benkner, and Wild. Motivated by the class of AVL trees, we further derive asymptotics for the information-theoretic lower bound on the number of bits needed to store tree classes whose generating functions satisfy certain functional equations. In particular, we prove that AVL trees require approximately 0.938 bits per node to encode.

We enhance space efficient representations of two types of intersection graphs. We refine the data structure for path graphs of Balakrishnan et al. to give a succinct data structure of n log n + o(n log n) bits that supports adjacency test, degree and neighbourhood queries in $O\left( {\frac{{\log n}}{{\log \log n}}} \right)$ time (for neighbourhood queries, this is the amount of time for each neighbour reported). To achieve O(1) query times, we give a data structure using (3 + ε)n log n + o(n log n) bits for any constant ε > 0. Furthermore, we are able to support both the distance and shortest path queries on unweighted path graphs using (2 + ε)n log n+ o(n log n) bits in O(log n/ log log n) time (shortest path uses an additional O(1) time per vertex on the path). This is the first compact distance oracles for path graphs. Turning to chordal graphs, we enhance the succinct data structure of Munro and Wu to reduce all query times including performing adjacency test in O(1) time.

An interval graph is the intersection graph of intervals on the real line. We consider the problem of constructing space efficient data structures for two subclasses of interval graphs: those with maximum degree σ1and those with chromatic number at most σ2.We show that both bounded degree and bounded chromatic number interval graphs have a tight lower bound of n lg σi− o(n lg σi) bits (i = 1, 2). This improves the lower bound of Chakraborty and Jo from $\frac{1}{6}n\lg {\sigma _i} - O(n)$. For bounded chromatic number interval graphs, we give the first succinct data structure occupying n lg σ2+ O(n) bits that supports navigational operations and distance queries in O(σ2lgn) time. To match Chakraborty and Jo’s time complexity of O(lg lg σ2), which uses (σ2− 1)n+O(n) bits, we use 2nlgσ2+O(n) bits instead.

We design the first dynamic distance oracles for interval graphs, which are intersection graphs of a set of intervals on the real line, and for proper interval graphs, which are intersection graphs of a set of intervals in which no interval is properly contained in another. For proper interval graphs, we design a linear space data structure which supports distance queries (computing the distance between two query vertices) and vertex insertion or deletion in O(lg⁡n) worst-case time, where n is the number of vertices currently in G. Under incremental (insertion only) or decremental (deletion only) settings in general interval graphs, we design linear space data structures that support distance queries in O(lg⁡n) worst-case time and vertex insertion or deletion in O(lg⁡n) amortized time, where n is the maximum number of vertices in the graph. Under fully dynamic settings in general interval graphs, we design a data structure that represents an interval graph G in O(n) words of space to support distance queries in O(nlg⁡n/S(n)) worst-case time and vertex insertion or deletion in O(S(n)+lg⁡n) worst-case time, where n is the number of vertices currently in G and S(n) is an arbitrary function that satisfies S(n)=Ω(1) and S(n)=O(n). This implies an O(n)-word solution with O(nlg⁡n)-time support for both distance queries and updates. All four data structures can answer shortest path queries by reporting the vertices in the shortest path between two query vertices in O(lg⁡n) worst-case time per vertex. We also study the hardness of supporting distance queries under updates over an intersection graph of 3D axis-aligned line segments, which generalizes our problem to 3D. Finally, we solve the problem of computing the diameter of a dynamic connected interval graph.

Our interest is in paths between pairs of vertices that go through at least one of a subset of the vertices known as beer vertices. Such a path is called a beer path, and the beer distance between two vertices is the length of the shortest beer path. We show that we can represent unweighted interval graphs using $2n \log n + O(n) + O(|B|\log n)$ bits where $|B|$ is the number of beer vertices. This data structure answers beer distance queries in $O(\log^\varepsilon n)$ time for any constant $\varepsilon > 0$ and shortest beer path queries in $O(\log^\varepsilon n + d)$ time, where $d$ is the beer distance between the two nodes. We also show that proper interval graphs may be represented using $3n + o(n)$ bits to support beer distance queries in $O(f(n)\log n)$ time for any $f(n) \in ω(1)$ and shortest beer path queries in $O(d)$ time. All of these results also have time-space trade-offs. Lastly we show that the information theoretic lower bound for beer proper interval graphs is very close to the space of our structure, namely $\log(4+2\sqrt{3})n - o(n)$ (or about $ 2.9 n$) bits.

Abstract Huang and Wong (Acta Inform 21(1):113–123, 1984) proposed a polynomial-time dynamic-programming algorithm for computing optimal generalized binary split trees. We show that their algorithm is incorrect. Thus, it remains open whether such trees can be computed in polynomial time. Spuler (Optimal search trees using two-way key comparisons, PhD thesis, 1994) proposed modifying Huang and Wong’s algorithm to obtain an algorithm for a different problem: computing optimal two-way comparison search trees. We show that the dynamic program underlying Spuler’s algorithm is not valid, in that it does not satisfy the necessary optimal-substructure property and its proposed recurrence relation is incorrect. It remains unknown whether the algorithm is guaranteed to compute a correct overall solution.

We present a simple O(n 4 ) -time algorithm for computing optimal search trees with two-way comparisons. The only previous solution to this problem, by Anderson et al., has the same running time but is significantly more complicated and is restricted to the variant where only successful queries are allowed. Our algorithm extends directly to solve the standard full variant of the problem, which also allows unsuccessful queries and for which no polynomial-time algorithm was previously known. The correctness proof of our algorithm relies on a new structural theorem for two-way-comparison search trees.

We present a new universal source code for distributions of unlabeled binary and ordinal trees that achieves optimal compression to within lower order terms for all tree sources covered by existing universal codes. At the same time, it supports answering many navigational queries on the compressed representation in constant time on the word-RAM; this is not known to be possible for any existing tree compression method. The resulting data structures, "hypersuccinct trees", hence combine the compression achieved by the best known universal codes with the operation support of the best succinct tree data structures. We apply hypersuccinct trees to obtain a universal compressed data structure for range-minimum queries. It has constant query time and the optimal worst-case space usage of $2n+o(n)$ bits, but the space drops to $1.736n + o(n)$ bits on average for random permutations of $n$ elements, and $2\lg\binom nr + o(n)$ for arrays with $r$ increasing runs, respectively. Both results are optimal; the former answers an open problem of Davoodi et al. (2014) and Golin et al. (2016). Compared to prior work on succinct data structures, we do not have to tailor our data structure to specific applications; hypersuccinct trees automatically adapt to the trees at hand. We show that they simultaneously achieve the optimal space usage to within lower order terms for a wide range of distributions over tree shapes, including: binary search trees (BSTs) generated by insertions in random order / Cartesian trees of random arrays, random fringe-balanced BSTs, binary trees with a given number of binary/unary/leaf nodes, random binary tries generated from memoryless sources, full binary trees, unary paths, as well as uniformly chosen weight-balanced BSTs, AVL trees, and left-leaning red-black trees.

We present a linear space data structure for Dynamic Evaluation of k-CNF Boolean Formulas which achieves O(m^{1-1/k}) query and variable update time where m is the number of clauses in the formula and clauses are of size at most a constant k. Our algorithm is additionally able to count the total number of satisfied clauses. We then show how this data structure can be parallelized in the PRAM model to achieve O(log m) span (i.e. parallel time) and still O(m^{1-1/k}) work. This parallel algorithm works in the stronger Binary Fork model. We then give a series of lower bounds on the problem including an average-case result showing the lower bounds hold even when the updates to the variables are chosen at random. Specifically, a reduction from k-Clique shows that dynamically counting the number of satisfied clauses takes time at least n^{(2ω-3)/6 √{2k} -1 -o(√k)}, where 2 ≤ ω < 2.38 is the matrix multiplication constant. We show the Combinatorial k-Clique Hypothesis implies a lower bound of m^{(1-k^{-1/2})(1-o(1))} which suggests our algorithm is close to optimal without involving Matrix Multiplication or new techniques. We next give an average-case reduction to k-clique showing the prior lower bounds hold even when the updates are chosen at random. We use our conditional lower bound to show any Binary Fork algorithm solving these problems requires at least Ω(log m) span, which is tight against our algorithm in this model. Finally, we give an unconditional linear space lower bound for Dynamic k-CNF Boolean Formula Evaluation.

We introduce the first index that can be built in o(n) time for a text of length n, and can also be queried in o(q) time for a pattern of length q. On an alphabet of size σ, our index uses O(n log σ) bits, is built in O(n log σ / √{log n}) deterministic time, and computes the number of occurrences of the pattern in time O(q/log_σ n + log n log_σ n). Each such occurrence can then be found in O(log n) time. Other trade-offs between the space usage and the cost of reporting occurrences are also possible.

Given a string S of length n, its Lyndon array identifies for each suffix S[i..n] the next lexicographically smaller suffix S[j..n], i.e. the minimal index j > i with S[i..n] ≻ S[j..n]. Apart from its plain (n log₂ n)-bit array representation, the Lyndon array can also be encoded as a succinct parentheses sequence that requires only 2n bits of space. While linear time construction algorithms for both representations exist, it has previously been unknown if the same time bound can be achieved with less than Ω(n lg n) bits of additional working space. We show that, in fact, o(n) additional bits are sufficient to compute the succinct 2n-bit version of the Lyndon array in linear time. For the plain (n log₂ n)-bit version, we only need 𝒪(1) additional words to achieve linear time. Our space efficient construction algorithm makes the Lyndon array more accessible as a fundamental data structure in applications like full-text indexing.

We present the first succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports the mapping between preorder (i.e., depth-first) ranks and level-order (breadth-first) ranks of nodes in constant time. Our distance oracles for interval graphs also support navigation queries – testing adjacency, computing node degrees, neighborhoods, and shortest paths – all in optimal time. Our technique also yields optimal distance oracles for proper interval graphs (unit-interval graphs) and circular-arc graphs. Our tree data structure supports all operations provided by different approaches in previous work, as well as mapping to and from level-order ranks and retrieving the last (first) internal node before (after) a given node in a level-order traversal, all in constant time.

We introduce a compressed suffix array representation that, on a text T of length n over an alphabet of size \(\sigma \) , can be built in O ( n ) deterministic time, within \(O(n\log \sigma )\) bits of working space, and counts the number of occurrences of any pattern P in T in time \(O(|P| + \log \log _w \sigma )\) on a RAM machine of \(w=\Omega (\log n)\) -bit words. This time is almost optimal for large alphabets ( \(\log \sigma =\Theta (\log n)\) ), and it outperforms all the other compressed indexes that can be built in linear deterministic time, as well as some others. The only faster indexes can be built in linear time only in expectation, or require \(\Theta (n\log n)\) bits. For smaller alphabets, where \(\log \sigma = o(\log n)\) , we show how, by using space proportional to a compressed representation of the text, we can build in linear time an index that counts in time \(O(|P|/\log _\sigma n + \log _\sigma ^\epsilon n)\) for any constant \(\epsilon >0\) . This is almost RAM-optimal in the typical case where \(w=\Theta (\log n)\) .

In this paper we describe a fully-dynamic data structure for the planar point location problem in the external memory model. Our data structure supports queries in O(log_B n(log log_B n)^3)) I/Os and updates in O(log_B n(log log_B n)^2)) amortized I/Os, where n is the number of segments in the subdivision and B is the block size. This is the first dynamic data structure with almost-optimal query cost. For comparison all previously known results for this problem require O(log_B^2 n) I/Os to answer queries. Our result almost matches the best known upper bound in the internal-memory model.

In this paper, we consider a variant of the color range reporting problem called color reporting with frequencies. Our goal is to pre-process a set of colored points into a data structure, so that given a query range Q, we can report all colors that appear in Q, along with their respective frequencies. In other words, for each reported color, we also output the number of times it occurs in Q. We describe an external-memory data structure that uses O(N(1+log^2D/log N)) words and answers one-dimensional queries in O(1 +K/B) I/Os, where N is the total number of points in the data structure, D is the total number of colors in the data structure, K is the number of reported colors, and B is the block size. Next we turn to an approximate version of this problem: report all colors sigma that appear in the query range; for every reported color, we provide a constant-factor approximation on its frequency. We consider color reporting with approximate frequencies in two dimensions. Our data structure uses O(N) space and answers two-dimensional queries in O(log_B N +log^*B + K/B) I/Os in the special case when the query range is bounded on two sides. As a corollary, we can also answer one-dimensional approximate queries within the same time and space bounds.

For any $ε\in (0,1)$, a $(1+ε)$-approximate range mode query asks for the position of an element whose frequency in the query range is at most a factor $(1+ε)$ smaller than the true mode. For this problem, we design an $O(n/ε)$ bit data structure supporting queries in $O(\lg(1/ε))$ time. This is an encoding data structure which does not require access to the input sequence; we prove the space cost is asymptotically optimal for constant $ε$. Our solution improves the previous best result of Greve et al. (Cell Probe Lower Bounds and Approximations for Range Mode, ICALP'10) by reducing the space cost by a factor of $\lg n$ while achieving the same query time. We also design an $O(n)$-word dynamic data structure that answers queries in $O(\lg n /\lg\lg n)$ time and supports insertions and deletions in $O(\lg n)$ time, for any constant $ε\in (0,1)$. This is the first result on dynamic approximate range mode; it can also be used to obtain the first static data structure for approximate 3-sided range mode queries in two dimensions. We also consider approximate range selection. For any $α\in (0,1/2)$, an $α$-approximate range selection query asks for the position of an element whose rank in the query range is in $[k - αs, k + αs]$, where $k$ is a rank given by the query and $s$ is the size of the query range. When $α$ is a constant, we design an $O(n)$-bit encoding data structure that can answer queries in constant time and prove this space cost is asymptotically optimal. The previous best result by Krizanc et al. (Range Mode and Range Median Queries on Lists and Trees, Nordic Journal of Computing, 2005) uses $O(n\lg n)$ bits, or $O(n)$ words, to achieve constant approximation for range median only. Thus we not only improve the space cost, but also provide support for any arbitrary $k$ given at query time.

Given an array A of $n$ elements, we wish to support queries for the most frequent and least frequent element in a subrange $[l, r]$ of $A$. We also wish to support updates that change a particular element at index $i$ or insert/ delete an element at index $i$. For the range mode problem, our data structure supports all operations in $O(n^{2/3})$ deterministic time using only $O(n)$ space. This improves two results by Chan et al. \cite{C14}: a linear space data structure supporting update and query operations in $\tilde{O}(n^{3/4})$ time and an $O(n^{4/3})$ space data structure supporting update and query operations in $\tilde{O}(n^{2/3})$ time. For the range least frequent problem, we address two variations. In the first, we are allowed to answer with an element of $A$ that may not appear in the query range, and in the second, the returned element must be present in the query range. For the first variation, we develop a data structure that supports queries in $\tilde{O}(n^{2/3})$ time, updates in $O(n^{2/3})$ time, and occupies $O(n)$ space. For the second variation, we develop a Monte Carlo data structure that supports queries in $O(n^{2/3})$ time, updates in $\tilde{O}(n^{2/3})$ time, and occupies $\tilde{O}(n)$ space, but requires that updates are made independently of the results of previous queries. The Monte Carlo data structure is also capable of answering $k$-frequency queries; that is, the problem of finding an element of given frequency in the specified query range. Previously, no dynamic data structures were known for least frequent element or $k$-frequency queries.

An optimal binary search tree for an access sequence on elements is a static tree that minimizes the total search cost. Constructing perfectly optimal binary search trees is expensive so the most efficient algorithms construct almost optimal search trees. There exists a long literature of constructing almost optimal search trees dynamically, i.e., when the access pattern is not known in advance. All of these trees, e.g., splay trees and treaps, provide a multiplicative approximation to the optimal search cost. In this paper we show how to maintain an almost optimal weighted binary search tree under access operations and insertions of new elements where the approximation is an additive constant. More technically, we maintain a tree in which the depth of the leaf holding an element $e_i$ does not exceed $\min(\log(W/w_i),\log n)+O(1)$ where $w_i$ is the number of times $e_i$ was accessed and $W$ is the total length of the access sequence. Our techniques can also be used to encode a sequence of $m$ symbols with a dynamic alphabetic code in $O(m)$ time so that the encoding length is bounded by $m(H+O(1))$, where $H$ is the entropy of the sequence. This is the first efficient algorithm for adaptive alphabetic coding that runs in constant time per symbol.

We present two stable mergesort variants, "peeksort" and "powersort", that exploit existing runs and find nearly-optimal merging orders with negligible overhead. Previous methods either require substantial effort for determining the merging order (Takaoka 2009; Barbay & Navarro 2013) or do not have an optimal worst-case guarantee (Peters 2002; Auger, Nicaud & Pivoteau 2015; Buss & Knop 2018) . We demonstrate that our methods are competitive in terms of running time with state-of-the-art implementations of stable sorting methods.

We study the problem of approximate shortest path queries in chordal graphs and give a n log n + o(n log n) bit data structure to answer the approximate distance query to within an additive constant of 1 in O(1) time. We study the problem of succinctly storing a static chordal graph to answer adjacency, degree, neighbourhood and shortest path queries. Let G be a chordal graph with n vertices. We design a data structure using the information theoretic minimal n^2/4 + o(n^2) bits of space to support the queries: - whether two vertices u,v are adjacent in time f(n) for any f(n) in omega(1). - the degree of a vertex in O(1) time. - the vertices adjacent to u in (f(n))^2 time per neighbour - the length of the shortest path from u to v in O(nf(n)) time

We present a space-efficient data structure using O(n log n) bits that represents a distributive lattice on n elements and supports finding meets and joins in O(log n) time. Our data structure extends the ideal tree structure of Habib and Nourine which occupies O(n log n) bits of space and requires O(m) time to compute a meet or join, where m depends on the specific lattice and may be as large as n – 1. We also give an encoding of a distributive lattice using bits, which is very close to the information theoretic lower bound. This encoding can be created or decompressed in O(n log n) time.

We consider the classical selection and sorting problems in a model where the initial permutation of the input has to be restored after completing thecomputation. Such algorithms are useful for designing space-efficient algorithms, when one encounters subproblems that have to be solved by subroutines. It is important that these subroutines leave the array in its original state after they finish so that the computation can be properly resumed. Algorithms in this model can also be relevant for saving communication time, in case the data is distributed among several machines and would need to be copied to further machines for execution of the subroutine. Although the requirement of the restoration is stringent compared to the classicalversions of the problems, this model is more relaxed than a read-only memory where the input elements are not allowed to be moved within the input array. We first show that for a sequence of n integers, selection (finding the median or more generally the k -th smallest element for a given k ) can be done in O ( n ) time using O (lg n ) words 1 of extra space in this model. In contrast, no linear-time selection algorithm is known that uses polylogarithmic space in the read-only memory model. For sorting n integers in this model, we first present an O ( n lg n )-time algorithm using O (lg n ) words of extra space that outputs (in a write only tape) the given sequence in sorted order while restoring the order of the original input in the input tape. When the universe size U is polynomial in n , we give a faster O ( n )-time algorithm (analogous to radix sort) that uses O ( n ε ) words of extra space for an arbitrarily small constant ε > 0. More generally, we show how to match the time bound of any word-RAM integer sorting algorithms using O ( n ε ) words of extra space. In sharp contrast, there is an Ω ( n 2 / S )-time lower bound for integer sorting using O ( S ) bits of space in the read-only memory model. Extension of our results to arbitrary input types beyond integers is not possible: for “indivisible” input elements, we can prove the same Ω ( n 2 / S ) lower bound for sorting in our model. We also describe space-efficient algorithms to count the number of inversions in a given sequence in this model. En route, we develop linear-time in-place algorithms to extract leading bits of the input array and to compress and decompress strings with low entropy; these techniques may be of independent interest.

In this paper we study succinct data structures for one-dimensional color reporting and color counting problems. We are given a set of n points with integer coordinates in the range [1,m] and every point is assigned a color from the set {1,...\sigma}. A color reporting query asks for the list of distinct colors that occur in a query interval [a,b] and a color counting query asks for the number of distinct colors in [a,b]. We describe a succinct data structure that answers approximate color counting queries in O(1) time and uses \mathcal{B}(n,m) + O(n) + o(\mathcal{B}(n,m)) bits, where \mathcal{B}(n,m) is the minimum number of bits required to represent an arbitrary set of size n from a universe of m elements. Thus we show, somewhat counterintuitively, that it is not necessary to store colors of points in order to answer approximate color counting queries. In the special case when points are in the rank space (i.e., when n=m), our data structure needs only O(n) bits. Also, we show that \Omega(n) bits are necessary in that case. Then we turn to succinct data structures for color reporting. We describe a data structure that uses \mathcal{B}(n,m) + nH_d(S) + o(\mathcal{B}(n,m)) + o(n\lg\sigma) bits and answers queries in O(k+1) time, where k is the number of colors in the answer, and nH_d(S) (d=\log_\sigma n) is the d-th order empirical entropy of the color sequence. Finally, we consider succinct color reporting under restricted updates. Our dynamic data structure uses nH_d(S)+o(n\lg\sigma) bits and supports queries in O(k+1) time.

We show that the compressed suffix array and the compressed suffix tree of a string T can be built in O(n) deterministic time using O(n log σ) bits of space, where n is the string length and σ is the alphabet size. Previously described deterministic algorithms either run in time that depends on the alphabet size or need ω(n log σ) bits of working space. Our result has immediate applications to other problems, such as yielding the first deterministic linear-time LZ77 and LZ78 parsing algorithms that use O(n log σ) bits.

Given a permutation of n elements, stored as an array, we address the problem of replacing the permutation by its kth power. We aim to perform this operation quickly using o(n) bits of extra storage. To this end, we first present an algorithm for inverting permutations that uses O(lg^2 n) additional bits and runs in O(n lg n) worst case time. This result is then generalized to the situation in which the permutation is to be replaced by its kth power. An algorithm whose worst case running time is O(n lg n) and uses O(lg^2 n + min{k lg n, n^{3/4 + epsilon}}) additional bits is presented.

We focus on succinct data structures, that is on time and space efficient representations of trees and other combinatorial objects that dominate the memory requirements of most sophisticated programs and systems.

Consider a tree T on n nodes, each having a weight drawn from [1‥σ]. In this article, we study the problem of supporting various path queries over the tree T . The path counting query asks for the number of the nodes on a query path whose weights are in a query range, while the path reporting query requires to report these nodes. The path median query asks for the median weight on a path between two given nodes, and the path selection query returns the k -th smallest weight. We design succinct data structures to encode T using n nH ( W T ) + 2 n + o ( n lg σ) bits of space, such that we can support path counting queries in O (lg σ/lg lg n + 1)) time, path reporting queries in O (( occ +1)(lg σ / lg lg n + 1)) time, and path median and path selection queries in O (lg σ / lg lg σ) time, where H ( W T ) is the entropy of the multiset of the weights of the nodes in T and occ is the size of the output. Our results not only greatly improve the best known data structures [Chazelle 1987; Krizanc et al. 2005], but also match the lower bounds for path counting, median, and selection queries [Pătraşcu 2007, 2011; Jørgensen and Larsen 2011] when σ = Ω( n /polylog( n )).

In the dynamic indexing problem, we must maintain a changing collection of text documents so that we can efficiently support insertions, deletions, and pattern matching queries. We are especially interested in developing efficient data structures that store and query the documents in compressed form. All previous compressed solutions to this problem rely on answering rank and select queries on a dynamic sequence of symbols. Because of the lower bound in [Fredman and Saks, 1989], answering rank queries presents a bottleneck in compressed dynamic indexing. In this paper we show how this lower bound can be circumvented using our new framework. We demonstrate that the gap between static and dynamic variants of the indexing problem can be almost closed. Our method is based on a novel framework for adding dynamism to static compressed data structures. Our framework also applies more generally to dynamizing other problems. We show, for example, how our framework can be applied to develop compressed representations of dynamic graphs and binary relations.

The idea of multi-pivot quicksort has recently received the attention of researchers after Vladimir Yaroslavskiy proposed a dual pivot quicksort algorithm that, contrary to prior intuition, outperforms standard quicksort by a a significant margin under the Java JVM [10]. More recently, this algorithm has been analysed in terms of comparisons and swaps by Wild and Nebel [9]. Our contributions to the topic are as follows. First, we perform the previous experiments using a native C implementation thus removing potential extraneous effects of the JVM. Second, we provide analyses on cache behavior of these algorithms. We then provide strong evidence that cache behavior is causing most of the performance differences in these algorithms. Additionally, we build upon prior work in multi-pivot quicksort and propose a 3-pivot variant that performs very well in theory and practice. We show that it makes fewer comparisons and has better cache behavior than the dual pivot quicksort in the expected case. We validate this with experimental results, showing a 7–8% performance improvement in our tests.

We consider the classical selection and sorting problems in a model where the initial permutation of the input has to be restored after completing the computation. While the requirement of the restoration is stringent compared to the classical versions of the problems, this model is more relaxed than a read-only memory where the input elements are not allowed to be moved within the input array. We first show that for a sequence of n integers, selection (finding the median or more generally the k-th smallest element for a given k) can be done in O(n) time using O(lgn) words1 of extra space in this model. In contrast, no linear-time selection algorithm is known which uses polylogarithmic space in the read-only memory model. For sorting n integers in this model, we first present an O(n lg n)-time algorithm using O(lg n) words of extra space. When the universe size U is polynomial in n, we give a faster O(n)-time algorithm (analogous to radix sort) which uses O(n∊) words of extra space for an arbitrarily small constant ∊ > 0. More generally, we show how to match the time bound of any word-RAM integer-sorting algorithms using O(n∊) words of extra space. In sharp contrast, there is an Ω(n2/S)-time lower bound for integer sorting using O(S) bits of space in the read-only memory model. Extension of our results to arbitrary input types beyond integers is not possible: for “indivisible” input elements, we can prove the same Ω(n2/S) lower bound for sorting in our model. En route, we develop linear-time in-place algorithms to extract leading bits of the input array and to compress and decompress strings with low entropy; these techniques may be of independent interest.

We will address several issues, old and new, in the computational complexity of comparison based problems, focusing on the long term development of techniques. Most notably, we will look at the comparison minimization problems of placing a set of n values into an arbitrary given partial order, and of completing the sort from this stage. The parallel development of the algorithmics and of graph entropy will be discussed in this context.

Various methods have been used to represent a tree on n nodes in essentially the information-theoretic minimum space while supporting various navigational operations in constant time, but different representations usually support different operations. Our main contribution is a succinct representation of ordinal trees, based on that of Geary et al. [2006], that supports all the navigational operations supported by various succinct tree representations while requiring only 2 n + o ( n ) bits. It also supports efficient level-order traversal, a useful ordering previously supported only with a very limited set of operations. Our second contribution expands on the notion of a single succinct representation supporting more than one traversal ordering, by showing that our method supports two other encoding schemes as abstract data types. In particular, it supports extracting a word ( O (lg n ) bits) of the balanced parenthesis sequence or depth first unary degree sequence in O ( f ( n )) time, using at most n / f ( n )+ o ( n ) additional bits, for any f ( n ) in O (lg n ) and Ω(1).

We define and design succinct indexes for several abstract data types (ADTs). The concept is to design auxiliary data structures that ideally occupy asymptotically less space than the information-theoretic lower bound on the space required to encode the given data, and support an extended set of operations using the basic operators defined in the ADT. The main advantage of succinct indexes as opposed to succinct (integrated data/index) encodings is that we make assumptions only on the ADT through which the main data is accessed, rather than the way in which the data is encoded. This allows more freedom in the encoding of the main data. In this article, we present succinct indexes for various data types, namely strings, binary relations and multilabeled trees. Given the support for the interface of the ADTs of these data types, we can support various useful operations efficiently by constructing succinct indexes for them. When the operators in the ADTs are supported in constant time, our results are comparable to previous results, while allowing more flexibility in the encoding of the given data. Using our techniques, we design a succinct encoding that represents a string of length n over an alphabet of size σ using n H k ( S ) + lg σ · o ( n ) + O ( n lg σ/lg lg lg σ) bits to support access/rank/select operations in o ((lg lg σ) 1+ϵ ) time, for any fixed constant ϵ > 0. We also design a succinct text index using n H 0 ( S ) + O ( n lg σ/lg lg σ) bits that supports finding all the occ occurrences of a given pattern of length m in O ( m lg lg σ + occ lg n /lg ϵ σ) time, for any fixed constant 0 < ϵ < 1. Previous results on these two problems either have a lg σ factor instead of lg lg σ in the running time, or are not compressed. Finally, we present succinct encodings of binary relations and multi-labeled trees that are more compact than previous structures.

Several existing cache-oblivious dynamic dictionaries achieve O(logB N) (or slightly better memory transfers per operation, where N is the number of items stored, M is the memory size, and B is the block size, which matches the classic B-tree data structure. One recent structure achieves the same query bound and a sometimes-better amortized update bound of memory transfers. This paper presents a new data structure, the xDict, implementing predecessor queries in worst-case memory transfers and insertions and deletions in amortized memory transfers, for any constant ε with 0 < ε < 1. For example, the xDict achieves subconstant amortized update cost when N = M B°(B1−∊), whereas the B-tree's is subconstant only when N = o(MB), and the previously obtained is subconstant only when . The xDict attains the optimal tradeoff between insertions and queries, even in the broader external-memory model, for the range where inserts cost between and O(1/lg3 N) memory transfers.

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set $P$, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of $P$. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical.

We consider the problem of partial order production: arrange the elements of an unknown totally ordered set T into a target partially ordered set S by comparing a minimum number of pairs in T. Special cases include sorting by comparisons, selection, multiple selection, and heap construction. We give an algorithm performing $ITLB+o(ITLB)+O(n)$ comparisons in the worst case. Here, n denotes the size of the ground sets, and $ITLB$ denotes a natural information-theoretic lower bound on the number of comparisons needed to produce the target partial order. Our approach is to replace the target partial order by a weak order (that is, a partial order with a layered structure) extending it, without increasing the information-theoretic lower bound too much. We then solve the problem by applying an efficient multiple selection algorithm. The overall complexity of our algorithm is polynomial. This answers a question of Yao [SIAM J. Comput., 18 (1989), pp. 679–689]. We base our analysis on the entropy of the target partial order, a quantity that can be efficiently computed and provides a good estimate of the information-theoretic lower bound.

Proceedings of the 41st annual ACM Symposium on Theory of Computing STOC 2009, Bethesda, Maryland, 31 mai–2 juin 2009

List update algorithms have been widely used as subroutines in compression schemas, most notably as part of Burrows-Wheeler compression. The Burrows-Wheeler transform (BWT), which is the basis of many state-of-the-art general purpose compressors applies a compression algorithm to a permuted version of the original text. List update algorithms are a common choice for this second stage of BWT-based compression. In this paper we perform an experimental comparison of various list update algorithms both as stand alone compression mechanisms and as a second stage of the BWT-based compression. Our experiments showMTF outperforms other list update algorithms in practice after BWT. This is consistent with the intuition that BWT increases locality of reference and the predicted result from the locality of reference model of Angelopoulos et al. [LATIN 2008]. Lastly, we observe that due to an often neglected difference in the cost models, good list update algorithms may be far from optimal for BWT compression and construct an explicit example of this phenomena. This is a fact that had yet to be supported theoretically in the literature.

We develop an optimal cache‐oblivious priority queue data structure, supporting insertion, deletion, and delete‐min operations in $O(\frac{1}{B}\log_{M/B}\frac{N}{B})$ amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache‐oblivious data structure, M and B are not used in the description of the structure. Our structure is as efficient as several previously developed external memory (cache‐aware) priority queue data structures, which all rely crucially on knowledge about M and B. Priority queues are a critical component in many of the best known external memory graph algorithms, and using our cache‐oblivious priority queue we develop several cache‐oblivious graph algorithms.

We consider the problem of representing and performing computations on finite abelian groups. Assuming a lg n-bit1 word model and considering any abelian group of order n, we show how to represent the group in constant number of words and perform three fundamental group operations of equality testing, multiplication, and inversion in constant number of word operations, provided we have the platform instruction to reverse the bits of a word.

No abstract available.

Internet traffic patterns are believed to obey the power law, implying that most of the bandwidth is consumed by a small set of heavy users. Hence, queries that return a list of frequently occurring items are important in the analysis of real-time Internet packet streams. While several results exist for computing frequent item queries using limited memory in the infinite stream model, in this paper we consider the limited-memory sliding window model. This model maintains the last $N$ items that have arrived at any given time and forbids the storage of the entire window in memory. We present a deterministic algorithm for identifying frequent items in sliding windows defined over real-time packet streams. The algorithm uses limited memory, requires constant processing time per packet (amortized), makes only one pass over the data, and is shown to work well when tested on TCP traffic logs.

We present a deterministic scalable overlay network. In contrast, most previous overlays use randomness or hashing (pseudo-randomness) to achieve a uniform distribution of data and routing traffic.

We reopen the issue of finding an implicit data structure for the dictionary problem. In particular, we examine the problem of maintaining n data values in the first n locations of an array in such a way that we can efficiently perform the operations insert, delete and search. No information other than n and the data is to be retained; and the only operations which we may perform on the data values (other than reads and writes) are comparisons. Our structure supports these operations in O(log/sup 2/ n/log log n) time, marking the first improvement on the problem since the mid 1980's. En route we develop a number of space efficient techniques for handling segments of a large array in a memory hierarchy. We achieve a cost of O(log/sub B/ n) block transfers like in regular B-trees, under the realistic assumption that a block stores B = /spl Omega/(log n) keys, so that reporting r consecutive keys in sorted order has a cost of O(log/sub B/n+r/B) block transfers. Being implicit, our B-tree occupies exactly [n/B] blocks after each update.

(MATH) In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O(1 \over B logM/BN \over B) amortized memory transfers, where M and B are the memory and block transfer sizes of any two consecutive levels of a multilevel memory hierarchy. In a cache-oblivious data structure, M and B are not used in the description of the structure. The bounds match the bounds of several previously developed external-memory (cache-aware) priority queue data structures, which all rely crucially on knowledge about M and B. Priority queues are a critical component in many of the best known external- memory graph algorithms, and using our cache-oblivious priority queue we develop several cache- oblivious graph algorithms.

We consider the implementation of abstract data types for the static objects: binary tree, rooted ordered tree, and a balanced sequence of parentheses. Our representations use an amount of space within a lower order term of the information theoretic minimum and support, in constant time, a richer set of navigational operations than has previously been considered in similar work. In the case of binary trees, for instance, we can move from a node to its left or right child or to the parent in constant time while retaining knowledge of the size of the subtree at which we are positioned. The approach is applied to produce a succinct representation of planar graphs in which one can test adjacency in constant time.

This paper deals with the problem of storing a subset of elements from the bounded universe $\mathcal{M} = \{0, \ldots, M-1\}$ so that membership queries can be performed efficiently. In particular, we introduce a data structure to represent a subset of N elements of $\mathcal{M}$ in a number of bits close to the information-theoretic minimum, $B = \left\lceil \lg {M\choose N} \right\rceil$, and use the structure to answer membership queries in constant time.

We consider the implementation of abstract data types for the static objects: binary tree, rooted ordered tree and balanced parenthesis expression. Our representations use an amount of space within a lower order term of the information theoretic minimum and support, in constant time, a richer set of navigational operations than has previously been considered in similar work. In the case of binary trees, for instance, we can move from a node to its left or right child or to the parent in constant time while retaining knowledge of the size of the subtree at which we are positioned. The approach is applied to produce succinct representation of planar graphs in which one can test adjacency in constant time.

This paper addresses the fundamental problem of permuting the elements of an array of n elements according to some given permutation. It aims to perform the permutation quickly by using only a polylogarithmic number of bits of extra storage. The main result is an algorithm whose worst case running time is $O(n \log n)$ and uses $O(\log n)$ additional $\log n$-bit words of memory. A simpler method is presented for the case in which both the permutation and its inverse can be computed at (amortised) unit cost. This algorithm requires $O(n \log n)$ time and $O(1)$ words in the worst case. These results are extended to the situation in which a power of the permutation must be applied. A linear time, $O(1)$ word method is presented for the special case in which the data values are all distinct and are either initially in sorted order or will be when permuted.

Abstract The median, the 0.25‐percentile and the 0.75‐percentile are three of the most relevant ranks in data analysis. MED2Q is a new in situ algorithm to solve this problem. It asymptotically performs an average of 2 5/8 n + o(n) comparisons when n numbers are given as input thus becoming the asymptotically fastest algorithm for this problem reported to date. The performance of MED2Q is compared with those of FIND1 and ALGORITHM 4892, two well‐known selection algorithms adapted to this specific problem. From this performance comparison, MED2Q is best when input sets consist of more than 50,000 numbers.

The fundamental problem of permuting the elements of an array according to some given permutation is addressed. The goal is to perform the permutation quickly using only a polylogarithmic number of bits of extra storage. The main result is an O(n log n)-time, O(log/sup 2/n)-space worst case method. A simpler method is presented for the case in which both the permutation and its inverse can be computed at (amortized) unit cost. This algorithm requires O(n log n) time and O(log n) bits in the worst case. These results are extended to the situation in which a power of the permutation is to be applied. A linear time, O(log n)-bit method is presented for the special case in which the data values are all distinct and are either initially in sorted order or will be when permuted.>

In this paper we present an extensive study into the long-term behaviour of binary search trees subjected to updates using the usual deletion algorithms taught in introductory textbooks. We develop a model of the behaviour of such trees which leads us to conjecture that the asymptotic average search path length is Θ(N½). We present results of large simulations which strongly support this conjecture. However, introducing a simple modification to ensure symmetry in the algorithms, the model predicts no such long-term deterioration. Simulations in fact indicate that asymptotically the average path length of such trees is less than the 1.386…log2 N average path length of trees generated from random insertion sequences.

It is shown that n + k - O (1) comparisons are necessary, on average, to find the k th smallest of n numbers ( k ⪇ n /2). This lower bound matches the behavior of the technique of Floyd and Rivest to within a lower-order term. 7 n /4 ± o ( n ) comparisons, on average, are shown to be necessary and sufficient to find the maximum and median of a set. An upper bound of 9 n /4 ± o ( n ) and a lower bound of 2 n - o ( n ) are shown for the max-min-median problem.

First, we propose a general framework that captures many of the variations on visibility found in the literature. Second, we investigate two specific variations: rectangular and square visibility.

We present a method for arranging an arbitrary 2-key table as an n by 2 array such that a search can be performed under either key in O(lg2n lglg n) time. This is in sharp contrast with an Ω(√n) lower bound for the problem under a model in which all comparisons must involve the value being searched for.

As part of a study of the general issue of complexity of comparison based problems, as well as interest in the specific problem, we consider the task of performing the basic priority queue operations on a heap. We show that in the worst case: $\lg \lg n \pm O(1)$ comparisons are necessary and sufficient to insert an element into a heap. (This improves the previous upper and lower bounds of $\lg n$ and $O(1)$.) $\lg n + \log ^ * n \pm O(1)$ comparisons are necessary and sufficient to replace the maximum in a heap. (This improves the previous upper and lower bounds of $2\lg n$ and $\lg n$.) $1.625n + O(\lg n\log ^ * n)$ comparisons are sufficient to create a heap. $1.37 \ldots n$ comparisons are necessary not only in the worst case but also on the average. Here lg indicates the logarithm base 2 and $\log ^ * $ denotes the iterated logarithm or number of times the logarithm base 2 may be taken before the quantity is at most 0.

This paper deals with hash tables in which conflicts are resolved by open addressing. The initial contribution is a very simple insertion procedure which (in comparison to the standard approach) has the effect of dramatically reducing the variance of the number of probes required for a search. This leads to a new search procedure which requires only a constant number of probes, on average, even for full tables. Finally, an extension to these methods yields a new, simple way of performing deletions and subsequent insertions. Experimental results strongly indicate little degeneration in search time. In particular deletions and successful searches appear to require constant time (≪ 2.57 probes) and insertions and unsuccessful searches, O(logn).

We introduce a data structure that requires only one pointer for every k data values and permits the operations search, insert and delete to be performed in 0 (k log n) time. This structure is used to develop another that requires no pointers and supports insert, delete and search in 0 (log2 n) time.

We consider problems such as selecting the k-th smallest of n numbers in as few comparisons as possible on average. n + k - 0(1) comparisons are proved to be necessary for this particular problem when k ≤ n/2. This shows a technique of Floyd and Rivest is essentially optimal. 7n/4 = o(n) comparisons, on average, are shown to be necessary and sufficient to find the maximum and median of a set. An upper bound of 9n/4 + o(n) and a lower bound of 2n − o(n) are shown for the max-min-median problem.

We develop a method of representing binary search trees in an environment in which pointers and other structural information may be "lost" or "maliciously altered". Our fault tolerant representation permits any 2 field changes to be detected and any 1 to be corrected without significantly increasing to storage requirements of the binary tree. The detection and correction procedures applied to the entire tree require 0(n) time.Our discipline is also used to represent binary search trees with a single pointer per datum without altering the cost of searching or updating. While our scheme can be applied in conjunction with any underlying tree balancing scheme ([AVL], bounded balance [Nievergelt et al] etc), if no balancing scheme is employed, the trees we form will have significantly shorter search paths than those formed using the straightforward algorithm.

We present a variant of the distribution sort approach which makes use of extra storage to sort a list of n elements in an average of about (2+√)n = 3.412...n probes into a table. An accurate analysis of this technique is made by introducing a transform from a Poisson approximation to the exact (finite) distribution. This analysis also leads to the solution of an interesting parking problem.

Algorithms for findmg medians and solving arbitrary selection problems using a minimum number of data storage locations are investigated A linear-tmle algorithm is given in the first case, and it ~s shown that no such scheme exists for many other interesting selection problems, such as finding a quartile A right trade-off is demonstrated balancing extra space versus time.

We consider techniques for self-organizing linear search, examining the behavior of methods under arbitrary and specific probability distributions. The notion of moving an element forward after it has been accessed k times in a row is introduced. One implementation performs the transformation after any k identical requests. A second essentially groups requests into batches of k, and performs the action only if all requests of a batch are the same. Adopting as the transformation, the move to front heuristic, the second approach is shown in general to be superior. We show that the batched approach, with $k = 2$, leads to an average search time no greater than 1.21... times that of the optimal ordering. For the more direct approach, a ratio of 1.36... is shown under the same constraints. The simple move to front heuristic (i.e., $k = 1$) is also examined. It is shown that for a particular distribution this scheme can lead to an average number of probes $\pi/2$ times that of the optimal order. Within an interesting class of distributions, this is shown to be the worst average behavior.

A failing of existing data structures for maintaining balanced trees is their inability to remember the situation they held at previous times. We propose a structure from which it is possible to efficiently reconstruct the state of the data it represented at any time. Applications of this data structure to a number of important problems in geometric computation are also given.

We consider techniques for adapting linear lists so that the more frequently accessed elements are found near the front, even though we are not told the probabilities of various elements being accessed. The main results are discussed in two sections. Perhaps the most interesting deals with techniques which move an element toward the front only after it has been requested k times in a row. The other, technically more difficult, section deals with the analysis of the heuristic which moves an element to the head of the list each time it is accessed. The behaviour of this scheme under a number of interesting probability distributions is discussed. Two basic approaches to the technique of moving an element forward after it has been accessed k times in a row are discussed. The first performs the transformation after any k identical requests. The second essentially groups requests into batches of at least k, and performs the action only if the last k requests of a batch are the same. Adopting as the transformation, the moving of the requested element to the front of the list, the second approach is shown to lead to faster average search time under all nontrivial probability distributions for k ≥2. It is also shown that the "periodic" approach, with k = 2, never leads to an average search time greater than 1.21.. times that of the optimal ordering. For the more direct approach, a ratio of 1.36.. is shown under the same constraints. In studying the simple move to front heuristic (i.e. k = 1), it is shown that for a particular distribution this scheme can lead to an average number of probes π/2 times that of the optimal order. Within an interesting class of distributions, this is shown to be the worst average behaviour.

@N) basic operations are shown to be necessary and sufficient, in the worst case, to perform these instructions provided that the data elements are kept in some fixed partial order. We demonstrate, however, that further improvements can be made if an arrangement other than a fixed partial order is used. A structure, based on a fixed partial order, is introduced to facilitate multiple key searches. This structure, together with the retrieval scheme based upon it, is shown to be within a constant factor of the optimal one based on a partial order.

We discuss the problem of hashing in a full or nearly full table using open addressing. A scheme for reordering the table as new elements are added is presented. Under the assumption of having a reasonable hash function sequence, it is shown that, even with a full table, only about 2.13 probes will be required, on the average, to access an element. This scheme has the advantage that the expected time for adding a new element is proportional to that required to determine that an element is not in the table. Attention is then turned to the optimal reordering scheme and the minimax problem of ordering the table so as to minimize the length of the longest probe sequence to find any element. Both arranging problems can be translated to assignment problems. A unified algorithm is presented for these, together with the first method suggested. A number of simulation results are reported, the most interesting being an indication that the optimal reordering scheme will lead to an average of about 1.83 probes per search in a full table.

When selecting from, or sorting, a file stored on a read-only tape and the internal storage is rather limited, several passes of the input tape may be required. We study the relation between the amount of internal storage available and the number of passes required to select the Kth highest of N inputs. We show, for example, that to find the median in two passes requires at least Ω(N1/2) and at most O(N1/2 log N) internal storage. For probabilistic methods, Θ(N1/2) internal storage is necessary and sufficient for a single pass method which finds the median with arbitrarily high probability.

Heurlsttcs are considered which attempt to maintain a binary search tree in a near optimal form, assuming that elements are requested with fixed, but unknown, independent probabilities.A "move to root'" heuristic is shown to yield an expected search time within a constant factor of that of an optimal static binary search tree.On the other hand, a closely related "simple exchange" technique is shown not to have this property.The rate of convergence of the move to root heuristic is discussed Also considered is the more general case m whmh elements not in the tree may have nonzero probabihty of being requested.

We discuss the problem of hashing in a full or nearly full table using open addressing. A scheme for reordering the table as new elements are added is presented. Under the assumption of having a reasonable hash function sequence, it is shown that even with a full table only about 2.13 probes will be required, on the average, to access an element. This scheme has the advantage that the expected time for adding a new element is proportional to that required to determine that an element is not in the table. Attention is then turned to the optimal reordering scheme (which is a maximum flow problem) and the minimax problem of arranging the table so as to minimize the length of the longest probe sequence to find any element. A unified algorithm is presented for both of these as well as the first method suggested. A number of simulation results are reported, the most interesting being an indication that the optimal reordering scheme will lead to an average of about 1.83 probes per search in a full table.

Abstract Although overlaying code segments is a very old technique, there is very little literature 68 on what the ground rules are, what the options are and how to select an overlay structure. As a result, the facilities provided by most linkage editors are much poorer than they need be. In this paper we define the problem, give an algorithm for obtaining ‘minimal’ overlay structures and describe the surrounding commands and environment that are necessary to turn this algorithm into a practical tool.

We consider heuristics which attempt to maintain a binary search tree in a near optimal form, assuming that elements are requested with fixed, but unknown, independent probabilities. A "move to root" heuristic is shown to yield an expected search time within a constant factor of that of an optimal static binary search tree. On the other hand, a closely related "simple exchange" technique is shown not to have this property. The rate of convergence of the "move to root" heuristic is discussed. We also consider the more general case in which elements not in the tree may have non-zero probability of being requested.

In this paper the problem of sorting multisets is considered. An information theoretic lower bound on the number of three branch comparisons is obtained, and it is shown that this bound is asymptotically attainable. It is shown that the multiplicities of a set can only be obtained by comparisons if the total order is discovered in the process. A lower bound on finding the mode of a multiset as a function of the actual multiplicity is given, and it is demonstrated that the bound can be achieved to within a multiplicative constant. The determination of the intersection of two multisets is also discussed, and partial results, including a generalization of Reingold’s result for determining whether or not two sets have a nonempty intersection, are obtained.

Computational Complexity is concerned with how difficult, under some measure of difficulty, it is to evaluate certain functions or classes of functions. Most of the work in this area, however, deals with models of computation quite unlike a stored program computer, and functions very different from those which are actually computed. In this paper we turn our attention to techniques of computing some useful functions on “computer-like” devices in optimal or near optimal ways.