Meta has open-sourced 'e-means', an algorithm that operates up to 45 times faster on GPU than existing data clustering algorithms. According to the explanation, this can significantly reduce the computational time and cost required to group large-scale data by similar characteristics, thereby improving the efficiency of building AI search and recommendation systems.
Meta's research team published the e-means research paper on the archive on the 6th (local time). It is an improved algorithm over the existing 'k-means', characterized by maintaining or improving the quality of results while increasing the speed of data clustering.
k-means is a method that groups data with similar characteristics into multiple clusters and calculates the center points of each cluster. 'Means' refers to the average, and each cluster's center point is determined by the average value of the data within it. It is widely used in vector search and data compression, but when the amount of data increases to tens of billions, it requires a significant amount of time and computational resources for repeated calculations.
e-means combines the exponential moving average (EMA) with the 'mini-batch' approach, which calculates by extracting only part of the data instead of processing all data each time. It assigns greater weights to recently processed data and updates the cluster centers accordingly. It automatically adjusts the processing unit and update magnitude according to the data scale, reducing the need for complex settings.
According to the research team, e-means achieved the same level of error as existing k-means after only 1.4 to 2.6 iterations, significantly reducing the number of required repeated calculations to achieve the same clustering quality.
In actual execution time comparisons, e-means was found to be 10 to 45 times faster than the existing high-performance algorithm 'Flash-KMeans' on GPU environments, and 8 to 15 times faster than the FAISS-based k-means on CPU environments. This is based on the research team's experimental results, and performance differences may occur depending on the data and hardware configuration.
The performance was confirmed even in the processing of large-scale data. The research team stated that with only 2.5 iterations of learning, they recorded lower error levels than the existing k-means results after 25 iterations when grouping the 'DINO10B' dataset, which consists of 10 billion image embeddings into approximately 16.7 million clusters.
e-means is included in Meta's open-source vector search library 'FAISS 1.16.0'. Developers can apply the published code to build large-scale vector indexes or process embedding data.
This research focuses on reducing the computational costs required to pre-cluster massive data in search and recommendation systems. However, it does not mean that the actual response speed of search and recommendation services will improve by the same ratio, but rather that it can improve the efficiency of the system construction process.
Park Chan Reporter cpark@aitimes.com
