[dbjapan] A talk by Professor Rakesh Agrawal on Wednesday, July 4

[Masatoshi Yoshikawa <yoshikawa [at] i.kyoto-u.ac.jp>]

dbjapanの皆様

現在，客員教授として京大にご滞在中のRakesh Agrawal先生による
講演を以下の要領で開催します．奮ってご参加下さい．

吉川正俊

----------------------------------------------------------------
Title: Optimality of Stratified Democracy for Knowledge Seeking Societies

Speaker: Rakesh Agrawal

Date: Wednesday, July 4

Time: 2:45p.m. to 4:15p.m.

Room: Lecture Room 2, the 7th research building
    （総合研究7号館 情報2講義室）

Abstract:
We present a variant of the classical data mining task of partitioning
in which the input is an ordered set of objects and any object
can be placed in any partition. Every object derives certain gain
from becoming a member of a particular partition. The amount of
gain depends on the other objects present in the partition and its
relative position with respect to them, and it is specified through
a gain function. The gain function is additive in the sense that the
sum of the gains of the individual objects add up to the total gain
for the population. The objective is to make partitions in such a
way that they collectively maximize the gain for the whole population.
We call this partitioning, the nco-partitioning, to emphasize
that the objects within a partition may occupy non-contiguous
positions in the original order, albeit they maintain this order
within every partition. We study two natural forms of gain functions,
mean maximization and percentile maximization, and provide
an algorithm, called StratifiedRandom, which is able to find
optimal partitioning for both in linearithmic time. Interestingly,
the partitioning produced is simultaneously optimal for both the
functions. We also show that the well-known Round Robin and Elevator
algorithms can be derived from StratifiedRandom and their
gain characteristics are identical to StratifiedRandom. We also compare
the gain of StratifiedRandom with three other algorithms, both
analytically and empirically. Our evaluation corroborates the theoretical
optimality of StratifiedRandom, and shows that StratifiedRandom
produces balanced partitions.

----------------------------------------------------------------
--
o-----------o-------o-----o---o--o
Masatoshi Yoshikawa
 Department of Social Informatics
 Graduate School of Informatics
 Kyoto University
 Yoshida-Honmachi, Sakyo,
 Kyoto 606-8501, JAPAN
 (#502, Science Frontier Laboratory,
  Medical Campus, Kyoto University)
 phone:  +81(75)753-5975
 mobile: +81 80 3506 5355
 fax:    +81(75)753-4970
 e-mail: yoshikawa [at] i.kyoto-u.ac.jp
o-----o---o--o-o-oo
吉川 正俊
 京都大学大学院 情報学研究科
 社会情報学専攻
 〒606-8501 京都市左京区吉田本町
 （医学部構内先端科学研究棟502）
 電話:     (075)753-5975
 携帯:     080 3506 5355
 ファクス: (075)753-4970
 メール: yoshikawa [at] i.kyoto-u.ac.jp
o-----------o-------o-----o---o--o