Streaming algorithms for center-based clustering in general metrics

[Sir Lüc]

Azul,

although not a Royal Society member, yesterday marked the official end of my academic career**, and I'd like to share my master's degree thesis for consumption by our scientific community. (The presentation was a bit less low-level and might have been more understandable by laypeople, but I don't have a full recording of it.)

Since my graduation coincided with Llimbaziuă, I'm extremely tempted to release at least some abridged version of it in Talossan. In the meantime though, here's the full stuff as submitted in English:

Streaming algorithms for center-based clustering in general metrics

Abstract: Center-based clustering is an important yet computationally difficult primitive in the realm of unsupervised learning and data analysis. We specifically focus on the k-median clustering problem in general metric spaces, in which one seeks to find a set of k centers, so to minimise the sum of distances from each point in the dataset to its closest center. In this thesis, we present and analyze efficient techniques to deal with the k-median clustering problem in the streaming setting – where the dataset is presented one point at a time and not accessible in its entirety* – by leveraging the dimensionality of the dataset's underlying metric space.

(*: not accessible in its entirety all at once, I should have written. Yay for writing it at some ungodly hour of the night :p)

(**: sike! in February 2023, I accepted a position as (non-postdoctoral) research fellow, so my academic career is not actually over yet.)

[Sir Lüc]

Forgot to mention, there's an experimental part for which I developed some C++ code:
- the PLS+ algorithm for streaming k-median coreset construction
- the StreamingCWB algorithm for streaming coreset refinement
- the kmedian++ (approximation) algorithm for solving the k-median clustering problem (not part of the proposed techniques; used to get an estimation of the optimum clustering cost for comparison purposes)

Since code snippets have previously been shared to the Royal Society board, I might share that as well, once I clean up the code a bit and move the repo somewhere safe (idk how long my department will preserve my GitLab account)

[Baron Alexandreu Davinescu]

CONGRATULATIONS!

And thank you for the excellent paper!  I look forward to reading it :)

[King Txec]

While the vast majority of this might as well be written in ancient Latin, congrats on achieving your goal!

[Sir Lüc]

Thank you ^^

[Breneir Tzaracomprada]

Congratulations Luc!

[Tierçéu Rôibeardescù]

Azul,

although not a Royal Society member, yesterday marked the official end of my academic career**, and I'd like to share my master's degree thesis for consumption by our scientific community. (The presentation was a bit less low-level and might have been more understandable by laypeople, but I don't have a full recording of it.)

Since my graduation coincided with Llimbaziuă, I'm extremely tempted to release at least some abridged version of it in Talossan. In the meantime though, here's the full stuff as submitted in English:

Streaming algorithms for center-based clustering in general metrics

Abstract: Center-based clustering is an important yet computationally difficult primitive in the realm of unsupervised learning and data analysis. We specifically focus on the k-median clustering problem in general metric spaces, in which one seeks to find a set of k centers, so to minimise the sum of distances from each point in the dataset to its closest center. In this thesis, we present and analyze efficient techniques to deal with the k-median clustering problem in the streaming setting – where the dataset is presented one point at a time and not accessible in its entirety* – by leveraging the dimensionality of the dataset's underlying metric space.

(*: not accessible in its entirety all at once, I should have written. Yay for writing it at some ungodly hour of the night :p)

(**: sike! in February 2023, I accepted a position as (non-postdoctoral) research fellow, so my academic career is not actually over yet.)

hi luc, under the new model of membership requirements your submitting of your this thesis qualifies you for membership in the Society, should you wish it.

[Breneir Tzaracomprada]

@Tierçéu Rôibeardescù I hope you will pardon my intrusion but I wanted to express my appreciation and happiness with your revitalization of the Royal Society. It is so nice to see the recent activity!

[Sir Lüc]

hi luc, under the new model of membership requirements your submitting of your this thesis qualifies you for membership in the Society, should you wish it.

I would be happy to join. I had my qualms with the way the Royal Society was being used as a cheap honours farm for a little while, but I think it's headed in a better direction these days.

Incidentally, my current research interests veered off in a different direction (computer engineering applied to natural risk assessment), which I think would make for a more interesting talk than approximation algorithms, if people were interested.

[Tierçéu Rôibeardescù]

hi luc, under the new model of membership requirements your submitting of your this thesis qualifies you for membership in the Society, should you wish it.

I would be happy to join. I had my qualms with the way the Royal Society was being used as a cheap honours farm for a little while, but I think it's headed in a better direction these days.

Incidentally, my current research interests veered off in a different direction (computer engineering applied to natural risk assessment), which I think would make for a more interesting talk than approximation algorithms, if people were interested.

I am keen to move away from being a title factory also, plus its not like I am in a position to give myself the PHD I dream of so what would be the point. My main reason of necro ing this post, the fact that as now submitting a paper (which we find ourselfs a lot just by being academics) allows for ease not just of membership but also dissemination of knowledge and expertise like never before. If there can be roving relevant that could even be applied here in talossa,  however small in scale, even better!