[ 
https://issues.apache.org/jira/browse/SPARK-62121?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

shuxu Wan updated SPARK-62121:
------------------------------
    Priority: Major  (was: Minor)

> [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
>            Priority: Major
>              Labels: pull-request-available
>
> 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