Bloom filter variants for multiple sets: a comparative assessment

Dario Maio; Luca Calderoni; Paolo Palmieri

REVIEW 3 major objections 4 minor 26 references

Bloom filter variants for multiple sets: a comparative assessment

T0 review · 3 major / 4 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 The paper argues that among two Bloom-filter variants that answer which set an element belongs to, the shifting Bloom filter is more memory-efficient while the spatial Bloom filter is much cheaper per query.

desk verdict Useful engineering comparison and a real but shallow generalization of ShBF; currently undermined by a mismatch between the formal 2m-bit definition and the circular m-bit filter actually analyzed. read the letter →

arxiv 1908.10644 v1 pith:HFTTZNTI submitted 2019-08-28 cs.DS

Luca Calderoni , Dario Maio , Paolo Palmieri This is my paper · ORCID

classification cs.DS

keywords Bloomfiltershiftingspatialmultiplesetsassociationqueriesfalsepositiveprobabilityinter-seterrorprobabilisticdatastructures

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

The paper argues that two Bloom filter variants that answer association queries (which set does this element belong to?) trade space against query cost in opposite directions. It generalises the shifting Bloom filter (ShBF) so it can hold any number of disjoint sets rather than just two, derives new false-positive and inter-set error formulas for this generalised version, and compares it experimentally with the spatial Bloom filter (SBF) over datasets of 65,280 elements split into 255 sets. The measured conclusion is that at equal bit length the ShBF reaches similar or better error rates using less memory, while at equal cell count the SBF is better; and each SBF query needs a constant number of hash computations, whereas each ShBF query needs a number that grows linearly with the number of sets. A memory-constrained designer would choose the ShBF; a latency-constrained designer would choose the SBF.

What carries the argument

The load-bearing object is the offset function $o(\delta)$ in the generalised ShBF: each originating set $\Delta_i$ is assigned its own hash function $h_i^{\mathrm{shift}}$, and an element of that set is written at positions $h(\delta)+o(\delta)$, so set identity is encoded by shifting rather than by writing a label. Because the vector is binary, the filter length in bits equals the number of cells $m$, whereas the SBF writes labels into multi-bit cells and therefore needs $m \cdot \lceil \log_2(s+1)\rceil$ bits. Equations (5)-(11) convert the classic Bloom occupancy argument into per-set, overall, and inter-set error rates for the ShBF, and Equations (18)-(21) recall the corresponding SBF rates from earlier analysis; the circular modulo implementation described in Section 4 is what lets the experiments treat bit length and cell count as equal for the ShBF.

What would settle it

Insert the same 255-set dataset into two ShBF implementations, one circular with $m=2^{20}$ cells and one non-circular with the formal $2m=2^{21}$ bits, query the same 500,000 non-elements, and compare the measured false-positive ratios with Equations (5) and (8); if only the circular version matches the $m$-based formulas, the $2m$-bit definition is not the structure actually analysed.

Watch

Extended reading notes

Core claim

The central claim is a trade-off for multi-set association filters: the generalised ShBF is more space-efficient but computationally more expensive than the SBF. The ShBF stores a binary vector and encodes set membership by adding a set-specific hash offset to each position, so one bit per cell suffices, while the SBF stores the set label inside each cell, so each cell needs enough bits to hold a label (about $\log_2(s+1)$ bits for $s$ sets). The paper's new formulas give the ShBF per-set false-positive probability as the classic Bloom formula, the overall false-positive probability as one minus the per-set probability raised to the number of sets, the inter-set error probability as one minus the per-set probability raised to $s-1$, and the probability that a query returns exactly $i$ candidate sets as a binomial expression. Experiments on uniform and random 255-set datasets confirm these rates: at equal bits, the ShBF reaches near-zero false positives at $l = 2^{21}$ while the SBF needs $l = 2^{23}$; at equal cell counts, the SBF is better. Each ShBF query requires $k+s-1$ hash computations and up to $s \cdot k$ cell reads, versus $k$ hashes and at most $k$ reads for the SBF.

Load-bearing premise

The probability formulas count $m$ cells, but the formal definition describes a $2m$-bit binary vector; the experiments use a circular $m$-position version, and the paper treats the two as interchangeable without proving they have the same error behaviour.

Editorial extensions

If this is right

For memory-bound deployments, the ShBF reaches the same false-positive target with fewer bits, so larger set collections can fit in a fixed RAM budget.
For latency-bound deployments, the SBF's constant hash count and single lookup give query time independent of the number of sets.
ShBF inter-set errors are recoverable: the true set always appears among the returned candidates, so an exact re-check can resolve the uncertainty; SBF errors return a single wrong set with no such signal.
SBF error probabilities can be tuned per set because lower-index sets are more likely to be overwritten, while ShBF errors spread uniformly across sets.
As the number of sets $s$ grows, the ShBF overall false-positive probability rises through the $s$ exponent in its formula while the SBF's stays flat, so the SBF's stability improves relative to the ShBF for filters storing very many sets.

Reading between the lines

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

Extension: the same offset-encoding idea could be applied to counting or cuckoo Bloom filters to give them multi-set association without widening cells, something the paper does not test.
Extension: because the SBF's per-cell width grows as $\log_2(s+1)$, for very large set counts the SBF's bit-length advantage over the ShBF should shrink; the crossover point can be computed from the paper's formulas but is not computed there.
Extension: a hybrid design could query an SBF first for a constant-time answer and fall back to ShBF-style candidate enumeration only when the result needs confirmation; the paper does not propose such a hybrid.

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.

Desk Editor's Note

read the letter

Bottom line: this is a useful, modest engineering comparison, and the generalized ShBF is genuinely new—but only in the straightforward sense of extending a two-set construction to s disjoint sets. The main thing to know before relying on it: the formal Definition 1 describes a 2m-bit vector, while Section 4 implements a circular m-bit filter with modulo-m indexing. All the probability formulas and experiments use the latter. That mismatch is load-bearing, but easy to repair.

What is actually new: the s-set ShBF with s−1 offset hash functions, the probability formulas in Section 2, and the experimental comparison that separates filter length in bits from number of cells. The paper does a fair job of distinguishing memory usage from cell count, and the qualitative conclusion—ShBF saves space but costs more per query—is supported by the data. The SBF formulas are quoted from the authors' earlier paper rather than re-derived here; that is acceptable, and the citation pattern looks reasonable.

The soft spots are real but not fatal. First, the definition/implementation mismatch: in Definition 1, h(δ)+o(δ) can fall anywhere in [2,2m], so the vector has 2m bits, and the standard occupancy formula (1−1/m)^{kn} does not follow for that structure—edge densities differ per set. The formulas only line up with the circular m-bit version actually used in Figure 4, Table 2, and the space-efficiency comparison. The fix is simple: rewrite Definition 1 and Equation (3) for m bits with modulo-m indexing, and say explicitly that offsets are reduced modulo m. Second, the experimental reporting is thin: no code release, no error bars, no statement of the hash functions used or the number of runs, and the datasets are small (65K elements). Minor: the caption text for Figure 5(b) appears to say 1.4×10^9 where it should say 1.4×10^-9.

Who this is for: practitioners choosing among multi-set Bloom filter variants, and researchers working on ShBF extensions. The theoretical depth is not high, but the comparison is useful. I would send this to a serious referee, primarily to force the consistency fix and fuller experimental details. Until the definition is aligned with the implementation, I would not cite the formulas as they stand.

Referee Report

3 major / 4 minor

Summary. The paper compares two probabilistic data structures for association queries over multiple sets: the shifting Bloom filter (ShBF) and the spatial Bloom filter (SBF). The authors propose a generalized ShBF that supports an unlimited number of disjoint sets, derive new false-positive and inter-set error probability formulas, and evaluate both structures experimentally on uniform and random datasets. The central conclusion is that the ShBF achieves better space efficiency while incurring a significantly higher computational cost per query than the SBF.

Significance. If the analysis were fully consistent, the paper would provide a useful comparative framework and a meaningful generalization of the ShBF to more than two sets. The empirical work covers both error rates and an entropy-based measure of answer quality, and the computational-cost comparison in Table 3 is straightforward and informative. However, the current manuscript contains a load-bearing inconsistency between the formal definition of the ShBF and the structure actually analyzed and tested, which affects the validity of the probability formulas and the space-efficiency conclusion.

major comments (3)

[Section 2, Definition 1 and Eq. (3), vs. Section 4] Definition 1 defines the ShBF as a binary vector b of 2m bits, where inserted positions are h(δ)+o(δ) and can range up to 2m. Section 4 instead states: "we implemented a circular ShBF version composed of m bits" and applies modulo-m indexing to h(δ)+o(δ). All probability formulas in Eqs. (5)-(11) use m as the number of cells. These are different objects: in the 2m-bit non-circular vector, the insertion positions are not uniformly distributed over the vector, so the standard Bloom-filter formula (5) does not follow from Definition 1; in the circular m-bit filter, the formal definition must be amended to state m cells with modulo-m indexing. Because Eqs. (5)-(11), Figure 4, Figure 5, and Table 2 all describe the circular structure, the paper's formal definition and its analysis concern different objects.
[Section 2.1, Eqs. (7)-(11)] The derivation of the overall false-positive probability and the inter-set error probabilities treats the s set-specific lookups as independent Bernoulli trials, each with the same probability fpp_i. This independence assumption does not hold: for a fixed query element, the k positions checked for different sets are shifts of the same underlying random bit vector, so the corresponding events are correlated. Equation (8) is therefore at best an approximation, and the same issue affects Eqs. (10) and (11). The paper should justify this independence assumption asymptotically or provide an exact or explicitly approximate treatment.
[Section 4, Figure 4 and Table 2] The central space-efficiency conclusion—that the ShBF achieves error rates comparable to the SBF while using l=m bits instead of l=8m bits—depends on the m-bit circular implementation. If the 2m-bit Definition 1 is retained, the memory usage of the ShBF doubles and the comparison in bits changes; if the circular structure is retained, Definition 1 and Eq. (3) must be revised. The paper must present one consistent definition and re-derive the comparison under it before the claimed space-efficiency advantage can be assessed.

minor comments (4)

[Section 4, after Figure 5] The text says the ShBF false-positive probability "ranges from close to 0 to 1.4 × 109" but the axis label is ×10^{-9}; the exponent is missing its minus sign.
[Footnote 1] The footnote states that the paper uses "multiset" following the mathematical definition of a set that permits multiple instances of any element; that object is a multiset, not a set, and this wording is likely to confuse readers.
[Table 3] The column header "lookups /" appears to have a stray slash, and the formatting of "cells read / query" is inconsistent with the two preceding columns; please make the table headers uniform.
[Figure 2] The example in Figure 2 uses a 16-bit filter, which matches the circular m-bit implementation but contradicts Definition 1 and Eq. (3), where the vector should have 2m bits; this example should be updated once the structure is made consistent.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the ShBF error model is a standard Bloom-filter/binomial analysis and the SBF formulas are prior published results; the only notable issue is a non-circular mismatch between the formal 2m-bit ShBF definition and the m-bit circular implementation used in the formulas.

full rationale

The ShBF probability formulas (5)-(11) are not fitted to the experimental outcomes and are not defined in terms of the comparison results. They follow the classical Bloom-filter occupancy argument: each of the n inserted items sets k cells chosen by the per-set offset hash, so a given cell remains zero with probability (1-1/m)^{kn}, and the per-set false-positive probability is the k-th power of the occupied-cell probability; the overall and inter-set formulas then use Bernoulli trials over the s set lookups. This is a self-contained derivation from standard assumptions, and the experiments merely validate it. The SBF formulas (18)-(21) are quoted from the authors' earlier paper [24]; although this is a self-citation, [24] is an externally published, parameter-free analysis, so the citation is real evidence rather than a circular load-bearing step. The manuscript does contain a definitional inconsistency: Definition 1 and Eq. (3) define a ShBF as a binary vector of 2m bits, while Section 4 states that 'we implemented a circular ShBF version composed of m bits' and all formulas (5)-(11) use m as the cell count. This means the probability analysis applies to the m-bit circular object, not to the formally defined 2m-bit object; however, neither object is defined in terms of the predicted error rates, so the inconsistency is a correctness/consistency risk, not a circularity. No parameter is fitted and no result is forced by a self-citation chain.

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

No free parameters are fitted to data. The new ShBF analysis rests on standard uniform hashing assumptions, an unproved equivalence between the formal 2m-bit ShBF and the circular m-bit implementation, an independence approximation for multiple lookups, and a disjointness restriction on sets. The SBF probability baselines are imported from a prior self-cited paper.

assumptions (5)

domain assumption Hash functions h and h_i^down are independent and output uniformly random values over their ranges.
Stated in Definition 1 and used to derive Equations (5)-(11); no specific hash family is proven to meet this.
ad hoc to paper The circular m-bit ShBF evaluated in Section 4 is equivalent to the 2m-bit vector defined in Definition 1 and Equation (3).
Definition 1 defines b_down as a binary vector of 2m bits; Section 4 sets l=m and uses modulo m indexing. The probability formulas use m as the cell count, so this equivalence is load-bearing but unproved.
domain assumption Set-specific lookups in ShBF verification are independent Bernoulli trials with success probability fpp_i^down.
Equations (7)-(11) use the binomial distribution; the lookups share the same h(delta) digests, so strict independence is an approximation.
domain assumption The SBF probability formulas quoted from [24] are correct.
Equations (18)-(21) are imported from the authors' earlier paper without derivation and underlie the SBF side of the comparison.
domain assumption The originating sets in the generalized ShBF are disjoint.
Section 2 states the extension removes intersecting sets; the formulas treat membership lookups per set and would need modification if sets overlapped, since an element could belong to multiple sets.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Bloom filter variants for multiple sets: a comparative assessment." pith.science (2026). https://pith.science/paper/HFTTZNTI

@misc{pith2026190810644,
  author       = {Pith},
  title        = {Pith review of: Bloom filter variants for multiple sets: a comparative assessment},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HFTTZNTI}},
  note         = {Machine review of arXiv:1908.10644}
}

read the original abstract

In this paper we compare two probabilistic data structures for association queries derived from the well-known Bloom filter: the shifting Bloom filter (ShBF), and the spatial Bloom filter (SBF). With respect to the original data structure, both variants add the ability to store multiple subsets in the same filter, using different strategies. We analyse the performance of the two data structures with respect to false positive probability, and the inter-set error probability (the probability for an element in the set of being recognised as belonging to the wrong subset). As part of our analysis, we extended the functionality of the shifting Bloom filter, optimising the filter for any non-trivial number of subsets. We propose a new generalised ShBF definition with applications outside of our specific domain, and present new probability formulas. Results of the comparison show that the ShBF provides better space efficiency, but at a significantly higher computational cost than the SBF.

Figures

Figures reproduced from arXiv: 1908.10644 by the authors.

**Figure 1.** The word size. 2.1. False positives As we redefined the ShBF data structure it is important to investigate its behaviour in terms of false positives. Definition 2. Given a filter b , a false positive event occurs when the verification procedure performed on an element δ < S¯ terminates with a non-empty set of positives matches, i.e. Γ , ∅. As we may see, a false positive event reported by a ShBF may pertain several… view at source ↗

**Figure 2.** Insertion of three originating sets ∆1, ∆2 and ∆3 and verification of elements in a shifting Bloom filter of length m = 16, featuring two hash functions (k = 2). With respect to the verification process, it is possible to observe true positives, true negatives, false positives and inter-set errors. Each scenario is depicted in sequence. observe an inter-set error (isep ) may be derived as the probability of the c… view at source ↗

**Figure 3.** Insertion of three originating sets ∆1, ∆2 and ∆3 and verification of elements in a spatial Bloom filter of length m = 16, featuring two hash functions (k = 2). With respect to the verification process, it is possible to observe true positives, true negatives, false positives and inter-set errors. Each scenario is depicted in sequence. Throughout this paper, we refer to spatial Bloom filters using the vector represe… view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: False positive probability for the two data structures over a uniformly distributed dataset, calculated over the same filter length in bits (left) and the same number of cells (right). 0 50 100 150 200 250 number of sets 0.00 0.02 0.04 0.06 0.08 0.10 false positive pro…

**Figure 5.** Figure 5: A plot of the false positive probability as express [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

**Figure 6.** Figure 6: Filter behaviour of the two data structures over tw [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]

**Figure 7.** Figure 7: Number of hash computations required for a single query over the ShBF (linear) and SBF (constant) over the number of sets. A shifting Bloom filter requires (k + s − 1) hash digests to be computed for each query (where k is the number of hash functions chosen at filter…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 15 canonical work pages

[1]

What's New? Summarizing Contributions in Scientific Literature

S. Tarkoma, C. E. Rothenberg, E. Lagerspetz, Theory and practice of bloom ﬁlters for distributed systems, IEEE Com- munications Surveys and Tutorials 14 (1) (2012) 131–155. doi:10.1109/SURV.2011.031611.00024

work page Pith review arXiv 2012
[2]

Chang, J

F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Bur- rows, T. Chandra, A. Fikes, R. E. Gruber, Bigtable: A distrib uted storage system for structured data, ACM Trans. Comput. Syst. 26 (2) ( 2008) 4:1– 4:26. doi:10.1145/1365815.1365816

arXiv 2008
[3]

B. H. Bloom, Space /time trade-o ﬀs in hash coding with allow- able errors, Communications of the ACM 13 (7) (1970) 422–426 . doi:10.1145/362686.362692

arXiv 1970
[4]

Grandi, On the analysis of bloom ﬁlters, Inf

F. Grandi, On the analysis of bloom ﬁlters, Inf. Process. Lett. 129 (2018) 35–39. doi:10.1016/j.ipl.2017.09.004

work page doi:10.1016/j.ipl.2017.09.004 2018
[5]

L. Luo, D. Guo, R. T. B. Ma, O. Rottenstreich, X. Luo, Optim izing bloom ﬁlter: Challenges, solutions, and comparisons, CoRR abs /1804.04777. arXiv:1804.04777

arXiv
[6]

L. Liu, M. T. ¨Ozsu (Eds.), Encyclopedia of Database Systems, Second Edition, Springer, 2018. doi:10.1007/978-1-4614-8265-9

doi:10.1007/978-1-4614-8265-9 2018
[7]

L. Fan, P . Cao, J. M. Almeida, A. Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE /ACM Trans. Netw. 8 (3) (2000) 281–293. doi:10.1109/90.851975

doi:10.1109/90.851975 2000
[8]

W. Wang, H. Jiang, H. Lu, J. X. Y u, Bloom histogram: Path se lectiv- ity estimation for XML data with updates, in: M. A. Nasciment o, M. T. ¨Ozsu, D. Kossmann, R. J. Miller, J. A. Blakeley, K. B. Schiefe r (Eds.), (e)Proceedings of the Thirtieth International Conference on V ery Large Data Bases, Toronto, Canada, August 31 - September 3 2004, Mo rgan Kau...

work page 2004

Show all 26 references

[9]

Geravand, M

S. Geravand, M. Ahmadi, Bloom ﬁlter applications in netw ork security: A state-of-the-art survey, Computer Networks 57 (18) (2013) 4047–4064. doi:10.1016/j.comnet.2013.09.003

2013 doi
[10]

A. Z. Broder, M. Mitzenmacher, Survey: Network applica tions of bloom ﬁlters: A survey, Internet Mathematics 1 (4) (2003) 48 5–509. doi:10.1080/15427951.2004.10129096

2003
[11]

Dharmapurikar, P

S. Dharmapurikar, P . Krishnamurthy, D. E. Taylor, Long est preﬁx match- ing using bloom ﬁlters, in: A. Feldmann, M. Zitterbart, J. Cr owcroft, D. Wetherall (Eds.), Proceedings of the ACM SIGCOMM 2003 Con - ference on Applications, Technologies, Architectures, an d Protocols f...

2003
[12]

H. Song, F. Hao, M. S. Kodialam, T. V . Lakshman, Ipv6 look ups us- ing distributed and load balanced bloom ﬁlters for 100gbps c ore router line cards, in: INFOCOM 2009. 28th IEEE International Confe rence on Computer Communications, Joint Conference of the IEEE Comp uter and ...

2009
[13]

Chang, K

F. Chang, K. Li, W. Feng, Approximate caches for packet c lassi- ﬁcation, in: Proceedings IEEE INFOCOM 2004, The 23rd Annual Joint Conference of the IEEE Computer and Communications So cieties, Hong Kong, China, March 7-11, 2004, IEEE, 2004, pp. 2196–220 7. doi:10.1109/INFCOM....

2004 arXiv
[14]

Y ang, D

D. Y ang, D. Tian, J. Gong, S. Gao, T. Y ang, X. Li, Diﬀerence bloom ﬁlter: A probabilistic structure for multi-set membership query, in: IEEE Inter- national Conference on Communications, ICC 2017, Paris, Fr ance, May 21-25, 2017, IEEE, 2017, pp. 1–6. doi:10.1109/ICC.2017.7996678

2017
[15]

Y ang, A

T. Y ang, A. X. Liu, M. Shahzad, Y . Zhong, Q. Fu, Z. Li, G. Xi e, X. Li, A shifting bloom ﬁlter framework for set queries, Proceeding s of the VLDB Endowment 9 (5) (2016) 408–419. doi:10.14778/2876473.2876476

2016
[16]

F. Hao, M. S. Kodialam, T. V . Lakshman, H. Song, Fast mult iset membership testing using combinatorial bloom ﬁlters, in: I NFOCOM
[17]

F. Hao, M. S. Kodialam, T. V . Lakshman, H. Song, Fast dy- namic multiple-set membership testing using combinatoria l bloom ﬁlters, IEEE /ACM Trans. Netw. 20 (1) (2012) 295–304. doi:10.1109/TNET.2011.2173351

2012
[18]

Palmieri, L

P . Palmieri, L. Calderoni, D. Maio, Spatial bloom ﬁlter s: Enabling pri- vacy in location-aware applications, in: D. Lin, M. Y ung, J. Zhou (Eds.), Information Security and Cryptology - 10th International C onference, In- scrypt 2014, Beijing, China, December 13-15, 2014, Rev...

2014 doi
[19]

Calderoni, P

L. Calderoni, P . Palmieri, D. Maio, Location privacy wi thout mutual trust: The spatial bloom ﬁlter, Computer Communications 68 (2015) 4–16. doi:10.1016/j.comcom.2015.06.011

2015 doi
[20]

Xiong, Y

S. Xiong, Y . Y ao, Q. Cao, T. He, kbf: A bloom ﬁlter for key- value storage with an application on approximate state machines, in: 2014 IEEE Conference on Computer Communications, INFOCOM 2014, Toronto, Canada, April 27 - May 2, 2014, IEEE, 2014, pp. 1150– 1158. doi:10.1109/I...

2014
[21]

Chazelle, J

B. Chazelle, J. Kilian, R. Rubinfeld, A. Tal, The bloomi er ﬁlter: an e ﬃ- cient data structure for static support lookup tables, in: J . I. Munro (Ed.), Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, Janu...

2004
[22]

D. X. Charles, K. Chellapilla, Bloomier ﬁlters: A secon d look, in: D. Halperin, K. Mehlhorn (Eds.), Algorithms - ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Pro- ceedings, V ol. 5193 of Lecture Notes in Computer Science, Sp ringer, 200...

2008 doi
[23]

Palmieri, L

P . Palmieri, L. Calderoni, D. Maio, Private inter-network routing for wire- less sensor networks and the internet of things, in: Proceed ings of the Computing Frontiers Conference, CF’17, Siena, Italy, May 1 5-17, 2017, ACM, 2017, pp. 396–401. doi:10.1145/3075564.3079068

2017
[24]

Calderoni, P

L. Calderoni, P . Palmieri, D. Maio, Probabilistic prop erties of the spatial bloom ﬁlters and their relevance to cryptographic protocol s, IEEE Trans- actions on Information Forensics and Security 13 (7) (2018) 1710–1721. doi:10.1109/TIFS.2018.2799486

2018
[25]

INFOCOM 2009. 28th IEEE International Conference on Co mputer Communications, Joint Conference of the IEEE Computer and C ommu- nications Societies, 19-25 April 2009, Rio de Janeiro, Braz il, IEEE, 2009. 10

2009
[2009]

5 13–521

28th IEEE International Conference on Computer Commu nica- tions, Joint Conference of the IEEE Computer and Communicat ions So- cieties, 19-25 April 2009, Rio de Janeiro, Brazil [25], pp. 5 13–521. doi:10.1109/INFCOM.2009.5061957

2009

Pith tools

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

[1] [1]

What's New? Summarizing Contributions in Scientific Literature

S. Tarkoma, C. E. Rothenberg, E. Lagerspetz, Theory and practice of bloom ﬁlters for distributed systems, IEEE Com- munications Surveys and Tutorials 14 (1) (2012) 131–155. doi:10.1109/SURV.2011.031611.00024

work page Pith review arXiv 2012

[2] [2]

Chang, J

F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Bur- rows, T. Chandra, A. Fikes, R. E. Gruber, Bigtable: A distrib uted storage system for structured data, ACM Trans. Comput. Syst. 26 (2) ( 2008) 4:1– 4:26. doi:10.1145/1365815.1365816

arXiv 2008

[3] [3]

B. H. Bloom, Space /time trade-o ﬀs in hash coding with allow- able errors, Communications of the ACM 13 (7) (1970) 422–426 . doi:10.1145/362686.362692

arXiv 1970

[4] [4]

Grandi, On the analysis of bloom ﬁlters, Inf

F. Grandi, On the analysis of bloom ﬁlters, Inf. Process. Lett. 129 (2018) 35–39. doi:10.1016/j.ipl.2017.09.004

work page doi:10.1016/j.ipl.2017.09.004 2018

[5] [5]

L. Luo, D. Guo, R. T. B. Ma, O. Rottenstreich, X. Luo, Optim izing bloom ﬁlter: Challenges, solutions, and comparisons, CoRR abs /1804.04777. arXiv:1804.04777

arXiv

[6] [6]

L. Liu, M. T. ¨Ozsu (Eds.), Encyclopedia of Database Systems, Second Edition, Springer, 2018. doi:10.1007/978-1-4614-8265-9

doi:10.1007/978-1-4614-8265-9 2018

[7] [7]

L. Fan, P . Cao, J. M. Almeida, A. Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE /ACM Trans. Netw. 8 (3) (2000) 281–293. doi:10.1109/90.851975

doi:10.1109/90.851975 2000

[8] [8]

W. Wang, H. Jiang, H. Lu, J. X. Y u, Bloom histogram: Path se lectiv- ity estimation for XML data with updates, in: M. A. Nasciment o, M. T. ¨Ozsu, D. Kossmann, R. J. Miller, J. A. Blakeley, K. B. Schiefe r (Eds.), (e)Proceedings of the Thirtieth International Conference on V ery Large Data Bases, Toronto, Canada, August 31 - September 3 2004, Mo rgan Kau...

work page 2004