# How to reduce number of points for clustering

Description

I have to find number of clusters for 1D data. All clusters are assumed to have a gaussian distribution (so there is a big number of same points). I have a robust "agglomerative clustering + EM"-based algorithm which is able to find cluster centers.

Problem

The number of clusters varies (in different data sets) from $1$ to $10$, but number of points in my 1D datasets varies from hundreds to hundreds of thousands. And that is the problem, because my algorithm is running pretty slow for high number of points.

Questions

Is there any simple method how to reduce number of points? The accuracy of cluster centers does not matter for me, I just only want to have fast detection.

Is it OK to select each k-th point and apply clustering algorithm on that selection. Or do I need something else like counting number of same points and leave out some percent of same points?

One-dimensional data is special. It can be sorted consistently in $O(n \log n)$, and then you can use various algorithms in $O(n)$ time. A naive implementation of e.g. hierarchical ("agglomerative") clustering is $O(n^3)$ and that will of course kill you with large data. By any means avoid distance matrixes. They kill scalability.