To solve approximate top-k in tight memory, I'll present the Space-Saving algorithm (best for exact top-k heavy hitters with small constant error) and contrast Count-Min Sketch (CMS) when we want point queries and mergeability. I'll give Java-like pseudocode for Space-Saving, explain error bounds, memory layout, and show how to merge shards for both approaches.Approach summary:- Space-Saving: maintain m counters (m determined by memory, e.g., 10MB -> number of counters). For each incoming item: - If item present, increment its counter. - Else if free slot exists, insert with count=1. - Else replace the minimum counter: set key=item, count=minCount+1, and remember error=previous minCount.- Guarantees: reported count >= true count - error. For any item not in table, estimated count ≤ true count ≤ estimated + total_stream_count/m.- CMS alternative: uses w×d table hashed; gives estimated count ≥ true count and an additive error <= εN with probability 1-δ. CMS is mergeable by summing tables.Java-like Space-Saving (memory-compact, O(1) update amortized):java
// Each bucket: key (long/int/hash), count (long), err (long)
class Bucket { long key; long count; long err; boolean used; }
class SpaceSaving {
Bucket[] buckets; // size m
int m;
SpaceSaving(int m){ this.m=m; buckets = new Bucket[m]; for(int i=0;i<m;i++) buckets[i]=new Bucket(); }
void update(long key){
int idx = findIndex(key);
if(idx!=-1){ buckets[idx].count++; return; }
int free = findFree();
if(free!=-1){ buckets[free].key=key; buckets[free].count=1; buckets[free].err=0; buckets[free].used=true; return; }
int minIdx = findMinIndex();
long minCount = buckets[minIdx].count;
buckets[minIdx].key = key;
buckets[minIdx].err = minCount;
buckets[minIdx].count = minCount + 1;
}
// linear scan helpers; in practice use hashmap + min-heap or doubly-linked freq lists for O(1)
int findIndex(long key){ for(int i=0;i<m;i++) if(buckets[i].used && buckets[i].key==key) return i; return -1; }
int findFree(){ for(int i=0;i<m;i++) if(!buckets[i].used) return i; return -1; }
int findMinIndex(){ int mi=0; for(int i=1;i<m;i++) if(buckets[i].count < buckets[mi].count) mi=i; return mi; }
List<Bucket> topK(int k){
List<Bucket> list = Arrays.asList(buckets);
list = list.stream().filter(b->b.used).sorted((a,b)->Long.compare(b.count,a.count)).limit(k).collect(Collectors.toList());
return list;
}
}
