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 3, the 7th research building （総合研究7号館 情報3講義室） 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@i.kyoto-u.ac.jp o-----o---o--o-o-oo 吉川 正俊 京都大学大学院 情報学研究科 社会情報学専攻 〒606-8501 京都市左京区吉田本町 （医学部構内先端科学研究棟502） 電話: (075)753-5975 携帯: 080 3506 5355 ファクス: (075)753-4970 メール: yoshikawa@i.kyoto-u.ac.jp o-----------o-------o-----o---o--o