世界の最高水準にあるインドのタタ基礎研究所で最先端のアルゴリズムを研究されているJaikumar Radhakrishnan教授をお迎えし、データサイエンスにも関係するデータストリームの発見に関する学術講演会を開催致しました。

 

日時：6月25日(木) 13:00-14:00

場所：電気通信大学 東3号館（総合研究棟）601号室

学内マップ（27番の建物）

http://www.uec.ac.jp/about/profile/access/

主催：住友電工グループ社会貢献基金寄附講座「IT融合とビッグデータ利活用イノベーション人材（データアントレプレナー）育成講座」

共催：電気通信大学 先進アルゴリズム研究ステーション

講演者：Jaikumar Radhakrishnan

Professor School of Technology and Computer Science Tata Institute of Fundamental Research

講演題目：Finding duplicates in a data stream

概要：

Given a data stream of length n over an alphabet [m] where n > m, we consider the problem of finding a duplicate in a single pass. We give a randomized algorithm for this problem that uses O((log m)3) space. This answers a question of Muthukrishnan [Mut05] and Tarui [Tar07], who asked if this problem could be solved using sub-linear space and one pass over the input. Our algorithm solves the more general problem of finding a positive frequency element in a stream given by frequency updates where the sum of all frequencies is positive. Our main tool is an Isolation Lemma that reduces this problem to the task of detecting and identifying a Dictatorial variable in a Boolean halfspace. We present various relaxations of the condition n > m, under which one can find duplicates efficiently. (Joint work with Parikshit Gopalan.)

本講演会に関する問合わせ先：西野 哲朗 (電気通信大学) nishino@uec.ac.jp