{"id":"a4692f49-a0a3-4e67-8ac8-10890d58a737","arxiv_id":"2505.03529","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"SKALD aggregates per-chunk equivalence-class histograms to perform k-anonymisation with a global view under limited RAM, reporting substantially lower DM* information loss than per-chunk ARX on synthetic data.","lead":"SKALD is a chunk-based k-anonymisation algorithm that keeps a global histogram of equivalence classes in bounded memory and then runs an existing lattice search on it, instead of anonymising each chunk separately. For a 125 million row synthetic dataset it reports up to nine times lower information loss than running ARX on each chunk.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Phase 1's encoding key-value map stores all unique numerical QID values across the whole dataset; this structure is absent from the Section III.A memory budget, so the bounded-memory scalability claim is not established.","rationale":"The reader's weakest_assumption correctly identifies the encoding map as the load-bearing unaccounted memory structure. My independent reading of Section III.B.1 confirms that the key-value map must persist across all chunks to decode the final output, and that its cardinality equals the number of distinct encoded numerical values in the entire dataset. This is not bounded by the histogram budget in Section III.A, so the scalability claim fails in the general case and is only masked in the synthetic experiment by the low cardinality of PIN codes (1,347 unique values). The secondary issue with Eq. (1) is real but less central; it only affects parameter selection and can be corrected without changing the algorithm's structure. Since the reader already assigned a conditional verdict based on this same concern, and the concern is addressable by either an external-memory encoding structure or a revised memory accounting, my stress-test does not move the verdict. I agree with the reader's assessment.","tokens_in":8832,"tokens_out":5182,"duration_ms":52649,"concrete_test":"Instrument Phase 1 to measure peak resident set size (RSS) of the encoding key-value map while varying the number of distinct values U in a synthetic numerical QID (e.g., U = 10^3, 10^5, 10^7) with fixed histogram budget NRAM from Eq. (3) (e.g., 4-byte counters). If RSS scales as Theta(U) and exceeds the available RAM budget for large U, the bounded-memory claim is false; if RSS stays within a constant factor of the histogram budget, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that SKALD k-anonymises datasets larger than RAM using only a bounded-memory histogram of equivalence-class counts. The weak point is Phase 1 (Section III.B.1): 'we pass the chunks of data one at a time, taking the unique values of the numerical QIDs to be encoded in the dataset, sorting the values, and then assigning a new identifier to that value. A key-value map is created during the encoding process.' This map holds one entry per distinct encoded value across the full dataset. Its size is not bounded by NRAM from Eqs. (1)-(3), which budget only histogram bins. For high-cardinality numerical QIDs (e.g., precise coordinates, raw identifiers, or PIN-like codes with millions of distinct values), the map can grow linearly with dataset cardinality and exceed available RAM, exactly the regime SKALD targets. The synthetic experiment uses only 1,347 unique PIN codes, so the map is tiny; the memory accounting in Section III.A would not cover a realistic large-cardinality case. A secondary internal inconsistency is Eq. (1): the '+1' suppression bin is placed inside the product over numerical QIDs, yielding cat*num+cat instead of cat*num+1; this overcount can force coarser (Ri,Wj) choices than necessary and understate achievable utility, but it is independently fixable. The encoding-map gap, by contrast, invalidates the claim that SKALD's memory footprint is bounded by histogram storage.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SKALD, a three-phase chunked algorithm for k-anonymisation of tabular datasets too large for RAM. In Phase 1, SKALD encodes numerical QIDs and selects categorical resolutions and numerical bin widths so that the number of histogram bins satisfies a RAM bound (Eqs. (1)-(3)). In Phase 2, it builds an aggregate histogram over all chunks, traverses a generalisation lattice using predictive tagging, and selects the node that minimises the monotonic Discernibility Metric DM* under the k-anonymity and suppression constraints. In Phase 3, it decodes and generalises the dataset. On a synthetic medical-style dataset with 125 chunks of one million rows each, the authors report that SKALD yields finer generalisation than per-chunk ARX Flash and achieves a DM* ratio of at least nine for 125 chunks.","tokens_in":9164,"tokens_out":6745,"duration_ms":69753,"significance":"If the memory accounting is completed, SKALD would be a useful practical contribution: it replaces per-chunk k-anonymisation with an aggregate-histogram approach that preserves a global view of the data, and the experimental comparison against the external ARX Flash baseline using the external DM* metric from [9] is appropriate and not circular. The core algorithmic idea is simple and internally coherent, and the paper makes falsifiable predictions, namely that SKALD's utility advantage over per-chunk anonymisation grows with the number of chunks. However, the manuscript does not yet establish the central bounded-memory claim because the Phase 1 encoding map is not included in the memory budget, and the chunk-size independence claim is contradicted by Eq. (3)'s explicit dependence on chunk size. These issues are fixable but load-bearing.","major_comments":[{"comment":"The Phase 1 encoding procedure creates a key-value map holding one entry per distinct encoded numerical QID value across the entire dataset. The size of this map is not bounded by NRAM from Eqs. (1)-(3), which budget only histogram bins. For high-cardinality numerical QIDs (e.g., precise coordinates or raw identifiers with millions of distinct values), this map can grow linearly with dataset cardinality and exceed available RAM, which is exactly the regime SKALD targets. The synthetic experiment uses only 1,347 unique PIN codes, so it does not exercise this issue. To establish the bounded-memory scalability claim, the authors must either explicitly budget the encoding map in RAM, replace it with a disk-backed or streaming encoding that does not require holding all unique values, or state a cardinality assumption under which the map is small.","section":"III.B.1, Phase 1"},{"comment":"Equation (1) places the '+1' suppression bin inside the product over numerical QIDs, yielding Ndata = (prod_i C_i[Ri]) * (prod_j ((Qj,max - Qj,min + 1)/Wj) + 1). This counts the suppression bin once per categorical combination, i.e., cat*num + cat, rather than once globally, which would be cat*num + 1. The overcount can force unnecessarily coarse choices of (Ri, Wj) to satisfy Eq. (2), thereby understating the achievable utility of SKALD. The equation should be corrected to Ndata = (prod_i C_i[Ri]) * (prod_j ((Qj,max - Qj,min + 1)/Wj)) + 1, or the authors should justify why a suppression bin per categorical combination is intended.","section":"III.A, Eq. (1)"},{"comment":"The claim that 'the accuracy of SKALD does not depend on the chunk size' is not supported by the derivation of NRAM. The text considers a reduced chunk of n/2 records occupying S/2 bytes, but then substitutes S = n*d into NRAM = S/16, giving NRAM = n*d/16. If n is the actual reduced chunk size, NRAM depends linearly on n; if n is the original chunk size, the accounting no longer matches the reduced-chunk scenario. The derivation should be recast in terms of a fixed total RAM budget R, with the chunk size and histogram space as explicit partitions of R, so that the dependence on chunk size can be stated correctly rather than asserted.","section":"III.A, Eq. (3)"},{"comment":"The headline empirical claim of 'at least nine-fold reduction' in DM* for 125 chunks rests on a single synthetic dataset, with no error bars, no repeated trials, and no code or data release. Since the result is quantitative and depends on the specific distribution of the 1,347 unique PIN codes, the authors should provide the benchmark artifacts or add additional datasets with varying cardinalities and QID types to support the general claim that the improvement grows with the number of chunks.","section":"V, Fig. 3"}],"minor_comments":[{"comment":"The caption reads 'An generalisation lattice'; it should read 'A generalisation lattice'.","section":"Fig. 1 caption"},{"comment":"The title of Sweeney's paper contains a typo: 'Knowldege-Based Systems' should be 'Knowledge-Based Systems'.","section":"References [11]"},{"comment":"The expression (Qj,max - Qj,min + 1)/Wj is ambiguous for continuous numerical attributes; the authors should specify whether integer division, flooring, or ceiling is intended, and how inclusive bin boundaries are handled.","section":"III.A, Eq. (1)"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a data-privacy/IT journal and the comparison methodology is not circular. The main technical gap is the unaccounted Phase 1 encoding map, which undermines the bounded-memory claim as written; if the authors fix the memory accounting, Eq. (1), and the chunk-size dependence, the paper could become publishable. I do not see citation or novelty-disclosure concerns beyond the incremental nature of the contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea here is real: k-anonymity and DM* can be evaluated exactly on a global histogram of equivalence-class counts, built incrementally from chunks, and that global view gives better utility than per-chunk ARX. That is a useful engineering contribution for practitioners sitting on datasets larger than RAM. The three-phase design is straightforward, and the comparison to ARX Flash is fair enough for a first evaluation. The reported nine-fold DM* reduction at 125 chunks is plausible and worth taking seriously.\n\nThe soft spots are real, though. The load-bearing one is Phase 1's encoding key-value map. The memory budget in Eqs. (1)-(3) only counts histogram bins, but the encoding map stores one entry per distinct numerical value across the entire dataset. For high-cardinality QIDs like precise coordinates or raw codes, that map can grow linearly with dataset size and blow the bounded-memory claim. The synthetic data uses only 1,347 distinct PIN codes, so it never exercises this. That matters because the central claim is bounded-memory operation on datasets larger than RAM.\n\nEq. (1) also puts the suppression bin inside the product, counting it per categorical combination rather than once. That overcounts bins and can push the algorithm toward coarser resolutions than needed. And the \"independent of chunk size\" claim is contradicted by Eq. (3), which makes the bin budget a function of chunk size. These are fixable, but they are actual flaws.\n\nThere is no code or data shipped, so reproducibility is currently limited. The paper should be asked to release the synthetic generator and the SKALD implementation, or at least the aggregation step.\n\nWho is this for? Practitioners anonymising large tabular data with limited RAM, and researchers working on scalable k-anonymisation. The central idea holds up; the soft spots are addressable. I'd send this to peer review, not desk reject, and ask for a revision that fixes the memory accounting, corrects the bin-count formula, and releases code/data. I would not cite it yet.","headline":"SKALD's chunk-histogram aggregation is a sensible engineering idea, but the memory accounting misses the Phase 1 encoding map and the paper overclaims chunk-size independence.","tokens_in":9674,"tokens_out":2896,"would_cite":false,"duration_ms":28792,"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":"SKALD k-anonymises datasets larger than available RAM by aggregating per-chunk histogram counts into one global histogram, then searching a generalisation lattice on that histogram, reporting at least a nine-fold lower DM* than a…","keywords":["k-anonymisation","chunked processing","sufficient statistics","generalisation lattice","RAM-constrained","data utility","DM* metric","privacy"],"falsifier":"Instrument peak memory during Phase 1 on a dataset whose unique-value map is larger than the RAM budget; if the run stays within budget the central scalability claim survives, and if it does not, the claim fails for that dataset. A second check is to run SKALD and a full-memory global-optimal solver on the same small dataset and compare DM*; a lower DM* from the global solver would show that SKALD's global view is still approximate.","tokens_in":8633,"feed_emoji":"📊","tokens_out":8693,"duration_ms":81613,"temperature":0.7,"pith_summary":"The paper proposes SKALD, a chunked algorithm for k-anonymising tabular data that exceeds available RAM. Its central claim is that a single histogram of equivalence-class counts, accumulated chunk by chunk, carries enough information to k-anonymise the whole dataset with a global view, so output utility does not depend on chunk size. On a synthetic medical-style dataset of 125 million records, the paper reports at least a nine-fold reduction in the DM* information-loss metric compared with a per-chunk baseline at 125 chunks, across several values of k. If the claim holds, memory-bound anonymisation can keep the global perspective that per-chunk tools lose.","feed_headline":"One global histogram beats per-chunk anonymisation nine-fold","feed_subtitle":"SKALD merges per-chunk counts into one bounded histogram, keeping a global view when datasets outgrow RAM.","key_machinery":"The central object is an aggregate histogram: each bin counts records sharing one equivalence class, i.e. one combination of quasi-identifier values at a chosen generalisation level. SKALD accumulates this histogram by adding per-chunk counts, so the final array is a bounded-memory sufficient statistic for the whole dataset. The lattice navigation uses predictive tagging to mark nodes as compliant or non-compliant with the memory bound and with k-anonymity, and the DM* metric ranks surviving nodes by information loss.","core_discovery":"The paper claims that a single histogram of equivalence-class counts, updated chunk by chunk, is enough to solve k-anonymisation for the entire dataset without ever holding more than one chunk in RAM. SKALD first encodes sparse numerical QIDs and picks the finest categorical resolutions and numerical bin widths that keep the bin count within memory. It then passes all chunks again, accumulating one global histogram whose bins are equivalence classes, and runs a lattice search over this aggregate histogram, using predictive tagging to prune nodes and the DM* metric to choose the least-loss node that meets k-anonymity. The resulting generalisation is applied on a final pass, decoding the encoding and releasing the anonymised table. The experiments report that this global view reduces DM* by at least a factor of nine relative to a per-chunk baseline at 125 chunks, across the tested values of k.","pith_inferences":["A direct extension would store per-sensitive-attribute counts in each histogram bin so that l-diversity or t-closeness could be enforced on the aggregate histogram; the paper names this as future work.","If the Phase 1 encoding map were spilled to disk, the same three-pass design could handle datasets whose unique-value dictionaries exceed RAM; the paper does not discuss this variant.","The reported DM* ratios come from one synthetic dataset; a reader could test whether the trend survives on real datasets with more categorical QIDs, where the bin-count formula in Eq. (1) grows quickly with the number of QID levels."],"forward_implications":["For a fixed RAM budget, smaller chunks do not degrade output: SKALD can halve the chunk size and use the freed memory for histogram storage while keeping the same aggregate counts.","As a dataset grows past available RAM, SKALD's utility advantage over per-chunk k-anonymisation grows; the paper's experiments show the gap widening as the number of chunks increases from 5 to 125.","Because the aggregate histogram is built before the lattice search, the search cost depends on the number of bins rather than the number of records, so row count can scale while the memory bound stays fixed.","The released dataset satisfies k-anonymity globally even though processing is chunked, since the suppression bin and all equivalence-class counts come from the merged histogram."],"supporting_citations":[{"why":"Supplies the lattice-search method, predictive tagging, and the DM* information-loss metric that SKALD adapts and reports.","marker":"[9]"},{"why":"Defines the globally optimal k-anonymity algorithm used as the per-chunk baseline that SKALD is measured against.","marker":"[18]"},{"why":"Describes the open-source anonymisation framework whose per-chunk behaviour motivates the need for SKALD.","marker":"[10]"},{"why":"Defines the k-anonymity model and the precision metric SKALD uses to choose memory-compliant resolutions.","marker":"[11]"},{"why":"Establishes NP-hardness of optimal k-anonymity, motivating lattice search with pruning and a memory-bounded design.","marker":"[16]"}],"fun_headline_variants":["Global histogram from chunks beats per-chunk k-anonymity","SKALD: one global histogram for large dataset anonymisation","9x better anonymisation via one global histogram from chunks","SKALD: anonymise datasets larger than RAM with one histogram"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm assumes that the sorted list of every distinct value appearing in the encoded numerical columns fits in memory at once, because the paper's memory budget counts only histogram bins, not this Phase 1 map.","fun_headline_variants_meta":{"raw":{"variants":["Global histogram from chunks beats per-chunk k-anonymity","SKALD: one global histogram for large dataset anonymisation","9x better anonymisation via one global histogram from chunks","SKALD: anonymise datasets larger than RAM with one histogram"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001716,"raw_usage":{"total_tokens":6748,"prompt_tokens":859,"completion_tokens":5889,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":5820}},"tokens_in":475,"tokens_out":5889,"duration_ms":39965,"temperature":1.0,"reasoning_tokens":5820,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:49:14.796859+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Instrument peak memory during Phase 1 on a dataset whose unique-value map is larger than the RAM budget; if the run stays within budget the central scalability claim survives, and if it does not, the claim fails for that dataset. A second check is to run SKALD and a full-memory global-optimal solver on the same small dataset and compare DM*; a lower DM* from the global solver would show that SKALD's global view is still approximate.","supporting_citations":[{"cited_title":"A Globally Optimal k-Anonymity Method for the De-Identification of Health Data,","cited_arxiv_id":null,"evidence_quote":"Supplies the lattice-search method, predictive tagging, and the DM* information-loss metric that SKALD adapts and reports."},{"cited_title":"Flash: Efficient, stable and optimal k- anonymity,","cited_arxiv_id":null,"evidence_quote":"Defines the globally optimal k-anonymity algorithm used as the per-chunk baseline that SKALD is measured against."},{"cited_title":"Lightning: Utility-driven anonymiza- tion of high-dimensional data,","cited_arxiv_id":null,"evidence_quote":"Describes the open-source anonymisation framework whose per-chunk behaviour motivates the need for SKALD."},{"cited_title":"Achieving k-anonymity privacy protection using generalization and suppression,","cited_arxiv_id":null,"evidence_quote":"Defines the k-anonymity model and the precision metric SKALD uses to choose memory-compliant resolutions."}],"review_version":1}