In multimedia, text or bioinformatics databases, applicat ions query sequences of n consecutive symbols called n-grams. Estimating the number of distinct n-grams is a view-size estimation problem. While view sizes can be estimated by sampling under statistical assumptions, we desire an unassuming algorithm with universally valid accuracy bounds. Most related work has focused on repeatedly hashing the data, which is prohibitive for large data sources. We prove that a one-pass one-hash algorithm is suffi cient for accurate estimates if the hashing is sufficiently independent. T o reduce costs further, we investigate recursive random hashing algorithms and show that they are sufficiently independent in practice. We compare our run ning times with exact counts using suffix arrays and show that, while we use ha rdly any storage, we are an order of magnitude faster. The approach further is extended to a one-pass one-hash computation of n-gram entropy and iceberg counts. The experiments use a large collection of English text from the Gutenberg Project as well as synthetic data.
A more sophisticated view-size estimation algorithm used in the context of data warehousing and OLAP @cite_26 @cite_35 is logarithmic probabilistic counting @cite_83 . This approach requires a single pass and almost no memory, but it assumes independent hashing for which no algorithm using limited storage is known @cite_41 . Practical results are sometimes disappointing @cite_30 , possibly because many random hash values need to be computed for each data point. Other variants of this approach include linear probabilistic counting @cite_51 @cite_38 and loglog counting @cite_40 .
@cite_30 @cite_35 @cite_38 @cite_26 @cite_41 @cite_40 @cite_83 @cite_51
2111678491 2008365755 2025051251 2145039842
This paper presents a family of bitmap algorithms that address the problem of counting the number of distinct header patterns (flows) seen on a high-speed link. Such counting can be used to detect DoS attacks and port scans and to solve measurement problems. Counting is especially hard when processing must be done within a packet arrival time (8 ns at OC-768 speeds) and, hence, may perform only a small number of accesses to limited, fast memory. A naive solution that maintains a hash table requires several megabytes because the number of flows can be above a million. By contrast, our new probabilistic algorithms use little memory and are fast. The reduction in memory is particularly important for applications that run multiple concurrent counting instances. For example, we replaced the port-scan detection component of the popular intrusion detection system Snort with one of our new algorithms. This reduced memory usage on a ten minute trace from 50 to 5.6 MB while maintaining a 99.77 probability of alarming on a scan within 6 s of when the large-memory algorithm would. The best known prior algorithm (probabilistic counting) takes four times more memory on port scan detection and eight times more on a measurement application. This is possible because our algorithms can be customized to take advantage of special features such as a large number of instances that have very small counts or prior knowledge of the likely range of the count. We present a probabilistic algorithm for counting the number of unique values in the presence of duplicates. This algorithm has O ( q ) time complexity, where q is the number of values including duplicates, and produces an estimation with an arbitrary accuracy prespecified by the user using only a small amount of space. Traditionally, accurate counts of unique values were obtained by sorting, which has O ( q log q ) time complexity. Our technique, called linear counting , is based on hashing. We present a comprehensive theoretical and experimental analysis of linear counting. The analysis reveals an interesting result: A load factor (number of unique values hash table size) much larger than 1.0 (e.g., 12) can be used for accurate estimation (e.g., 1 of error). We present this technique with two important applications to database problems: namely, (1) obtaining the column cardinality (the number of unique values in a column of a relation) and (2) obtaining the join selectivity (the number of unique values in the join column resulting from an unconditional join divided by the number of unique join column values in the relation to he joined). These two parameters are important statistics that are used in relational query optimization and physical database design. This paper introduces a class of probabilistic counting algorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large file stored on disk) in a single pass using only a small additional storage (typically less than a hundred binary words) and only a few operations per element scanned. The algorithms are based on statistical observations made on bits of hashed values of records. They are by construction totally insensitive to the replicative structure of elements in the file; they can be used in the context of distributed systems without any degradation of performances and prove especially useful in the context of data bases query optimisation. In this paper, we consider hashing with linear probing for a hashing table with m places, n items (n > m), and l = m - n empty places. For a noncomputer science-minded reader, we shall use the metaphore of n cars parking on m places: each car ci chooses a place pi at random, and if pi is occupied, ci tries successively pi + 1, pi + 2, until it finds an empty place. Pittel [42] proves that when l m goes to some positive limit β > 1, the size B1m,l1 of the largest block of consecutive cars satisfies 2(β - 1 - log β)B1m,l - 3 log log m + Ξm, where Ξm converges weakly to an extreme-value distribution. In this paper we examine at which level for n a phase transition occurs between B1m,l = o(m) and m - B1m,l = o(m). The intermediate case reveals an interesting behavior of sizes of blocks, related to the standard additive coalescent in the same way as the sizes of connected components of the random graph are related to the multiplicative coalescent.