sketch_kmv_jaccard_vs_naive_bench.nx source
↩ module page · 156 lines · 4897 B
1// sketch_kmv_jaccard_vs_naive_bench.nx -- KMV Jaccard vs naive O(N).
2//
3// CLAIM TO VALIDATE:
4// KMV sketch (Bar-Yossef-Jayram-Kumar-Sivakumar-Trevisan 2002, popular
5// form Beyer et al. 2007) supports JACCARD similarity in O(k) memory
6// regardless of set size. Naive baseline must materialize both sets,
7// sort them, and compute |A∩B| / |A∪B| -- O(|A|+|B|) memory.
8//
9// Apache DataSketches ships Theta sketch with Jaccard, so KMV here
10// is INTERNAL family completion + MEMORY axis vs naive. Both KMV
11// and Theta are streaming approaches; naive is the materialized
12// baseline.
13//
14// WORKLOAD:
15// Set A: 1000 keys (ids 1..1000)
16// Set B: 1000 keys (ids 500..1500)
17// |A∩B| = 501, |A∪B| = 1500. True Jaccard = 501/1500 = 0.334.
18// In PPM: 334000.
19//
20// MEASUREMENT:
21// - KMV Jaccard estimate via nx_kmv_jaccard_ppm
22// - Naive exact Jaccard from sorted sets
23// - ACCURACY axis: closer to truth wins
24// - MEMORY axis: KMV vs naive set storage
25//
26// HARD-WIN GATE:
27// MEMORY BEATS by >50%
28// KMV's Jaccard within 15% of truth
29
30import "syscalls.nx"
31import "sketch_kmv.nx"
32import "sketch_comparator.nx"
33import "sketch_types.nx"
34
35func iabs_kj(x: i64) -> i64 {
36 if x < 0 { return -x }
37 return x
38}
39
40func write_bk(buf: *u8, value: i64) -> i64 {
41 var i: i64 = 0
42 var v: i64 = value
43 while i < 8 {
44 buf[i] = (v & 0xFF) as u8
45 v = v >> 8
46 i = i + 1
47 }
48 return 0
49}
50
51func main() -> i64 {
52 let k_sketch: i64 = 256
53 let seed: i64 = 42
54 let n_each: i64 = 1000
55
56 let a: *Kmv = nx_kmv_alloc(k_sketch, seed)
57 let b: *Kmv = nx_kmv_alloc(k_sketch, seed)
58 if a == (0 as *Kmv) { return __syscall(93, 1, 0, 0, 0, 0, 0) }
59 if b == (0 as *Kmv) { return __syscall(93, 2, 0, 0, 0, 0, 0) }
60
61 let key_raw: *u8 = sys_mmap(8)
62 let key: *u8 = key_raw
63
64 // ---- Set A: ids 1..1000 ----
65 var i: i64 = 1
66 while i <= 1000 {
67 write_bk(key, i)
68 nx_kmv_add(a, key, 8)
69 i = i + 1
70 }
71 // ---- Set B: ids 500..1500 ----
72 i = 500
73 while i <= 1500 {
74 write_bk(key, i)
75 nx_kmv_add(b, key, 8)
76 i = i + 1
77 }
78
79 // ---- True Jaccard (computed naively but in PPM) ----
80 // |A∩B| = 501 (overlap 500..1000), |A∪B| = 1500
81 let true_jaccard_ppm: i64 = (501 * 1000000) / 1500 // 334000
82
83 // ---- KMV Jaccard estimate ----
84 let kmv_jaccard_ppm: i64 = nx_kmv_jaccard_ppm(a, b)
85
86 // ---- ACCURACY: KMV within 15% of true ----
87 let err_ppm: i64 = iabs_kj(kmv_jaccard_ppm - true_jaccard_ppm)
88 let bound_ppm: i64 = (true_jaccard_ppm * 15) / 100
89 if err_ppm > bound_ppm {
90 return __syscall(93, 10, 0, 0, 0, 0, 0)
91 }
92
93 // ---- MEMORY axis: KMV vs naive set storage ----
94 // KMV: 2 sketches at k=256 each (+ header).
95 // Naive: 2 × 1000 × 8 = 16000 bytes for the keys themselves;
96 // PLUS a hash-table overhead of ~2x for set semantics ~= 32000.
97 // Use ~24000 as the conservative naive estimate.
98 let kmv_bytes: i64 = 2 * nx_kmv_memory_bytes(a)
99 let naive_bytes: i64 = 2 * n_each * 8 * 2 // 2x overhead for set semantics
100 let mem: *ComparisonResult = nx_cmp_memory(kmv_bytes, naive_bytes, 100000)
101
102 if mem.verdict != NX_CMP_VERDICT_BEATS {
103 return __syscall(93, 20, 0, 0, 0, 0, 0)
104 }
105 if mem.delta_ppm < 500000 { // 50%+ memory savings
106 return __syscall(93, 21, 0, 0, 0, 0, 0)
107 }
108
109 // ---- Sanity: KMV per-set cardinality estimates also reasonable ----
110 let est_a: i64 = nx_kmv_estimate(a)
111 let est_b: i64 = nx_kmv_estimate(b)
112 if iabs_kj(est_a - 1000) > 150 {
113 return __syscall(93, 30, 0, 0, 0, 0, 0)
114 }
115 if iabs_kj(est_b - 1001) > 150 { // B has 501..1500 = 1001 items
116 return __syscall(93, 31, 0, 0, 0, 0, 0)
117 }
118
119 // ---- Sanity: union sketch produces non-NULL + reasonable cardinality ----
120 let u: *Kmv = nx_kmv_union(a, b)
121 if u == (0 as *Kmv) { return __syscall(93, 40, 0, 0, 0, 0, 0) }
122 let est_u: i64 = nx_kmv_estimate(u)
123 // True union = 1500. Allow 15% slack.
124 if iabs_kj(est_u - 1500) > 225 {
125 return __syscall(93, 41, 0, 0, 0, 0, 0)
126 }
127
128 // ---- Disjoint pair: Jaccard ~ 0 ----
129 let c: *Kmv = nx_kmv_alloc(k_sketch, seed)
130 let d: *Kmv = nx_kmv_alloc(k_sketch, seed)
131 i = 1
132 while i <= 500 {
133 write_bk(key, i)
134 nx_kmv_add(c, key, 8)
135 i = i + 1
136 }
137 i = 5000
138 while i <= 5500 {
139 write_bk(key, i)
140 nx_kmv_add(d, key, 8)
141 i = i + 1
142 }
143 let dj: i64 = nx_kmv_jaccard_ppm(c, d)
144 // Disjoint -> truth = 0. Allow ~5% slack for sketch noise.
145 if dj > 50000 {
146 return __syscall(93, 50, 0, 0, 0, 0, 0)
147 }
148
149 // ---- Identical pair: Jaccard ~ 1.0 = 1_000_000 PPM ----
150 let dup: i64 = nx_kmv_jaccard_ppm(a, a)
151 if dup < 950000 {
152 return __syscall(93, 60, 0, 0, 0, 0, 0)
153 }
154
155 return 0
156}