Robert Sedgewick

TCS Journal 2025 Journal Article

Bit-array-based alternatives to HyperLogLog

• Svante Janson
• Jérémie Lumbroso
• Robert Sedgewick

We present a family of algorithms for the problem of estimating the number of distinct items in an input stream that are simple to implement and are appropriate for practical applications. Our algorithms are a logical extension of the series of algorithms developed by Flajolet and his coauthors starting in 1983 that culminated in the widely used HyperLogLog algorithm. These algorithms divide the input stream into M substreams and lead to a time-accuracy tradeoff where a small number of bits per substream are saved to achieve a relative accuracy proportional to 1 / M. Our algorithms use just one or two bits per substream. Their effectiveness is demonstrated by a proof of approximate normality, with explicit expressions for standard errors that inform parameter settings and allow proper quantitative comparisons with other methods. Performance hypotheses are validated through experiments using a realistic input stream, with the general conclusion that our algorithms are significantly more accurate than HyperLogLog when using the same amount of memory, and they use significantly less memory than HyperLogLog to achieve a given accuracy.

SODA Conference 1997 Conference Paper

Fast Algorithms for Sorting and Searching Strings

• Jon Louis Bentley
• Robert Sedgewick

TCS Journal 1995 Journal Article

Mellin transforms and asymptotics: Finite differences and Rice's integrals

• Philippe Flajolet
• Robert Sedgewick

High order differences of simple number sequences may be analysed asymptotically by means of integral representations, residue calculus, and contour integration. This technique, akin to Mellin transform asymptotics, is put in perspective and illustrated by means of several examples related to combinatorics and the analysis of algorithms like digital tries, digital search trees, quadtrees, and distributed leader election.

SODA Conference 1992 Conference Paper

Deterministic Skip Lists

• J. Ian Munro
• Thomas Papadakis
• Robert Sedgewick

FOCS Conference 1984 Conference Paper

Shortest Paths in Euclidean Graphs (Extended Abstract)

• Robert Sedgewick
• Jeffrey Scott Vitter

We analyze a simple method for finding shortest paths in Euclidean graphs (where vertices are points in a Euclidean space and edge weights are distances between points). For many graph models, the running time of the algorithm to find the shortest path between a specified pair of vertices in a graph with V vertices and E edges is shown to be O(V) as compared with O (V log V + E) required by the classical (Dijkstra) algorithm.

FOCS Conference 1983 Conference Paper

Improved Upper Bounds on Shellsort

• Janet Incerpi
• Robert Sedgewick

The running time of Shellsort, with the number of passes restricted to O(log N), was thought for some time to be Θ(N3/2), due to general results of Pratt. Sedgewick recently gave an O(N4/3) bound, but extensions of his method to provide better bounds seem to require new results on a classical problem in number theory. In this paper, we use a different approach to achieve O(N1+4/√2lgN).

STOC Conference 1982 Conference Paper

Notes on Merging Networks (Preliminary Version)

• Zhu Hong
• Robert Sedgewick

STOC Conference 1981 Conference Paper

Lower Bounds for VLSI

• Richard J. Lipton
• Robert Sedgewick

Increased use of Very Large Scale Integration (VLSI) for the fabrication of digital circuits has led to increased interest in complexity results on the inherent VLSI difficulty of various problems. Lower bounds have been obtained for problems such as integer multiplication [1,2], matrix multiplication [7], sorting [8], and discrete Fourier transform [9], all within VLSI models similar to one originally developed by Thompson [8,9]. The lower bound results all pertain to a space-time trade-off measure that arises naturally within this model.

STOC Conference 1979 Conference Paper

The Complexity of Finding Periods

• Robert Sedgewick
• Thomas G. Szymanski

Given a function f over a finite domain D and an arbitrary starting point x , the sequence x,f(x),f(f(x)), ... is ultimately periodic. Such sequences typically are used for constructing random number generators. The cycle problem is to determine the first repeated element f n (x) in the sequence. Previous algorithms for this problem have required 3 n operations. In this paper we present an algorithm which only requires n (1+ O (1/(@@@@) M )) steps, if M memory cells are available to store values of the function. By increasing M , this running time can be made arbitrarily close to the information-theoretic lower bound on the running time of any algorithm for the cycle problem. Our treatment is novel in that we explicitly consider the performance of the algorithm as a function of the amount of memory available as well as the relative cost of evaluating f and comparing sequence elements for equality.

FOCS Conference 1978 Conference Paper

A Dichromatic Framework for Balanced Trees

• Leonidas J. Guibas
• Robert Sedgewick

In this paper we present a uniform framework for the implementation and study of balanced tree algorithms. We show how to imbed in this framework the best known balanced tree techniques and then use the framework to develop new algorithms which perform the update and rebalancing in one pass, on the way down towards a leaf. We conclude with a study of performance issues and concurrent updating.