Probabilistic counting algorithms for data base applications

This paper introduces a class of probabilistic count ing algorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large tile stored on disk) in a single pass using only a small additional storage (typically less than a hundred binary words) and only a few operat ions per element scanned. The algorithms are based on statistical observat ions made on bits of hashed values of records. They are by con-struction totally insensitive to the replicative structure of elements in the file; they can be used in the context of distributed systems without any degradat ion of per formances and prove especially useful in the context of data bases query optimisation. ‘7 ’ 1985 Academic Press. Inc 1. INTR~OUCTI~N As data base systems allow the user to specify more and more complex queries, the need arises for efficient processing methods. A complex query can however generally be evaluated in a number of different manners, and the overall perfor-mance of a data base system depends rather crucially on the selection of appropriate decomposit ion strategies in each particular case. Even a problem as trivial as computing the intersection of two collections of data A and B lends itself to a number of different treatments (see, e.g., [7]): 1. Sort A, search each element of B in A and retain it if it appears in A; 2. sort A, sort B, then perform a merge-l ike operation to determine the inter-section; 3. eliminate duplicates in A and/or B using hashing or hash filters, then per-form Algorithm 1 or 2. Each of these evaluation strategy will have a cost essentially determined by the number of records a, b in A and B, and the number of distinct elements ~1, j? in A and B, and for typical sorting methods, the costs are