Arrow Research search

Author name cluster

Gerth Stølting Brodal

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

28 papers
2 author rows

Possible papers

28

TCS Journal 2025 Journal Article

Bottom-up rebalancing binary search trees by flipping a coin

  • Gerth Stølting Brodal

Rebalancing schemes for dynamic binary search trees are numerous in the literature, where the goal is to maintain trees of low height, either in the worst-case or expected sense. In this paper we study randomized rebalancing schemes for sequences of n insertions into an initially empty binary search tree, under the assumption that a tree only stores the elements and the tree structure without any additional balance information. Seidel (2009) presented a top-down randomized insertion algorithm, where insertions take expected O ( lg 2 n ) time, and the resulting trees have the same distribution as inserting a uniform random permutation of n elements into a binary search tree without rebalancing. Seidel states as an open problem if a similar result can be achieved with bottom-up insertions. In this paper we fail to answer this question. We consider two simple canonical randomized bottom-up insertion algorithms on binary search trees, assuming that an insertion is given the position where to insert the next element. The subsequent rebalancing is performed bottom-up in expected O ( 1 ) time, uses expected O ( 1 ) random bits, performs at most two rotations, and the rotations appear with geometrically decreasing probability in the distance from the leaf. For some insertion sequences the expected depth of each node is proved to be O ( lg n ). On the negative side, we prove for both algorithms that there exist simple insertion sequences where the expected depth is Ω ( n ), i. e. , the studied rebalancing schemes are not competitive with (most) other rebalancing schemes in the literature.

Details DOI

TCS Journal 2024 Journal Article

Priority queues with decreasing keys

  • Gerth Stølting Brodal

A priority queue stores a multiset of items, each item being a 〈 key, value 〉 pair, and supports the insertion of a new item and extraction of an item with minimum key. In applications like Dijkstra's single source shortest path algorithm and Prim-Jarník's minimum spanning tree algorithm, the key of an item can decrease over time. Usually this is handled by either using a priority queue supporting the deletion of an arbitrary item or a dedicated DecreaseKey operation, or by inserting the same item multiple times but with decreasing keys. In this paper we study what happens if the keys associated with the items in a priority queue can decrease over time without informing the priority queue, and how such a priority queue can be used in Dijkstra's algorithm. We show that binary heaps with bottom-up insertions fail to report items with unchanged keys in correct order, while binary heaps with top-down insertions report items with unchanged keys in correct order. Furthermore, we show that skew heaps, leftist heaps, and priority queues based on linking the roots of heap-ordered trees, like pairing heaps, binomial queues and Fibonacci heaps, work correctly with decreasing keys without any modifications. Finally, we show that the post-order heap by Harvey and Zatloukal, a variant of a binary heap with amortized constant time insertions and amortized logarithmic time deletions, works correctly with decreasing keys and is a strong contender for an implicit priority queue supporting decreasing keys in practice.

Details DOI

TCS Journal 2020 Journal Article

Fully persistent B-trees

  • Gerth Stølting Brodal
  • Spyros Sioutas
  • Konstantinos Tsakalidis
  • Kostas Tsichlas

We present efficient fully persistent B-trees in the I/O model with block size B that support range searches on t reported elements at any accessed version of size n in O ( log B ⁡ n + t / B ) I/Os and updates at any accessed version in O ( log B ⁡ n + log 2 ⁡ B ) amortized I/Os, using O ( m / B ) disk blocks after m updates. This improves both the query and update I/O-efficiency of the previous fully persistent B-trees of Lanka and Mays (ACM SIGMOD ICMD 1991). To achieve the result, we introduce an implementation for ephemeral B-trees that supports searches and updates in O ( log B ⁡ n ) I/Os, using O ( n / B ) blocks, where moreover every update makes a worst-case constant number of modifications to the structure. We make these B-trees fully persistent using an I/O-efficient method for full persistence, inspired by the node-splitting method of Driscoll et al. (JCSS 1989). Interesting in its own right, the method is generic enough to be applied to any external memory pointer-based data structure with maximum in-degree d i n and out-degree O ( B ), where every node occupies a constant number of blocks on disk. For a user-specified parameter π = Ω ( d i n ), we achieve O ( π B + log 2 ⁡ π ) I/O-overhead per access to a field of an ephemeral block and amortized O ( π B + log 2 ⁡ π + d i n π log 2 ⁡ B ) I/O-overhead and O ( 1 / B ) block space-overhead per modification to the ephemeral structure.

Details DOI

TCS Journal 2016 Journal Article

Two dimensional range minimum queries and Fibonacci lattices

  • Gerth Stølting Brodal
  • Pooya Davoodi
  • Moshe Lewenstein
  • Rajeev Raman
  • Srinivasa Rao Satti

Given a matrix of size N, two dimensional range minimum queries (2D-RMQs) ask for the position of the minimum element in a rectangular range within the matrix. We study trade-offs between the query time and the additional space used by indexing data structures that support 2D-RMQs. Using a novel technique—the discrepancy properties of Fibonacci lattices—we give an indexing data structure for 2D-RMQs that uses O ( N / c ) bits additional space with O ( c log ⁡ c ( log ⁡ log ⁡ c ) 2 ) query time, for any parameter c, 4 ≤ c ≤ N. Also, when the entries of the input matrix are from { 0, 1 }, we show that the query time can be improved to O ( c log ⁡ c ) with the same space usage.

Details DOI

TCS Journal 2014 Journal Article

Dynamic 3-sided planar range queries with expected doubly-logarithmic time

  • Gerth Stølting Brodal
  • Alexis C. Kaporis
  • Apostolos N. Papadopoulos
  • Spyros Sioutas
  • Konstantinos Tsakalidis
  • Kostas Tsichlas

The Priority Search Tree is the classic solution for the problem of dynamic 2-dimensional searching for the orthogonal query range of the form [ a, b ] × ( − ∞, c ] (3-sided rectangle). It supports all operations in logarithmic worst case complexity in both main and external memory. In this work we show that the update and query complexities can be improved to expected doubly-logarithmic, when the input coordinates are being continuously drawn from specific probability distributions. We present three pairs of linear space solutions for the problem, i. e. a RAM and a corresponding I/O model variant: (1) First, we improve the update complexity to doubly-logarithmic expected with high probability, under the most general assumption that both the x- and y-coordinates of the input points are continuously being drawn from a distribution whose density function is unknown but fixed. (2) Next, we improve both the query complexity to doubly-logarithmic expected with high probability and the update complexity to doubly-logarithmic amortized expected, by assuming that only the x-coordinates are being drawn from a class of smooth distributions, and that the deleted points are selected uniformly at random among the currently stored points. In fact, the y-coordinates are allowed to be arbitrarily distributed. (3) Finally, we improve both the query and the update complexity to doubly-logarithmic expected with high probability by moreover assuming the y-coordinates to be continuously drawn from a more restricted class of realistic distributions. All data structures are deterministic and their complexity's expectation is with respect to the assumed distributions. They comprise combinations of known data structures and of two new data structures introduced here, namely the Weight Balanced Exponential Tree and the External Modified Priority Search Tree.

Details DOI

SODA Conference 2013 Conference Paper

Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree

  • Gerth Stølting Brodal
  • Rolf Fagerberg
  • Thomas Mailund
  • Christian N. S. Pedersen
  • Andreas Sand

The triplet and quartet distances are distance measures to compare two rooted and two unrooted trees, respectively. The leaves of the two trees should have the same set of n labels. The distances are defined by enumerating all subsets of three labels (triplets) and four labels (quartets), respectively, and counting how often the induced topologies in the two input trees are different. In this paper we present efficient algorithms for computing these distances. We show how to compute the triplet distance in time O ( n log n ) and the quartet distance in time O ( dn log n ), where d is the maximal degree of any node in the two trees. Within the same time bounds, our framework also allows us to compute the parameterized triplet and quartet distances, where a parameter is introduced to weight resolved (binary) topologies against unresolved (non-binary) topologies. The previous best algorithm for computing the triplet and parameterized triplet distances have O ( n 2 ) running time, while the previous best algorithms for computing the quartet distance include an O ( d 9 n log n ) time algorithm and an O ( n 2. 688 ) time algorithm, where the latter can also compute the parameterized quartet distance. Since d ≤ n, our algorithms improve on all these algorithms.

Details

SODA Conference 2012 Conference Paper

Fully persistent B-trees

  • Gerth Stølting Brodal
  • Konstantinos Tsakalidis
  • Spyros Sioutas
  • Kostas Tsichlas

We present I/O-efficient fully persistent B-Trees that support range searches at any version in O (log B n + t/B ) I/Os and updates at any version in O (log B n + log 2 B ) amortized I/Os, using space O ( m/B ) disk blocks. By n we denote the number of elements in the accessed version, by m the total number of updates, by t the size of the query's output, and by B the disk block size. The result improves the previous fully persistent B-Trees of Lanka and Mays by a factor of O (log B m ) for the range query complexity and O (log B n ) for the update complexity. To achieve the result, we first present a new B-Tree implementation that supports searches and updates in O (log B n ) I/Os, using O ( n/B ) blocks of space. Moreover, every update makes in the worst case a constant number of modifications to the data structure. We make these B-Trees fully persistent using an I/O-efficient method for full persistence that is inspired by the node-splitting method of Driscoll et al. The method we present is interesting in its own right and can be applied to any external memory pointer based data structure with maximum in-degree d in bounded by a constant and out-degree bounded by O ( B ), where every node occupies a constant number of blocks on disk. The I/O-overhead per modification to the ephemeral structure is O ( d in log 2 B ) amortized I/Os, and the space overhead is O ( d in /B ) amortized blocks. Access to a field of an ephemeral block is supported in O (log 2 d in ) worst case I/Os.

Details

STOC Conference 2012 Conference Paper

Strict fibonacci heaps

  • Gerth Stølting Brodal
  • George Lagogiannis
  • Robert Endre Tarjan

We present the first pointer-based heap implementation with time bounds matching those of Fibonacci heaps in the worst case. We support make-heap, insert, find-min, meld and decrease-key in worst-case O(1) time, and delete and delete-min in worst-case O(lg n) time, where n is the size of the heap. The data structure uses linear space. A previous, very complicated, solution achieving the same time bounds in the RAM model made essential use of arrays and extensive use of redundant counter schemes to maintain balance. Our solution uses neither. Our key simplification is to discard the structure of the smaller heap when doing a meld. We use the pigeonhole principle in place of the redundant counter mechanism.

Details

SODA Conference 2011 Conference Paper

Ordered and Unordered Top-K Range Reporting in Large Data Sets

  • Peyman Afshani
  • Gerth Stølting Brodal
  • Norbert Zeh

We study the following problem: Given an array A storing N real numbers, preprocess it to allow fast reporting of the K smallest elements in the subarray A [ i, j ] in sorted order, for any triple ( i, j, K ) with 1 ≤ i ≤ j ≤ N and 1 ≤ K ≤ j − i + 1. We are interested in scenarios where the array A is large, necessitating an I/O-efficient solution. For a parameter f with 1 ≤ f ≤ log m n, we construct a data structure that uses O(( N/f ) log m n ) space and achieves a query bound of O(log B N + fK/B ) I/Os, 1 where B is the block size, M is the size of the main memory, n: = N/B, and m: = M/B. Our main contribution is to show that this solution is nearly optimal. To be precise, we show that achieving a query bound of O(log α n + fK/B ) I/Os, for any constant α, requires space, assuming B = Ω(log N ). For M ≥ B 1+ε, this is within a log log m n factor of the upper bound. The lower bound assumes indivisibility of records and holds even if we assume K is always set to j − 1 + 1. We also show that it is the requirement that the K smallest elements be reported in sorted order which makes the problem hard. If the K smallest elements in the query range can be reported in any order, then we can obtain a linear-size data structure with a query bound of O(log B N + K/B ) I/Os.

Details

TCS Journal 2011 Journal Article

Towards optimal range medians

  • Gerth Stølting Brodal
  • Beat Gfeller
  • Allan Grønlund Jørgensen
  • Peter Sanders

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O ( n log k + k log n ) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k = O ( n ). The space complexity of our simple algorithm is O ( n log n ) in the pointer machine model, and O ( n ) in the RAM model. In the latter model, a more involved O ( n ) space data structure can be constructed in O ( n log n ) time where the time per query is reduced to O ( log n / log log n ). We also give efficient dynamic variants of both data structures, achieving O ( log 2 n ) query time using O ( n log n ) space in the comparison model and O ( ( log n / log log n ) 2 ) query time using O ( n log n / log log n ) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O ( log O ( 1 ) n ) time must have Ω ( log n / log log n ) query time. Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries.

Details DOI

MFCS Conference 2007 Conference Paper

A Linear Time Algorithm for the k Maximal Sums Problem

  • Gerth Stølting Brodal
  • Allan Grønlund Jørgensen

Abstract Finding the sub-vector with the largest sum in a sequence of n numbers is known as the maximum sum problem. Finding the k sub-vectors with the largest sums is a natural extension of this, and is known as the k maximal sums problem. In this paper we design an optimal O ( n + k ) time algorithm for the k maximal sums problem. We use this algorithm to obtain algorithms solving the two-dimensional k maximal sums problem in O ( m 2 · n + k ) time, where the input is an m × n matrix with m ≤ n. We generalize this algorithm to solve the d -dimensional problem in O ( n 2 d − 1 + k ) time. The space usage of all the algorithms can be reduced to O ( n d − 1 + k ). This leads to the first algorithm for the k maximal sums problem in one dimension using O ( n + k ) time and O ( k ) space.

Details

MFCS Conference 2007 Conference Paper

Dynamic Matchings in Convex Bipartite Graphs

  • Gerth Stølting Brodal
  • Loukas Georgiadis
  • Kristoffer Arnsfelt Hansen
  • Irit Katriel

Abstract We consider the problem of maintaining a maximum matching in a convex bipartite graph G = ( V, E ) under a set of update operations which includes insertions and deletions of vertices and edges. It is not hard to show that it is impossible to maintain an explicit representation of a maximum matching in sub-linear time per operation, even in the amortized sense. Despite this difficulty, we develop a data structure which maintains the set of vertices that participate in a maximum matching in O (log 2 | V |) amortized time per update and reports the status of a vertex (matched or unmatched) in constant worst-case time. Our structure can report the mate of a matched vertex in the maximum matching in worst-case O ( min { k log 2 | V | + log| V |, | V | log| V |}) time, where k is the number of update operations since the last query for the same pair of vertices was made. In addition, we give an \(O(\sqrt{|V|} \log^2{|V|})\) -time amortized bound for this pair query.

Details

FOCS Conference 2006 Conference Paper

Improved Dynamic Planar Point Location

  • Lars Arge
  • Gerth Stølting Brodal
  • Loukas Georgiadis

We develop the first linear-space data structures for dynamic planar point location in general subdivisions that achieve logarithmic query time and poly-logarithmic update time

Details

STOC Conference 2003 Conference Paper

On the limits of cache-obliviousness

  • Gerth Stølting Brodal
  • Rolf Fagerberg

In this paper, we present lower bounds for permuting and sorting in the cache-oblivious model. We prove that (1) I/O optimal cache-oblivious comparison based sorting is not possible without a tall cache assumption, and (2) there does not exist an I/O optimal cache-oblivious algorithm for permuting, not even in the presence of a tall cache assumption.Our results for sorting show the existence of an inherent trade-off in the cache-oblivious model between the strength of the tall cache assumption and the overhead for the case M » B, and show that Funnelsort and recursive binary mergesort are optimal algorithms in the sense that they attain this trade-off.

Details

FOCS Conference 2003 Conference Paper

The Cost of Cache-Oblivious Searching

  • Michael A. Bender
  • Gerth Stølting Brodal
  • Rolf Fagerberg
  • Dongdong Ge
  • Simai He
  • Haodong Hu
  • John Iacono
  • Alejandro López-Ortiz

Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log/sub B/N block transfers between any two levels of the memory hierarchy. This lower bound holds even if all of the block sizes are limited to be powers of 2. A modified version of the van Emde Boas layout is proposed, whose expected block transfers between any two levels of the memory hierarchy arbitrarily close to [lg e + O(lg lg B/ lgB)] logB N + O(1). This factor approaches lg e /spl ap/ 1. 443 as B increases. The expectation is taken over the random placement of the first element of the structure in memory. As searching in the disk access model (DAM) can be performed in log/sub B/N + 1 block transfers, this result shows a separation between the 2-level DAM and cache-oblivious memory-hierarchy models. By extending the DAM model to k levels, multilevel memory hierarchies can be modeled. It is shown that as k grows, the search costs of the optimal k-level DAM search structure and of the optimal cache-oblivious search structure rapidly converge. This demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure.

Details

FOCS Conference 2002 Conference Paper

Dynamic Planar Convex Hull

  • Gerth Stølting Brodal
  • Riko Jacob

In this paper we determine the computational complexity of the dynamic convex hull problem in the planar case. We present a data structure that maintains a finite set of n points in the plane under insertion and deletion of points in amortized O(log n) time per operation. The space usage of the data structure is O(n). The data structure supports extreme point queries in a given direction, tangent queries through a given point, and queries for the neighboring points on the convex hull in O(log n) time. The extreme point queries can be used to decide whether or not a given line intersects the convex hull, and the tangent queries to determine whether a given point is inside the convex hull. We give a lower bound on the amortized asymptotic time complexity that matches the performance of this data structure.

Details

STOC Conference 2001 Conference Paper

Optimal static range reporting in one dimension

  • Stephen Alstrup
  • Gerth Stølting Brodal
  • Theis Rauhe

We consider static one dimensional range searching problems. These problems are to build static data structures for an integer set S \subseteq U , where U = \{0,1,\dots,2^ w -1\}, which support various queries for integer intervals of U . For the query of reporting all integers in S contained within a query interval, we present an optimal data structure with linear space cost and with query time linear in the number of integers reported. This result holds in the unit cost RAM model with word size w and a standard instruction set. We also present a linear space data structure for approximate range counting. A range counting query for an interval returns the number of integers in S contained within the interval. For any constant ε>0, our range counting data structure returns in constant time an approximate answer which is within a factor of at most 1+ε of the correct answer.

Details

FOCS Conference 2000 Conference Paper

New Data Structures for Orthogonal Range Searching

  • Stephen Alstrup
  • Gerth Stølting Brodal
  • Theis Rauhe

We present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R/sup 3/, we achieve query time O(log n+k) using space O(n log/sup 1+/spl epsiv// n), where n denotes the number of stored points and k the number of points to be reported. For the range reporting problem on an n/spl times/n grid, we achieve query time O(log log n+k) using space O(n log/sup /spl epsiv// n). For the two-dimensional semi-group range sum problem we achieve query time O(log n) using space O(n log n).

Details
v2026.09.13