Why Thorup and Zhang built the sparse sketch

  • Both authors were at AT&T Research, which operates a very large number of routers 42:28.
  • The vector: n = number of destination IP addresses; xᵢ = how many packets destination i received in a time window. Deletions were not even needed 42:51.
  • Why L2: ‖x‖₂² measures spikes / skewness in the traffic distribution — used as part of a system for detecting denial-of-service attacks 42:51, 43:37.
  • Why not L∞: the infinity norm measures spikes best, but no space-efficient streaming algorithm for ‖x‖_∞ exists. The largest p for which a space-efficient Lp algorithm exists is p = 2 — a known, proven boundary 43:17, 43:37.
  • Why speed mattered so much: the sketch runs on the router at network line rate. At 1% error, 1/ε² = 100² = 10,000 — so the sparse construction removed a factor of 10,000 from their update cost 44:03.

Cosine similarity between documents

  • Contrast with Jaccard similarity from a problem set, which used the minimum of a hash function to compare sets (e.g. web pages) 44:27, 44:48.
  • Setup: xᵢ = number of occurrences of word i in document x; normalize x to unit norm so all documents lie on a sphere 44:48, 45:32.
  • Similarity of two documents = the angle θ between them; small angle ⇒ similar 45:56.
  • The trick: forget streaming — treat Πx as a compression (a "sketch") of the document, and estimate ⟨x, y⟩ = cos θ by ⟨Πx, Πy⟩ with the same Π 46:23, 46:49.
  • Guarantee: an expectation/variance analysis gives additive ε error on the true dot product with probability 1 − δ 47:16.

Norms ⇒ dot products, via the polarization identity

  • ‖a − b‖² = ‖a‖² + ‖b‖² − 2⟨a,b⟩, hence ⟨a,b⟩ = (‖a‖² + ‖b‖² − ‖a−b‖²)/2 47:40.
  • Apply with a = Πx, b = Πy. Since Π preserves the squared norms of x, y, and x − y (which is just another vector), each of the three terms is preserved up to ε 48:15, 48:43.
  • Takeaway used repeatedly for the rest of the lecture: preserving L2 norms ⇒ preserving dot products ⇒ preserving cosines of angles 48:43, 48:58.