leaves12138 commented on PR #71: URL: https://github.com/apache/paimon-vector-index/pull/71#issuecomment-5211617172
I think the batched hierarchical splitting changes the clustering policy in a way that can significantly hurt quality on skewed datasets. At `core/src/kmeans.rs:145`, `max_new` is the entire remaining centroid count, and the loop then pops as many eligible clusters as possible before any children are reinserted. For `target_k = 1024`, this effectively splits all 16, then all 32, 64, 128, 256, and 512 clusters level by level. Therefore, the heap's “largest cluster first” ordering no longer influences most of the allocation. Small clusters receive roughly the same split depth as large clusters until they become too small, whereas the previous best-first policy allocated more centroids to the high-population clusters. I isolated the scheduling difference while keeping the PR's current assignment implementation and the new degenerate-split handling. On a deterministic skewed dataset (`n=21,500`, `d=2`, `k=512`; 20,000 points in one broad population and 15 remote low-volume populations of 100 points each), I measured: - Current batched schedule: SSE `339,858.785`, 100 centroids assigned to the low-volume populations - Best-first schedule: SSE `309,751.377`, 38 centroids assigned to the low-volume populations That is about a 9.7% increase in quantization error. The added recall scenario uses fairly uniform generated populations, so it does not cover this regression mode. Could we keep the parallel assignment and degenerate-split fixes, but avoid replacing best-first splitting with a breadth-first schedule? Alternatively, the parallel split selection needs to preserve the population-aware allocation property, with a skewed-distribution quality regression test. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
