A glossary of tiny lectures, part 3
Week 3: clustering by poles
By Tim Menzies, published 2026-09-07, updated 2026-09-07
Summary: Week 2 built distance (glossary 1); this week distance buys structure, found without labels. Two sweeps find the far poles of the data; the cosine rule projects every row onto the line between them; a median split makes two halves; recursion makes a tree. The demos are ezr-eg3.lua; the machinery below is verbatim from ezr.lua. Same deal as always: each entry is a tiny lecture — hook, idea, math if any, then the code.
Clustering by poles
New acronyms: none.
- cluster: Learning without labels. Before anyone will pay for a single y value, the x columns are already free — so group rows by x-distance and structure appears: rows that sit together tend to behave together. Clustering is how this code spends its unlabelled riches; the only question is how to split a table cheaply. The classic answers (k-means and friends) sweep the data many times chasing centroids. This code splits once, on two rows.
-
fastmap: How do you find the two most separated rows? The honest way compares everything to everything: O(n²) distance calls. The fastmap trick gets close for O(2n): pick any row at random; its farthest neighbor is pole one; pole one's farthest neighbor is pole two. Two sweeps, and you hold (roughly) the longest line through the data.
function TBL.poles(i,rows,lo,hi, far,c)
far = function(r, t)
t = keysort(rows, function(z) return i:distx(z, r) end)
return t[#t] end
lo = lo or far(rows[rand(#rows)])
hi = hi or far(lo)
if i:disty(lo) > i:disty(hi) then lo, hi = hi, lo end
c = i:distx(lo, hi) + TINY
return function(r) return (i:distx(lo,r)^2 + c*c
- i:distx(hi,r)^2) / (2*c) end,
lo, hi end
Note the middle line: after finding the poles, ONE comparison sorts them by disty, so lo is always the pole nearer heaven. That costs two labels — the only two this whole chapter spends — and it means every split knows which side is the good side. Remember that thrift: it grows into active learning.Faloutsos & Lin: FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. Christos Faloutsos, King-Ip Lin. SIGMOD 1995, 163-174. -
projection: Where does a row r sit on the line between the poles? High-school geometry answers. With a = the gap from lo to r, b = the gap from hi to r, and c = the gap between the poles:
r
/|
a / | x = (a² + c² - b²) / (2c)
/ |
/ | \ b
lo ----+----+----------- hi
x
<------- c ------->
That is the cosine rule, solved for the foot of the perpendicular. x near 0: the row sits with the good pole (lo); x near c: with the bad one; x below 0 or beyond c: outside the poles entirely, which fastmap's approximation happily allows. And look at what poles returns: not a number — a FUNCTION, carrying lo, hi and c in its closure (glossary 2). One line of geometry, wrapped so keysort can use it as a key. -
halve: Project every row, sort by projection, cut at the median: two halves, better half first. The sort key calls distx twice per row, so this is exactly the slow-key situation from the DSU notes — keysort computes each projection once.
Then note some(rows, the.few): the poles come from a random sample of 128 rows, not from all of them. That line is the voice of experience. Early versions of this code found poles over ALL the remaining rows — and each far call is a full distance sweep, so every split of every node paid O(n²)-ish distance work, at every level of the recursion. Slow. Then came the experiment of doing it on just a few rows — and the splits were as good as anything the full sweep found. Which makes sense: two far-apart rows in a random 128 are already close to the diameter of the whole cloud, and the split only needs the poles to be far and roughly opposed, not optimal. Moral, and it recurs all semester: before optimizing the computation, check how little of the data the computation actually needs.function TBL.halve(i,rows, fun,a,b,n)
rows = rows or i.rows
fun, a, b = i:poles(some(rows, the.few))
rows = keysort(rows, fun)
n = floor(#rows / 2)
return a, b, slice(rows, 1, n), slice(rows, n + 1) end -
node: halve, above, divides the data once. node divides the data, then recurses on each half — and a tree falls out: each node holds its rows (as a fresh cloned table) and its two poles; splitting stops when a node is too small to bother (fewer than 2 · the.stop rows). auto93's 398 rows, with stop=32: 398 → 199 → ~100 → ~50, then stop — three levels, eight leafs. A binary chop through data space: no centroids, no k, no distance matrix, and label cost of two poles per split.
function Node(tbl,rows, recurse)
function recurse(rows, node,a,b,lo,hi)
node = new(NODE, {here=tbl:clone(rows),
a=nil, b=nil, lo=nil, hi=nil})
if #rows >= 2 * the.stop then
a, b, lo, hi = tbl:halve(rows)
node.a, node.b = a, b
if #lo > 0 and #hi > 0 then
node.lo, node.hi = recurse(lo), recurse(hi) end end
return node
end -- recurse
return recurse(rows or tbl.rows) end
To place a NEW row, walk down: at each level, go to whichever pole is nearer. Log-many distance checks and the stranger has an address:function NODE.leaf(i,row, t)
while i.lo do
t = i.here
i = t:distx(row, i.a) <= t:distx(row, i.b)
and i.lo or i.hi end
return i end -
sway (the sampling way): Not examinable — this entry marks the gap between here and bleeding-edge research.
After all the machinery above, optimization becomes almost embarrassingly simple: halve the data, IGNORE the worse half, recurse only into the better one. Since each split labels only its two poles, reaching a good leaf costs about 2·log(n) labels — call it a (.5, 2) strategy: keep half, spend two new labels per level. That baseline, run against state-of-the-art evolutionary optimizers on SE problems, proved hard to beat — which raised awkward questions about how much of the fancy machinery was ever needed.
Recent work does better still:- sway2: given a labelling budget B, descend with sway; if budget remains at the bottom, start again from the root — but this time run fastmap only over the already-labelled examples to pick the first division. Restarts get smarter for free, because every restart inherits everything paid for so far.
- sway3: loosen (.5, 2) to (.66, 4) — keep the top 66% of the pool and label 4 new things at each level — plus sway2's start-again trick. Gentler culls waste fewer good rows; more labels per level steady the poles.
def poles(tbl, rows, y, ordering=False): # far pair in rows
far = lambda r: max(rows, key=lambda x: distx(tbl, x, r))
a = far(rows[0]); z = far(a)
if ordering and y(z) < y(a): a, z = z, a
c = distx(tbl, a, z) + 1/BIG
return lambda r: (distx(tbl,a,r)**2 + c*c -
distx(tbl,z,r)**2)/(2*c)
One descent: spend up to the.more labels per level, sort the pool by projection onto poles drawn from the labelled rows, keep the the.best fraction (sway3's .66):def descend(tbl, rows, y, seen, cap, label, go=False):
while len(rows) > the.stop and len(seen) < cap: # one descent
todo, more = [], min(the.more, cap - len(seen))
for r in rows:
if id(r) in seen:
todo += [seen[id(r)]]
elif more > 0:
more -= 1; go = True; seen[id(r)] = label(r)
todo += [seen[id(r)]]
rows = sorted(rows, key=poles(tbl, todo, y))
rows = rows[:int(the.best*len(rows))]
return go
And the sway2 restart trick is the outer loop: while budget remains and the last descent still labelled something new, go again from a fresh shuffle — each restart's poles drawn from everything labelled so far:def descends(tbl, rows, label=lambda row: row):
seen = {}
cap = the.budget - the.check
y = lambda r: disty(tbl, r)
while len(seen) < cap and \
descend(tbl, shuffle(rows), y, seen, cap, label): pass
return sorted(seen.values(), key=y)Chen, Nair, Krishna & Menzies: "Sampling" as a baseline optimizer for search-based software engineering. Jianfeng Chen, Vivek Nair, Rahul Krishna, Tim Menzies. IEEE Trans. Software Engineering 45, 6 (2019), 597-614.