Edward Kmett: What's a wavelet tree? Why do we care?

Date of publication: 12. 11. 2013

Mathematics and theoretical computing seminar

POZOR: petek, 15. 11. 2013, od 12h do 14h, učilnica 3.06, Jadranska 21

POZOR: Seminar za osnove se bo sestal v petek 15. 11. 2013 ob 12h v učilnici 3.06 na Jadranska 21, ker bo Edward Kmett na obisku v Ljubljani samo ta dan.

What's a wavelet tree? Why do we care?

Edward Kmett (of Control.Lens fame) will talk about his latest fascination, a data structure called wavelet trees. And how we can use them in Haskell, of course. A data structure is succinct if you can represent it in space very close to entropy. I want to talk about how we can work with succinct indexed dictionaries and "wavelet trees" to represent data in a highly compact form, and yet still index it efficiently. We'll explore multiple applications of these primitives, including aggregate queries over big data sets, accelerating queries against smaller JSON data sets, full-text indexing, and support for the lazy deserialization of Haskell data types.