Revision as of 11:52, 3 November 2009 edit Rich Farmbrough (talk \| contribs) Edit filter managers, Autopatrolled, Extended confirmed users, File movers, IP block exemptions, Pending changes reviewers, Rollbackers, Template editors 1,733,970 edits m clean up, added orphan tag using AWB ← Previous edit		Revision as of 14:36, 6 February 2012 edit undo Nazneen Rupawalla (talk \| contribs) 1 edit No edit summary Next edit →
Line 4: In computing, a '''one-pass algorithm''' is one 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. Basically one-pass algorithm operates as follows: (1) the object descriptions are processed serially; (2) the first object becomes the cluster representative of the first cluster; (3) each subsequent object is matched against all cluster representatives existing at its processing time; (4) a given object is assigned to one cluster (or more if overlap is allowed) according to some condition on the matching function; (5) when an object is assigned to a cluster the representative for that cluster is recomputed; (6) if an object fails a certain test it becomes the cluster representative of a new cluster ==Example problems solvable by one-pass algorithms== Given any list as an input:

One-pass algorithm: Difference between revisions