Approach summary:- Use fixed-score binning (histogram) as a simple, memory-bounded sketch: maintain counts of positives and negatives per bin. This gives O(B) memory and O(1) update. Alternative higher-accuracy sketches: t-digest or KLL quantile sketches to approximate score CDFs; these give better error with skewed distributions but are more complex to merge and update.- We compute approximate ROC by treating each bin as a bucketed score (use bin midpoints), accumulate TPR/FPR via cumulative sums, and compute AUC by trapezoidal rule.- Merge: sum per-bin pos/neg counts across shards (simple, exact for histogram). For t-digest/KLL merge by their merge APIs.Python implementation (fixed-bin histogram):python
class StreamingAUC:
def __init__(self, bins=100, score_min=0.0, score_max=1.0):
self.bins = bins
self.min = score_min
self.max = score_max
self.pos = [0]*bins
self.neg = [0]*bins
self.total_pos = 0
self.total_neg = 0
self.bin_width = (self.max - self.min) / bins
def _bin_index(self, score):
if score <= self.min: return 0
if score >= self.max: return self.bins-1
return int((score - self.min) / self.bin_width)
def add(self, y_true, score):
idx = self._bin_index(score)
if y_true:
self.pos[idx] += 1
self.total_pos += 1
else:
self.neg[idx] += 1
self.total_neg += 1
def merge(self, other):
assert self.bins == other.bins and self.min == other.min and self.max == other.max
for i in range(self.bins):
self.pos[i] += other.pos[i]
self.neg[i] += other.neg[i]
self.total_pos += other.total_pos
self.total_neg += other.total_neg
def auc(self):
if self.total_pos == 0 or self.total_neg == 0:
return 0.5
# iterate bins from high score -> low score to build ROC
tpr_prev = fpr_prev = 0.0
auc = 0.0
cum_pos = 0
cum_neg = 0
for i in reversed(range(self.bins)):
cum_pos += self.pos[i]
cum_neg += self.neg[i]
tpr = cum_pos / self.total_pos
fpr = cum_neg / self.total_neg
# trapezoid area between previous and current FPR
auc += (fpr - fpr_prev) * (tpr + tpr_prev) / 2.0
tpr_prev, fpr_prev = tpr, fpr
return auc
