CIS Seminar: “Sketching Algorithms”
CIS Seminar: “Sketching Algorithms”
Abstract: A "sketch" is a data structure supporting some pre-specified set of queries and updates to a database while consuming space substantially (often exponentially) less than the information theoretic minimum required to store everything seen, and thus can also be seen as some form of functional compression. A "streaming algorithm" is simply a data structure […]