2009年3月26日木曜日

プログラマは世界をこう視る

プログラマが普段どのように問題と向き合あっているかを知るのに、これはうってつけ。



今回、縁があってこの本の出版のお手伝いをさせていただきました。内容はやや難し目のパズル問題集。すべての問題に目を通して、紙と鉛筆で解けるものもあれば、実際に手を動かしてプログラムを書いてみたり。前半は、プログラマでない人でも取り組めるようになっていますが、お勧めは実際にプログラムを使って解く後半。

プログラミングコンテストに挑んだことのある人には、もうおなじみの考え方だと思います。普通の人間ならやらないけれど、コンピュータというお供がいると、すべての可能性を調べ上げるような愚直な方法でも着実に実行してくれる。その様子を見て、人間がより良いアルゴリズムを思いつく、というサイクルが問題を通して学べます。

例えば「数独」。日本では、紙と鉛筆で解くパズルの代表例になっていますが、プログラマの手にかかると、コンピューターを使った答えの探索問題に早変わりです。

原著者のDennis Shasha先生も以下のように述べています。
授業中、私は、いわゆる“講義” をほとんどしない。その代わり、パズルを解くテクニックを披露する。問題の“解答” ではなく、“解法” を紹介するのだ。(中略)面白いことに、学生たちはその週の授業を終えると、自分の問題解決能力が向上していることに驚く。授業を通して得られた体験が、現実問題への取り組み方の一部なのだ。
現実の問題にどう取り組むかを、パズルを通して学ぶ。そのような「プログラマの視点」を垣間見られる例を挙げるとするなら、たとえば、Googleが膨大なデータを扱うために開発したMap-Reduceという計算フレームワーク。その仕組みは説明するととても簡単(問題を分割して解いて、後でまとめるだけ)ですが、それを生みだしたベースとなる物事の見方が、まさに「プログラマの視点」なのです。

こればかりは考え方(Shasha先生の言う「解法」)を知らないと、なかなか0からは出てこないものなので、既にプログラマの人にも、これからプログラミングを始める人にも、お勧めの1冊です。

(補足)
すでにこういった考え方に親しみのあるプログラマにとっては、後半より、前半のパズル問題の方が難しくて手ごたえがあると思います。腕に覚えがある方は、頭のトレーニング用にもどうぞ。

関連:

2009年3月13日金曜日

子どもはどこにいるの?

(最初に)長文です。そして、このエントリ、特に後半部分は、むしろ今「親」になっていない人、あるいは、子供に手がかからなくなってきた人に読んで欲しいと思っています。

「研究している間、子どもはどこにいるの?」研究に限らず、夫婦共働きなどでも気になるこの話。ボストンに留学中のtsugo-tsugoさんに、アメリカでの様子を教えてもらいました。(アメリカは州によってぜんぜん法律が違うことは念頭に置いて読んでください。)
マサチューセッツ州の場合、14才以下の子供だけを家においておくのは幼児虐待とみなされ、それに気づいた周囲の人には通報義務があります。ということで、周囲の話を聞いてる限りでは、子供の保育園、学校がない時間帯はベビーシッターを雇うか、常に家に両親どちらかがいるはずです。ベビーシッターは、教会や大学、近所のコミュニティ等で近所の学生等を紹介してもらう無認可のサービスが多いです。

法律の縛りが社会に与える影響は大きい。需要が生まれ、供給体制もできてくる。今の日本だと、子育てのためにどちらか片方(9割以上母親)が仕事・キャリアをあきらめてる、という状況ではないでしょうか。そしてそれが当然という風潮がある(3歳までは母親が~云々、とか)。ちなみに学童保育は学年の途中までということも多いので、両親共働きの家庭では、まだ小学生の子どもが一人で誰もいない家に帰ることになります。これを国(州)として是とするかどうか。この法律には、明確にNOというメッセージが表れています。
大学の先生の場合、わりあい自分のスケジュールを自由に調節できるのと、アメリカは家族の用事で休むのは当然、という文化があるので、結構フレキシブルにやっている印象。子供が病気になったので、東海岸に単身赴任している旦那さんが育休をとって西海岸まで飛んでいく(!)、という話も聞いたことはあります。わりあい男女関係なく育児にかかわっている、というよりもそうしないとやっていけない印象があります。

アメリカでも研究者同士で夫婦別居せざるを得ない場合も多いようなので、必ずしもアメリカが理想郷というわけでもありません。一方、日本にいる僕の周りでは、子どもの保育園や小学校関係の保護者会などで、お父さんが参加しているのを目にすることはほとんどありません。周りはお母さんばかりで、参加している男性は僕一人というケースがほとんど。紅一点ならぬ青一点(?)。仕事が終わって(終わらせて)から、スーツ姿で駆けつけるお母さん達はほんとうに偉いと思います。

あとは中国出身の研究者の場合、出身地によっては子供は2、3歳ぐらいまで母親方の両親が育てる風習があります。その場合、母親方の祖母がビザを取ってアメリカまで出向いてきたりします。

これだと保育園に入れなかったとしても、なんとかやっていけそうです。おじいちゃん、おばあちゃんが家にいて面倒を見てくれる。それがたとえ週に1日とか、子どもが病気のときだけだとしても大変ありがたいことです。けれど、改めて考えみてほしいのは、昼間の子どもをちゃんと見てもらえるというのは、実は既に相当の「溜め」がある状況なのです。

「溜め」のある社会へ

この「溜め」という言葉は湯浅誠さんが、お金の多寡だけではない「貧困」の様子を表現するために使っている言葉です。(「生きづらさ」の臨界―“溜め”のある社会へを読むと、今の日本では、本当に紙一重の差で「溜め」がなくなってしまうことがよくわかります。)
子どもを育てながら研究や仕事を続けられるのも、なんらかの「溜め」があるから。この「溜め」に自覚がなく、仕事がない人に「高校、大学などに行って手に職をつけなかったのが悪い」「私は頑張ったからできた」という類の発言を無邪気にしてしまうと、「溜め」を持たない人にどうしようもない絶望感を与えてしまいます。「自己責任」で済ませるにはあまりにも重い話です。例えば、「勉強する環境があった」、そして、「無事に大学に通うことができた」というのも立派な「溜め」です。経済的、家庭の事情で諦めざるをえなかった人もいるし、勉強に必要な「親の理解」「心の余裕」があるかどうかも「溜め」になることがわかってきています(後述する「子どもの貧困」に関連)

中国での、祖父母が孫の面倒を見るという慣習は、キャリアを確立する20代~30代の大事なときに「溜め」を作るのに有効に働いているように思います。女性研究者なら、ちょうど子育てと、テニュアトラックに入る時期が重なります。tsugo-tsugoさんのエントリで紹介されている出産後すぐに研究を始める女性研究者たちの気持ちは、十分察してあげるべきでしょう。

残念ながら今の日本に、子供を持つ人のキャリア形成を支援する「溜め」が十分あるようには思いません。 核家族化が進んでいるのは、僕が小学生のころ(20年以上前)から社会科で教わっているような話です。昼間こどもを見てくれる親や祖父母は後から作れないし、自分でいきなり保育園を作るわけにもいかない。既存の保育園は、既にキャリアや仕事がある人でないと、定員がいっぱいで入れず、手に職をつけるための勉強や、就職活動すらできなくなります。不況でパートナーの稼ぎが減少し、いざ自分が新たに仕事を見つけようとしても、資格やキャリアがないために仕事を見つけるのが難しく、この「溜め」のなさを痛感している人はさらに多くなったことと思います。

子育て支援は保育園だけでは全然足りない

子どもが幼いときは、一週間ずっと高熱をだして保育園では預かってもらえないなど、仕事を休まざるを得なくなるときがかなりの頻度であります。(病気のときは基本的にベビーシッターさんも使えません)。核家族、共働き、病児保育もないという環境で、頻繁に仕事を休んで、果たして仕事を失わない、キャリアを傷つけずに済むと断言できるでしょうか?

「溜め」を作るには、会社側の子育てへの理解も必要です。先に述べた母親ばかりの保護者会。これはお父さんがさぼっているから?(というのもけっこうあると思います。そんなお父さん達は要反省。)それだけでなく、こどもの面倒をみられる時間に仕事を終わらせること、そしてそれが、「溜め」を作るのに必要なのだという意識が会社や上司の中にも必要です。それがないと、お父さんが職場にとられてしまいます。東大でも、会議は5時までと決めたようですが、これは評価すべきことだと思います。
東京大学は3日、新年度から、原則、午後5時以降の公的な会議を行わないことを決めた。この日定めた「男女共同参画加速のための宣言」の中の一項で、教員に、仕事と生活のバランスを考えてもらい、特に女性研究者の活躍を促すのが狙いだ。・・・

ただし、この目的を「女性がいるから」とするのは大きな間違い。お父さん方も早く自宅に帰れるようにしないと、子供の面倒を見る余裕という「溜め」がない人はさらに「溜め」を失い、社会から取り残されていく。そして、その影響は世代をまたがって固定化していきます。子どもの貧困―日本の不公平を考える、では、親のそういった心の余裕という「溜め」や、さらには学歴までもが、子供の将来における収入に影響を及ぼすというデータを示しています。子どもの「貧困」とはなにか、そしていかに多くの日本の子供が、まさに今「貧困」状態にありながら、そこから抜け出せなくなっているかが、詳細な分析結果とともに述べられています。

子どもを助けようとするなら、親を助けよ

この「溜め」の問題で隠れているのは、「溜め」がないことで、大学や仕事などのキャリアをあきらめてしまった人は、もう「溜め」がない人とすらカウントされないという事実。キャリアを目指せる環境が整うなら目指したい(これが需要になる)のに、到底かなわないと最初から諦めてしまっている人は、需要としては決してカウントされない。小泉政権下で、保育園の待機児童の定義の分母をすり替えて、待機児童の割合を少なく見せるトリックをしたのと同じです。
2002年(平成14年)4月から国は、待機児童の定義を変えた。認可外の保育所に入っている児童の内、自治体が助成金を出している保育所にいる児童は、待機児童から外すことにしたのである。つまり今後は、認可保育所に入所を希望していても、自治体独自の保育の取り組みや、幼稚園の預かりシステムなどで、一時的にお世話になっている児童は、待機児童としてカウントされなくなったわけだ。
http://www.sensenfukoku.net/policy/ninsyo/index.html

保育園に預けて働きたい、大学に通いたいのにそれができない人は、待機児童数が示すよりもたくさんいるのです。日本では、「溜め」をつくるために親がキャリアを身につけようとすれば、親(特に母親)はこどもを優先すべきだからキャリアはあきらめろ、とでもいわんばかりの雰囲気があります。現に既に仕事(あるいは仕事に就く見込み)がないと保育園には入れません。仕事があっても年度途中から入るのは、かなり絶望的です。

教育や将来の収入などを見越した上で、本当の意味でこどもを大事にする、というのは、実はその親のキャリア形成を支援することに他ならないことを「子どもの貧困」という本は示唆しています。子どもを持つことがキャリア形成に不利に働く今の日本の現状では、本当に子供を大事にしていないのは、「親」ではなく、むしろこの日本という「国」や「社会」の方だと言わざるを得ません。それゆえ、病気のときにまで誰かしらに子どもを見てもらえるような、既に「溜め」のある人と、そうでない人との差は広がるばかりになります。これは月数万の補助で埋められるような「差」ではありません。

そして、この問題に気付くのは、たいていこどもが生まれた後です。そのときにはもう当事者であり、今の生活、仕事を守るのに必死なため、政治活動に一番参加しにくい立場になってしまいます。まずは、この問題意識を共有してくれる人を、政界だけでなく、学校や企業などの社会の中に生み出さないといけない。もはや「貧困」はホームレスだけの問題でないし、「子育て」も「親」になった人だけの問題ではない。「親」になってからでは遅いのです。

2009年3月11日水曜日

SIGMOD2009 Accepted Papers

SIGMOD2009採録論文が発表されました。そのうちのいくつかについて、タイトルだけから内容を推測。
  • Yahoo! Researchの"Generating Example Data for Dataflow Programs"は恐らくPig Latinのデバッグ用のサンプルデータ生成の話。Hadoopなどの上で、複雑なデータ構造を動的に組み立てていくプログラム書きながら、横に実行結果の例を「適切に」示したサンプルが表示されると、わかりやすいよね、という話。
  • ”Towards a simpler XML Schema: effortless handling of nondeterministic regular expressions”はついに来たか、という感じ。Relational styleの考えが入っていて、スキーマ(relation)から考えられるいろいろな木構造をNFAを使って同時に検証する、という流れだったら嬉しい。
  • "DDE: From Dewey to a Fully Dynamic XML Labeling" 。XMLの索引づけはもう食傷気味なのですが。。。「Fully」といいつつ挿入・削除以外の更新操作(木の移動とか)をサポートしていないと、がっくりきそう。
  • その他、multi-core CPU(Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs)とか、SSD(Query Processing Techniques for Solid State Drives)の話もちらほら。
  • 圧巻は、64番 ”A Comparison of Approaches to Large Scale Data Analysis”。Brown, MIT, UW Madison, Yale、そしてMicrosoftって、どんだけコネクションが広いんだ、あなたたちw。日本がDBコミュニティで存在感が出せないのは、こういった人脈がないことに尽きると思います。
  • それにしても、"Why Not?"ってなんだろう?DBMSがこう検索したらどう?とでも聞いてくるのかな?"Schema-Free XQuery"のときといい、Jagadishたちのグループは、論文のネーミングが秀逸です。
全体としての印象は、シリコンバレーに集まっているラボが強い。Microsoft, Yahoo! Research, HPなどなど。もともとはMITやStanford出身だったりするのですが。Stanfordもシリコンバレーの大学。

今回のSIGMODでは、僕は勝負すらできなかったので、投稿して落とされるよりたちが悪い。大負けです。悔しい。
  • 23 
    Entity Resolution with Iterative Blocking
    Steven Whang*, Stanford University
    David Menestrina, Stanford University
    Georgia Koutrika, Stanford University
    Martin Theobald, Stanford University
    Hector Garcia-Molina, Stanford University
  • 25
    Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs
    Wook-Shin Han*, Kyungpook National University
    Jinsoo Lee, 
  • 38
    Minimizing the Communication Cost for Continuous Skyline Maintenance
    Zhenjie Zhang*, National University of Singapo
    Reynold Cheng, 
    Dimitris Papadias, HKUST
    Anthony K. H. Tung, National University of Singapore
  • 47
    FlexRecs: Expressing and Combining Flexible Recommendations
    Georgia Koutrika*, Stanford University
    Benjamin Bercovitz, Stanford University
    Hector Garcia-Molina, Stanford University
  • 64
    A Comparison of Approaches to Large Scale Data Analysis
    Andrew Pavlo*, Brown University
    Samuel Madden, Massachusetts Institute of Technology
    David DeWitt, Microsoft
    Michael Stonebraker, Massachusetts Institute of Technology
    Alexander Rasin, Brown University
    Erik Paulson, University of Wisconsin-Madison
    Lakshmikant Shrinivas, UW-Madison
    Daniel Abadi, Yale University
  • 69
    GAMPS: Compressing Multi Sensor Data by Grouping and Amplitude Scaling
    Sorabh Gandhi, University of California, Santa Barbara
    Suman Nath*, Microsoft Research
    Subhash Suri, UCSB
    Jie Liu, 
  • 94
    Authenticated Join Processing in Outsourced Databases
    Yin Yang, HKUST
    Dimitris Papadias*, HKUST
    Stavros Papadopoulos, HKUST
    Panos Kalnis, NUS
  • 115
    Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis
    Frank McSherry*, Microsoft
  • 118
    Query Simplification: Graceful Degradation for Join-Order Optimization
    Thomas Neumann*, Max-Planck-Institut Informatik
  • 119
    Scalable Join Processing on Very Large RDF Graphs
    Thomas Neumann*, Max-Planck-Institut Informatik
    Gerhard Weikum, Max-Planck-Institut Informatik
  • 120
    Combining Keyword Search and Forms for Ad Hoc Querying of Databases
    Eric Chu*, University of Wisconsin-Madiso
    Akanksha Baid, University of Wisconsin-Madison
    Xiaoyong Chai, University of Wisconsin-Madison
    AnHai Doan, Univ of Wisconsin
    Jeff Naughton, University of Wisconsin
  • 121
    Attacks on Privacy and deFinetti's Theorem
    Daniel Kifer*, Penn State University
  • 122
    Optimizing Complex Extraction Programs over Evolving Text Data
    Fei Chen*, UW-Madison
    AnHai Doan, Univ of Wisconsin
    Jun Yang, Duke University
    Raghu Ramakrishnan, 
    Byron Gao, 
  • 142
    DDE: From Dewey to a Fully Dynamic XML Labeling
    Liang Xu*, NUS
    Tok Wang Ling, NUS
    Huayu Wu, NUS
    Zhifeng Bao, NUS
  • 143
    Self-organizing Tuple Reconstruction in Column-stores
    Stratos Idreos*, CWI
    Martin Kersten, CWI
    Stefan Manegold, CWI
  • 151
    Ranking Queries on Distributed Probabilistic Data
    Feifei Li*, Florida State University
    Ke Yi, Department of Computer Science and Engineering, HKUST
    Jeffrey Jestes, Computer Science Department, FSU
  • 161
    Generating Example Data for Dataflow Programs
    Christopher Olston*, Yahoo! Research
    Shubham Chopra, Yahoo! Research
    Utkarsh Srivastava, Yahoo! Research
  • 165
    Secure Outsourced Aggregation via One-way Chains
    Suman Nath*, Microsoft Research
    Haifeng Yu, 
  • 166
    ZStream: A Cost-based Query Processor for Adaptively Detecting Composite Events
    Yuan Mei*, MIT
    Samuel Madden, Massachusetts Institute of Technology
  • 190
    Serial and Parallel Methods for I/O Efficient Suffix Tree Construction
    Amol Ghoting*, IBM Research
    Konstantin Makarychev, IBM Research
  • 191
    Asynchronous View Maintenance for VLSD Databases
    Parag Agrawal, Stanford University
    Adam Silberstein, Yahoo! Research
    Brian Cooper*, Yahoo! Research
    Utkarsh Srivastava, Yahoo! Research
    Raghu Ramakrishnan, 
  • 195
    Kernel-Based Skyline Cardinality Estimation
    Zhenjie Zhang*, National University of Singapo
    Yin Yang, HKUST
    Ruichu Cai, School of Computer Science and Engineering, South China University of Technology
    Dimitris Papadias, HKUST
    Anthony K. H. Tung, National University of Singapore
  • 207
    Quality and Efficiency in High Dimensional Nearest Neighbor Search
    Yufei Tao*, CUHK
    Ke Yi, Department of Computer Science and Engineering, HKUST
    Cheng Sheng, The Chinese University of Hong Kong
    Panos Kalnis, National University of Singapore
  • 224
    Continuous Obstructed Nearest Neighbor Queries in Spatial Databases
    Yunjun Gao*, Singapore Management Univ.
    Baihua Zheng, Singapore Management Univ.
  • 235
    Keyword Search in Databases: The Power of RDBMS
    Lu Qin*, CUHK
    Jeffrey Xu Yu, The Chinese Univ. of Hong Kong
    Lijun Chang, 
  • 242
    Why Not?
    Adriane Chapman*, MITRE Corporation
    H.V. Jagadish, Univ. Michigan
  • 244
    Dictionary-based Order-preserving String Compression for Main Memory Column Stores
    Carsten Binnig*, ETH Zurich
    Stefan Hildenbrand, ETH Zurich
    Franz Frber, 
  • 245
    ROX: Run-time Optimization of XQueries
    Riham Abdel Kader*, University of Twente
    Peter Boncz, CWI
    Stefan Manegold, CWI
    Maurice Van Keulen, University of Twente
  • 253
    An Architecture for Recycling Intermediates in a Column-store
    Milena Ivanova*, CWI
    Martin Kersten, CWI
    Niels Nes, CWI
    Romulo Goncalves, CWI
  • 266
    Scalable Skyline Computation Using Object-based Space Partitioning
    ZHANG Shiming, HKU
    Nikos Mamoulis*, University of Hong Kong
    David Cheung, University of Hong Kong
  • 269
    FlashLogging: Exploiting Flash Devices for Synchronous Logging Performance
    Shimin Chen*, Intel Research Pittsburgh
  • 292
    Skip-and-Prune: Cosine-based Top-K Query Processing for Efficient Context-Sensitive Document Retrieval 
    Jong wook Kim*, ASU
    K. Selcuk Candan, 
  • 293
    Robust XPath Expressions for Web Extraction
    Philip Bohannon, Yahoo! Research
    Nilesh Dalvi*, Yahoo! Research
    Fei Sha, University of Southern California
  • 301
    Incremental Maintenance of Length Normalized Indexes for Approximate String Matching
    Marios Hadjieleftheriou*, AT&T Labs - Research
    Nick Koudas, University of Toronto
    Divesh Srivastava, AT&T Labs-Research
  • 308
    Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers
    Tingjian Ge*, Brown University
    Stanley Zdonik, Brown University
    Samuel Madden, Massachusetts Institute of Technology
  • 316
    Top-K Generation of Integrated Schemas Based on Directed and Weighted Correspondences
    Ahmed Radwan, University of Miami
    Lucian Popa*, IBM Almaden
    Ioana Stanoi, IBM Almaden
    Akmal Younis, University of Miami
  • 319
    E = MC3: Managing Uncertain Enterprise Data
    Peter Haas, IBM
    Fei Xu, University of Florida
    Vuk Ercegovac*, IBM
    Eugene Shekita, IBM
  • 335
    Estimating the Confidence of Conditional Functional Dependencies
    Graham Cormode, AT&T Labs - Research
    Lukasz Golab*, AT&T Research
    Flip Korn, AT&T Labs - Research
    Andrew McGregor, Microsoft Research
    Divesh Srivastava, AT&T Labs-Research
    Xi Zhang, SUNY Buffalo
  • 343
    Monitoring Path Nearest Neighbor in Road Networks
    Zaiben Chen, The University of Queensland
    Heng Tao Shen*, The University of Queensland
    Xiaofang Zhou, University of Queensland
    Jeffrey Xu Yu, The Chinese Univ. of Hong Kong
  • 347
    Uncertainty Management in Rule-based Information Extraction Systems
    Eirinaios Michelakis*, UC Berkeley
    Peter Haas, IBM
    Rajasekar Krishnamurthy, IBM
    Shivakumar Vaithyanathan, IBM
  • 359
    Approximate Entity Extraction with Edit Constraints
    Wei Wang, University of New South Wales
    Chuan Xiao*, UNSW
    Xuemin Lin, 
    Chengqi Zhang, UTS, Australia
  • 361
    Secure k-NN Computation on Encrypted Databases
    Wai Kit Wong*, The University of Hong Kong
    David Cheung, University of Hong Kong
    Ben Kao, The University of Hong Kong
    Nikos Mamoulis, University of Hong Kong
  • 364
    Query Processing Techniques for Solid State Drives
    Dimitris Tsirogiannis*, University of Toronto
    Stavros Harizopoulos, HP Labs
    Mehul Shah, HP Labs
    Janet Wiener, Hewlett-Packard Laboratories
    Goetz Graefe, HP Labs
  • 385
    Query by Output
    Quoc Trung Tran*, NUS
    Chee-Yong Chan, 
    Srinivasan Parthasarathy, Ohio State University
  • 387
    Exploiting Context Analysis for Combining Multiple Entity Resolution Systems
    Zhaoqi Chen*, UCI
  • 395
    Towards a simpler XML Schema: effortless handling of nondeterministic regular expressions
    Geert Jan Bex, Hasselt University
    Wouter Gelade*, Hasselt University
    Wim Martens, University of Dortmund
    Frank Neven, Hasselt University
  • 399
    Cost Based optimization and plan selection for XPath
    Haris Georgiadis*, AUEB
    Minas Charalambidis, AUEB
    Vasilis Vassalos, AUEB
  • 400
    Core Schema Mappings
    Giansalvatore Mecca*, Università della Basilicata
    Paolo Papotti, Università di Roma Tre
    Salvatore Raunich, Unversità della Basilicata
  • 403
    A Gauss Funtion based Approach for Unbalanced Ontology Matching
    Qian Zhong, Tsinghua University
    Hanyu Li*, IBM CRL
    Juanzi Li, 
    Guo tong Xie, ibm
    Jie Tang, 
    Lizhu Zhou, Tsinghua University
  • 407
    Efficient Type-Ahead Search on Relational Data: a TASTIER Approach
    Guoliang Li*, Tsinghua University
    Shengyue Ji, UC Irvine
    Chen Li, Univeristy of California, Irvine
    Jianhua Feng, Tsinghua University
  • 493
    A Revised R*-tree in Comparison with Related Index Structures
    Norbert Beckmann, University of Marburg
    Bernhard Seeger*, University of Marburg
  • 495
    Indexing Correlated Probabilistic databases
    Bhargav Kanagal*, University of Maryland
    Amol Deshpande, University of Maryland, college Park
  • 505
    Efficient Incorporation of User Feedback into Information Extraction and Integration Programs
    Xiaoyong Chai*, University of Wisconsin-Madison
    Ba-Quy Vuong, Univ. of Wisconsin at Madison
    AnHai Doan, Univ of Wisconsin
    Jeff Naughton, University of Wisconsin
  • 513
    Extending Autocompletion to Tolerate Errors
    Surajit Chaudhuri, Microsoft Research
    Raghav Kaushik*, Microsoft Research
  • 526
    Privacy Preservation of Aggregates in Hidden Databases: Why and How?
    Arjun Dasgupta*, University of Texas Arlington
    Nan Zhang, George Washington University
    Gautam Das, Univ of Texas at Arlington
    Surajit Chaudhuri, Microsoft Research
  • 534
    A Declarative Data Representation Framework
    Arvind Arasu*, Microsoft Research
    Raghav Kaushik, Microsoft Research
  • 553
    Secondary-Storage Confidence Computation for Conjunctive Queries with Inequalities
    Jiewen Huang, Oxford University
    Dan Olteanu*, Oxford University
  • 562
    3-HOP: A High-Compression Indexing Scheme for Reachability Query
    Ruoming Jin*, Kent State University
    Yang Xiang, Kent State University
    Ning Ruan, Kent State University
    Dave Fuhry, Kent State University
  • 565
    A Framework for Testing Query Transformation Rules
    Hicham Elmongui, Purdue University
    Vivek Narasayya*, Microsoft Research
    Ravi Ramamurthy, Microsoft Research
  • 568
    Robust and Efficient Algorithms for Rank Join Evaluation
    Jonathan Finger, University of California Santa Cruz
    Alkis Polyzotis*, UC Santa Cruz
  • 569
    Cross-tier, Label-based Security Enforcement for Web Applications
    Brian Corcoran*, University of Maryland
    Michael Hicks, University of Maryland
    Nikhil Swamy, Microsoft Research
  • 583
    Optimizing I/O-Intensive Transactions in Highly Interactive Applications
    Mohamed Sharaf*, Univ. of Toronto
    Cristiana Amza, UofT
    Panos Chrysanthis, University of Pittsburgh
    Alexandros Labrinidis, University of Pittsburgh
  • 585
    Detecting and Resolving Unsound Workflow Views for Provenance Preservation
    Peng Sun, Arizona State University
    Ziyang Liu*, Arizona State University
    Susan Davidson, University of Pennsylvania
    Yi Chen, Arizona State University

2009年3月10日火曜日

イラストで知る研究の世界とその醍醐味

研究の世界の雰囲気や、その面白さがどこにあるかご存じな方はとても少ないことと思います。

例えば大学4年で卒業し就職してしまうと(法学部や経済学部に多い)全くといっていいほど研究の世界を知らないまま社会に出ることになります。日本では、報道などのメディアに就職する方も学部卒ということが多いため、テレビ・新聞などで研究の世界について深く書かれた記事を目にする機会はほとんどありません。

NHKのサイエンス・ゼロなどの番組で、研究者の様子を垣間見ることもできます。しかし、番組は研究の世界の一側面を見せているだけであり(取材時間に比べてカットが多く、内容も製作者の主観に左右される)、研究の世界で活躍していて評判の高い人は、実はほとんどメディアにでてこない事情もあります(「21歳からのハローワーク(研究者編)」を参照)。そのような研究者は、論文という形で一生懸命アウトプットを出しているのですが、論文は学部教育や大学院、博士での研究トレーニングを経ないと読みこなせない(研究の内容だけでなく、意義すら理解できない)ため、学者間にとっては非常に価値のあることでも、一般の人にとっては無用の長物に見えてしまうことも少なくないのです。

そのように謎に包まれた研究の世界の様子を、tsugo-tsugoさんが、イラストを通して伝えてくれています。研究の面白さや、研究の進め方の本質をしっかりとらえていて、一部に根強いファンがつく人気ぶりです。僕もtsugo-tsugo劇場と勝手に名付けて、連載を楽しんで読んでいます。以下のリンク先からどうぞ。
2009022711394420090301003316
こんな感じのかわいいイラストで、研究の世界に流れる感動や空気、驚きや醍醐味などをよく伝えてくれています。

ただし、一つだけ注意。tsugo-tsugoさん本人もおっしゃっているとおり、実際の研究は、かわいいばかりでなく結構殺伐としていることが多いです。博士課程では論文という形で成果が出せないと鬱になりがちです(学生相談所には博士課程の学生の相談が多いとか)。それに、日本では、ポスドク以外のアカデミアのポストにつける博士の割合は3割以下でもあります(H20年度の統計で、1万人の博士課程修了者のうち大学教員になった割合は23%、その他の研究者になったのは26%です)。研究の世界に飛び込むときは、実際の雰囲気に加え、社会の現状を知った上で入るのが望ましいと思います。
参考:
テレビなどのメディアで紹介されていて分野に興味を持ったから、というのも悪くはありませんが、実際の研究現場と想像していた雰囲気のギャップに苦しむことがあります。例えば、一時期、精神鑑定がはやって精神科医を志す人が増えたけれど、プロファイリングなどの言葉でテレビで華々しく紹介されているのとは違い、現実はかなり地道な調査が要求される分野だそうです。(そもそも疾患者数が少なく、統計的に有意な結果が見出しにくいため、健常者にまで外挿した質問肢調査から病気の傾向を見出すSchizotypyのような研究が必要だったり)

参考:
  • 教授からのメッセージ (研究者という道について厳しく書かれています。しかし、実際これくらいの心づもりで闘争心を持って研究に臨んでいかないと、とても大成できないので、実は愛情たっぷりのお話)

研究の世界を知るには、実際に研究室を覗いてみたり、中に入って話を聞いたり、扱っているテーマに関して勉強して手を動かしてみるのが一番だと思います。僕自身、そうやって志望する研究室を変えた経験がありますし、自分が勉強したい分野と、実際にその研究が肌にあうかどうかは意外に異なるので、例えさわりだけだとしても、経験してみることが大事です。

研究テーマをベースに選ぶとしても、例えば生物学なら、対象が生物ではあることは常に変わらないけれども、実際に用いる研究手法は、測定機械、実験設備の有無、さらには特定の分野に強い人がいるかどうか、などという様々な事情で変わってきます。人の入れ替わりも激しい世界なので、5年、10年以上と同じテーマの研究を続けているラボは珍しいくらいです。ただ、研究の軸が一本通っていれば、それを元にいろいろな理論、手法、解析に手を出していける強みもあります。僕の場合は「データベースシステムを作ること」が研究の軸にあります。今現在は、ちょうど生物情報という融合分野にいますが、生物でも、情報系でも、そのアプリケーションは違えど、研究の目的自体にあまり違いはありません。

これからの研究の世界に飛び込む人には、酸いも甘いも知った上で臨んでほしい、という思いをこめて。

2009年3月3日火曜日

PODS 2009: Accepted Papers

今日発表されました。

今年のPODS2009は面白そうです。XML関連の研究もまだまだ盛ん。研究の世界ではやりの、Uncertain dataは多くなってきていますが、それだけでなく、heavy-hitterとか、secondary indexingとか、DBのcore技術寄りの論文もあるみたいで、論文が出てくるのが楽しみです。

採録された中には、日本人(面識はないのですが天野さんという方)も一人。Libkinのラボにいるのですね。おめでとうございます。こうやって日本からデータベースコミュニティの中で活躍していけるようになる人が増えるとうれしいですね。


29 Dynamic Indexability: The Query-Update Tradeoff for One-Dimensional Range Queries
(Ke Yi)

31 Satisfiability of the downward fragment of XPath with data equality tests
(Diego Figueira)

37 Satisfiability and relevance for queries over active documents
(Serge Abiteboul, Pierre Bourhis and Bogdan Marinoiu)

38 Equivalence of SQL Queries In Presence of Embedded Dependencies
(Rada Chirkova and Michael Genesereth)

58 Distributed XML Design
(Serge Abiteboul, Georg Gottlob and Marco Manna)

59 Relationship Privacy: Output Perturbation for Queries with Joins
(Vibhor Rastogi, Michael Hay, Gerome Miklau and Dan Suciu)

63 Size and Treewidth Bounds for Conjunctive Queries
(Georg Gottlob, Stephanie Lee and Gregory Valiant)

65 A General Datalog-Based Framework for Tractable Query Answering over Ontologies
(Andrea Cali, Georg Gottlob and Thomas Lukasiewicz)

67 Optimal Tracking of Distributed Heavy Hitters and Quantiles
(Ke Yi and Qin Zhang)

69 Indexing Uncertain Data
(Pankaj K. Agarwal, Siu-Wing Cheng, Yufei Tao and Ke Yi)

71 Equivalence of Nested Queries with Mixed Semantics
(David DeHaan)

76 Running Tree Automata on Probabilistic XML
(Sara Cohen, Benny Kimelfeld and Yehoshua Sagiv)

78 XML with Incomplete Information: Models, Properties, and Query Answering
(Pablo Barcelo, Leonid Libkin, Antonella Poggi and Cristina Sirangelo)

79 XML Schema Mappings
(Shunichi Amano, Leonid Libkin and Filip Murlak)

82 XPath Evaluation in Linear Time with Polynomial Combined Complexity
(Pawel Parys)

89 Relative Information Completeness
(Wenfei Fan and Floris Geerts)

94 An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets
(Adam Kirsch, Michael Mitzenmacher, Andrea Pietracaprina, Geppino Pucci, Eli Upfal and Fabio Vandin)

98 Generalized Schema-Mappings, From Termination To Tractability
(Bruno Marnette)

103 Similarity Caching
(Flavio Chierichetti, Ravi Kumar and Sergei Vassilvitskii)

105 Optimal Sampling from Sliding Windows
(Vladimir Braverman, Rafail Ostrovsky and Carlo Zaniolo)

111 Exceeding Expectations and Clustering Uncertain Data
(Sudipto Guha and Kamesh Munagala)

116 Consensus Answers for Queries over Probabilistic Databases
(Jian Li and Amol Deshpande)

118 Computing All Skyline Probabilities for Uncertain Data
(Mikhail Atallah and Yinian Qi)

119 Reverse data exchange: coping with nulls
(Ronald Fagin, Phokion Kolaitis, Lucian Popa and Wang-Chiew Tan)

134 Space-optimal Heavy Hitters with Strong Error Bounds
(Radu Berinde, Graham Cormode, Piotr Indyk and Martin Strauss)

143 Secondary Indexing in One Dimension: Beyond Btrees and Bitmap Indexes
(Rasmus Pagh and S. Srinivasa Rao)

License

Creative Commons LicenseLeo's Chronicle by Taro L. Saito is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 2.1 Japan License.