API Snapshots: Java Core, C++ Core, Python, Memory, Pig, Hive,

Frequent Items

Error Threshold Table

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