One-pass algorithm: Difference between revisions

Revision as of 11:11, 13 April 2021

Revision as of 15:38, 14 April 2021

Line 7:

In computing, a '''one-pass algorithm''' or '''single-pass algorithm''' is a [[streaming algorithm]] which reads its input exactly once, in order, without unbounded [[Buffer (computer science)|buffering]]. A one-pass algorithm generally requires ''O''(''n'') (see [[Big O Notation|'big O' notation]]) time and less than ''O''(''n'') storage (typically ''O''(1)), where ''n'' is the size of the input.<ref>{{Citation|last=Schweikardt|first=Nicole|title=One-Pass Algorithm|date=2009|url=https://doi.org/10.1007/978-0-387-39940-9_253|work=Encyclopedia of Database Systems|pages=1948–1949|editor-last=LIU|editor-first=LING|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-0-387-39940-9_253|isbn=978-0-387-39940-9|access-date=2021-04-13|editor2-last=ÖZSU|editor2-first=M. TAMER}}</ref>

Basically one-pass algorithm operates as follows:

# The object descriptions are processed serially

# The first object becomes the cluster representative of the first cluster

# Each subsequent object is matched against all cluster representatives existing at its processing time

# A given object is assigned to one cluster (or more if overlap is allowed) according to some condition on the matching function

# When an object is assigned to a cluster the representative for that cluster is recomputed

# If an object fails a certain test it becomes the cluster representative of a new cluster nothing happened

==Example problems solvable by one-pass algorithms==