Antoine De Mathelin, Mathilde Mougeot, Nicolas Vayatis, Nicolas Cecchi
We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. If it links a repository, it is listed below.
This paper proposes a novel k-medoids approximation algorithm to handle large-scale datasets with reasonable computational time and memory complexity. We develop a localsearch algorithm that iteratively improves the medoid selection based on the estimation of the k-medoids objective. A single batch of size m ≪ n provides the estimation, which reduces the required memory size and the number of pairwise dissimilarities computations to O(mn), instead of O(n 2 ) compared to most k-medoids baselines. We obtain theoretical results highlighting that a batch of size m = O(log(n)) is sufficient to guarantee, with strong probability, the same performance as the original local-search algorithm. Multiple experiments conducted on real datasets of various sizes and dimensions show that our algorithm provides similar performances as state-of-the-art methods such as FasterPAM and BanditPAM++ with a drastically reduced running time.
The same record, over MCP at https://syntology.ai/mcp:
get_harvested_code_for_paper("2501.19285")
get_code_for_paper("2501.19285")
have("2501.19285")
Connect an agent — have() is free.