One-pass algorithm とは

コンピューティングでは、ワンパスアルゴリズムは無制限のバッファリングをせずに入力を1回だけ順に読み込むストリーミングアルゴリズムです。 1パスアルゴリズムは一般にO(n)(「大きなO」表記を参照)時間とO(n)記憶(通常O(1))未満を必要とします。ここでnは入力のサイズです。
基本的に1パスアルゴリズムは、以下のように動作する。(1)オブジェクト記述が連続的に処理される。 (2)第1のオブジェクトが第1のクラスタを表すクラスタになる。 (3)後続の各オブジェクトは、その処理時間に存在するすべてのクラスタ代表と照合される。 (4)マッチング関数のある条件に従って、あるオブジェクトが1つのクラスタに割り当てられる(重複が許される場合はそれ以上)。 (5)オブジェクトがクラスタに割り当てられると、そのクラスタの代表が再計算される。 (6)オブジェクトがあるテストに失敗した場合、それは新しいクラスタを表すクラスタになります(7)何も起こりません