Incorporating privacy into counts in Metroview

Derick Yang2 Sep 2022

Problem

Strava Metro gives cities de-identified activity counts per street segment (an "edge"), with filters for trip purpose, time of day, activity type, day of week and month. A count may be shown only if enough distinct athletes contributed to it. Querying raw events is too slow and too expensive: the activity table has over a hundred billion rows. Pre-aggregated counts are fast, but cannot say how many distinct athletes sit behind a sum of rows, and per-row ID lists are too big.

Example from the article: one athlete, Sonya, records daily dog walks in her rural neighborhood. If nobody else uploads there, the counts are high but describe only her.

Solution in brief

Store one row per smallest filter combination ("atomic edge count") with a 64-bit bitmap of hashed athlete IDs. At query time, sum the counts, OR the bitmaps and count the set bits. The bit count never exceeds the true number of athletes, so every count shown has at least n contributors. The price is over-suppression near the threshold.

Questions this case answers
  • How to enforce a minimum-distinct-contributors threshold on pre-aggregated counts when per-row distinct counts cannot be summed and per-row ID lists are too large
  • How to serve arbitrary filter combinations on pre-aggregated data at interactive latency without storing every filter permutation
  • How to show filtered aggregate counts only when enough distinct users contributed, without storing user lists?
  • How to serve many filter combinations over hundreds of billions of events at interactive latency?

Tools and methods

  • Atomic edge counts — one count per smallest filter combination
  • athleteIdBitmap — 64-bit OR of hashed athlete IDs per row
  • Hamming weight — set-bit count, a lower bound on distinct athletes
  • Apache Spark — monthly batch job
  • Amazon S3 — sorted, partitioned storage plus in-memory cache
Continue reading — it's free

Google or a one-time email code. No password.