On the false-positive rate of Bloom filters

Bloom filters are a randomized data structure for membership queries dating back to 1970. Bloom filters sometimes give erroneous answers to queries, called false positives. Bloom analyzed the probability of such erroneous answers, called the false-positive rate, and Bloom's analysis has appeared in many publications throughout the years. We show that Bloom's analysis is incorrect and give a correct analysis.     

Double hashing with passbits

Double hashing with bucket capacity one is augmented with multiple passbits to obtain significant reduction to unsuccessful search lengths. This improves the analysis of Martini et al. [P.M. Martini, W.A. Burkhard, Double hashing with multiple passbits, Internat. J. Found. Theoret. Comput. Sci. 14 (6) (2003) 1165-1188] by providing a closed form expression for the expected unsuccessful search lengths.     

Using spine decompositions to efficiently solve the length-constrained heaviest path problem for trees

The length-constrained heaviest path (LCHP) in a weighted tree T, where each edge is assigned a weight and a length, is the path P in T with maximum total path weight and total path length bounded by a given value B. This paper presents an O(nlogn) time LCHP algorithm which utilizes a data structure constructed from the spine decomposition of the input tree. This is an improvement over the existing algorithm by Wu et al. (1999), which runs in O(nlog²n) time. Our method also improves on a previous O(nlogn) time algorithm by Kim (2005) for the special case of finding a longest nonnegative path in a constant degree tree in that we can handle trees of arbitrary degree within the same time bounds.     

A new analysis of the false positive rate of a Bloom filter

A Bloom filter is a space-efficient data structure used for probabilistic set membership testing. When testing an object for set membership, a Bloom filter may give a false positive. The analysis of the false positive rate is a key to understanding the Bloom filter and applications that use it. We show experimentally that the classic analysis for false positive rate is wrong. We formally derive a correct formula using a balls-and-bins model and show how to numerically compute the new, correct formula in a stable manner. We also prove that the new formula always results in a predicted greater false positive rate than the classic formula. This correct formula is numerically compared to the classic formula for relative error - for a small Bloom filter the prediction of false positive rate will be in error when the classic formula is used.     

Trading uninitialized space for time

The design of efficient graph algorithms usually precludes the test of edge existence, because an efficient support of that operation already requires time for the initialization of an adjacency-matrix representation. We describe an alternative representation of static directed graphs taking Θ(n+m) initialization time and using Θ(n²) space, which supports the efficient implementation of all usual operations on static graphs. The sparse graph representation allows the design of efficient graph algorithms using both iteration over all vertices adjacent with a given vertex and edge-existence operations, although at the expense of additional (uninitialized) space which may, nevertheless, be used for other purposes. To the best of our knowledge, the representation leads to the first graph algorithms with the disconcerting property that the time complexity is better than the space complexity.     

List update with probabilistic locality of reference

In this paper we study the performance of list update algorithms under arbitrary distributions that exhibit strict locality of reference and prove that Move-To-Front (MTF) is the best list update algorithm under any such distribution. We also show that the performance of MTF depends on the amount of locality of reference, while the performance of any static list update algorithm is independent of the amount of locality.     

Lower bounds on the OBDD size of two fundamental functions' graphs

Ordered Binary Decision Diagrams (OBDDs) are a data structure for Boolean functions which supports many useful operations. Among others it finds applications in CAD, model checking, and symbolic graph algorithms. Nevertheless, many simple functions are known to have exponential OBDD size with respect to their number of variables. In order to investigate the limits of symbolic graph algorithms which work on OBDD-represented graph instances, it is useful to have simply-structured graphs whose OBDD representation has exponential size. Therefore, we consider two fundamental functions with exponential lower bounds on their OBDD size and transfer these results to their corresponding graphs. Concretely, we consider the Indirect Storage Access function and the Hidden Weighted Bit function.     

On the existence and construction of non-extreme (a,b)-trees

In amortized analysis of data structures, it is standard to assume that initially the structure is empty. Usually, results cannot be established otherwise. In this paper, we investigate the possibilities of establishing such results for initially non-empty multi-way trees.     

A lower bound for the time to assure interactive consistency

A fast algorithm for composition of sparse maps (i.e.,maps which act as the identity on most of the elements of their domain) is presented.     

A note on predecessor searching in the pointer machine model

Predecessor searching is a fundamental data structuring problem and at the core of countless algorithms: given a totally ordered universe U with n elements, maintain a subset S⊆U such that for each element x∈U its predecessor in S can be found efficiently. During the last thirty years the problem has been studied extensively and optimal algorithms in many classical models of computation are known. In 1988, Mehlhorn et al. [K. Mehlhorn, S. Näher, H. Alt, A lower bound on the complexity of the union-split-find problem, SIAM J. Comput. 17 (6) (1988) 1093-1102] showed an amortized lower bound of Ω(loglogn) in the pointer machine model. We give a different proof for this bound which sheds new light on the question of how much power the adversary actually needs.     

On-line construction of parameterized suffix trees for large alphabets

We consider on-line construction of the suffix tree for a parameterized string, where we always have the suffix tree of the input string read so far. This situation often arises from source code management systems where, for example, a source code repository is gradually increasing in its size as users commit new codes into the repository day by day. We present an on-line algorithm which constructs a parameterized suffix tree in randomized O(n) time, where n is the length of the input string. Our algorithm is the first randomized linear time algorithm for the on-line construction problem.     

Efficient unbalanced merge-sort

Sorting algorithms based on successive merging of ordered subsequences are widely used, due to their efficiency and to their intrinsically parallelizable structure. Among them, the merge-sort algorithm emerges indisputably as the most prominent method. In this paper we present a variant of merge-sort that proceeds through arbitrary merges between pairs of quasi-ordered subsequences, no matter which their size may be. We provide a detailed analysis, showing that a set of n elements can be sorted by performing at most n⌊logn⌋ key comparisons. Our method has the same optimal asymptotic time and space complexity as compared to previous known unbalanced merge-sort algorithms, but experimental results show that it behaves significantly better in practice.     

On the density and discrepancy of a 2D point set with applications to thermal analysis of VLSI chips

In this era of giga-scale integration, thermal analysis has become one of the hot topics in VLSI chip design. Active thermal sources may be abstracted as a set of weighted points on a 2D chip-floor. The conventional notion of discrepancy that deals with the congestion properties of a set of scattered points may not be able to capture properly all real-life instances in this context. In this paper, we have introduced a new concept, called the density of a region to study some of the properties of the distribution of these weighted points. We prove several counter-intuitive results concerning the properties of the regions that have maximum or minimum density. We then outline algorithms for recognizing these regions. We also compare the attributes of density with the existing concept of discrepancy.     

Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

The interval-merging problem

A closed interval is an ordered pair of real numbers [x, y], with x ? y. The interval [x, y] represents the set {i ∈ R∣x ? i ? y}. Given a set of closed intervals I={[a₁,b₁],[a₂,b₂],…,[a_k,b_k]}, the Interval-Merging Problem is to find a minimum-cardinality set of intervals M(I)={[x₁,y₁],[x₂,y₂],…,[x_j,y_j]}, j ? k, such that the real numbers represented by equal those represented by . In this paper, we show the problem can be solved in O(d log d) sequential time, and in O(log d) parallel time using O(d) processors on an EREW PRAM, where d is the number of the endpoints of I. Moreover, if the input is given as a set of sorted endpoints, then the problem can be solved in O(d) sequential time, and in O(log d) parallel time using O(d/log d) processors on an EREW PRAM.     

Parallel computational geometry

We present efficient parallel algorithms for several basic problems in computational geometry: convex hulls, Voronoi diagrams, detecting line segment intersections, triangulating simple polygons, minimizing a circumscribing triangle, and recursive data-structures for three-dimensional queries.The work of C. Ó'Dúnlaing and C. Yap was supported by NSF Grants DCR-84-01898 and DCR-84-01633.     

Randomized splay trees: Theoretical and experimental results

Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [J. ACM 32 (1985) 652-686]. In this paper we present a randomized variant of these trees. The new algorithm for reorganizing the tree is both simple and easy to implement. We prove that our randomized splaying scheme has the same asymptotic performance as the original deterministic scheme but improves constants in the expected running time. This is interesting in practice because the search time in splay trees is typically higher than the search time in skip lists and AVL-trees. We present a detailed experimental study of our algorithm. On request sequences generated by fixed probability distributions, we can achieve improvements of up to 25% over deterministic splaying. On request sequences that exhibit high locality of reference, the improvements are minor.