情報科学屋さんを目指す人のメモ(FC2ブログ版)

何かのやり方や、問題の解決方法をどんどんメモするブログ。そんな大学院生の活動「キャッシュ」に誰かがヒットしてくれることを祈って。

ブログ内検索

スポンサーサイト このエントリーを含むはてなブックマーク

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

スポンサー広告 | 編集
このエントリーをはてなブックマークに追加 Clip to Evernote

過去10年間のComputer Science系論文で被引用数トップ10を作ってみた このエントリーを含むはてなブックマーク

2000年以降の論文に限定して、 CS系論文の被引用数ランキングを作って分析してみた

この作業を通じて予想以上に得るものがあった。

ランキングの作り方

CiteSeerXが公開している「Most Cited Computer Science Articles (2010/9/14)」を元データに採用した。 ここから2000年以降の文章に限定した後、ハンドブックや雑誌記事などを取り除いて論文だけのランキングを作成した。

被引用数は時間が経つほど増える一方なので、2000年・2001年あたりの論文が有利であることに注意する必要がある。 ただし、このことがかえって得るものを増やしてくれた。

アブストラクトをチェック

良い機会であるので、 各論文の概要や結論をチェックし日本語で改めてまとめを記述した。 そして、 どうしてそんなに引用されたのかを分析し、 コメントとして付け加えた。

また、ここで紹介する論文はすべて各リンク先からPDFファイルを取得可能である。

ランキングの使い方(?)

ランキングに登場する論文を参考にすれば、より出来の良い、今後の研究につながる論文が書けるかもしれない。 今回は10年間に限定したが、 いずれの論文も期間を限定せずとも上位に食い込む超有名論文 なので、 気が向いたときにランキングの中から読んでみるのもよいかも。

ランキング

以下、1位~10位11位。掲載当初、ミスがあり、3位を追加中。

【1位】
"Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications"

分野

P2P Computing

被引用数

2644

論文

I Stoica, R Morris, D Karger, M Kaashoek, H Balakrishnan.
Chord: A scalable peer-to-peer lookup service for Internet applications.
in Proc. ACM SIGCOMM 2001.

概要

データの効率的な配置はP2Pアルゴリズムの根本的な課題である。 提案手法Chordはこの課題に取り組んだ。

Chordはkeyに対応するノードの取得を実現するアルゴリズムである。 この機能を利用することで、 keyに対応するデータを特定のノードに保存・取得できるアプリケーションを容易に実装できる。 Chordはノードの出入りがある状況下であっても、ノードの参加・離脱および問い合わせを効率よく実行できる。

コメント

ChordアルゴリズムによるDHT入門

ChordはDHTと呼ばれるP2Pアルゴリズムの中で最も有名なアルゴリズムで、DHTの論文は決まってこのChordを引用している印象。

右の画像のリンク先は、私が以前書いたChordアルゴリズムの解説

【2位】
"Pastry: Scalable, Distributed Object Location and Routing for Large-scale Peer-to-Peer Systems"

分野

P2P Computing

被引用数

2375

論文

A Rowstron, P Druschel.
Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems.
In Proc. IFIP/ACM Middleware 2001.

概要

Pastryは、スケーラブルなオブジェクト配置と広域P2Pネットワークにおけるルーティングを実現し、 グローバルなデータストレージやデータ共有を行うP2Pアプリケーションの構成に利用できる。

Pastryはデータを保存するとき、ユーザーが定義した数だけオブジェクトの複製を配置する。 そしてそのコピーが存在する限り、その複製を確実に取得できる。 また、複製保持しているノードのうち最もネットワーク的に近いノードから取得する特徴がある。

Pastryはノードの参加・離脱・故障に自動的に対応可能なスケーラブルな方式であり、 実験によりそれを示す。

コメント

これもP2Pアルゴリズムの論文であり、Chordと並んで引用されることが多い。今回PastryがTOP10に2つランクインして扱いに困ったので、ここでは引用数を合算(1386+989=2375)した。

【3位】
"Distinctive Image Features from Scale-invariant Keypoints"

分野

コンピュータビジョン

被引用数

2217

論文

D G Lowe.
Distinctive image features from scale-invariant keypoints.
International Journal of Computer Vision

概要

この論文では、特徴量の検出を行う手法を提案する。 この手法を用いることで、同じ物体の異なる画像のマッチングを行うことができる。 特に、水平移動や回転、ノイズの追加や視点の移動、光源の変化に強いという信頼性の高さが特徴である。

コメント

この手法の最初の発表は1999年らしく、これは2004年のジャーナル。SIFTとよばれる超有名手法のようです。

【4位】
"A Scalable Content-Addressable Network"

分野

P2P Computing

被引用数

2114

論文

S Ratnasamy, P Francis, M Handley, R Karp, S Shenker.
A scalable content-addressable network.
in Proc. ACM SIGCOMM 2001.

概要

今日のソフトウェアにとってハッシュテーブルは必要不可欠な構成要素であり、 大規模分散システム上であってもこの要素が重要であると考えている。

大規模分散システム上のハッシュテーブルを実現する基盤としてCAN(Content-Addressable Network)を提案する。 CANはスケーラビリティと耐故障性および完全な自己組織性のある手法であり実験によりその特徴を明らかにする。

コメント

これも Chord や Pastry と同様にDHTと呼ばれるP2Pアルゴリズムの一つであり、 DHTの論文で頻繁に引用される。 1位・2位・3位から、いかに2000年代にDHTの研究が盛んに行われたかが分かる。

【5位】
"The Anatomy of the Grid: Enabling Scalable Virtual Organizations"

分野

Grid Computing

被引用数

1478

論文

I Foster, C Kesselman, S Tuecke.
The Anatomy of the Grid: Enabling Scalable Virtual Organizations.
Supercomputer Applications (2001).

概要

グリッドコンピューティングは重要な新領域となってきており、 大規模なリソースの共有、革新的なアプリケーションなどの点で 従来の分散コンピューティングと大きく異なる。

本論文ではグリッドコンピューティングを改めて定義するとともに、 グリッドが直面する問題を柔軟でかつセキュアで協調的なリソースの共有であると定めた。 こうしたとき、認証・承認・リソースへのアクセス・リソースの発見などに関する 興味深い課題が見えてきた。

我々はグリッドを構成する要素をリソースの共有に対する役割に応じて分割した アーキテクチャを提案し、その各役割が必要とする要件を明らかにする。 そして、グリッドという技術が他の技術領域とどのように関連しているのかを議論する。

コメント

今後研究が行われるべき領域を分析しており、以降の研究の指針となり得る論文。 この引用数から、実際に大きな影響を与えたのだろう。 引用する側からすれば、この論文を引用することで研究の必要性・重要性を示すことが出来る。

【6位】
"The Capacity of Wireless Networks"

分野

無線アドホックネットワーク

被引用数

1325

論文

P Gupta, P Kumar.
The capacity of wireless networks.
IEEE Trans. Inf. Theory, , 2000.

概要

(これ自信ない、論文の結論部分も読んだ) W bit/sec でデータを転送可能な n 台のノードをランダムに配置したとき、それぞれのノードからランダムに選択したノードへのスループットλ(n)が、非干渉のプロトコルを仮定した場合にΘ(W/sqrt(n log n))となることを明らかにした。また、単位円盤上にノードを配置し、理想的な設定と環境を仮定した場合でもΘ(W/sqrt(n))であり、 他の物理モデルを仮定した場合も同様の結果が得られることを明らかにした。 また、キャパシティーの締め付けを避けるために行うチャネルの部分的な分割がこの結果に影響を与えないことも同様に明らかにした。

これらの結果は、少ないノードでのネットワークの構成の必要性を示している。

コメント

やはりこの結論も、今後の研究の裏付けになるような内容。 こういう制約条件が明らかになっているから、我々はここに注力する、みたいな。 こういう論文がやはり引用する価値の大きい論文なのだろうか。

【7位】
"Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks"

分野

センサーネットワーク

被引用数

1309

論文

Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin.
Directed diffusion: A scalable and robust communication paradigm for sensor networks.
In Proc. of the Sixth Annual International Conference on Mobile Computing and Networks (MobiCOM 2000, , 2000.

概要

技術の進歩により、通信・計算のできる小型で安価なセンサーが実現されるだろう。 またこれらのセンサーを用いてネットワークを構成することにより、協調した分散センシングが可能である。

本論文では、そのような協調を実現するための理論的枠組みとしてdirected diffusion(指向性のあるデータ拡散法)について詳しく述べる。Directed diffusion におけるすべての通信は名前づけられたデータに対して行われる。また、すべてのノードがアプリケーション・アウェアに動作する。そのため、良い経路の経験的な選択や、ネットワーク上でのデータのキャッシュや計算が可能となり、省電力に貢献する。

コメント

センサーネットワークに関する論文。アルゴリズムデザインのための良い理論的枠組みを提供している点でやはり引用されやすかったのだろう。これに基づくアルゴリズムがたくさん提案されればされるほど引用されるわけで。そして本文中でもっとも強調されている特徴が「エネルギー効率」であって、センサーネットワークのアルゴリズムにふさわしい「売り」になっているのかもしれないあまり詳しくないけどセンサーネットワークいいよね

【8位】
"System Architecture Directions for Networked Sensors"

分野

システムアーキテクチャ

被引用数

1112

論文

J Hill, R Szewczyk, A Woo, S Hollar, D Culler, K Pister.
System architecture directions for networked sensors.
ARCHITECTURAL SUPPORT FOR PROGRAMMING LANGUAGES AND OPERATING SYSTEMS, 2000.

概要

技術の進歩と共に、ネットワーク接続が可能なセンサーのデザインスペースは拡大したが、 総合的なシステムアーキテクチャとへの系統だった方法論が欠如していた。 そして我々はこれを達成するために必要な要件を特定した。

また、その要件を満たすデバイスを開発すると共に、 高いモジュラリティと並列性インテンシブな命令をサポートした非常にコンパクトなOSを設計した。 そしてこれを分析することによりメモリの使用効率性の高さが明らかとなった。 この分析は今後のアーキテクチャの進展の基礎となるだろう

コメント

これはセンサーネットワークの論文ではなく、アーキテクチャ・オペレーティングシステム系の論文。 この論文も、当然のように今後の研究の基礎となり得る研究であることをアブストラクトの中で 明示している。 また、この研究が開発したデバイスやOSが重要なわけではなく、それを用いて裏付けようとした 理論にこそ価値があるという論文構成がやはり引用する価値の高さなのだろう。

【9位】
"Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data"

分野

機械学習

被引用数

1077

論文

J Lafferty, A McCallum, F Pereira.
Conditional random fields: Probabilistic models for segmenting and labeling sequence data.
In Proc. ICML '01 Proceedings of the Eighteenth International Conference on Machine Learning, 2001.

概要

系列データの分割とラベル付けのためのモデルを構築するためのフレームワークである「条件付き確率場(Conditional random fields, CRF)」を提案する。 CRFには隠れマルコフモデル(HMMs)や確率文法に優る利点があるだけでなく、 最大エントロピーマルコフモデル(MEMMs)やその他の有向グラフィカルモデルに基づく識別マルコフモデルの抱える根本的な限界を取り払うことに成功している。

そして我々はCRFに対する逐次的なパラメータ推定アルゴリズムを設計し、HMMsやMEMMsとの比較を行った。

コメント

この論文は今までのとは違って、アブストラクトを読むだけだではたくさん引用される匂いをそこまで感じられない。しかし、このCRFというモデルはこの分野では今や標準的に用いられるモデルであり、様々な応用手法がこれを元にデザインされている。そして、そもそも適用範囲の広い研究領域であるため、次々とCRFという優れたモデルを適用した研究が発生したと予想できる。

【10位】
"GPSR: Greedy Perimeter Stateless Routing for Wireless Networks"

分野

無線アドホックネットワーク

被引用数

1066

論文

B Karp, H T Kung.
GPSR: Greedy Perimeter Stateless Routing for wireless networks.
In Proceedings of MobiCom 2000, , 2000.

概要

Greedy Perimeter Stateless Routing (GPSR) はルータの位置とパケットの宛先の情報を利用してフォワーディング(転送)先を決定する無線ネットワーク向けルーティングプロトコルである。 GPSRは隣接するルーターの位置のみを利用する。 パケットがGreedyルーティング不能な領域に到達してしまった場合には、 その領域の周囲(perimeter)に沿ってフォワーディングすることで復旧する。

隣接するルータの情報のみを利用するため、GPSRはスケールする。 また、モバイル環境におけるトポロジの頻繁な変更があったとしてもGPSRは 隣接するルータの情報を利用して新しいルートを直ちに発見できる。

本論文では、GPSRの詳細を延べ、シミュレーションにより、 GPSRのスケーラビリティを示す。

コメント

これもネットワークについての論文。 アブストラクトを読むと、この論文も本質でない部分を詰め込まない、 応用しがいのある手法を提案しており、 たくさん引用されるある種の要件を満たしているように感じる。

【11位】
"Rapid Object Detection using a Boosted Cascade of Simple Features"

分野

パターン認識

被引用数

989

論文

Paul Viola, Michael Jones.
Rapid object detection using a boosted cascade of simple features.
In Proc. of IEEE Int. Conf. on Computer Vision and Pattern Recognition (2001).

概要

画像から高速かつ精度良く物体を認識する方式を提案する。 この研究には大きく3つの貢献がある。一つ目はIntegral Imageと呼ばれる新しい画像表現を導入し、高速化を実現したことであり、二つ目は 少ない画像の特徴を大量の画像から選び出す方法を提示し、効率の良いクラス判別器を提案したことである。 三つ目はクラス判別器をつなぎ合わせ、物体の存在しそうな領域に計算を集中させる方法を提案した点であり、 これは既存手法とは全く異なる新しい手法である。

コメント

アブストラクトを見る限り、非常に優れた性質を実現した手法であり、 顔認識などの応用も豊富であることが伺える。 また、現在標準的な手法となっているようだ。

たくさん引用されている論文の特徴

ランキングを作り、概要を書いた過程で見えてきた引用される論文・研究の特徴を列挙してみる。

特徴1:研究領域を創造する研究

新しい研究領域を生み出した論文は当然その研究領域から多くの引用を受けることになる。

今回のランキングは2000年以降に限定したため、 2000年以降に盛り上がった領域「DHT」の代表的論文 「Chord(1位)」「Pastry(2位)」「CAN(4位)」 が多く引用されていた。

特徴2:研究領域を体系づける研究

ある研究領域の研究対象を改めて分析し、 研究対象の再定義・再構成し、 研究が注力すべき点を明らかにした論文はやはり引用されやすいようだ。

適切に研究対象を整理した論文はそれを引用した論文の水準を高めるといえる。 Gridの再定義を行った 「The Anatomy of the Grid(5位)」や、 性能向上に寄与する要素の切り分けを行った 「The Capacity of Wireless Networks(6位)」 「System Architecture Directions for Networked Sensors(8位)」 がこれに分類できると考えられる。

特徴3:研究領域の応用研究を促進する基盤的研究

手法の枠組みを提示し、今後の応用手法の登場に貢献する論文も引用されやすいと感じた。

「Directed Diffusion(7位)」「GPSR(10位)」がまさに手法の枠組みを提案し、 新しい手法/研究の出現を予感させてくれる。

特徴4:既存の手法を置き換える方式を提案する研究

もともと応用されている分野の中心的手法と交換可能な基礎的な研究は、 それを当てはめ直し、性質を明らかにしていくという目的から引用されやすいのかもしれない。 「Conditional Random Fields(9位)」は今現在、多くの応用手法があり、 「Boosted Cascade(11位)」と同様に標準的な手法となり、実用に直結しているらしい。

研究に対する影響が引用数に直結する

当然のことのようでもあるが、 後続の研究に大きな影響を与えた論文ほど、多く引用されていると結論づけられるランキングだった。 引用関係が枝に相当する木として研究が広がり、 根に近く、幹の中心に近ければ近いほど多大なる影響を与えているという姿が見て取れた。

自分の研究領域を見直してみる

今回は2000年以降に頻繁に引用された論文を見た。 この制約条件によって研究領域の年齢にずれがはっきりとし、 研究領域の成長・発展過程の様々な段階に現れる特徴的な論文を見渡すことが出来た。

この視点を持って自分の研究分野(Peer-to-Peer Computing)を見てみると、 今回のランキングにあるように「分野の創出に関わる研究」が多く引用されていることが分かる。 しかし、研究対象を体系づけたり、手法の基盤や枠組みとなる手法はランクインしていない。 当然、分野が出現してからの経過時間が短いためにランクインできなかったとも考えられる。 だが実際のところ、 現時点でこの分野にその種の研究が不足しているように感じられる。

研究分野そのものから見れば、今後そういう研究に現れて欲しいに違いないし、 自身、そういう研究を目指していきたい。 今現在、私はDHTのルーティングで用いられる構造化オーバレイを体系づける研究を行っている。

まとめ

将来の研究により大きく貢献する方法を学ぶつもりが、 それだけでなく研究分野の発展と、各研究の役割についても確認することが出来た。 そう、あくまで確認。やっぱりそういう研究をしていきたい。

研究 | コメント:2 | トラックバック:0 | 編集
このエントリーをはてなブックマークに追加 Clip to Evernote

この記事のコメント

他の順位の論文と違って論文への参照になっていないようです。以下のようなアドレスへのリンクになっています
http://citeseerx.ist.psu.edu/stats/articles
こちらが正しい参照先で合っていますか?
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.4931

それから、私もセンサーネットワークはかっこいいと思います
2011-09-23 Fri 20:17 |  hamanako [ 編集]
> hamanakoさん
コメントありがとうございます

> 他の順位の論文と違って論文への参照になっていないようです。以下のようなアドレスへのリンクになっています
> http://citeseerx.ist.psu.edu/stats/articles
> こちらが正しい参照先で合っていますか?
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.4931

リンク先を間違っていたみたいです。
そのリンク先が正しいので、修正しました。

> それから、私もセンサーネットワークはかっこいいと思います

ですよねー^^
2011-09-24 Sat 14:32 |  did2

コメントの投稿 エントリの新旧に関わらず、極力18時間中に返信します。














この記事のトラックバック

トラックバックURL:
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。