shuxu Wan created SPARK-62121:
---------------------------------

             Summary: [ML] KMeans auto solver always selects the row solver 
because preferBlockSolver sums feature indices
                 Key: SPARK-62121
                 URL: https://issues.apache.org/jira/browse/SPARK-62121
             Project: Spark
          Issue Type: Bug
          Components: ML
    Affects Versions: 4.4.0
            Reporter: shuxu Wan


h3. Problem

KMeans.preferBlockSolver computes the input density incorrectly for 
solver=auto. It sums the feature indices returned by numNonzeros.activeIterator 
instead of the non-zero counts:

{code:scala}
val nnz = numNonzeros.activeIterator.map(_._1).foldLeft(BigDecimal(0))(_ + _)
nnz >= BigDecimal(count) * numFeatures * 0.5
{code}

activeIterator on a Vector yields (index, value) pairs, so _._1 is the feature 
index. The sum is bounded by numFeatures * (numFeatures - 1) / 2 while the 
threshold is count * numFeatures * 0.5. For any dataset with at least as many 
rows as features (i.e. essentially all real-world datasets), the condition is 
always false and solver=auto always falls back to the row solver. Dense 
datasets never reach the block solver, contradicting the scaladoc of the solver 
param: "If input instances are arrays or input vectors are dense, set to block".

h3. Reproduction

Create a dense dataset of 100 rows x 10 features with all values non-zero. With 
solver=auto, preferBlockSolver returns false (row solver), although the density 
is 1.0 and the 50% threshold is 500 non-zero entries.

h3. Version

Still present on master (verified on commit 87d177b), and in 3.4.x, 3.5.x, 
4.0.x and 4.1.x. Introduced in SPARK-30661 (commit 
215b1b9e518a0cdd3683cc652dcedd8b7c2326d7), first released in 3.4.0.

h3. Impact

preferBlockSolver also runs a full-dataset aggregation job before every 
training run, so for dense data the scan is pure overhead and the block solver 
is never used. In a benchmark of 384 concurrent KMeans jobs (Spark 3.4.0, 2 GB 
heap, Temurin 11), explicitly setting solver=row (skipping the scan while 
keeping the same effective algorithm) improved the throughput score by 9.7% and 
reduced the slowest job's elapsed time by 8.9%.

h3. Suggested fix

Sum the non-zero counts instead of the indices: map(_._2). A unit test covering 
dense and sparse inputs is included in the PR.




--
This message was sent by Atlassian Jira
(v10.3.26#10030026)

---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to