{"id":"10102758-fe01-49b2-af12-4b48aeccfdce","arxiv_id":"1908.10644","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A generalized shifting Bloom filter for many disjoint sets is compared with the spatial Bloom filter, showing better space efficiency at higher computational cost.","lead":"This paper compares two Bloom filter variants that let a single filter store multiple sets: the shifting Bloom filter and the spatial Bloom filter. It finds the shifting filter uses less memory, but pays for it with much higher query cost as sets grow.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 1 defines a 2m-bit ShBF, but Section 4 switches to an m-bit circular implementation and all probability formulas use m; the central comparison may be quantifying a different structure than the one formally proposed.","rationale":"The reader's weakest assumption identifies exactly the discrepancy I find most load-bearing: Definition 1 and Eq. (3) define a 2m-bit ShBF, while the probability analysis and the experiments use an m-bit circular ShBF with modulo-m indexing. The paper itself flags the circular choice in Section 4, but that self-reference does not resolve the inconsistency; it confirms that the formal definition and the evaluated structure diverge. This matters because the paper's main quantitative claims, including the new formulas (5)-(11) and the space-efficiency comparison in Figure 4 and Table 2, depend on the number of cells being m. If the formal 2m-bit structure is intended, the formulas are not justified: the distribution of set bits over 2m cells is not uniform, so the standard Bloom-filter approximation in Eq. (5) needs a different derivation. If the circular m-bit structure is intended, Definition 1 and Eq. (3) should be rewritten to describe m cells with modulo-m indexing. Either way, the paper cannot be accepted as written. I do not see evidence that the qualitative trade-off, ShBF roughly matching SBF error rates at lower memory cost but with query cost linear in s, is false; the concern is that the quantitative support for that trade-off is attached to an internally inconsistent specification. For that reason the reader's CONDITIONAL verdict remains appropriate: the authors should align the definition with the implementation, restate the formulas for the chosen structure, and make the experimental parameters and code explicit. I would not reject the paper, because the circular version is clearly described in Section 4 and the qualitative comparison is plausible; I also would not accept it as is, because a reader cannot tell which structure the probability model actually covers.","tokens_in":15679,"tokens_out":10023,"duration_ms":115558,"concrete_test":"Simulate the formal 2m-bit ShBF described by Definition 1 (no modulo, positions h(δ)+o(δ) in a 2m-bit vector) using the same n, k, s, and m as Section 4, and measure the empirical false-positive rate. Compare that rate with Eq. (5) computed with m and with 2m, and also with the circular m-bit implementation. If the 2m-bit false-positive rate differs from the circular rate by more than the sampling error (e.g., 10% relative), the paper's formulas and experiments do not describe the same data structure; the space-efficiency conclusion must then be re-derived for whichever structure is actually proposed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central contribution is the generalized ShBF (Definition 1), whose vector representation b has 2m bits (Eq. 3). Yet every probability formula (5)-(11) uses m as the number of cells, and Section 4 explicitly replaces the structure with a circular m-bit version: 'we implemented a circular ShBF version composed of m bits' and 'cell indexing is subject to a m modulus.' These are not equivalent. In the formal 2m-bit structure, positions h(δ)+o(δ) range over [2,2m] but are not uniformly distributed: Δ1 occupies [1,m], while set i occupies [o_i+1,m+o_i], producing nonuniform edge densities and per-set windows of length m rather than 2m. The standard Bloom-filter formula (5) therefore does not follow from Definition 1. For the circular m-bit structure, the formulas are plausible only if the formal definition is revised to m cells with modulo-m indexing. Because the empirical comparison, Figure 4, Table 2, and the space-efficiency conclusion are all evaluated on the circular structure, the paper's formal definition and its analysis describe different objects. This ambiguity is load-bearing: the claimed 'new probability formulas' and the memory comparison (l=m for ShBF versus l=8m for SBF) would need to be recomputed under one consistent definition, and it is not knowable from the paper which object was actually assessed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15970,"tokens_out":3948,"duration_ms":40902,"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":[{"comment":"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":"Section 2, Definition 1 and Eq. (3), vs. Section 4"},{"comment":"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":"Section 2.1, Eqs. (7)-(11)"},{"comment":"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.","section":"Section 4, Figure 4 and Table 2"}],"minor_comments":[{"comment":"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.","section":"Section 4, after Figure 5"},{"comment":"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.","section":"Footnote 1"},{"comment":"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.","section":"Table 3"},{"comment":"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.","section":"Figure 2"}],"recommendation":"major_revision","confidential_remarks":"The main issue is fixable: the authors should either revise Definition 1 to describe the circular m-bit ShBF or re-derive all formulas and experiments for the 2m-bit structure. In the current form, the reader cannot tell which object was actually evaluated. I also note that no code or datasets are provided, which limits reproducibility of the experimental results; making the implementation available would strengthen the paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nThe 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.\n\nWho 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.","headline":"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.","tokens_in":16455,"tokens_out":2348,"would_cite":false,"duration_ms":28202,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Bloom filter","shifting Bloom filter","spatial Bloom filter","multiple sets","association queries","false positive probability","inter-set error","probabilistic data structures"],"falsifier":"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.","tokens_in":15475,"feed_emoji":"🔍","tokens_out":8741,"duration_ms":76982,"temperature":0.7,"pith_summary":"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.","feed_headline":"Shifting Bloom filter saves memory, costs more hashes","feed_subtitle":"Head-to-head tests over 255 sets: one filter uses fewer bits, the other answers every query in constant time.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces the original Bloom filter whose occupancy reasoning and false-positive formula underpin Equations (5) and (18).","marker":"[3]"},{"why":"Defines the original two-set shifting Bloom filter that this paper generalises to s disjoint sets and to an unrestricted offset space.","marker":"[15]"},{"why":"Defines the spatial Bloom filter with labelled multi-bit cells, the structure the ShBF is compared against.","marker":"[19]"},{"why":"Supplies the SBF false-positive and inter-set error probabilities recalled as Equations (18)-(21) and the collision-state analysis used in the comparison.","marker":"[24]"}],"fun_headline_variants":["New ShBF cuts bits per set, hikes hash work","Multi-set Bloom: ShBF saves space, SBF saves time","Generalized ShBF: fewer bits, more hashes per query","Shifting Bloom filter: leaner but slower for set lookup","Space vs speed: ShBF and SBF for multi-set filters"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["New ShBF cuts bits per set, hikes hash work","Multi-set Bloom: ShBF saves space, SBF saves time","Generalized ShBF: fewer bits, more hashes per query","Shifting Bloom filter: leaner but slower for set lookup","Space vs speed: ShBF and SBF for multi-set filters"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000554,"raw_usage":{"total_tokens":2651,"prompt_tokens":969,"completion_tokens":1682,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":585,"completion_tokens_details":{"reasoning_tokens":1594}},"tokens_in":585,"tokens_out":1682,"duration_ms":10633,"temperature":1.0,"reasoning_tokens":1594,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:38:01.047971+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Calderoni, P","cited_arxiv_id":null,"evidence_quote":"Defines the spatial Bloom filter with labelled multi-bit cells, the structure the ShBF is compared against."},{"cited_title":"Calderoni, P","cited_arxiv_id":null,"evidence_quote":"Supplies the SBF false-positive and inter-set error probabilities recalled as Equations (18)-(21) and the collision-state analysis used in the comparison."}],"review_version":1}