I have a large dataset (around $ 10^6 $ samples) and an algorithm that will surely choke on that much data.
Suppose that I have removed duplicates and near-duplicates. What are the well-known techniques for reducing sample size without losing too much of the information possibly encoded in the initial dataset?
I thought about using some clustering algorithm (which scales well with respect to number of clusters, possibly BIRCH) and use the resulting clusters to find $ N $ nearest points to cluster centroid. However this feels somehow wrong.