This table of thresholds is computed a follows:
M = Max Map Size. Always a power of 2.
N = Stream Length (Total Weights or counts of items)
e = Epsilon = 3.5/M (minimum detectable frequency)
T = Threshold = (N < 0.75 * M)? 0 : e * N.
The error in getEstimate(item) is guaranteed to be at most T.
The function getFrequentItems(NO_FALSE_NEGATIVES) is guaranteed to return a list of items that contains all items with frequency greater than T and might contain some additional items, the False Positives, as well.
The function getFrequentItems(NO_FALSE_POSITIVES) is guaranteed return a list of items that contains all items with frequency greater than 2*T, and no items with frequency less than T, but it may exclude some items with frequency greater than T (the False Negatives).
Max Map Size-> |8|16|32|64|128|256|512|1,024|2,048|4,096|8,192|16,384|32,768|65,536|131,072|262,144|524,288|1,048,576 Epsilon-> |0.4375|0.2188|0.1094|0.0547|0.0273|0.0137|6.84E-03|3.42E-03|1.71E-03|8.54E-04|4.27E-04|2.14E-04|1.07E-04|5.34E-05|2.67E-05|1.34E-05|6.68E-06|3.34E-06 Stream Length |Threshold-> | -------------- | ----------|------|------|------|------|------|--------|--------|--------|--------|--------|--------|--------|--------|--------|--------|--------|-------- _____________|| 100|44|22|11|5|3|0|0|0|0|0|0|0|0|0|0|0|0|0 178|78|39|19|10|5|0|0|0|0|0|0|0|0|0|0|0|0|0 316|138|69|35|17|9|4|0|0|0|0|0|0|0|0|0|0|0|0 562|246|123|62|31|15|8|4|0|0|0|0|0|0|0|0|0|0|0 1,000|438|219|109|55|27|14|7|3|0|0|0|0|0|0|0|0|0|0 1,778|778|389|194|97|49|24|12|6|3|0|0|0|0|0|0|0|0|0 3,162|1,383|692|346|173|86|43|22|11|5|3|0|0|0|0|0|0|0|0 5,623|2,460|1,230|615|308|154|77|38|19|10|5|0|0|0|0|0|0|0|0 10,000|4,375|2,188|1,094|547|273|137|68|34|17|9|4|0|0|0|0|0|0|0 17,783|7,780|3,890|1,945|972|486|243|122|61|30|15|8|4|0|0|0|0|0|0 31,623|13,835|6,917|3,459|1,729|865|432|216|108|54|27|14|7|3|0|0|0|0|0 56,234|24,602|12,301|6,151|3,075|1,538|769|384|192|96|48|24|12|6|3|0|0|0|0 100,000|43,750|21,875|10,938|5,469|2,734|1,367|684|342|171|85|43|21|11|5|3|0|0|0 177,828|77,800|38,900|19,450|9,725|4,862|2,431|1,216|608|304|152|76|38|19|9|5|0|0|0 316,228|138,350|69,175|34,587|17,294|8,647|4,323|2,162|1,081|540|270|135|68|34|17|8|4|0|0 562,341|246,024|123,012|61,506|30,753|15,377|7,688|3,844|1,922|961|481|240|120|60|30|15|8|4|0 1.0E+06|437,500|218,750|109,375|54,688|27,344|13,672|6,836|3,418|1,709|854|427|214|107|53|27|13|7|3 1.8E+06|777,997|388,999|194,499|97,250|48,625|24,312|12,156|6,078|3,039|1,520|760|380|190|95|47|24|12|6 3.2E+06|1.38E+06|691,748|345,874|172,937|86,469|43,234|21,617|10,809|5,404|2,702|1,351|676|338|169|84|42|21|11 5.6E+06|2.46E+06|1.23E+06|615,061|307,530|153,765|76,883|38,441|19,221|9,610|4,805|2,403|1,201|601|300|150|75|38|19 1.0E+07|4.38E+06|2.19E+06|1.09E+06|546,875|273,438|136,719|68,359|34,180|17,090|8,545|4,272|2,136|1,068|534|267|134|67|33 1.8E+07|7.78E+06|3.89E+06|1.94E+06|972,497|486,248|243,124|121,562|60,781|30,391|15,195|7,598|3,799|1,899|950|475|237|119|59 3.2E+07|1.38E+07|6.92E+06|3.46E+06|1.73E+06|864,685|432,343|216,171|108,086|54,043|27,021|13,511|6,755|3,378|1,689|844|422|211|106 5.6E+07|2.46E+07|1.23E+07|6.15E+06|3.08E+06|1.54E+06|768,826|384,413|192,207|96,103|48,052|24,026|12,013|6,006|3,003|1,502|751|375|188 1.0E+08|4.38E+07|2.19E+07|1.09E+07|5.47E+06|2.73E+06|1.37E+06|683,594|341,797|170,898|85,449|42,725|21,362|10,681|5,341|2,670|1,335|668|334 1.8E+08|7.78E+07|3.89E+07|1.94E+07|9.72E+06|4.86E+06|2.43E+06|1.22E+06|607,810|303,905|151,953|75,976|37,988|18,994|9,497|4,749|2,374|1,187|594 3.2E+08|1.38E+08|6.92E+07|3.46E+07|1.73E+07|8.65E+06|4.32E+06|2.16E+06|1.08E+06|540,428|270,214|135,107|67,554|33,777|16,888|8,444|4,222|2,111|1,056 5.6E+08|2.46E+08|1.23E+08|6.15E+07|3.08E+07|1.54E+07|7.69E+06|3.84E+06|1.92E+06|961,033|480,516|240,258|120,129|60,065|30,032|15,016|7,508|3,754|1,877 1.0E+09|4.38E+08|2.19E+08|1.09E+08|5.47E+07|2.73E+07|1.37E+07|6.84E+06|3.42E+06|1.71E+06|854,492|427,246|213,623|106,812|53,406|26,703|13,351|6,676|3,338 1.8E+09|7.78E+08|3.89E+08|1.94E+08|9.72E+07|4.86E+07|2.43E+07|1.22E+07|6.08E+06|3.04E+06|1.52E+06|759,763|379,881|189,941|94,970|47,485|23,743|11,871|5,936 3.2E+09|1.38E+09|6.92E+08|3.46E+08|1.73E+08|8.65E+07|4.32E+07|2.16E+07|1.08E+07|5.40E+06|2.70E+06|1.35E+06|675,535|337,768|168,884|84,442|42,221|21,110|10,555 5.6E+09|2.46E+09|1.23E+09|6.15E+08|3.08E+08|1.54E+08|7.69E+07|3.84E+07|1.92E+07|9.61E+06|4.81E+06|2.40E+06|1.20E+06|600,645|300,323|150,161|75,081|37,540|18,770 1.0E+10|4.38E+09|2.19E+09|1.09E+09|5.47E+08|2.73E+08|1.37E+08|6.84E+07|3.42E+07|1.71E+07|8.54E+06|4.27E+06|2.14E+06|1.07E+06|534,058|267,029|133,514|66,757|33,379