BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computer Science and Engineering - ECPv6.13.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://homecse.iitd.ac.in
X-WR-CALDESC:Events for Computer Science and Engineering
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Kolkata
BEGIN:STANDARD
TZOFFSETFROM:+0530
TZOFFSETTO:+0530
TZNAME:IST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Kolkata:20250127T120000
DTEND;TZID=Asia/Kolkata:20250127T133000
DTSTAMP:20260924T070117
CREATED:20250121T160348Z
LAST-MODIFIED:20250219T003504Z
UID:1141-1737979200-1737984600@homecse.iitd.ac.in
SUMMARY:Distinct Elements in Streams and the Klee's Measure Problem
DESCRIPTION:Sourav Chakraborty  (Indian Statistical Institute)\n\nWe will present a very simple streaming algorithm on F0 estimation that also caught the eye of Donald E. Knuth.  In a recent article\, Donald E. Knuth started with the following two paragraphs:\n \n“Sourav Chakraborty\, N. V. Vinodchandran\, and Kuldeep S. Meel have recently proposed an interesting algorithm for the following problem: A stream of elements (a1\, a2\,…\,am) is input\, one at a time\, and we want to know how many of them are distinct. In other words\, if A = {a1\, a2\,…\,am} is the set of elements in the stream\, with multiplicities ignored\, we want to know |A|\, the size of that set. But we don’t have much memory; in fact\, |A| is probably a lot larger than the number of elements that we can hold in memory at any one time. What is a good strategy for computing an unbiased estimate of |A|?\n \nTheir algorithm is not only interesting\, it is extremely simple. Furthermore\, it’s wonderfully suited to teaching students who are learning the basics of computer science. (Indeed\, ever since I saw it\, a few days ago\, I’ve been unable to resist trying to explain the ideas to just about everybody I meet.) Therefore I’m pretty sure that something like this will eventually become a standard textbook topic. This note is an initial approximation to what I might write about it\, if I were preparing a textbook about data streams.”\n\nThis simple algorithm comes out of the first ever “efficient” streaming algorithm (from PODS 21) for the Klee’s Measure problem\, which was a big open problem in the world of streaming for many years.\n\nThis work is based on joint works with N. V. Vinodchandran\, and Kuldeep S. Meel across multiple articles\, notable the following: Estimating the Size of Union of Sets in Streaming Models. PODS 2021 [Paper 1]\nDistinct Elements in Streams: An Algorithm for the (Text) Book. ESA 2022 [Paper 2].
URL:https://homecse.iitd.ac.in/event/distinct-elements-in-streams-and-the-klees-measure-problem/
LOCATION:Bharti 501\, IIT Campus\, Hauz Khas\, New Delhi
CATEGORIES:Seminars
END:VEVENT
END:VCALENDAR