One-pass algorithm

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 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 nothing happened

   Example problems solvable by one-pass algorithms

• Count the number of elements.

• Find the k largest or smallest elements, k given in advance.
• Find the sum, mean, variance and standard deviation of the elements of the list.

• Count the number of times each symbol appears in the input.
• Find the most or least frequent elements.
• Sort the list according to some order on the symbols.
• Find the maximum gap between two appearances of a given symbol.

  Example problems not solvable by one-pass algorithms

• Find the nth element from the end.
• Find the middle element of the list.

• Find the median.
• Find the modes.
• Sort the list.