J. Ian Munro

TCS Journal 2025 Journal Article

Succinct encodings of binary trees with application to AVL trees

• Jeremy Chizewer
• Stephen Melczer
• J. Ian Munro
• Ava Pun

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.

I&C Journal 2021 Journal Article

On the cost of unsuccessful searches in search trees with two-way comparisons

• Marek Chrobak
• Mordecai Golin
• J. Ian Munro
• Neal E. Young

Search trees are commonly used to implement access operations to a set of stored keys. If this set is static and the probabilities of membership queries are known in advance, then one can precompute an optimal search tree, namely one that minimizes the expected access cost. For a non-key query, a search tree can determine its approximate location by returning the inter-key interval containing the query. This is in contrast to other dictionary data structures, like hash tables, that only report a failed search. We address the question “what is the additional cost of determining approximate locations for non-key queries”? We prove that for two-way comparison trees this additional cost is at most 1. Our proof is based on a novel probabilistic argument that involves converting a search tree that does not identify non-key queries into a random tree that does.

TCS Journal 2020 Journal Article

Ranked document selection

• J. Ian Munro
• Gonzalo Navarro
• Rahul Shah
• Sharma V. Thankachan

Let D be a collection of string documents of n characters in total. The top-k document retrieval problem is to preprocess D into a data structure that, given a query ( P, k ), can return the k documents of D most relevant to pattern P. The relevance of a document d for a pattern P is given by a predefined ranking function w ( P, d ). Linear space and optimal query time solutions already exist for this problem. In this paper we consider a novel problem, document selection, in which a query ( P, k ) aims to report the kth document most relevant to P (instead of reporting all top-k documents). We present a data structure using O ( n log ϵ ⁡ n ) space, for any constant ϵ > 0, answering selection queries in time O ( log ⁡ k / log ⁡ log ⁡ n ), and a linear-space data structure answering queries in time O ( log ⁡ k ), given the locus node of P in a (generalized) suffix tree of D. We also prove that it is unlikely that a succinct-space solution for this problem exists with poly-logarithmic query time, and that O ( log ⁡ k / log ⁡ log ⁡ n ) is indeed optimal within O ( n polylog n ) space for most text families. Finally, we present some additional space-time trade-offs exploring the extremes of those lower bounds.

SODA Conference 2018 Conference Paper

Time and Space Efficient Representations of Distributive Lattices

• J. Ian Munro
• Corwin Sinnamon

TCS Journal 2017 Journal Article

Finding modes with equality comparisons

• Varukumar Jayapaul
• J. Ian Munro
• Venkatesh Raman
• Srinivas Rao Satti

We consider the comparison complexity of finding modes (the most frequently occurring elements) in a list of elements that are not necessarily from a totally ordered set. Here, the relation between elements is determined by equality comparisons whose outcome is = when the two elements being compared are equal, and ≠ otherwise. The problem generalizes the classical majority problem studied in this model (using equalities). We show that n 2 / 2 m − n / 2 comparisons are necessary and n 2 / m + n comparisons are sufficient to find an element that appears at least m times. This is in sharp contrast to the bound of Θ ( n log ⁡ ( n / m ) ) bound in the model where comparisons are <, =, > or ≤, >. We give three algorithms for finding mode, including one that is a generalization of a classical majority finding algorithm due to Fischer and Salzberg (1982) [9]. We also discuss upper and lower bounds for sorting (i. e. , finding the frequency of every element) and for finding the least frequent element. Sorting problem (under the equality comparisons) also known as equivalence class sorting, has applications in several scenarios where the total order of elements is either not possible or can not be revealed for security reasons.

SODA Conference 2017 Conference Paper

Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time

• J. Ian Munro
• Gonzalo Navarro 0001
• Yakov Nekrich

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.

TCS Journal 2016 Journal Article

Document retrieval with one wildcard

• Moshe Lewenstein
• J. Ian Munro
• Yakov Nekrich
• Sharma V. Thankachan

In this paper we extend several well-known document listing problems to the case when documents contain a substring that approximately matches the query pattern. We study the scenario when the query string can contain a wildcard symbol that matches any alphabet symbol; all documents that match a query pattern with one wildcard must be enumerated. We describe a linear space data structure that reports all documents containing a substring P in O ( | P | + σ log ⁡ log ⁡ log ⁡ n + docc ) time, where σ is the alphabet size and docc is the number of listed documents. We also describe a succinct solution for this problem, as well as a solution for an extension of this problem. Furthermore our approach enables us to obtain an O ( n σ ) -space data structure that enumerates all documents containing both a pattern P 1 and a pattern P 2 in the special case when P 1 and P 2 differ in one symbol.

TCS Journal 2016 Journal Article

Dynamic range majority data structures

• Amr Elmasry
• Meng He
• J. Ian Munro
• Patrick K. Nicholson

Given a set P of n coloured points on the real line, we study the problem of answering range α-majority (or “heavy hitter”) queries on P. More specifically, for a query range Q, we want to return each colour that is assigned to more than an α-fraction of the points contained in Q. We present a new data structure for answering range α-majority queries on a dynamic set of points, where α ∈ ( 0, 1 ). Our data structure uses O ( n ) space, supports queries in O ( ( lg ⁡ n ) / α ) time, and updates in O ( ( lg ⁡ n ) / α ) amortized time. If the coordinates of the points are integers, then the query time can be improved to O ( lg ⁡ n / ( α lg ⁡ lg ⁡ n ) ). For constant values of α, this improved query time matches an existing lower bound, for any data structure with polylogarithmic update time. We also generalize our data structure to handle sets of points in d dimensions, for d ≥ 2, as well as dynamic arrays, in which each entry is a colour.

TCS Journal 2016 Journal Article

Fast construction of wavelet trees

• J. Ian Munro
• Yakov Nekrich
• Jeffrey S. Vitter

In this paper we describe a fast algorithm that creates a wavelet tree for a sequence of symbols. We show that a wavelet tree can be constructed in O ( n ⌈ log ⁡ σ / log ⁡ n ⌉ ) time where n is the number of symbols and σ is the alphabet size.

TCS Journal 2016 Journal Article

Permuted scaled matching

• Ayelet Butman
• Noa Lewenstein
• J. Ian Munro

Scaled matching and permutation matching are two well known paradigms in the domain of pattern matching. Scaled matching refers to finding an occurrence of a pattern which is enlarged proportionally by some scale k within a larger text. Permutation matching is the problem of finding all substrings within a text where the character statistics of the substring and the pattern are the same. Permutation matching is easy, while scaled matching requires innovative solutions. One interesting setting of applications is the merge of the two. The problem of scaled permuted matching (i. e. first permuting and then scaling) has been addressed and solved optimally. However, it was left as an open problem whether there are efficient algorithms for permuted scaled matching. In this paper we solve the problem efficiently in a deterministic setting and optimally in a randomized setting.

TCS Journal 2015 Journal Article

Finding median in read-only memory on integer input

• Timothy M. Chan
• J. Ian Munro
• Venkatesh Raman

Starting with Munro and Paterson (1980) [13], the selection or median-finding problem has been extensively studied in the read-only memory model and in streaming models. Munro and Paterson's deterministic algorithm and its subsequent refinements require at least polylogarithmic or logarithmic space, whereas the algorithms by Munro and Raman (1996) [14] and Raman and Ramnath (1999) [15] can be made to use just O ( 1 ) storage cells but take O ( n 1 + ε ) time for an arbitrarily small constant ε > 0. In this paper, we initiate the first study on this problem when the input is a sequence of integers. We show that faster selection algorithms in read-only memory are possible if the input is a sequence of integers. For example, one of our algorithms uses O ( 1 ) storage cells and takes O ( n lg ⁡ U ) 1 time where U is the universe size. Another algorithm uses O ( 1 ) storage cells and takes O ( n lg ⁡ n lg ⁡ lg ⁡ U ) time. A combination of the two yields an algorithm that uses O ( 1 ) words of space and takes O ( n lg 1 + ϵ ⁡ n ) time, a bound independent of U. We also describe an O ( n ) -time algorithm for finding an approximate median using O ( lg ε ⁡ U ) storage cells. All our algorithms are simple and deterministic. Interestingly, one of our algorithms is inspired by ‘centroids’ of binary trees and finds an approximate median by repeatedly invoking a textbook algorithm for the ‘majority’ problem. This technique could be of independent interest.

TCS Journal 2015 Journal Article

Low space data structures for geometric range mode query

• Stephane Durocher
• Hicham El-Zein
• J. Ian Munro
• Sharma V. Thankachan

Let S be a set of n points in d dimensions such that each point is assigned a color. Given a query range Q = [ a 1, b 1 ] × [ a 2, b 2 ] × … × [ a d, b d ], the geometric range mode query problem asks to report the most frequent color (i. e. , a mode) of the multiset of colors corresponding to points in S ∩ Q. When d = 1, Chan et al. (2012) [1] gave a data structure that requires O ( n + ( n / Δ ) 2 / w ) words and supports range mode queries in O ( Δ ) time for any Δ ≥ 1, where w = Ω ( log ⁡ n ) is the word size. Chan et al. also proposed a data structures for higher dimensions (i. e. , d ≥ 2 ) with O ( s n + ( n / Δ ) 2 d ) words and O ( Δ ⋅ t n ) query time, where s n and t n denote the space and query time of a data structure that supports orthogonal range counting queries on the set S. In this paper we show that the space can be improved without any increase to the query time, by presenting an O ( s n + ( n / Δ ) 2 d / w ) -word data structure that supports orthogonal range mode queries on a set of n points in d dimensions in O ( Δ ⋅ t n ) time, for any Δ ≥ 1. When d = 1, these space and query time costs match those achieved by the current best known one-dimensional data structure.

TCS Journal 2015 Journal Article

On hardness of several string indexing problems

• Kasper Green Larsen
• J. Ian Munro
• Jesper Sindahl Nielsen
• Sharma V. Thankachan

Let D = { d 1, d 2, …, d D } be a collection of D string documents of n characters in total. The two-pattern matching problems ask to index D for answering the following queries efficiently. • Report/count the unique documents containing P 1 and P 2. • Report/count the unique documents containing P 1, but not P 2. Here P 1 and P 2 represent input patterns of length p 1 and p 2 respectively. Linear space data structures with O ( p 1 + p 2 + n k log O ( 1 ) ⁡ n ) query cost are already known for the reporting version, where k represents the output size. For the counting version (i. e. , report the value k), a simple linear-space index with O ( p 1 + p 2 + n ) query cost can be constructed in O ( n 3 / 2 ) time. However, it is still not known if these are the best possible bounds for these problems. In this paper, we show a strong connection between these string indexing problems and the boolean matrix multiplication problem. Based on this, we argue that these results cannot be improved significantly using purely combinatorial techniques. We also provide an improved upper bound for a related problem known as common colors query problem.

TCS Journal 2014 Journal Article

Less space: Indexing for queries with wildcards

• Moshe Lewenstein
• J. Ian Munro
• Venkatesh Raman
• Sharma V. Thankachan

Text indexing is a fundamental problem in computer science, where the task is to index a given text (string) T [ 1. . n ], such that whenever a pattern P [ 1. . p ] comes as a query, we can efficiently report all those locations where P occurs as a substring of T. In this paper, we consider the case when P contains wildcard characters (which can match with any other character). The first non-trivial solution for the problem was given by Cole et al. [11], where the index space is O ( n log k ⁡ n ) words or O ( n log k + 1 ⁡ n ) bits and the query time is O ( p + 2 h log ⁡ log ⁡ n + occ ), where k is the maximum number of wildcard characters allowed in P, h ≤ k is the number of wildcard characters in P and occ represents the number of occurrences of P in T. Even though many indexes offering different space-time trade-offs were later proposed, a clear improvement on this result is still not known. In this paper, we first propose an O ( n log k + ϵ ⁡ n ) bits index achieving the same query time as the of Cole et al. 's index, where 0 < ϵ < 1 is an arbitrary small constant. Then we propose another index of size O ( n log k ⁡ n log ⁡ σ ) bits, but with a slightly higher query time of O ( p + 2 h log ⁡ n + occ ), where σ denotes the alphabet set size. We also study a related problem, where the task is to index a collection of documents (of n characters in total) so as to find the number of distinct documents containing a query pattern P. For the case where P contains at most a single wildcard character, we propose an O ( n log ⁡ n ) -word index with optimal O ( p ) query time.

SODA Conference 2014 Conference Paper

Selection and Sorting in the "Restore" Model

• Timothy M. Chan
• J. Ian Munro
• Venkatesh Raman 0001

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 (lg n ) words 1 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 Ω( 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. 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.

I&C Journal 2013 Journal Article

Range majority in constant time and linear space

• Stephane Durocher
• Meng He
• J. Ian Munro
• Patrick K. Nicholson
• Matthew Skala

Given an array A of size n, we consider the problem of answering range majority queries: given a query range [ i. . j ] where 1 ⩽ i ⩽ j ⩽ n, return the majority element of the subarray A [ i. . j ] if it exists. We describe a linear space data structure that answers range majority queries in constant time. We further generalize this problem by defining range α-majority queries: given a query range [ i. . j ], return all the elements in the subarray A [ i. . j ] with frequency greater than α ( j − i + 1 ). We prove an upper bound on the number of α-majorities that can exist in a subarray, assuming that query ranges are restricted to be larger than a given threshold. Using this upper bound, we generalize our range majority data structure to answer range α-majority queries in O ( 1 α ) time using O ( n lg ( 1 α + 1 ) ) space, for any fixed α ∈ ( 0, 1 ). This result is interesting since other similar range query problems based on frequency have nearly logarithmic lower bounds on query time when restricted to linear space.

TCS Journal 2013 Journal Article

Succinct encoding of arbitrary graphs

• Arash Farzan
• J. Ian Munro

We consider the problem of encoding graphs with n vertices and m edges compactly supporting adjacency, neighborhood and degree queries in constant time in the Θ ( log n ) -bit word RAM model. The adjacency query asks whether there is an edge between two vertices, the neighborhood query reports the neighbors of a given vertex in constant time per neighbor, and the degree query reports the number of incident edges to a given vertex. We study the problem in the context of succinctness, where the goal is to achieve the optimal space requirement as a function of n and m, to within lower order terms. We prove a lower bound in the cell probe model indicating it is impossible to achieve the information-theory lower bound up to lower order terms unless the graph is either too sparse (namely, m = o ( n δ ) for any constant δ > 0 ) or too dense (namely m = ω ( n 2 − δ ) for any constant δ > 0 ). Furthermore, we present a succinct encoding of graphs supporting aforementioned queries in constant time. The space requirement of the encoding is within a multiplicative 1 + ϵ factor of the information-theory lower bound for any arbitrarily small constant ϵ > 0. This is the best achievable space bound according to our lower bound where it applies. The space requirement of the representation achieves the information-theory lower bound tightly within lower order terms where the graph is very sparse ( m = o ( n δ ) for any constant δ > 0 ), or very dense ( m > n 2 / lg 1 − δ n for an arbitrarily small constant δ > 0 ).

TCS Journal 2012 Journal Article

Succinct representations of permutations and functions

• J. Ian Munro
• Rajeev Raman
• Venkatesh Raman
• Srinivasa Rao S.

We investigate the problem of succinctly representing an arbitrary permutation, π, on { 0, …, n − 1 } so that π k ( i ) can be computed quickly for any i and any (positive or negative) integer power k. A representation taking ( 1 + ϵ ) n lg n + O ( 1 ) bits suffices to compute arbitrary powers in constant time, for any positive constant ϵ ≤ 1. A representation taking the optimal ⌈ lg n! ⌉ + o ( n ) bits can be used to compute arbitrary powers in O ( lg n / lg lg n ) time. We then consider the more general problem of succinctly representing an arbitrary function, f: [ n ] → [ n ] so that f k ( i ) can be computed quickly for any i and any integer power k. We give a representation that takes ( 1 + ϵ ) n lg n + O ( 1 ) bits, for any positive constant ϵ ≤ 1, and computes arbitrary positive powers in constant time. It can also be used to compute f k ( i ), for any negative integer k, in optimal O ( 1 + ∣ f k ( i ) ∣ ) time. We place emphasis on the redundancy, or the space beyond the information-theoretic lower bound that the data structure uses in order to support operations efficiently. A number of lower bounds have recently been shown on the redundancy of data structures. These lower bounds confirm the space–time optimality of some of our solutions. Furthermore, the redundancy of one of our structures “surpasses” a recent lower bound by Golynski [Golynski, SODA 2009], thus demonstrating the limitations of this lower bound.

TCS Journal 2011 Journal Article

Succinct representation of dynamic trees

• Arash Farzan
• J. Ian Munro

We study the problem of maintaining a dynamic ordered tree succinctly under updates of the following form: insertion or deletion of a leaf, insertion of a node on an edge (edge subdivision) or deletion of a node with only one child (the child becomes a child of its former grandparent). We allow satellite data of a fixed size to be associated to the nodes of the tree. We support update operations in constant amortized time and support access to satellite data and basic navigation operations in worst-case constant time; the basic navigation operations include parent, first/last-child, previous/next-child. These operations are moving from a node to its parent, leftmost/rightmost child, and its previous and next child respectively. We demonstrate that to efficiently support more extended operations, such as determining the i -th child of a node, rank of a child among its siblings, or size of the subtree rooted at a node, one requires a restrictive pattern for update strategy, for which we propose the finger-update model. In this model, updates are performed at the location of a finger that is only allowed to crawl on the tree between a child and a parent or between consecutive siblings. Under this model, we describe how the named extended operations are performed in worst-case constant time. Previous work on dynamic succinct trees (Munro et al. , 2001 [17]; Raman and Rao, 2003 [19]) is mainly restricted to binary trees and achieves poly-logarithmic (Munro et al. , 2001 [17]) or “poly-log–log” (Raman and Rao, 2003 [19]) update time under a more restricted model, where updates are performed in traversals starting at the root and ending at the root and queries can be answered when the traversal is completed. A previous result on ordinal trees achieves only sublinear amortized update time and “poly-log–log” query time (Gupta et al. , 2007 [11]). More recently, the update time has been improved to O ( log n / log log n ) while queries can be performed in O ( log n / log log n ) time (Sadakane and Navarro, 2010 [20]).

TCS Journal 2011 Journal Article

Untangled monotonic chains and adaptive range search

• Diego Arroyuelo
• Francisco Claude
• Reza Dorrigiv
• Stephane Durocher
• Meng He
• Alejandro López-Ortiz
• J. Ian Munro
• Patrick K. Nicholson

We present the first adaptive data structure for two-dimensional orthogonal range search. Our data structure is adaptive in the sense that it gives improved search performance for data that is better than the worst case (Demaine et al. , 2000) [8]; in this case, data with more inherent sortedness. Given n points on the plane, the linear space data structure can answer range queries in O ( log n + k + m ) time, where m is the number of points in the output and k is the minimum number of monotonic chains into which the point set can be decomposed, which is O ( n ) in the worst case. Our result matches the worst-case performance of other optimal-time linear space data structures, or surpasses them when k = o ( n ). Our data structure can be made implicit, requiring no extra space beyond that of the data points themselves (Munro and Suwanda, 1980) [16], in which case the query time becomes O ( k log n + m ). We also present a novel algorithm of independent interest to decompose a point set into a minimum number of untangled, similarly directed monotonic chains in O ( k 2 n + n log n ) time.

SODA Conference 2010 Conference Paper

Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs

• Gerth Stølting Brodal
• Erik D. Demaine
• Jeremy T. Fineman
• John Iacono
• Stefan Langerman
• J. Ian Munro

STOC Conference 2010 Conference Paper

Sorting under partial information (without the ellipsoid algorithm)

• Jean Cardinal
• Samuel Fiorini
• Gwenaël Joret
• Raphaël M. Jungers
• J. Ian Munro

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 develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n 2 ) algorithm performing O(log n ⋅ log e(P)) comparisons; an O(n 2.5 ) algorithm performing at most (1+ε) log e(P) + O ε(n) comparisons; an O(n 2.5 ) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement.

STOC Conference 2009 Conference Paper

An efficient algorithm for partial order production

• Jean Cardinal
• Samuel Fiorini
• Gwenaël Joret
• Raphaël M. Jungers
• J. Ian Munro

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 of this problem include sorting by comparisons, selection, multiple selection, and heap construction.

TCS Journal 2009 Journal Article

On the relative dominance of paging algorithms

• Reza Dorrigiv
• Alejandro López-Ortiz
• J. Ian Munro

In this paper, we give a finer separation of several known paging algorithms using a new technique called relative interval analysis. This technique compares the fault rate of two paging algorithms across the entire range of inputs of a given size, rather than in the worst case alone. Using this technique, we characterize the relative performance of LRU and LRU-2, as well as LRU and FWF, among others. We also show that look-ahead is beneficial for a paging algorithm, a fact that is well known in practice but it was, until recently, not verified by theory.

TCS Journal 2007 Journal Article

Adaptive searching in succinctly encoded binary relations and tree-structured documents

• Jérémy Barbay
• Alexander Golynski
• J. Ian Munro
• S. Srinivasa Rao

The methods most heavily used by search engines to answer conjunctive queries on binary relations (such as one associating keywords with web-pages) are based on computing the intersection of postings lists stored as sorted arrays and using variants of binary search. We show that a succinct representation of the binary relation permits much better results, while using less space than traditional methods. We apply our results not only to conjunctive queries on binary relations, but also to queries on semi-structured documents such as XML documents or file-system indexes, using a variant of an adaptive algorithm used to solve conjunctive queries on binary relations.

SODA Conference 2007 Conference Paper

Succinct indexes for strings, binary relations and multi-labeled trees

• Jérémy Barbay
• Meng He 0001
• J. Ian Munro
• Srinivasa Rao Satti

SODA Conference 2006 Conference Paper

Implicit dictionaries with O (1) modifications per update and fast search

• Gianni Franceschini
• J. Ian Munro

TCS Journal 2006 Journal Article

Preface

• Kyung-Yong Chwa
• J. Ian Munro

SODA Conference 2006 Conference Paper

Rank/select operations on large alphabets: a tool for text indexing

• Alexander Golynski
• J. Ian Munro
• Srinivasa Rao Satti

TCS Journal 2006 Journal Article

The binomial transform and the analysis of skip lists

• Patricio V. Poblete
• J. Ian Munro
• Thomas Papadakis

To any sequence of real numbers 〈 a n 〉 n ⩾ 0, we can associate another sequence 〈 a ^ s 〉 s ⩾ 0, which Knuth calls its binomial transform. This transform is defined through the rule a ^ s = B s a n = ∑ n ( - 1 ) n s n a n. We study the properties of this transform, obtaining rules for its manipulation and a table of transforms, that allow us to invert many transforms by inspection. We use these methods to perform a detailed analysis of skip lists, a probabilistic data structure introduced by Pugh as an alternative to balanced trees. In particular, we obtain the mean and variance for the cost of searching for the first or the last element in the list (confirming results obtained previously by other methods), and also for the cost of searching for a random element (whose variance was not known). We obtain exact solutions, although not always in closed form. From them we are able to find the corresponding asymptotic expressions.

SODA Conference 2005 Conference Paper

A categorization theorem on suffix arrays with applications to space efficient text indexes

• Meng He 0001
• J. Ian Munro
• Srinivasa Rao Satti

STOC Conference 2002 Conference Paper

Cache-oblivious priority queue and graph algorithm applications

• Lars Arge
• Michael A. Bender
• Erik D. Demaine
• Bryan Holland-Minkley
• J. Ian Munro

(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 log M/B N \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.

FOCS Conference 2002 Conference Paper

Implicit B-Trees: New Results for the Dictionary Problem

• Gianni Franceschini
• Roberto Grossi
• J. Ian Munro
• Linda Pagli

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.

SODA Conference 2001 Conference Paper

On universally easy classes for NP-complete problems

• Erik D. Demaine
• Alejandro López-Ortiz
• J. Ian Munro

SODA Conference 2001 Conference Paper

Representing dynamic binary trees succinctly

• J. Ian Munro
• Venkatesh Raman 0001
• Adam J. Storm

SODA Conference 2001 Conference Paper

Worst case constant time priority queue

• Andrej Brodnik
• Svante Carlsson
• Johan Karlsson 0003
• J. Ian Munro

SODA Conference 2000 Conference Paper

Adaptive set intersections, unions, and differences

• Erik D. Demaine
• Alejandro López-Ortiz
• J. Ian Munro

FOCS Conference 1997 Conference Paper

Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs

• J. Ian Munro
• Venkatesh Raman 0001

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.

SODA Conference 1996 Conference Paper

Efficient Suffix Trees on Secondary Storage (extended Abstract)

• David R. Clark
• J. Ian Munro

SODA Conference 1992 Conference Paper

Deterministic Skip Lists

• J. Ian Munro
• Thomas Papadakis
• Robert Sedgewick

I&C Journal 1991 Journal Article

Fringe analysis for Extquick: Anin situ distributive external sorting algorithm

• Walter Cunto
• Gasto´n H. Gonnet
• J. Ian Munro
• Patricio V. Poblete

A newin situ external sorting algorithm, to be calledExtquick, is developed and its time and space performance are analysed. It is shown that Extquick performs more efficiently than similarin situ sorting algorithms based on Quicksort that appear in the literature. Since the computational tree of Quicksort-like sorting algorithms is equivalent to a search tree, techniques that model the time complexity of such a structure are then used for the analysis of Extquick.

FOCS Conference 1990 Conference Paper

Permuting

• Faith Ellen
• J. Ian Munro
• Patricio V. Poblete

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. >

STOC Conference 1987 Conference Paper

Searching a Two Key Table Under a Single Key

• J. Ian Munro

MFCS Conference 1986 Invited Paper

Developing Implicit Data Structures

• J. Ian Munro

Abstract We present a new, and basically simple, algorithm for maintaining a structure supporting insert, delete and search in O(log 2 n ) with no storage requirements other than that of the data itself.

FOCS Conference 1985 Conference Paper

Robin Hood Hashing (Preliminary Report)

• Pedro Celis
• Per-Åke Larson
• J. Ian Munro

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).

FOCS Conference 1984 Conference Paper

An Implicit Data Structure for the Dictionary Problem that Runs in Polylog Time

• J. Ian Munro

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.

STOC Conference 1984 Conference Paper

Average Case Selection

• Walter Cunto
• J. Ian Munro

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. 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.

STOC Conference 1981 Conference Paper

A Linear Probing Sort and its Analysis (Preliminary Draft)

• Gaston H. Gonnet
• J. Ian Munro

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.

MFCS Conference 1981 Conference Paper

Partial Match Retrieval in Implicit Data Structures

• Helmut Alt
• Kurt Mehlhorn
• J. Ian Munro

FOCS Conference 1980 Conference Paper

Efficient Uses of the Past

• David P. Dobkin
• J. Ian Munro

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.

STOC Conference 1979 Conference Paper

Implicit Data Structures (Preliminary Draft)

• J. Ian Munro
• Hendra Suwanda

We consider representations of data structures in which the relative ordering of the values stored is implicit in the pattern in which the elements are retained, rather than explicit in pointers. Several implicit schemes for storing data are introduced to permit efficient implementation of the instructions insert, delete and find . θ(@@@@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.

FOCS Conference 1979 Conference Paper

Toward Self-Organizing Linear Search (Preliminary Draught)

• Gaston H. Gonnet
• J. Ian Munro
• Hendra Suwanda

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.

FOCS Conference 1978 Conference Paper

Selection and Sorting with Limited Storage

• J. Ian Munro
• Mike Paterson

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.

STOC Conference 1977 Conference Paper

The Analysis of an Improved Hashing Technique

• Gaston H. Gonnet
• J. Ian Munro

FOCS Conference 1976 Conference Paper

Self-Organizing Binary Search Trees

• Brian Allen
• J. Ian Munro

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.

STOC Conference 1971 Conference Paper

Some Results Concerning Efficient and Optimal Algorithms

• J. Ian Munro

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.