Pith. sign in

REVIEW 2 major objections 5 minor 62 references

On Occupancy Moments and Bloom Filter Efficiency

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Exact occupancy moments show a standard Bloom filter peaks in efficiency with one hash function, not the customary many, and that the k≈(m/n)ln2 rule overshoots the optimum.

desk verdict Solid occupancy-moment paper with correct false-positive formulas, but the headline efficiency theorems are proven only for a continuous relaxation and one advertised monotonicity result is still a conjecture. read the letter →

arxiv 1908.04810 v1 pith:ZZ62HVUR submitted 2019-08-13 math.CO cs.DScs.ITmath.ITmath.PR

Jonathan Burns This is my paper · ORCID
classification math.COcs.DScs.ITmath.ITmath.PR MSC 60C0568R0594A2433C20
keywords classicoccupancyproblemcommitteeStevens-CraigdistributionfactorialseriesgeneralizedhypergeometricmomentBloomfilterfalse-positiverateefficiency
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Using exact moment formulas for occupancy distributions—the count of occupied urns when balls are cast in batches—the paper obtains exact expressions for the false-positive rate and efficiency of both classic and standard Bloom filters, probabilistic set-membership structures widely used in storage and network systems. It proves that a standard Bloom filter's peak efficiency decreases as the number of hash functions $k$ increases, so the most efficient configuration is $k=1$ storing $n = (\log_2 \frac{m}{m-1})^{-1}$ items, giving efficiency $\varepsilon_S^* = (m \log_2 \frac{m}{m-1})^{-1}$. From these exact formulas it concludes that the familiar optimization rule $k \approx \frac{m}{n}\ln 2$ overestimates the optimal hash count for small filters, producing extra hash work and a higher false-positive rate. The same machinery shows the classic Bloom filter approaches the information-theoretic efficiency limit of 1 as $m\to\infty$, while the standard variant approaches $\ln 2$. The result makes exact small-filter optimization available in place of asymptotic approximation.

What carries the argument

The engine is the family of committee-occupancy distributions—multivariate generalizations of the classic balls-into-urns occupancy count—together with their membership in the factorial series and generalized hypergeometric factorial moment families. The load-bearing identities are the moment formulas: $f_S = E[X_S^k]/m^k$ for the standard filter and $f_C = E[\binom{X_C}{k}]/\binom{m}{k}$ for the classic filter, expressed through finite differences and generalized hypergeometric functions (Theorems 4, 10, 13, and 22). These convert false-positive and efficiency calculations into computable moment evaluations even when the filter length $m$ is enormous, because the sums run over $k$ rather than $m$. The comparison of adjacent hash counts in Theorem 26 rests on the norm inequality $E[|X|^{k+1}]^{1/(k+1)} \ge E[|X|^k]^{1/k}$ applied to the occupancy random variable.

What would settle it

Take a small filter length such as $m=64$ or $m=100$, compute the exact standard-filter false-positive rate from the moment sum in Theorem 22 for every integer $n$ and $k$, and find the integer maximum of $\varepsilon_S = -\frac{n}{m}\log_2 f_S$. If the maximum over integers occurs away from $k=1$ and the nearest integer to $(\log_2 \frac{m}{m-1})^{-1}$, or if $\varepsilon_S(m,n/k,k) > \varepsilon_S(m,n/(k+1),k+1)$ fails for some integer $m,n \ge 2$, then the claimed global optimum depends on the unstated continuous relaxation.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is that exact occupancy moments answer Bloom filter efficiency. For a standard Bloom filter, the expected false-positive rate is $f_S(m,n,k)=E[X_S^k]/m^k$, where $X_S$ is the classic-occupancy count of 1-bits; for a classic Bloom filter it is $f_C(m,n,k)=E[\binom{X_C}{k}]/\binom{m}{k}$, a binomial moment. Substituting these into $\varepsilon = -\frac{n}{m}\log_2 f$ and comparing $k$ with $k+1$ through a standard $L^p$ norm inequality yields the theorem $\varepsilon_S(m,n/k,k) > \varepsilon_S(m,n/(k+1),k+1)$ and its corollary that the standard filter's maximum efficiency is $\varepsilon_S^* = [m \log_2 \frac{m}{m-1}]^{-1}$, attained at $k=1$ and $n=(\log_2 \frac{m}{m-1})^{-1}$ with false-positive rate $1/2$. For classic filters the paper proves in the limit that peak efficiency tends to 1 as $m\to\infty$ at $n=1$, $k=m/2$, while the standard filter tends to $\ln 2 \approx 0.693$; the monotone increase of classic-filter peak efficiency in $k$ is stated as Conjecture 28, not proven as a theorem. The exact formulas also make the common approximation $(1-e^{-nk/m})^k$ unnecessary for small-filter optimization.

Load-bearing premise

The efficiency theorems optimize over non-integer item counts—Theorem 26 compares $n/k$ and $n/(k+1)$, and Corollary 27 sets $n = (\log_2 \frac{m}{m-1})^{-1}$—even though the occupancy random variable counts whole items, and the paper never states that it is using a continuous relaxation of item counts.

Editorial extensions

If this is right

  • Standard Bloom filters should be configured with one hash function and about $m \ln 2$ stored items for peak efficiency; at that configuration the false-positive rate per probe is $1/2$.
  • The common formula $k^* \approx \frac{m}{n}\ln 2$ overshoots the exact optimal hash count for small filters; the paper's $m=1024$, $n=5$ example gives $k^*=142$ predicted versus $k_S^*=133$ and $k_C^*=124$ exact, so following the rule adds hash work and raises the false-positive rate.
  • Classic Bloom filters with one stored item and $k=m/2$ approach the information-theoretic efficiency ceiling of 1 as $m$ grows, while standard filters level off at $\ln 2 \approx 0.693$.
  • The exact formulas and recurrences in the paper let practitioners optimize small filters directly instead of relying on the Poisson approximation $(1-e^{-nk/m})^k$.
  • A classic filter holding one item can be losslessly compressed to $\log_2 \binom{m}{k}$ bits, preserving its false-positive rate and reaching efficiency 1 for every $k \le m/2$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the one-hash optimum survives the integer-item-count restriction, standard-filter design reduces to choosing $m$ with $n \approx m \ln 2$ and using a single hash; the entire optimization over $k$ disappears in practice.
  • The exact moment analysis exposes a small-filter regime in which the standard Poisson approximation is systematically biased; a natural testable extension is to characterize, as a function of $m/n$, the smallest filter where the approximation's optimal $k$ first agrees with the exact optimum.
  • Because the committee distributions form factorial series and generalized hypergeometric factorial moment families, the same machinery likely supplies exact false-positive formulas for other occupancy-modeled membership filters, such as counting or partitioned Bloom filters, where asymptotic estimates are still the norm.
  • If Conjecture 28 is true, classic filters dominate standard filters in efficiency at every hash count, not just in the large-$m$ limit, which would make the standard construction harder to justify on efficiency grounds alone.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper develops exact moment formulas for classic occupancy, committee, and multivariate committee distributions, identifies these distributions as members of Berg's factorial series and Kemp's generalized hypergeometric factorial-moment families, and applies the moment machinery to Bloom filter analysis. It derives exact false-positive rate formulas for standard and classic Bloom filters, gives bounds and estimators, and analyzes filter efficiency. The headline claims are that the conventional approximation k ≈ (m/n) ln 2 overestimates the optimal number of hash functions, that standard Bloom filter efficiency is maximized with a single hash function, and that Bloom filter efficiency is monotonic in the number of hash functions.

Significance. If its scoping issues are resolved, the paper makes a solid contribution. The moment derivations in Sections 2 and 3 are internally consistent, reproduce known results, and provide genuinely useful formulas and bounds. The exact false-positive rate formulas for classic and standard Bloom filters, and the side-by-side comparison in Section 3, are valuable correctives to a literature that often conflates the two constructions. The efficiency analysis is thought-provoking: it suggests that the standard Bloom filter, under a continuous relaxation, is most efficient with one hash function, and that the classic filter can approach the information-theoretic efficiency limit. However, the central efficiency theorem is currently stated as a result about finite Bloom filters when it is, in fact, a result about a continuous relaxation; this must be fixed before the headline claims can be accepted.

major comments (2)
  1. [Section 4.1.1, Theorem 26 and Corollary 27] The proof of Corollary 27 eliminates k > 1 using Theorem 26, but Theorem 26 compares configurations whose item counts n/k and n/(k+1) are, in general, non-integers, while an actual Bloom filter stores a whole number of items. The optimizer n = (log2(m/(m-1)))^(-1) in Corollary 27 is not an integer for typical m (for m = 100 it is approximately 68.97), so the asserted 'maximum efficiency of an m-bit standard Bloom filter' is actually a supremum over a continuous relaxation, not a maximum over finite Bloom filters. The integer-constrained maximizer is not identified, and the exact value 1/(m log2(m/(m-1))) is not attained by any real filter with an integer item count. The paper should either prove the integer version of the theorem or explicitly present the result as a continuous-relaxation supremum and revise the abstract and conclusions accordingly.
  2. [Abstract and Section 1.2] The claim that 'Bloom filter efficiency is monotonic in the number of hash functions' is broader than the results support. Theorem 26 proves monotonicity only for the continuous-relaxation comparison of configurations with item counts n/k and n/(k+1), not for fixed integer item counts in an actual filter. Moreover, for classic Bloom filters the analogous monotonicity statement is explicitly labeled Conjecture 28, so the unqualified monotonicity assertion in the abstract overstates what is derived. The abstract and the contribution bullets need to be qualified by filter type and by whether the claim concerns fixed n or peak efficiency, and the conjectural status of the classic-filter case should be acknowledged.
minor comments (5)
  1. [Section 4.1.1, proof of Theorem 26] The equality condition stated in the proof is incorrect: equality in the Lp-norm inequality requires the random variable to be constant almost surely, not uniformly distributed over [m]. This does not affect the strict inequality for n,m >= 2, but the sentence should be corrected.
  2. [Section 4.1.1, display after (73)] The displayed expression '2εk_S - εk+1_S' appears to be a typo; the subsequent argument establishes εk_S > εk+1_S via the logarithm of the ratio. Please correct the display to avoid confusing the strict inequality being proved.
  3. [Figure 9] The caption states that the maximum efficiency ε*_S(100) = 0.69 occurs at n = 69, while Corollary 27 gives the non-integer optimizer n ≈ 68.97 and ε*_S ≈ 0.6897. The text should clarify that 69 is the nearest integer to the continuous maximizer and that the exact formula in Corollary 27 is not attained by an integer-item filter.
  4. [Section 4.1.2] The bullet in Section 1.2 saying the efficiency of a classic Bloom filter 'decreases as the number of hash bits decrease' is confusingly worded; the intended statement appears to be that peak efficiency increases with k. Please rephrase and mark the monotonicity as conjectural, consistent with Conjecture 28.
  5. [Corollary 30] The word 'respectfully' should be 'respectively' in the statement of Corollary 30.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the Bloom-filter efficiency claims follow from the occupancy model's exact moment formulas, with no fitted input or load-bearing self-citation.

full rationale

The derivation chain is self-contained. The false-positive rates are derived from occupancy probabilities via inclusion-exclusion (Lemma 1) and Stirling inversion (Theorem 22 for standard filters, equations (59)-(60) for classic filters), and efficiency is then defined externally as ε = (n/m) log2(1/p) rather than being made equivalent to any fitted quantity. Theorem 26 compares the exact efficiency expression at equal total ball counts using Hölder's inequality on the exact moment E[X^k], and Corollary 27 maximizes the resulting k=1 expression by calculus; neither step assumes the conclusion. The sole self-citation, Burns [8] in Section 5, is a methodological pointer on linear regression for distribution fitting and is not load-bearing for any claimed theorem. The paper's known limitations—Corollary 27 optimizes over a non-integer n, and the classic-filter monotonicity claim is labeled Conjecture 28—are correctness or scoping concerns, not circularity. No quantity is fitted to a subset of data and then renamed a prediction, and no uniqueness result is imported from the authors' prior work.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

There are no fitted constants; all expressions are derived. The assumptions above are the explicit and implicit modeling choices the central claims depend on, including the unstated continuous item-count relaxation in the efficiency section.

assumptions (5)
  • domain assumption Urn occupancy is exchangeable: P[χ_{i1}...χ_{is}=1]=p_s depends only on s.
    Invoked at the start of Section 2 to justify the binomial moment formula Eq. (2) and all subsequent occupancy moment calculations.
  • domain assumption Hash functions are uniformly random and independent: standard filter uses k independent draws from [m], classic uses k distinct positions.
    Section 3.2 and Table 1; without this, the false-positive expectations fS=E[X^k]/m^k and fC=E[C(X,k)]/C(m,k) do not hold.
  • domain assumption The query element's hash positions are independent of the filter contents, and |S| is small relative to |D|, so a positive test is treated as a false positive.
    Section 3.2, first paragraph; this turns the false-positive rate into the probability that k hash bits are set.
  • ad hoc to paper Item count n may vary continuously in the efficiency optimization (unstated).
    Theorem 26 and Corollary 27 use n/k and n=(log2(m/(m-1)))^(-1), which are non-integer for typical m; the paper never states a continuous relaxation of the integer occupancy model.
  • standard math Standard background results: Stirling numbers of the second kind, inclusion-exclusion, finite-difference identities, Holder's inequality, and generalized hypergeometric function identities.
    Used throughout Sections 2 through 4, for example in Lemma 1, Theorem 4, and Theorem 26.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Occupancy Moments and Bloom Filter Efficiency." pith.science (2026). https://pith.science/paper/ZZ62HVUR

@misc{pith2026190804810,
  author       = {Pith},
  title        = {Pith review of: On Occupancy Moments and Bloom Filter Efficiency},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZZ62HVUR}},
  note         = {Machine review of arXiv:1908.04810}
}
read the original abstract

Two multivariate committee distributions are shown to belong to Berg's family of factorial series distributions and Kemp's family of generalized hypergeometric factorial moment distributions. Exact moment formulas, upper and lower bounds, and statistical parameter estimators are provided for the classic occupancy and committee distributions. The derived moment equations are used to determine exact formulas for the false-positive rate and efficiency of Bloom filters -- probabilistic data structures used to solve the set membership problem. This study reveals that the conventional Bloom filter analysis overestimates the number of hash functions required to minimize the false-positive rate, and shows that Bloom filter efficiency is monotonic in the number of hash functions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

62 extracted references · 61 canonical work pages

  1. [1]

    Arfwedson, O. (1951). A probability distribution connected with Stirling’s second class numbers. Scand. Actuar. J. 1951 121–132

    work page 1951

  2. [2]

    Barton, D. E. and David, F. N. (1959). Contagious Occupancy. Journal of the Royal Statistical Society. Series B (Methodological) 21 120–133

    work page 1959

  3. [3]

    Berg, S. (1974). Factorial Series Distributions, with Applications to Capture- Recapture Problems. Scand. Actuar. J. 1 145–152

    work page 1974

  4. [4]

    Bloom, B. H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. AMC 13 422–426

    work page 1970

  5. [5]

    , Mitzenmacher, M., Panigrahy, R., Singh, S

    Bonomi, F. , Mitzenmacher, M., Panigrahy, R., Singh, S. and Varghese, G. (2006). Bloom Filters via d-left Hashing and Dynamic Bit Reassignment. In Proc. Allerton Conf. Commun. Control Comput

    work page 2006

  6. [6]

    and Tang, Y

    Bose, P., Guo, H., Kranakis, E., Maheshwari, A., Morin, P., Morrison, J., Smid, M. and Tang, Y. (2008). On the false-positive rate of Bloom filters. Inform. Process. Lett. 108 210–213

    work page 2008

  7. [7]

    and Mitzenmacher, M

    Broder, A. and Mitzenmacher, M. (2003). Network Applications of Bloom Filters: A Survey. Internet Math. 1 485–509

    work page 2003

  8. [8]

    Burns, J. (2014). Recursive Methods in Number Theory, Combinatorial Graph The- ory, and Probability. PhD thesis, University of South Florida

    work page 2014

Show all 62 references
  1. [9]

    Catcheside, D. G. , Lea, D. E. and Thoday, J. M. (1945–1946). Types of chro- mosome structural change induced by the irradiation of Tradescantia microspores. J. Genet. 47 113–149

    1945

  2. [10]

    , Dean, J

    Chang, F. , Dean, J. , Ghemawat, S., Hsieh, W. C. , Wallach, D. A. , Bur- rows, M., Chandra, T., Fikes, A. and Gruber, R. E. (2006). Bigtable: A Dis- tributed Storage System for Structured Data. In 7th USENIX Symp. Oper. Syst. Design Implent. (OSDI 06) . USENIX Association, Se...

    2006

  3. [11]

    Charalambides, C. A. (2005). Combinatorial Methods in Discrete Distributions . Wiley Series in Probability and Statistics . John Wiley & Sons, Inc

    2005

  4. [12]

    and Jimeno, M

    Christensen, K., Roginsky, A. and Jimeno, M. (2010). A new analysis of the false positive rate of a Bloom filter. Inform. Process. Lett. 110 944–949. 42 BURNS

    2010

  5. [13]

    Craig, C. C. (1953). On the Utilization of Marked Specimens in Estimating Popu- lations of Flying Insects. Biometrika 40 170–176

    1953

  6. [14]

    David, F. N. and Barton, D. E. (1962). Combinatorial chance. London: C. Griffin

    1962

  7. [15]

    and Cao, P

    Erdogan, O. and Cao, P. (2005). Hash-AV: Fast virus signature scanning by cache- resident filters. InGLOBECOM ’05. IEEE Global Telecommun. Conf., 2005.3 1767— 1772

    2005

  8. [16]

    Fan, B., Andersen, D. G. , Kaminsky, M. and Mitzenmacher, M. D. (2014). Cuckoo Filter: Practically Better Than Bloom. In Proc. 10th ACM Internat. Conf. Emerg. Netw. Exp. Tech.. CoNEXT ’14 75–88. ACM, New York, NY, USA

    2014

  9. [17]

    Some further applications of finite difference operators Technical Report No

    Fang, K.-T.(1982). Some further applications of finite difference operators Technical Report No. 3, Stanford University, Department of Statistics

    1982

  10. [18]

    Feller, W. (1968). Ch. IV – Combination of Events. In An Introduction to Proba- bility Theory and Its Applications , 3rd ed. 1 98–113. John Wiley & Sons

    1968

  11. [19]

    Geravand, S.and Ahmadi, M. (2013). Bloom filter applications in network security: A state-of-the-art survey. Comput. Netw. 57 4047–4064

    2013

  12. [20]

    Gittelsohn, A. M. (1969). An Occupancy Problem. Amer. Statist. 23 11–12

    1969

  13. [21]

    Theγ-transform: A New Approach to the Study of a Discrete and Finite Random Variable

    Grandi, F. Theγ-transform: A New Approach to the Study of a Discrete and Finite Random Variable. Internat. J. Math. Models Appl. Sci. 9 624–635

  14. [22]

    Grandi, F. (2018). On the analysis of Bloom filters. Inform. Process. Lett. 129 35–39

    2018

  15. [23]

    Gremillion, L. L. (1982). Designing a Bloom Filter for Differential File Access. Commun. ACM 25 600–604

    1982

  16. [24]

    Johnson, N. L. and Kotz, S. (1977). Urn models and their application: an approach to modern discrete probability theory . John Wiley & Sons Inc

    1977

  17. [25]

    Johnson, N. L. , Kemp, A. W. and Kotz, S. (2005). Matching, Occupancy, Runs, and q-Series Distributions In Univariate Discrete Distributions 430–477. John Wiley & Sons, Inc

    2005

  18. [26]

    Kalinka, A. T. (2014). The probability of drawing intersections: extending the hypergeometric distribution. arXiv. 1305.0717

    2014 arXiv

  19. [27]

    Kemp, A. W. (1978). On Probability Generating Functions for Matching and Occu- pancy Distributions. Appl. Math. (Warsaw) 16 207–213

    1978

  20. [28]

    Kemp, A. W. and Kemp, C. D. (1974). A family of discrete distributions defined via their factorial moments. Comm. Statist. Theory Methods 3 1187–1196

    1974

  21. [29]

    and Mitzenmacher, M

    Kirsch, A. and Mitzenmacher, M. (2008). Less Hashing, Same Performance: Building a Better Bloom Filter. Random Structures Algorithms 33 187–218

    2008

  22. [30]

    Knuth, D. E. TAOCP Vol 3 – Bloom Filters. Personal Communication

  23. [31]

    Knuth, D. E. (1973). Retrieval on Secondary Keys. In Searching and Sorting . The Art of Computer Programming 3 561–562. Addison-Wesley

    1973

  24. [32]

    Kolchin, V. F. , Sevast´yanov, B. A. and Chistyakov, V. P. (1978). Random allocations. Scripta Series in Mathematics . John Wiley & Sons Inc. Translated from the Russian

    1978

  25. [33]

    Kumar, C. S. (2009). A new class of discrete distributions. Braz. J. Probab. Stat. 23 49–56

    2009

  26. [34]

    and Malik, P

    Lakshman, A. and Malik, P. (2010). Cassandra: A Decentralized Structured Stor- age System. SIGOPS Oper. Syst. Rev. 44 35–40. ON OCCUPANCY MOMENTS AND BLOOM FILTER EFFICIENCY 43

    2010

  27. [35]

    , Nam, Y

    Lu, G. , Nam, Y. J. and Du, D. H. C. (2012). BloomStore: Bloom-Filter based memory-efficient key-value store for indexing of data deduplication on flash. In 012 IEEE 28th Symposium on Mass Storage Systems and Technologies (MSST) 1–11

    2012

  28. [36]

    Luo, L., Guo, D., Ma, R. T. B. , Rottenstreich, O. and Luo, X. (2018). Opti- mizing Bloom Filter: Challenges, Solutions, and Comparisons. arXiv. 1804.04777

    2018 arXiv

  29. [37]

    and Pasternack, B

    Mantel, N. and Pasternack, B. S.(1968). A Class of Occupancy Problems. Amer. Statist. 22 23–24

    1968

  30. [38]

    Mingshu, T. (2011). Some Combinatorial Identities and Explanations Based on Oc- cupancy Model. Appl. Math. Sci. 5 697–705

    2011

  31. [39]

    Mitzenmacher, M. (2002). Compressed Bloom Filters. IEEE/ACM Trans. Netw. 10 604–612

    2002

  32. [40]

    Mooers, C. N. (1947). Putting Probability to Work in Coding Punched Cards. Amer. Chem. Soc. Meet. 112 14E–15E

    1947

  33. [41]

    Mullin, J. K. (1983). A Second Look at Bloom Filters. Comm. ACM 26 570–571

    1983

  34. [42]

    and Sibuya, M

    Nishimura, K. and Sibuya, M. (1988). Occupancy with two types of balls. Ann. Inst. Statist. Math. 40 77–91

    1988

  35. [43]

    and Najork, M

    Olston, C. and Najork, M. (2010). Web Crawling. Found. Trends Inform. Retr. 4 175–246

    2010

  36. [44]

    Pandey, P., Bender, M. A. , Johnson, R. and Patro, R. (2017). A General- Purpose Counting Filter: Making Every Bit Count. In Proceedings of the 2017 ACM International Conference on Management of Data . SIGMOD ’17 775–787

    2017

  37. [45]

    and Zhou, A

    Peng, Y., Guo, J., Li, F., Qian, W. and Zhou, A. (2018). Persistent Bloom Filter: Membership Testing for the Entire History. In Proc. 2018 Internat. Conf. Manag. Data. SIGMOD ’18 1037–1052

    2018

  38. [46]

    Porat, E. (2009). An Optimal Bloom Filter Replacement Based on Matrix Solving. In Proc. Fourth Internat. Comp. Sci. Symp. Russia Comp. Sci. - Theory and Appl. . CSR ’09 263–273. Springer-Verlag, Berlin, Heidelberg

    2009

  39. [47]

    Price, G. B. (1946). Distributions Derived from the Multinomial Expansion. Amer. Math. Monthly 53 59–74

    1946

  40. [48]

    and Chen, S

    Qiao, Y., Li, T. and Chen, S. (2011). One memory access Bloom filters and their generalization. In INFOCOM, 2011 Proc. IEEE 1745–1753

    2011

  41. [49]

    and Chen, S

    Qiao, Y., Li, T. and Chen, S. (2014). Fast Bloom Filters and Their Generalization. IEEE Transactions on Parallel and Distributed Systems 25 93–103

    2014

  42. [50]

    Riordan, J. (1968). Combinatorial Identities. Wiley series in probability and math- ematical statistics. Wiley, New York, NY

    1968

  43. [51]

    Roberts, C. S. (1979). Partial-match retrieval via the method of superimposed codes. Proc. IEEE 67 1624–1642

    1979

  44. [52]

    Sanfilippo, S. (2009). Redis. https://redis.io/

    2009

  45. [53]

    Severance, D. G. and Lohman, G. M. (1976). Differential Files: Their Application to the Maintenance of Large Datasets. ACM Trans. Database Syst. 1 256–267

    1976

  46. [54]

    and Kingsford, C

    Solomon, B. and Kingsford, C. (2016). Fast search of thousands of short-read sequencing experiments. Nat. Biotech. 34 300–302

    2016

  47. [55]

    Sprott, D. A. (1969). A Note on a Class of Occupancy Problems. Amer. Statist. 23 12–13

    1969

  48. [56]

    Stevens, W. L. (1937). Significance of Grouping. Ann. Eugen. 8 57–69. 44 BURNS

    1937

  49. [57]

    Swamidass, S. J. and Baldi, P. (2007). Mathematical Correction for Fingerprint Similarity Measures to Improve Chemical Retrieval. J. Chem. Inform. and Model. 47 952–964

    2007

  50. [58]

    Walker, A. (2007). Filters Undergraduate thesis, Haverford College, 370 W Lan- caster Ave, Haverford, PA 19041

    2007

  51. [59]

    Walter, S. D. (1979). Some Generalizations of the Committee Problem. Canad. J. Statist. 7 1–10

    1979

  52. [60]

    A., Ray, K

    Weaver, S. A., Ray, K. J. , Marek, V. W. , Mayer, A. J. and Walker, A. K. (2014). Satisfiability-based Set Membership Filters. J. Satisf. Boolean Model. Com- put. 8 129–148

    2014

  53. [61]

    A., Roberts, H

    Weaver, S. A., Roberts, H. J. and Smith, M. J. (2018). XOR-Satisfiability Set Membership Filters. In Theory and Applications of Satisfiability Testing – SAT 2018 (O. Beyersdorff and C. M. Wintersteiger, eds.) 401–418. Springer International Publishing, Cham

    2018

  54. [62]

    White, C. (1971). The Committee Problem. Amer. Statist. 25 25–26. Ionic Security Inc., 1170 Peachtree St. NE, Suite 400, Atlanta, GA 30309 E-mail: jburns@ionic.com

    1971

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.