nx_kfloor_lib.nx source
↩ module page · 142 lines · 6154 B
1// nx_kfloor_lib.nx -- HIERARCHICAL k-ANONYMITY RELEASE WITH COMPLEMENTARY SUPPRESSION (shared lib, 2026-08-24).
2//
3// THE ONE OWNER of the question "which nodes of an aggregate tree may be published under a floor k".
4// Admitted as a LIBRARY, not a verb of one organ, because every multi-organisation feedback surface on
5// the estate (surveys, connect polls, the community pulse) faces the same two defects and today solves
6// only the first, per organ:
7// 1. a level with fewer than k contributors is withheld (nx_survey_serve already does this, per survey);
8// 2. a PUBLISHED parent minus its PUBLISHED children exposes the withheld remainder -- if that remainder
9// has fewer than k contributors the floor at the child was defeated by subtraction. Nobody on the
10// estate handled (2); the lib exists so nobody has to remember it.
11// Model: Sweeney, k-anonymity, IJUFKS 10(5) 2002 -- a release is k-anonymous when every released group
12// is indistinguishable from at least k-1 others. Here a "group" is the set of contributors behind one
13// published number; the complementary rule keeps every DERIVABLE group at k as well.
14//
15// DATA MODEL (parallel arrays, caller-owned, n nodes):
16// own[i] contributors recorded directly at node i (an organisation's own ballots; 0 for a locality)
17// parent[i] index of the parent node, or KFL_NOPARENT for a root; a forest is allowed
18// tot[i] OUT: own[i] plus every descendant's own (kfl_totals)
19// state[i] OUT: KFL_PUB, KFL_WITHHELD_K (under the floor) or KFL_WITHHELD_COMP (complementary)
20// Every function returns a count or a NAMED negative; nothing here prints, allocates beyond scratch, or
21// reads a file. Pure integer. No sampling: every node is visited every call.
22// license_tier: ORIGINAL
23import "nx_syscalls.nx"
24
25const KFL_NOPARENT: i64 = 0 - 1
26const KFL_WITHHELD_K: i64 = 0
27const KFL_PUB: i64 = 1
28const KFL_WITHHELD_COMP: i64 = 2
29const KFL_ERR_K: i64 = 0 - 1 // k < 1 is not a floor
30const KFL_ERR_TREE: i64 = 0 - 2 // a parent index out of range, or a cycle (walk longer than n)
31const KFL_ERR_N: i64 = 0 - 3 // n < 1: a release over nothing is not a release
32
33// subtree totals. Each node walks up to its root adding its own count; a walk longer than n nodes is
34// a cycle and the call REFUSES rather than loop. O(n * depth), exact, no recursion.
35func kfl_totals(own: *i64, parent: *i64, n: i64, tot: *i64) -> i64 {
36 if n < 1 { return KFL_ERR_N }
37 var i: i64 = 0
38 while i < n {
39 if parent[i] != KFL_NOPARENT { if parent[i] < 0 { return KFL_ERR_TREE } }
40 if parent[i] >= n { return KFL_ERR_TREE }
41 if own[i] < 0 { return KFL_ERR_TREE }
42 tot[i] = 0
43 i = i + 1
44 }
45 i = 0
46 while i < n {
47 var j: i64 = i
48 var depth: i64 = 0
49 while j != KFL_NOPARENT {
50 tot[j] = tot[j] + own[i]
51 j = parent[j]
52 depth = depth + 1
53 if depth > n { return KFL_ERR_TREE }
54 }
55 i = i + 1
56 }
57 return 0
58}
59
60// the floor: publish iff tot >= k. Returns the published count.
61func kfl_floor(tot: *i64, n: i64, k: i64, state: *i64) -> i64 {
62 if k < 1 { return KFL_ERR_K }
63 if n < 1 { return KFL_ERR_N }
64 var pub: i64 = 0
65 var i: i64 = 0
66 while i < n {
67 if tot[i] >= k { state[i] = KFL_PUB; pub = pub + 1 } else { state[i] = KFL_WITHHELD_K }
68 i = i + 1
69 }
70 return pub
71}
72
73// residual of node i = tot[i] minus the totals of its PUBLISHED children: the number of contributors an
74// outsider can isolate by subtracting what is printed from what is printed.
75func kfl_residual(tot: *i64, parent: *i64, n: i64, state: *i64, i: i64) -> i64 {
76 var r: i64 = tot[i]
77 var c: i64 = 0
78 while c < n {
79 if parent[c] == i { if state[c] == KFL_PUB { r = r - tot[c] } }
80 c = c + 1
81 }
82 return r
83}
84
85// COMPLEMENTARY SUPPRESSION, to a fixpoint: a published node whose residual is strictly between 0 and k
86// is withheld (state KFL_WITHHELD_COMP). Withholding a node only ever RAISES an ancestor's residual, so
87// the loop converges; it is a loop rather than a single pass so the guarantee does not depend on that
88// argument being remembered. Wrong in the direction of withholding by construction: it never publishes.
89// Returns the number of nodes newly withheld.
90func kfl_complement_suppress(tot: *i64, parent: *i64, n: i64, k: i64, state: *i64) -> i64 {
91 if k < 1 { return KFL_ERR_K }
92 if n < 1 { return KFL_ERR_N }
93 var newly: i64 = 0
94 var changed: i64 = 1
95 var rounds: i64 = 0
96 while changed == 1 {
97 changed = 0
98 var i: i64 = 0
99 while i < n {
100 if state[i] == KFL_PUB {
101 let r: i64 = kfl_residual(tot, parent, n, state, i)
102 if r > 0 { if r < k {
103 state[i] = KFL_WITHHELD_COMP
104 newly = newly + 1
105 changed = 1
106 } }
107 }
108 i = i + 1
109 }
110 rounds = rounds + 1
111 if rounds > n + 1 { return KFL_ERR_TREE } // cannot happen on a tree; named rather than trusted
112 }
113 return newly
114}
115
116// the whole release: totals -> floor -> complementary suppression. Returns the published count after
117// suppression, or the first named error.
118func kfl_release(own: *i64, parent: *i64, n: i64, k: i64, tot: *i64, state: *i64) -> i64 {
119 let rt: i64 = kfl_totals(own, parent, n, tot)
120 if rt < 0 { return rt }
121 let pub: i64 = kfl_floor(tot, n, k, state)
122 if pub < 0 { return pub }
123 let sup: i64 = kfl_complement_suppress(tot, parent, n, k, state)
124 if sup < 0 { return sup }
125 return pub - sup
126}
127
128// partition check: published + withheld_k + withheld_comp must equal n. Returns 1 when it sums.
129func kfl_partition(state: *i64, n: i64, out3: *i64) -> i64 {
130 out3[0] = 0
131 out3[1] = 0
132 out3[2] = 0
133 var i: i64 = 0
134 while i < n {
135 if state[i] == KFL_PUB { out3[0] = out3[0] + 1 }
136 if state[i] == KFL_WITHHELD_K { out3[1] = out3[1] + 1 }
137 if state[i] == KFL_WITHHELD_COMP { out3[2] = out3[2] + 1 }
138 i = i + 1
139 }
140 if out3[0] + out3[1] + out3[2] == n { return 1 }
141 return 0
142}