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. • Efficient algorithms for estimating the number of distinct items in a data stream. • Explicit characterization of the distribution of reported values. • Detailed fair comparisons with other algorithms in the literature. • Sufficient detail to enable development of real-world implementations.

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 constant 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. Hypotheses about performance are validated through experiments using a realistic input stream, with the conclusion that our algorithms are more accurate than HyperLogLog when using the same amount of memory, and they use two-thirds as much memory as HyperLogLog to achieve a given accuracy.

This paper is concerned with a simple, rather intuitive preprocessing step that is likely to improve the average-case performance of any convex hull algorithm. For n points randomly distributed in the unit square, we show that a simple linear pass through the points can eliminate all but Ο(√n) of the points by showing that a simple superset of the remaining points has size c√n + ο(√n). We give a full implementation of the method, which should be useful in any practical application for finding convex hulls. Most of the paper is concerned with an analysis of the number of points eliminated by the procedure, including derivation of an exact expression for c. Extensions to higher dimensions are also considered.

Several algorithms have been proposed which build search trees using digital properties of the search keys. A general approach to the study of the average case performance of such algorithms is discussed, with particular attention to the analysis of the digital search tree structures of Coflman and Eve. Specifically, the method leads to the solution of a problem left open by Knuth, finding the average number of nodes in digital search trees with both sons null. The paper may be of interest as a survey and tutorial treatment of the analysis of the three primary digital tree search methods: digital search trees, radix search tries, and Patricia tries.

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.

An instructional computing laboratory, consisting of about 60 high-performance, graphics-based personal workstations connected by a high-bandwidth, resource-sharing local area network, has recently become operational at Brown University. This hardware, coupled with an innovative courseware/software environment, is being used in the classroom in an attempt to radically improve the state of the art of computer science pedagogy. This paper describes the current state of the project. The hardware and courseware/software environments are described and their use illustrated with detailed descriptions, including sample screen images. Some comments are included on our initial reactions to our experience to date with the environment and on our future plans.

A software environment is described which provides facilities at a variety of levels for “animating” algorithms: exposing properties of programs by displaying multiple dynamic views of the program and associated data structures. The system is operational on a network of graphics-based, personal workstations and has been used successfully in several applications for teaching and research in computer science and mathematics. In this paper, we outline the conceptual framework that we have developed for animating algorithms, describe the system that we have implemented, and give several examples drawn from the host of algorithms that we have animated.

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

The first component of a VLSI (very large-scale integration) design environment being built at Princeton University is described.The general theme of this effort is to make the design of VLSI circuits as similar to programming as possible.The attempt is to build tools that do for the VLSI circuit designer what the best software tools do for the implementer of large software systems.

ALI is a procedural language to specify VLSI layouts. It allows the designer to describe layouts without reference to the sizes and positions of the layout elements or to the distances between them. Among the interesting characteristics of ALI are that it does not need design rule checking, is easy to extend, facilitates the division of labor and permits the easy update of a layout to new design rules or to new processes. The general features of the language and the experience gained with a preliminary implementation of it are described.

Two components of a VLSI design environment being built at Princeton are described. The general theme of this effort is to make the design of VLSI circuits as similar to programming as possible. A conscious attempt is being made to apply experience in the design of large software systems to the creation of an appropriate environment for VLSI circuits. The two components described are a procedural language to specify circuit layouts and a switch-level circuit simulator for layout produced with this language. They have been chosen for presentation because many issues in their design are very similar to the issues that arise in the design of programming languages and software environments.

Several new results which contribute to the understanding of parallel merging networks are presented. First, a simple new explanation of the operation of Batcher's merging networks is offered. This view leads to the derivation of a modified version of Batcher's odd-even (m, n) network which has delay time [log(m+n)]. This is the same delay time as Batcher's bitonic (m, n) network, but it is achieved with substantially fewer comparators. Second, a correspondence is demonstrated between the number of comparators (and the delay time) for such networks and certain properties of binary number systems which have recently been extensively studied. Third, the [log(m + n)] delay time is shown to be optimal for a non-degenerate range of values of m and n.

Given a function f over a finite domain D and an arbitrary starting point x, the sequence $f^0 (x),f^1 (x),f^2 (x), \cdots $ is ultimately periodic. Such sequences are typically the output of 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 $3n + O(1)$ operations. In this paper we show that $n(1 + \Theta (1/\sqrt M ))$ steps are both necessary and sufficient, if M memory cells are available to store values of the function. We explicitly consider the performance of the algorithm as a function of the amount of memory available and the relative cost of evaluating f and comparing sequence elements for equality.

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. In this paper, we extend the model and the class of functions for which non-trivial bounds can be proved. In Section 2, we give a more general model than has been proposed previously. In Section 3 we show how to reduce the derivation of lower bounds within the model to a problem in distributed computing In Section 4, we consider lower bounds for a number of predicates: n-input, l-output functions (as contrasted with the n-input, n-output functions which have been studied previously). In Section 5, we show that previous lower bound results (for n-input, n-output functions) also apply even when the model is extended to allow nondeterminism, randomness, and multiple arrivials. Finally, the full details of the results presented here will appear in the final version of this paper.

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 fn(x) in the sequence. Previous algorithms for this problem have required 3n 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.

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.

A complete analysis is given of the number of exchanges used by the well-known Batcher’s odd-even merging (and sorting) networks. Batcher’s method involves a fixed sequence of “compare-exchange” operations, so the number of comparisons required is easy to compute, but the problem of determining how many comparisons result in exchanges has not been successfully attacked before. New results are derived in this paper giving accurate formulas for the worst-case and average values of this quantity. The worst-case analysis leads to the unexpected result that, asymptotically, the ratio of exchanges to comparisons approaches 1, although convergence to this asymptotic maximum is very slow. The average-case analysis shows that, asymptotically, only $\frac{1}{4}$ of the comparators are involved in exchanges. The method used to derive this result can in principle be used to get any asymptotic accuracy. The derivation involves principles of the theory of complex functions; in particular, properties of the $\Gamma $-function and the generalized Riemann $\zeta $-function are integral to the solution. Intermediate results in the analysis may be applicable to the average-case analysis of other merging methods, and the final portion of the derivation illustrates the utility of the “gamma function” method of asymptotic analysis.

This paper considers the problem of implementing and analyzing a Quicksort program when equal keys are likely to be present in the file to be sorted. Upper and lower bounds are derived on the average number of comparisons needed by any Quicksort program when equal keys are present. It is shown that, of the three strategies which have been suggested for dealing with equal keys, the method of always stopping the scanning pointers on keys equal to the partitioning element performs best.

According to the authors this book treats "the most important formal methods that have been applied to the study of operating systems algorithms." The emphasis of the book is on the mathematical analysis of models of computing systems, which means that there are several important methods and concepts in the theory of operating systems that are not treated. However, the book is the first serious attempt in this area and is a valuable addition to the reference and text books in computer science.