BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Department of Computer Science - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Department of Computer Science
X-ORIGINAL-URL:https://www.cs.jhu.edu
X-WR-CALDESC:Events for Department of Computer Science
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20170312T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20171105T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20180311T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20181104T060000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:20190310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:20191103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20181005T100000
DTEND;TZID=America/New_York:20181005T120000
DTSTAMP:20260422T144811
CREATED:20210629T210715Z
LAST-MODIFIED:20210629T210715Z
UID:1962160-1538733600-1538740800@www.cs.jhu.edu
SUMMARY:Computer Science Student Defense:: Nikita Ivkin\, Johns Hopkins University – “Streaming algorithms for finding frequent items”
DESCRIPTION:LocationMalone 228AbstractStreaming model supplies solutions for handling enormous data flows for over 20 years now. The model works with sequential data access and states sublinear memory as its primary restriction.Although the majority of the algorithms are randomized and approximate\, the field facilitates numerous applications from handling networking traffic to analyzing cosmology simulations and beyond. This thesis focuses on one of the most foundational and well-studied problems of finding heavy hitters\, i.e. frequent items:1.  We challenge the long-lasting complexity gap in finding heavy hitters with L2-guarantee in the insertion-only stream and present the first optimal algorithm with a space complexity of O(1) words and O(1) update time. Our result improves on Count sketch algorithm with space and time complexity of O(log n) by Charikar et al. 2002.2.  We consider the L2-heavy hitter problem in the interval query settings\, rapidly emerging in the field. Compared to well known Sliding Window model where an algorithm is required to report the function of interest computed over the last N updates\, Interval Query provides query flexibility\, such that at any moment t one can query the function value on any interval (t1\,t2) subset (t-N\,t). We present the first L2-heavy hitter algorithm in that model and extend the result to the estimation of all streamable functions of frequency vector.3.  We provide the experimental study for the recent space optimal result on streaming quantiles by Karnin et al. 2016. The problem can be considered as a generalization to the heavy hitters. Additionally\, we suggest several variations to the algorithms which improve the running time from O(1/eps) to O(log 1/eps)\, provide twice better space/precision tradeoff and extend the algorithm for the case of weighted updates.4.  We establish the connection between finding “haloes”\, i.e. dense areas\, in cosmology N-body simulation and finding heavy hitters. We build the first halo finder and scale it to handle datasets with up-to 1012 particles via GPU boosting\, sampling and parallel I/O. We investigate its behavior and compare it to traditional in-memory halo finders. Our solution pushes the memory footprint from several terabytes down to less than a gigabyte\, therefore\, make the problem feasible for small servers and even desktops.BioI am a Ph.D. candidate at the Department of Computer Science at Johns Hopkins University\, working with Prof. Vladimir Braverman. I received B.S and M.S degrees in Applied Math in 2011 and 2013 correspondingly both from Moscow Institute of Physics and Technology and enrolled in the Ph.D. program in 2014. My primary interest is concentrated around streaming algorithms and its applications\,starting from theoretical foundations behind the time and space complexity guarantees ending with hardware specific optimizations in real-world applications.
URL:https://www.cs.jhu.edu/event/computer-science-student-defense-nikita-ivkin-johns-hopkins-university-streaming-algorithms-for-finding-frequent-items/
END:VEVENT
END:VCALENDAR