オンラインアルゴリズム

オンラインアルゴリズム（）は、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していけるアルゴリズムを指す。これに対して、オフラインアルゴリズム（）は、問題を解くのに最初からデータ全体へのアクセスが必要なバッチ処理型アルゴリズムを指す。例えば、挿入ソートはオンラインアルゴリズムで、選択ソートはオフラインアルゴリズムである。

また、時系列データをリアルタイムに処理して未来を予測するようなアルゴリズムを特に「オンラインアルゴリズム」と呼ぶ場合もあり、その場合単に入力を蓄積せずに逐次的に処理するアルゴリズムを「ストリームアルゴリズム」と呼ぶ。

例として、有限な連結グラフにおける最短経路問題を考えてみよう。ひとつのノードが入力され、そこから次の連結されたノードが辿れるようなデータ形式の場合、単純かつ完全な探索をしないと問題が解けないのは明らかである。そこで、オンラインアルゴリズムの性能と理想的なオフラインアルゴリズムの性能（全てのデータが最初からわかっている状態）とを比較する Competitive Analysis という手法が新たに生まれた。

オンラインアルゴリズムは、データをあらかじめすべて用意したり、読みだしたりする必要がなく、少量のデータを逐次読み込んで処理を行うことが可能である。そのため、すべてのデータを保持しておくのが難しいような大規模データ（ビッグデータ）を扱う状況や、時々刻々とデータが与えられる状況においてよく用いられる。また未来のデータに依拠せず、その時点までに得られたデータだけに依拠し、かつ逐次型で処理を行う特徴がある。

オンラインアルゴリズムの例
 粒子フィルタ (Particle filter)
 データ圧縮アルゴリズムの多くはストリームアルゴリズムである。LZSS、LZ77

脚注

関連項目
 ページング問題
 リアルタイムシステム
 ビッグデータ

参考文献

外部リンク
 Bibliography of papers on online algorithms

Category:アルゴリズム