Probabilistic Data Structures in Go

(antonz.org)

29 points | by mfrw 11 hours ago

3 comments

  • ncruces 56 minutes ago
    I'm in the process of adding a few of these to my Go SQLite driver.

    https://pkg.go.dev/github.com/ncruces/go-sqlite3/ext/approx

    They work as window functions, and they also support creating roll-up tables, e.g. you have a table storing a sketch of daily active users and can use that to get weekly and monthly active users.

    Same for quantiles (e.g. median and tail latencies) and next up top-K (e.g. most popular content, highest spenders, etc).

  • jpitz 2 hours ago
    My introduction to probabilistic data structures was Pugh's skip list, which is probabilistic in structure and performance, but precise with answers.
  • aarjaneiro 1 hour ago
    Note a lot of the diagrams seem broken