Theory Lunch 2/13 GCS 502C 12:00 PM

[Grayson York]

Hi All,

Please join us tomorrow 2/13 at 12:00 PM in GCS 502C for our weekly theory lunch. This week we will have a guest speaker, Jack Spalding-Jamieson, who will be giving the following talk:

Title: Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search

Abstract: For very large values of k, we consider methods for fast k-means clustering of massive datasets with 10^7~10^9 points in high-dimensions (d>=100). All current practical methods for this problem have runtimes at least Ω(k^2). We find that initialization routines are not a bottleneck for this case. Instead, it is critical to improve the speed of Lloyd's local-search algorithm, particularly the step that reassigns points to their closest center. Attempting to improve this step naturally leads us to leverage approximate nearest-neighbor search methods, although this alone is not enough to be practical. Instead, we propose a family of problems we call "Seeded Approximate Nearest-Neighbor Search", for which we propose "Seeded Search-Graph" methods as a solution.

[Grayson York]

Hi all,

Please join us at the following zoom link:

https://usc.zoom.us/j/8561565993?pwd=LzhDWnY2citubmtyQXR1NnVtK0ZaQT09

Thanks,

Grayson