[ https://issues.apache.org/jira/browse/SPARK-3250?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14130809#comment-14130809 ]
Erik Erlandson commented on SPARK-3250: --------------------------------------- I developed prototype iterator classes for "fast gap sampling" with and without replacement. The code, testing rig and test results can be seen here: https://gist.github.com/erikerlandson/05db1f15c8d623448ff6 I also wrote up some discussion of the algorithms here: Faster Random Samples With Gap Sampling http://erikerlandson.github.io/blog/2014/09/11/faster-random-samples-with-gap-sampling/ > More Efficient Sampling > ----------------------- > > Key: SPARK-3250 > URL: https://issues.apache.org/jira/browse/SPARK-3250 > Project: Spark > Issue Type: Improvement > Components: Spark Core > Reporter: RJ Nowling > > Sampling, as currently implemented in Spark, is an O\(n\) operation. A > number of stochastic algorithms achieve speed ups by exploiting O\(k\) > sampling, where k is the number of data points to sample. Examples of such > algorithms include KMeans MiniBatch (SPARK-2308) and Stochastic Gradient > Descent with mini batching. > More efficient sampling may be achievable by packing partitions with an > ArrayBuffer or other data structure supporting random access. Since many of > these stochastic algorithms perform repeated rounds of sampling, it may be > feasible to perform a transformation to change the backing data structure > followed by multiple rounds of sampling. -- This message was sent by Atlassian JIRA (v6.3.4#6332) --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org For additional commands, e-mail: issues-h...@spark.apache.org