演習３　論文の精読

４つ論文を紹介します。どれか１つ選んでください。

1) XML データ処理

XMLデータ解析の拠点となっている米国のペンシルバニア大学、ベル研究所、フランスの INRIA のチームが提案している方法に関する論文を読む課題です。

HTML に代わって XML で書かれた Web Page が増えるにつれて、XMLファイルへの問合せやデータ統合をするための言語や問合せ代数が提案されつつあります。下記の論文は、米国のベル研とフランスの INRIAのチームの提案です。これも本当は実装まで行きたいところですが、とても短期間では無理なので論文を読む課題にします。

●　Vassilis Christophides, Sophie Cluet and Jerome Simeon: On wrapping query languages and efficient XML integration. ACM SIGMOD 2000, May 2000. Pages 141 - 152. PDF file

XMLファイルは、いろんなタグが入るので大きくなりがち…という問題点を解消するために XML ファイルの圧縮方法に関する提案があります。タグ情報を考慮することで gzip の２倍程度の圧縮を可能にした方法に関する論文で、ACM SIGMOD2000 の最優秀論文賞を取っています。論文を読むだけでなく、実装してもむろん構いません。

●　Hartmut Liefke, Dan Suciu: XMILL: An efficient Compressor for XML Data, ACM SIGMOD 2000, May 2000. Pages 153 - 164. PDF file

2) WEB グラフ解析

知能システム論の講義（講義ノート）で紹介した Web Graph 構造解析に関する論文を紹介します。 かなり大胆な Web Graph 構造を主張をしていますが、本当にそうなっているのか？　実験して検証したり、現在の構造がどうなっているか調べてみたり、興味は尽きませんが、とても１ヶ月の演習でこなせるテーマでないので、論文を読む課題にします。

下記の論文は殆ど同じ顔ぶれの研究者により書かれていますが、論文１は実装と結果の解析をしており、論文２は理論的モデルを構築しています。

●　論文１　Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, Janet Wiener: Graph structure in the web. WWW9. May 2000. HTML file

●　論文２　Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins (IBM Almaden), and Eli Upfal (Brown University). The Web as a Graph. PODS2000, May 2000 PDF file