{"action":"created","comment":{"url":"https://api.github.com/repos/apache/spark/pulls/comments/22712763","id":22712763,"diff_hunk":"@@ -0,0 +1,964 @@\n+/*\n+ * Licensed to the Apache Software Foundation (ASF) under one or more\n+ * contributor license agreements.  See the NOTICE file distributed with\n+ * this work for additional information regarding copyright ownership.\n+ * The ASF licenses this file to You under the Apache License, Version 2.0\n+ * (the \"License\"); you may not use this file except in compliance with\n+ * the License.  You may obtain a copy of the License at\n+ *\n+ *    http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ * Unless required by applicable law or agreed to in writing, software\n+ * distributed under the License is distributed on an \"AS IS\" BASIS,\n+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ * See the License for the specific language governing permissions and\n+ * limitations under the License.\n+ */\n+\n+package org.apache.spark.ml.recommendation\n+\n+import java.{util => javaUtil}\n+\n+import scala.collection.mutable\n+\n+import com.github.fommil.netlib.BLAS.{getInstance => blas}\n+import com.github.fommil.netlib.LAPACK.{getInstance => lapack}\n+import org.netlib.util.intW\n+\n+import org.apache.spark.{HashPartitioner, Logging, Partitioner}\n+import org.apache.spark.ml.{Estimator, Model}\n+import org.apache.spark.ml.param._\n+import org.apache.spark.rdd.RDD\n+import org.apache.spark.sql.{SchemaRDD, StructType}\n+import org.apache.spark.sql.catalyst.dsl._\n+import org.apache.spark.sql.catalyst.expressions.Cast\n+import org.apache.spark.sql.catalyst.plans.LeftOuter\n+import org.apache.spark.sql.catalyst.types.{DoubleType, FloatType, IntegerType, StructField}\n+import org.apache.spark.util.Utils\n+import org.apache.spark.util.collection.{OpenHashMap, OpenHashSet, SortDataFormat, Sorter}\n+import org.apache.spark.util.random.XORShiftRandom\n+\n+/**\n+ * Common params for ALS.\n+ */\n+private[recommendation] trait ALSParams extends Params with HasMaxIter with HasRegParam\n+  with HasPredictionCol {\n+\n+  /** Param for rank of the matrix factorization. */\n+  val rank = new IntParam(this, \"rank\", \"rank of the factorization\", Some(10))\n+  def getRank: Int = get(rank)\n+\n+  /** Param for number of user blocks. */\n+  val numUserBlocks = new IntParam(this, \"numUserBlocks\", \"number of user blocks\", Some(10))\n+  def getNumUserBlocks: Int = get(numUserBlocks)\n+\n+  /** Param for number of item blocks. */\n+  val numItemBlocks =\n+    new IntParam(this, \"numItemBlocks\", \"number of item blocks\", Some(10))\n+  def getNumItemBlocks: Int = get(numItemBlocks)\n+\n+  /** Param to decide whether to use implicit preference. */\n+  val implicitPrefs =\n+    new BooleanParam(this, \"implicitPrefs\", \"whether to use implicit preference\", Some(false))\n+  def getImplicitPrefs: Boolean = get(implicitPrefs)\n+\n+  /** Param for the alpha parameter in the implicit preference formulation. */\n+  val alpha = new DoubleParam(this, \"alpha\", \"alpha for implicit preference\", Some(1.0))\n+  def getAlpha: Double = get(alpha)\n+\n+  /** Param for the column name for user ids. */\n+  val userCol = new Param[String](this, \"userCol\", \"column name for user ids\", Some(\"user\"))\n+  def getUserCol: String = get(userCol)\n+\n+  /** Param for the column name for item ids. */\n+  val itemCol =\n+    new Param[String](this, \"itemCol\", \"column name for item ids\", Some(\"item\"))\n+  def getItemCol: String = get(itemCol)\n+\n+  /** Param for the column name for ratings. */\n+  val ratingCol = new Param[String](this, \"ratingCol\", \"column name for ratings\", Some(\"rating\"))\n+  def getRatingCol: String = get(ratingCol)\n+\n+  /**\n+   * Validates and transforms the input schema.\n+   * @param schema input schema\n+   * @param paramMap extra params\n+   * @return output schema\n+   */\n+  protected def validateAndTransformSchema(schema: StructType, paramMap: ParamMap): StructType = {\n+    val map = this.paramMap ++ paramMap\n+    assert(schema(map(userCol)).dataType == IntegerType)\n+    assert(schema(map(itemCol)).dataType== IntegerType)\n+    val ratingType = schema(map(ratingCol)).dataType\n+    assert(ratingType == FloatType || ratingType == DoubleType)\n+    val predictionColName = map(predictionCol)\n+    assert(!schema.fieldNames.contains(predictionColName),\n+      s\"Prediction column $predictionColName already exists.\")\n+    val newFields = schema.fields :+ StructField(map(predictionCol), FloatType, nullable = false)\n+    StructType(newFields)\n+  }\n+}\n+\n+/**\n+ * Model fitted by ALS.\n+ */\n+class ALSModel private[ml] (\n+    override val parent: ALS,\n+    override val fittingParamMap: ParamMap,\n+    k: Int,\n+    userFactors: RDD[(Int, Array[Float])],\n+    itemFactors: RDD[(Int, Array[Float])])\n+  extends Model[ALSModel] with ALSParams {\n+\n+  def setPredictionCol(value: String): this.type = set(predictionCol, value)\n+\n+  override def transform(dataset: SchemaRDD, paramMap: ParamMap): SchemaRDD = {\n+    import dataset.sqlContext._\n+    import org.apache.spark.ml.recommendation.ALSModel.Factor\n+    val map = this.paramMap ++ paramMap\n+    // TODO: Add DSL to simplify the code here.\n+    val instanceTable = s\"instance_$uid\"\n+    val userTable = s\"user_$uid\"\n+    val itemTable = s\"item_$uid\"\n+    val instances = dataset.as(Symbol(instanceTable))\n+    val users = userFactors.map { case (id, features) =>\n+      Factor(id, features)\n+    }.as(Symbol(userTable))\n+    val items = itemFactors.map { case (id, features) =>\n+      Factor(id, features)\n+    }.as(Symbol(itemTable))\n+    val predict: (Seq[Float], Seq[Float]) => Float = (userFeatures, itemFeatures) => {\n+      if (userFeatures != null && itemFeatures != null) {\n+        blas.sdot(k, userFeatures.toArray, 1, itemFeatures.toArray, 1)\n+      } else {\n+        Float.NaN\n+      }\n+    }\n+    val inputColumns = dataset.schema.fieldNames\n+    val prediction =\n+      predict.call(s\"$userTable.features\".attr, s\"$itemTable.features\".attr) as map(predictionCol)\n+    val outputColumns = inputColumns.map(f => s\"$instanceTable.$f\".attr as f) :+ prediction\n+    instances\n+      .join(users, LeftOuter, Some(map(userCol).attr === s\"$userTable.id\".attr))\n+      .join(items, LeftOuter, Some(map(itemCol).attr === s\"$itemTable.id\".attr))\n+      .select(outputColumns: _*)\n+  }\n+\n+  override private[ml] def transformSchema(schema: StructType, paramMap: ParamMap): StructType = {\n+    validateAndTransformSchema(schema, paramMap)\n+  }\n+}\n+\n+private object ALSModel {\n+  /** Case class to convert factors to SchemaRDDs */\n+  private case class Factor(id: Int, features: Seq[Float])\n+}\n+\n+/**\n+ * Alternating Least Squares (ALS) matrix factorization.\n+ *\n+ * ALS attempts to estimate the ratings matrix `R` as the product of two lower-rank matrices,\n+ * `X` and `Y`, i.e. `X * Yt = R`. Typically these approximations are called 'factor' matrices.\n+ * The general approach is iterative. During each iteration, one of the factor matrices is held\n+ * constant, while the other is solved for using least squares. The newly-solved factor matrix is\n+ * then held constant while solving for the other factor matrix.\n+ *\n+ * This is a blocked implementation of the ALS factorization algorithm that groups the two sets\n+ * of factors (referred to as \"users\" and \"products\") into blocks and reduces communication by only\n+ * sending one copy of each user vector to each product block on each iteration, and only for the\n+ * product blocks that need that user's feature vector. This is achieved by pre-computing some\n+ * information about the ratings matrix to determine the \"out-links\" of each user (which blocks of\n+ * products it will contribute to) and \"in-link\" information for each product (which of the feature\n+ * vectors it receives from each user block it will depend on). This allows us to send only an\n+ * array of feature vectors between each user block and product block, and have the product block\n+ * find the users' ratings and update the products based on these messages.\n+ *\n+ * For implicit preference data, the algorithm used is based on\n+ * \"Collaborative Filtering for Implicit Feedback Datasets\", available at\n+ * [[http://dx.doi.org/10.1109/ICDM.2008.22]], adapted for the blocked approach used here.\n+ *\n+ * Essentially instead of finding the low-rank approximations to the rating matrix `R`,\n+ * this finds the approximations for a preference matrix `P` where the elements of `P` are 1 if\n+ * r > 0 and 0 if r = 0. The ratings then act as 'confidence' values related to strength of\n+ * indicated user\n+ * preferences rather than explicit ratings given to items.\n+ */\n+class ALS extends Estimator[ALSModel] with ALSParams {\n+\n+  import org.apache.spark.ml.recommendation.ALS.Rating\n+\n+  def setRank(value: Int): this.type = set(rank, value)\n+  def setNumUserBlocks(value: Int): this.type = set(numUserBlocks, value)\n+  def setNumItemBlocks(value: Int): this.type = set(numItemBlocks, value)\n+  def setImplicitPrefs(value: Boolean): this.type = set(implicitPrefs, value)\n+  def setAlpha(value: Double): this.type = set(alpha, value)\n+  def setUserCol(value: String): this.type = set(userCol, value)\n+  def setItemCol(value: String): this.type = set(itemCol, value)\n+  def setRatingCol(value: String): this.type = set(ratingCol, value)\n+  def setPredictionCol(value: String): this.type = set(predictionCol, value)\n+  def setMaxIter(value: Int): this.type = set(maxIter, value)\n+  def setRegParam(value: Double): this.type = set(regParam, value)\n+\n+  /** Sets both numUserBlocks and numItemBlocks to the specific value. */\n+  def setNumBlocks(value: Int): this.type = {\n+    setNumUserBlocks(value)\n+    setNumItemBlocks(value)\n+    this\n+  }\n+\n+  setMaxIter(20)\n+  setRegParam(1.0)\n+\n+  override def fit(dataset: SchemaRDD, paramMap: ParamMap): ALSModel = {\n+    import dataset.sqlContext._\n+    val map = this.paramMap ++ paramMap\n+    val ratings =\n+      dataset.select(map(userCol).attr, map(itemCol).attr, Cast(map(ratingCol).attr, FloatType))\n+        .map { row =>\n+          new Rating(row.getInt(0), row.getInt(1), row.getFloat(2))\n+        }\n+    val (userFactors, itemFactors) = ALS.train(ratings, rank = map(rank),\n+      numUserBlocks = map(numUserBlocks), numItemBlocks = map(numItemBlocks),\n+      maxIter = map(maxIter), regParam = map(regParam), implicitPrefs = map(implicitPrefs),\n+      alpha = map(alpha))\n+    val model = new ALSModel(this, map, map(rank), userFactors, itemFactors)\n+    Params.inheritValues(map, this, model)\n+    model\n+  }\n+\n+  override private[ml] def transformSchema(schema: StructType, paramMap: ParamMap): StructType = {\n+    validateAndTransformSchema(schema, paramMap)\n+  }\n+}\n+\n+private[recommendation] object ALS extends Logging {\n+\n+  /** Rating class for better code readability. */\n+  private[recommendation] case class Rating(user: Int, item: Int, rating: Float)\n+\n+  /** Cholesky solver for least square problems. */\n+  private[recommendation] class CholeskySolver {\n+\n+    private val upper = \"U\"\n+    private val info = new intW(0)\n+\n+    /**\n+     * Solves a least squares problem with L2 regularization:\n+     *\n+     *   min norm(A x - b)^2^ + lambda * n * norm(x)^2^\n+     *\n+     * @param ne a [[NormalEquation]] instance that contains AtA, Atb, and n (number of instances)\n+     * @param lambda regularization constant, which will be scaled by n\n+     * @return the solution x\n+     */\n+    def solve(ne: NormalEquation, lambda: Double): Array[Float] = {\n+      val k = ne.k\n+      // Add scaled lambda to the diagonals of AtA.\n+      val scaledlambda = lambda * ne.n\n+      var i = 0\n+      var j = 2\n+      while (i < ne.triK) {\n+        ne.ata(i) += scaledlambda\n+        i += j\n+        j += 1\n+      }\n+      lapack.dppsv(upper, k, 1, ne.ata, ne.atb, k, info)\n+      val code = info.`val`\n+      assert(code == 0, s\"lapack.dppsv returned $code.\")\n+      val x = new Array[Float](k)\n+      i = 0\n+      while (i < k) {\n+        x(i) = ne.atb(i).toFloat\n+        i += 1\n+      }\n+      ne.reset()\n+      x\n+    }\n+  }\n+\n+  /** Representing a normal equation (ALS' subproblem). */\n+  private[recommendation] class NormalEquation(val k: Int) extends Serializable {\n+\n+    /** Number of entries in the upper triangular part of a k-by-k matrix. */\n+    val triK = k * (k + 1) / 2\n+    /** A^T^ * A */\n+    val ata = new Array[Double](triK)\n+    /** A^T^ * b */\n+    val atb = new Array[Double](k)\n+    /** Number of observations. */\n+    var n = 0\n+\n+    private val da = new Array[Double](k)\n+    private val upper = \"U\"\n+\n+    private def copyToDouble(a: Array[Float]): Unit = {\n+      var i = 0\n+      while (i < k) {\n+        da(i) = a(i)\n+        i += 1\n+      }\n+    }\n+\n+    /** Adds an observation. */\n+    def add(a: Array[Float], b: Float): this.type = {\n+      require(a.size == k)\n+      copyToDouble(a)\n+      blas.dspr(upper, k, 1.0, da, 1, ata)\n+      blas.daxpy(k, b.toDouble, da, 1, atb, 1)\n+      n += 1\n+      this\n+    }\n+\n+    /**\n+     * Adds an observation with implicit feedback. Note that this does not increment the counter.\n+     */\n+    def addImplicit(a: Array[Float], b: Float, alpha: Double): this.type = {\n+      require(a.size == k)\n+      val confidence = 1.0 + alpha * math.abs(b)\n+      copyToDouble(a)\n+      blas.dspr(upper, k, confidence - 1.0, da, 1, ata)\n+      if (b > 0) {\n+        blas.daxpy(k, confidence, da, 1, atb, 1)\n+      }\n+      this\n+    }\n+\n+    /** Merges another normal equation object. */\n+    def merge(other: NormalEquation): this.type = {\n+      require(other.k == k)\n+      blas.daxpy(ata.size, 1.0, other.ata, 1, ata, 1)\n+      blas.daxpy(atb.size, 1.0, other.atb, 1, atb, 1)\n+      n += other.n\n+      this\n+    }\n+\n+    /** Resets everything to zero, which should be called after each solve. */\n+    def reset(): Unit = {\n+      javaUtil.Arrays.fill(ata, 0.0)\n+      javaUtil.Arrays.fill(atb, 0.0)\n+      n = 0\n+    }\n+  }\n+\n+  /**\n+   * Implementation of the ALS algorithm.\n+   */\n+  private def train(\n+      ratings: RDD[Rating],\n+      rank: Int = 10,\n+      numUserBlocks: Int = 10,\n+      numItemBlocks: Int = 10,\n+      maxIter: Int = 10,\n+      regParam: Double = 1.0,\n+      implicitPrefs: Boolean = false,\n+      alpha: Double = 1.0): (RDD[(Int, Array[Float])], RDD[(Int, Array[Float])]) = {\n+    val userPart = new HashPartitioner(numUserBlocks)\n+    val itemPart = new HashPartitioner(numItemBlocks)\n+    val userLocalIndexEncoder = new LocalIndexEncoder(userPart.numPartitions)\n+    val itemLocalIndexEncoder = new LocalIndexEncoder(itemPart.numPartitions)\n+    val blockRatings = partitionRatings(ratings, userPart, itemPart).cache()\n+    val (userInBlocks, userOutBlocks) = makeBlocks(\"user\", blockRatings, userPart, itemPart)\n+    // materialize blockRatings and user blocks\n+    userOutBlocks.count()\n+    val swappedBlockRatings = blockRatings.map {\n+      case ((userBlockId, itemBlockId), RatingBlock(userIds, itemIds, localRatings)) =>\n+        ((itemBlockId, userBlockId), RatingBlock(itemIds, userIds, localRatings))\n+    }\n+    val (itemInBlocks, itemOutBlocks) = makeBlocks(\"item\", swappedBlockRatings, itemPart, userPart)\n+    // materialize item blocks\n+    itemOutBlocks.count()\n+    var userFactors = initialize(userInBlocks, rank)\n+    var itemFactors = initialize(itemInBlocks, rank)\n+    if (implicitPrefs) {\n+      for (iter <- 1 to maxIter) {\n+        userFactors.setName(s\"userFactors-$iter\").persist()\n+        val previousItemFactors = itemFactors\n+        itemFactors = computeFactors(userFactors, userOutBlocks, itemInBlocks, rank, regParam,\n+          userLocalIndexEncoder, implicitPrefs, alpha)\n+        previousItemFactors.unpersist()\n+        itemFactors.setName(s\"itemFactors-$iter\").persist()\n+        val previousUserFactors = userFactors\n+        userFactors = computeFactors(itemFactors, itemOutBlocks, userInBlocks, rank, regParam,\n+          itemLocalIndexEncoder, implicitPrefs, alpha)\n+        previousUserFactors.unpersist()\n+      }\n+    } else {\n+      for (iter <- 0 until maxIter) {\n+        itemFactors = computeFactors(userFactors, userOutBlocks, itemInBlocks, rank, regParam,\n+          userLocalIndexEncoder)\n+        userFactors = computeFactors(itemFactors, itemOutBlocks, userInBlocks, rank, regParam,\n+          itemLocalIndexEncoder)\n+      }\n+    }\n+    val userIdAndFactors = userInBlocks\n+      .mapValues(_.srcIds)\n+      .join(userFactors)\n+      .values\n+      .setName(\"userFactors\")\n+      .cache()\n+    userIdAndFactors.count()\n+    itemFactors.unpersist()\n+    val itemIdAndFactors = itemInBlocks\n+      .mapValues(_.srcIds)\n+      .join(itemFactors)\n+      .values\n+      .setName(\"itemFactors\")\n+      .cache()\n+    itemIdAndFactors.count()\n+    userInBlocks.unpersist()\n+    userOutBlocks.unpersist()\n+    itemInBlocks.unpersist()\n+    itemOutBlocks.unpersist()\n+    blockRatings.unpersist()\n+    val userOutput = userIdAndFactors.flatMap { case (ids, factors) =>\n+      ids.view.zip(factors)\n+    }\n+    val itemOutput = itemIdAndFactors.flatMap { case (ids, factors) =>\n+      ids.view.zip(factors)\n+    }\n+    (userOutput, itemOutput)\n+  }\n+\n+  /**\n+   * Factor block that stores factors (Array[Float]) in an Array.\n+   */\n+  private type FactorBlock = Array[Array[Float]]\n+\n+  /**\n+   * Out-link block that stores, for each dst (item/user) block, which src (user/item) factors to\n+   * send. For example, outLinkBlock(0) contains the local indices (not the original src IDs) of the\n+   * src factors in this block to send to dst block 0.\n+   */\n+  private type OutBlock = Array[Array[Int]]\n+\n+  /**\n+   * In-link block for computing src (user/item) factors. This includes the original src IDs\n+   * of the elements within this block as well as encoded dst (item/user) indices and corresponding\n+   * ratings. The dst indices are in the form of (blockId, localIndex), which are not the original\n+   * dst IDs. To compute src factors, we expect receiving dst factors that match the dst indices.\n+   * For example, if we have an in-link record\n+   *\n+   * {srcId: 0, dstBlockId: 2, dstLocalIndex: 3, rating: 5.0},\n+   *\n+   * and assume that the dst factors are stored as dstFactors: Map[Int, Array[Array[Float]]], which\n+   * is a blockId to dst factors map, the corresponding dst factor of the record is dstFactor(2)(3).\n+   *\n+   * We use a CSC-like (compressed sparse column) format to store the in-link information. So we can\n+   * compute src factors one after another using only one normal equation instance.\n+   *\n+   * @param srcIds src ids (ordered)\n+   * @param dstPtrs dst pointers. Elements in range [dstPtrs(i), dstPtrs(i+1)) of dst indices and\n+   *                ratings are associated with srcIds(i).\n+   * @param dstEncodedIndices encoded dst indices\n+   * @param ratings ratings\n+   *\n+   * @see [[LocalIndexEncoder]]\n+   */\n+  private[recommendation] case class InBlock(\n+      srcIds: Array[Int],\n+      dstPtrs: Array[Int],\n+      dstEncodedIndices: Array[Int],\n+      ratings: Array[Float]) {\n+    /** Size of the block. */\n+    val size: Int = ratings.size\n+    require(dstEncodedIndices.size == size)\n+    require(dstPtrs.size == srcIds.size + 1)\n+  }\n+\n+  /**\n+   * Initializes factors randomly given the in-link blocks.\n+   *\n+   * @param inBlocks in-link blocks\n+   * @param rank rank\n+   * @return initialized factor blocks\n+   */\n+  private def initialize(inBlocks: RDD[(Int, InBlock)], rank: Int): RDD[(Int, FactorBlock)] = {\n+    inBlocks.map { case (srcBlockId, inBlock) =>\n+      val random = new XORShiftRandom(srcBlockId)\n+      val factors = Array.fill(inBlock.srcIds.size) {\n+        val factor = Array.fill(rank)(random.nextGaussian().toFloat)\n+        val nrm = blas.snrm2(rank, factor, 1)\n+        blas.sscal(rank, 1.0f / nrm, factor, 1)\n+        factor\n+      }\n+      (srcBlockId, factors)\n+    }\n+  }\n+\n+  /**\n+   * A rating block that contains src IDs, dst IDs, and ratings, stored in primitive arrays.\n+   */\n+  private[recommendation]\n+  case class RatingBlock(srcIds: Array[Int], dstIds: Array[Int], ratings: Array[Float]) {\n+    /** Size of the block. */\n+    val size: Int = srcIds.size\n+    require(dstIds.size == size)\n+    require(ratings.size == size)\n+  }\n+\n+  /**\n+   * Builder for [[RatingBlock]]. [[mutable.ArrayBuilder]] is used to avoid boxing/unboxing.\n+   */\n+  private[recommendation] class RatingBlockBuilder extends Serializable {\n+\n+    private val srcIds = mutable.ArrayBuilder.make[Int]\n+    private val dstIds = mutable.ArrayBuilder.make[Int]\n+    private val ratings = mutable.ArrayBuilder.make[Float]\n+    var size = 0\n+\n+    /** Adds a rating. */\n+    def add(r: Rating): this.type = {\n+      size += 1\n+      srcIds += r.user\n+      dstIds += r.item\n+      ratings += r.rating\n+      this\n+    }\n+\n+    /** Merges another [[RatingBlockBuilder]]. */\n+    def merge(other: RatingBlock): this.type = {\n+      size += other.srcIds.size\n+      srcIds ++= other.srcIds\n+      dstIds ++= other.dstIds\n+      ratings ++= other.ratings\n+      this\n+    }\n+\n+    /** Builds a [[RatingBlock]]. */\n+    def build(): RatingBlock = {\n+      RatingBlock(srcIds.result(), dstIds.result(), ratings.result())\n+    }\n+  }\n+\n+  /**\n+   * Partitions raw ratings into blocks.\n+   *\n+   * @param ratings raw ratings\n+   * @param srcPart partitioner for src IDs\n+   * @param dstPart partitioner for dst IDs\n+   *\n+   * @return an RDD of rating blocks in the form of ((srcBlockId, dstBlockId), ratingBlock)\n+   */\n+  private def partitionRatings(\n+      ratings: RDD[Rating],\n+      srcPart: Partitioner,\n+      dstPart: Partitioner): RDD[((Int, Int), RatingBlock)] = {\n+\n+     /* The implementation produces the same result as the following but generates less objects.\n+\n+     ratings.map { r =>\n+       ((srcPart.getPartition(r.user), dstPart.getPartition(r.item)), r)\n+     }.aggregateByKey(new RatingBlockBuilder)(\n+         seqOp = (b, r) => b.add(r),\n+         combOp = (b0, b1) => b0.merge(b1.build()))\n+       .mapValues(_.build())\n+     */\n+\n+    val numPartitions = srcPart.numPartitions * dstPart.numPartitions\n+    ratings.mapPartitions { iter =>\n+      val builders = Array.fill(numPartitions)(new RatingBlockBuilder)\n+      iter.flatMap { r =>\n+        val srcBlockId = srcPart.getPartition(r.user)\n+        val dstBlockId = dstPart.getPartition(r.item)\n+        val idx = srcBlockId + srcPart.numPartitions * dstBlockId\n+        val builder = builders(idx)\n+        builder.add(r)\n+        if (builder.size >= 2048) { // 2048 * (3 * 4) = 24k\n+          builders(idx) = new RatingBlockBuilder\n+          Iterator.single(((srcBlockId, dstBlockId), builder.build()))\n+        } else {\n+          Iterator.empty\n+        }\n+      } ++ {\n+        builders.view.zipWithIndex.filter(_._1.size > 0).map { case (block, idx) =>\n+          val srcBlockId = idx % srcPart.numPartitions\n+          val dstBlockId = idx / srcPart.numPartitions\n+          ((srcBlockId, dstBlockId), block.build())\n+        }\n+      }\n+    }.groupByKey().mapValues { blocks =>\n+      val builder = new RatingBlockBuilder\n+      blocks.foreach(builder.merge)\n+      builder.build()\n+    }.setName(\"ratingBlocks\")\n+  }\n+\n+  /**\n+   * Builder for uncompressed in-blocks of (srcId, dstEncodedIndex, rating) tuples.\n+   * @param encoder encoder for dst indices\n+   */\n+  private[recommendation] class UncompressedInBlockBuilder(encoder: LocalIndexEncoder) {\n+\n+    private val srcIds = mutable.ArrayBuilder.make[Int]\n+    private val dstEncodedIndices = mutable.ArrayBuilder.make[Int]\n+    private val ratings = mutable.ArrayBuilder.make[Float]\n+\n+    /**\n+     * Adds a dst block of (srcId, dstLocalIndex, rating) tuples.\n+     *\n+     * @param dstBlockId dst block ID\n+     * @param srcIds original src IDs\n+     * @param dstLocalIndices dst local indices\n+     * @param ratings ratings\n+     */\n+    def add(\n+        dstBlockId: Int,\n+        srcIds: Array[Int],\n+        dstLocalIndices: Array[Int],\n+        ratings: Array[Float]): this.type = {\n+      val sz = srcIds.size\n+      require(dstLocalIndices.size == sz)\n+      require(ratings.size == sz)\n+      this.srcIds ++= srcIds\n+      this.ratings ++= ratings\n+      var j = 0\n+      while (j < sz) {\n+        this.dstEncodedIndices += encoder.encode(dstBlockId, dstLocalIndices(j))\n+        j += 1\n+      }\n+      this\n+    }\n+\n+    /** Builds a [[UncompressedInBlock]]. */\n+    def build(): UncompressedInBlock = {\n+      new UncompressedInBlock(srcIds.result(), dstEncodedIndices.result(), ratings.result())\n+    }\n+  }\n+\n+  /**\n+   * A block of (srcId, dstEncodedIndex, rating) tuples stored in primitive arrays.\n+   */\n+  private[recommendation] class UncompressedInBlock(\n+      val srcIds: Array[Int],\n+      val dstEncodedIndices: Array[Int],\n+      val ratings: Array[Float]) {\n+\n+    /** Size the of block. */\n+    def size: Int = srcIds.size\n+\n+    /**\n+     * Compresses the block into an [[InBlock]]. The algorithm is the same as converting a\n+     * sparse matrix from coordinate list (COO) format into compressed sparse column (CSC) format.\n+     * Sorting is done using Spark's built-in Timsort to avoid generating too many objects.\n+     */\n+    def compress(): InBlock = {\n+      val sz = size\n+      assert(sz > 0, \"Empty in-link block should not exist.\")\n+      sort()\n+      val uniqueSrcIdsBuilder = mutable.ArrayBuilder.make[Int]\n+      val dstCountsBuilder = mutable.ArrayBuilder.make[Int]\n+      var preSrcId = srcIds(0)\n+      uniqueSrcIdsBuilder += preSrcId\n+      var curCount = 1\n+      var i = 1\n+      var j = 0\n+      while (i < sz) {\n+        val srcId = srcIds(i)\n+        if (srcId != preSrcId) {\n+          uniqueSrcIdsBuilder += srcId\n+          dstCountsBuilder += curCount\n+          preSrcId = srcId\n+          j += 1\n+          curCount = 0\n+        }\n+        curCount += 1\n+        i += 1\n+      }\n+      dstCountsBuilder += curCount\n+      val uniqueSrcIds = uniqueSrcIdsBuilder.result()\n+      val numUniqueSrdIds = uniqueSrcIds.size\n+      val dstCounts = dstCountsBuilder.result()\n+      val dstPtrs = new Array[Int](numUniqueSrdIds + 1)\n+      var sum = 0\n+      i = 0\n+      while (i < numUniqueSrdIds) {\n+        sum += dstCounts(i)\n+        i += 1\n+        dstPtrs(i) = sum\n+      }\n+      InBlock(uniqueSrcIds, dstPtrs, dstEncodedIndices, ratings)\n+    }\n+\n+    private def sort(): Unit = {\n+      val sz = size\n+      // Since there might be interleaved log messages, we insert a unique id for easy pairing.\n+      val sortId = Utils.random.nextInt()\n+      logDebug(s\"Start sorting an uncompressed in-block of size $sz. (sortId = $sortId)\")\n+      val start = System.nanoTime()\n+      val sorter = new Sorter(new UncompressedInBlockSort)\n+      sorter.sort(this, 0, size, Ordering[IntWrapper])\n+      val duration = (System.nanoTime() - start) / 1e9\n+      logDebug(s\"Sorting took $duration seconds. (sortId = $sortId)\")\n+    }\n+  }\n+\n+  /**\n+   * A wrapper that holds a primitive integer key.\n+   *\n+   * @see [[UncompressedInBlockSort]]\n+   */\n+  private class IntWrapper(var key: Int = 0) extends Ordered[IntWrapper] {\n+    override def compare(that: IntWrapper): Int = {\n+      key.compare(that.key)\n+    }\n+  }\n+\n+  /**\n+   * [[SortDataFormat]] of [[UncompressedInBlock]] used by [[Sorter]].\n+   */\n+  private class UncompressedInBlockSort extends SortDataFormat[IntWrapper, UncompressedInBlock] {\n+\n+    override def newKey(): IntWrapper = new IntWrapper()\n+\n+    override def getKey(\n+        data: UncompressedInBlock,\n+        pos: Int,\n+        reuse: IntWrapper): IntWrapper = {\n+      if (reuse == null) {\n+        new IntWrapper(data.srcIds(pos))\n+      } else {\n+        reuse.key = data.srcIds(pos)\n+        reuse\n+      }\n+    }\n+\n+    override def getKey(\n+        data: UncompressedInBlock,\n+        pos: Int): IntWrapper = {\n+      getKey(data, pos, null)\n+    }\n+\n+    private def swapElements[@specialized(Int, Float) T](\n+        data: Array[T],\n+        pos0: Int,\n+        pos1: Int): Unit = {\n+      val tmp = data(pos0)\n+      data(pos0) = data(pos1)\n+      data(pos1) = tmp\n+    }\n+\n+    override def swap(data: UncompressedInBlock, pos0: Int, pos1: Int): Unit = {\n+      swapElements(data.srcIds, pos0, pos1)\n+      swapElements(data.dstEncodedIndices, pos0, pos1)\n+      swapElements(data.ratings, pos0, pos1)\n+    }\n+\n+    override def copyRange(\n+        src: UncompressedInBlock,\n+        srcPos: Int,\n+        dst: UncompressedInBlock,\n+        dstPos: Int,\n+        length: Int): Unit = {\n+      System.arraycopy(src.srcIds, srcPos, dst.srcIds, dstPos, length)\n+      System.arraycopy(src.dstEncodedIndices, srcPos, dst.dstEncodedIndices, dstPos, length)\n+      System.arraycopy(src.ratings, srcPos, dst.ratings, dstPos, length)\n+    }\n+\n+    override def allocate(length: Int): UncompressedInBlock = {\n+      new UncompressedInBlock(\n+        new Array[Int](length), new Array[Int](length), new Array[Float](length))\n+    }\n+\n+    override def copyElement(\n+        src: UncompressedInBlock,\n+        srcPos: Int,\n+        dst: UncompressedInBlock,\n+        dstPos: Int): Unit = {\n+      dst.srcIds(dstPos) = src.srcIds(srcPos)\n+      dst.dstEncodedIndices(dstPos) = src.dstEncodedIndices(srcPos)\n+      dst.ratings(dstPos) = src.ratings(srcPos)\n+    }\n+  }\n+\n+  /**\n+   * Creates in-blocks and out-blocks from rating blocks.\n+   * @param prefix prefix for in/out-block names\n+   * @param ratingBlocks rating blocks\n+   * @param srcPart partitioner for src IDs\n+   * @param dstPart partitioner for dst IDs\n+   * @return (in-blocks, out-blocks)\n+   */\n+  private def makeBlocks(\n+      prefix: String,\n+      ratingBlocks: RDD[((Int, Int), RatingBlock)],\n+      srcPart: Partitioner,\n+      dstPart: Partitioner): (RDD[(Int, InBlock)], RDD[(Int, OutBlock)]) = {\n+    val inBlocks = ratingBlocks.map {\n+      case ((srcBlockId, dstBlockId), RatingBlock(srcIds, dstIds, ratings)) =>\n+        // The implementation is a faster version of\n+        // val dstIdToLocalIndex = dstIds.toSet.toSeq.sorted.zipWithIndex.toMap\n+        val start = System.nanoTime()\n+        val dstIdSet = new OpenHashSet[Int](1 << 20)\n+        dstIds.foreach(dstIdSet.add)\n+        val sortedDstIds = new Array[Int](dstIdSet.size)\n+        var i = 0\n+        var pos = dstIdSet.nextPos(0)\n+        while (pos != -1) {\n+          sortedDstIds(i) = dstIdSet.getValue(pos)\n+          pos = dstIdSet.nextPos(pos + 1)\n+          i += 1\n+        }\n+        assert(i == dstIdSet.size)\n+        javaUtil.Arrays.sort(sortedDstIds)\n+        val dstIdToLocalIndex = new OpenHashMap[Int, Int](sortedDstIds.size)\n+        i = 0\n+        while (i < sortedDstIds.size) {\n+          dstIdToLocalIndex.update(sortedDstIds(i), i)\n+          i += 1\n+        }\n+        logDebug(\n+          \"Converting to local indices took \" + (System.nanoTime() - start) / 1e9 + \" seconds.\")\n+        val dstLocalIndices = dstIds.map(dstIdToLocalIndex.apply)\n+        (srcBlockId, (dstBlockId, srcIds, dstLocalIndices, ratings))\n+    }.groupByKey(new HashPartitioner(srcPart.numPartitions))\n+        .mapValues { iter =>\n+      val builder =\n+        new UncompressedInBlockBuilder(new LocalIndexEncoder(dstPart.numPartitions))\n+      iter.foreach { case (dstBlockId, srcIds, dstLocalIndices, ratings) =>\n+        builder.add(dstBlockId, srcIds, dstLocalIndices, ratings)\n+      }\n+      builder.build().compress()\n+    }.setName(prefix + \"InBlocks\").cache()\n+    val outBlocks = inBlocks.mapValues { case InBlock(srcIds, dstPtrs, dstEncodedIndices, _) =>\n+      val encoder = new LocalIndexEncoder(dstPart.numPartitions)\n+      val activeIds = Array.fill(dstPart.numPartitions)(mutable.ArrayBuilder.make[Int])\n+      var i = 0\n+      val seen = new Array[Boolean](dstPart.numPartitions)\n+      while (i < srcIds.size) {\n+        var j = dstPtrs(i)\n+        javaUtil.Arrays.fill(seen, false)\n+        while (j < dstPtrs(i + 1)) {\n+          val dstBlockId = encoder.blockId(dstEncodedIndices(j))\n+          if (!seen(dstBlockId)) {\n+            activeIds(dstBlockId) += i // add the local index in this out-block\n+            seen(dstBlockId) = true\n+          }\n+          j += 1\n+        }\n+        i += 1\n+      }\n+      activeIds.map { x =>\n+        x.result()\n+      }\n+    }.setName(prefix + \"OutBlocks\").cache()\n+    (inBlocks, outBlocks)\n+  }\n+\n+  /**\n+   * Compute dst factors by constructing and solving least square problems.\n+   *\n+   * @param srcFactorBlocks src factors\n+   * @param srcOutBlocks src out-blocks\n+   * @param dstInBlocks dst in-blocks\n+   * @param rank rank\n+   * @param regParam regularization constant\n+   * @param srcEncoder encoder for src local indices\n+   * @param implicitPrefs whether to use implicit preference\n+   * @param alpha the alpha constant in the implicit preference formulation\n+   *\n+   * @return dst factors\n+   */\n+  private def computeFactors(\n+      srcFactorBlocks: RDD[(Int, FactorBlock)],\n+      srcOutBlocks: RDD[(Int, OutBlock)],\n+      dstInBlocks: RDD[(Int, InBlock)],\n+      rank: Int,\n+      regParam: Double,\n+      srcEncoder: LocalIndexEncoder,\n+      implicitPrefs: Boolean = false,\n+      alpha: Double = 1.0): RDD[(Int, FactorBlock)] = {\n+    val numSrcBlocks = srcFactorBlocks.partitions.size\n+    val YtY = if (implicitPrefs) Some(computeYtY(srcFactorBlocks, rank)) else None\n+    val srcOut = srcOutBlocks.join(srcFactorBlocks).flatMap {\n+      case (srcBlockId, (srcOutBlock, srcFactors)) =>\n+        srcOutBlock.view.zipWithIndex.map { case (activeIndices, dstBlockId) =>","path":"mllib/src/main/scala/org/apache/spark/ml/recommendation/ALS.scala","position":874,"original_position":874,"commit_id":"a76da7bb4d3a3073999725f8c10c5c2443fd7839","original_commit_id":"a76da7bb4d3a3073999725f8c10c5c2443fd7839","user":{"login":"srowen","id":822522,"avatar_url":"https://avatars.githubusercontent.com/u/822522?v=3","gravatar_id":"","url":"https://api.github.com/users/srowen","html_url":"https://github.com/srowen","followers_url":"https://api.github.com/users/srowen/followers","following_url":"https://api.github.com/users/srowen/following{/other_user}","gists_url":"https://api.github.com/users/srowen/gists{/gist_id}","starred_url":"https://api.github.com/users/srowen/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/srowen/subscriptions","organizations_url":"https://api.github.com/users/srowen/orgs","repos_url":"https://api.github.com/users/srowen/repos","events_url":"https://api.github.com/users/srowen/events{/privacy}","received_events_url":"https://api.github.com/users/srowen/received_events","type":"User","site_admin":false},"body":"I assume it's to materialize the result lazily. Otherwise it creates the entire result in memory at once.","created_at":"2015-01-09T12:06:34Z","updated_at":"2015-01-09T12:06:34Z","html_url":"https://github.com/apache/spark/pull/3720#discussion_r22712763","pull_request_url":"https://api.github.com/repos/apache/spark/pulls/3720","_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/22712763"},"html":{"href":"https://github.com/apache/spark/pull/3720#discussion_r22712763"},"pull_request":{"href":"https://api.github.com/repos/apache/spark/pulls/3720"}}},"pull_request":{"url":"https://api.github.com/repos/apache/spark/pulls/3720","id":26205521,"html_url":"https://github.com/apache/spark/pull/3720","diff_url":"https://github.com/apache/spark/pull/3720.diff","patch_url":"https://github.com/apache/spark/pull/3720.patch","issue_url":"https://api.github.com/repos/apache/spark/issues/3720","number":3720,"state":"open","locked":false,"title":"[SPARK-3541][MLLIB] New ALS implementation with improved storage","user":{"login":"mengxr","id":829644,"avatar_url":"https://avatars.githubusercontent.com/u/829644?v=3","gravatar_id":"","url":"https://api.github.com/users/mengxr","html_url":"https://github.com/mengxr","followers_url":"https://api.github.com/users/mengxr/followers","following_url":"https://api.github.com/users/mengxr/following{/other_user}","gists_url":"https://api.github.com/users/mengxr/gists{/gist_id}","starred_url":"https://api.github.com/users/mengxr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mengxr/subscriptions","organizations_url":"https://api.github.com/users/mengxr/orgs","repos_url":"https://api.github.com/users/mengxr/repos","events_url":"https://api.github.com/users/mengxr/events{/privacy}","received_events_url":"https://api.github.com/users/mengxr/received_events","type":"User","site_admin":false},"body":"This PR adds a new ALS implementation to `spark.ml` using the pipeline API, which should be able to scale to billions of ratings. Compared with the ALS under `spark.mllib`, the new implementation\r\n\r\n1. uses the same algorithm,\r\n2. uses float type for ratings,\r\n3. uses primitive arrays to avoid GC,\r\n4. sorts and compresses ratings on each block so that we can solve least squares subproblems one by one using only one normal equation instance.\r\n\r\nThe following figure shows performance comparison on copies of the Amazon Reviews dataset using a 16-node (m3.2xlarge) EC2 cluster (the same setup as in http://databricks.com/blog/2014/07/23/scalable-collaborative-filtering-with-spark-mllib.html):\r\n![als-wip](https://cloud.githubusercontent.com/assets/829644/5659447/4c4ff8e0-96c7-11e4-87a9-73c1c63d07f3.png)\r\n\r\nI keep the `spark.mllib`'s ALS untouched for easy comparison. If the new implementation works well, I'm going to match the features of the ALS under `spark.mllib` and then make it a wrapper of the new implementation, in a separate PR.\r\n\r\nTODO:\r\n[ ] Add unit tests for implicit preferences.\r\n","created_at":"2014-12-17T07:26:54Z","updated_at":"2015-01-09T12:06:34Z","closed_at":null,"merged_at":null,"merge_commit_sha":"1a8dcaa6c743f43b812a0cc25b208b67d2970e02","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/apache/spark/pulls/3720/commits","review_comments_url":"https://api.github.com/repos/apache/spark/pulls/3720/comments","review_comment_url":"https://api.github.com/repos/apache/spark/pulls/comments/{number}","comments_url":"https://api.github.com/repos/apache/spark/issues/3720/comments","statuses_url":"https://api.github.com/repos/apache/spark/statuses/a76da7bb4d3a3073999725f8c10c5c2443fd7839","head":{"label":"mengxr:SPARK-3541","ref":"SPARK-3541","sha":"a76da7bb4d3a3073999725f8c10c5c2443fd7839","user":{"login":"mengxr","id":829644,"avatar_url":"https://avatars.githubusercontent.com/u/829644?v=3","gravatar_id":"","url":"https://api.github.com/users/mengxr","html_url":"https://github.com/mengxr","followers_url":"https://api.github.com/users/mengxr/followers","following_url":"https://api.github.com/users/mengxr/following{/other_user}","gists_url":"https://api.github.com/users/mengxr/gists{/gist_id}","starred_url":"https://api.github.com/users/mengxr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mengxr/subscriptions","organizations_url":"https://api.github.com/users/mengxr/orgs","repos_url":"https://api.github.com/users/mengxr/repos","events_url":"https://api.github.com/users/mengxr/events{/privacy}","received_events_url":"https://api.github.com/users/mengxr/received_events","type":"User","site_admin":false},"repo":{"id":17278743,"name":"spark","full_name":"mengxr/spark","owner":{"login":"mengxr","id":829644,"avatar_url":"https://avatars.githubusercontent.com/u/829644?v=3","gravatar_id":"","url":"https://api.github.com/users/mengxr","html_url":"https://github.com/mengxr","followers_url":"https://api.github.com/users/mengxr/followers","following_url":"https://api.github.com/users/mengxr/following{/other_user}","gists_url":"https://api.github.com/users/mengxr/gists{/gist_id}","starred_url":"https://api.github.com/users/mengxr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mengxr/subscriptions","organizations_url":"https://api.github.com/users/mengxr/orgs","repos_url":"https://api.github.com/users/mengxr/repos","events_url":"https://api.github.com/users/mengxr/events{/privacy}","received_events_url":"https://api.github.com/users/mengxr/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/mengxr/spark","description":"Mirror of Apache Spark","fork":true,"url":"https://api.github.com/repos/mengxr/spark","forks_url":"https://api.github.com/repos/mengxr/spark/forks","keys_url":"https://api.github.com/repos/mengxr/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mengxr/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mengxr/spark/teams","hooks_url":"https://api.github.com/repos/mengxr/spark/hooks","issue_events_url":"https://api.github.com/repos/mengxr/spark/issues/events{/number}","events_url":"https://api.github.com/repos/mengxr/spark/events","assignees_url":"https://api.github.com/repos/mengxr/spark/assignees{/user}","branches_url":"https://api.github.com/repos/mengxr/spark/branches{/branch}","tags_url":"https://api.github.com/repos/mengxr/spark/tags","blobs_url":"https://api.github.com/repos/mengxr/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mengxr/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mengxr/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/mengxr/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mengxr/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/mengxr/spark/languages","stargazers_url":"https://api.github.com/repos/mengxr/spark/stargazers","contributors_url":"https://api.github.com/repos/mengxr/spark/contributors","subscribers_url":"https://api.github.com/repos/mengxr/spark/subscribers","subscription_url":"https://api.github.com/repos/mengxr/spark/subscription","commits_url":"https://api.github.com/repos/mengxr/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/mengxr/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/mengxr/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/mengxr/spark/issues/comments/{number}","contents_url":"https://api.github.com/repos/mengxr/spark/contents/{+path}","compare_url":"https://api.github.com/repos/mengxr/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mengxr/spark/merges","archive_url":"https://api.github.com/repos/mengxr/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mengxr/spark/downloads","issues_url":"https://api.github.com/repos/mengxr/spark/issues{/number}","pulls_url":"https://api.github.com/repos/mengxr/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/mengxr/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/mengxr/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mengxr/spark/labels{/name}","releases_url":"https://api.github.com/repos/mengxr/spark/releases{/id}","created_at":"2014-02-28T07:27:59Z","updated_at":"2014-11-25T00:46:59Z","pushed_at":"2015-01-08T07:33:54Z","git_url":"git://github.com/mengxr/spark.git","ssh_url":"git@github.com:mengxr/spark.git","clone_url":"https://github.com/mengxr/spark.git","svn_url":"https://github.com/mengxr/spark","homepage":null,"size":90052,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"3d0c37b8118f6057a663f959321a79b8061132b6","user":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":17165658,"name":"spark","full_name":"apache/spark","owner":{"login":"apache","id":47359,"avatar_url":"https://avatars.githubusercontent.com/u/47359?v=3","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/apache/spark","description":"Mirror of Apache Spark","fork":false,"url":"https://api.github.com/repos/apache/spark","forks_url":"https://api.github.com/repos/apache/spark/forks","keys_url":"https://api.github.com/repos/apache/spark/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/spark/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/spark/teams","hooks_url":"https://api.github.com/repos/apache/spark/hooks","issue_events_url":"https://api.github.com/repos/apache/spark/issues/events{/number}","events_url":"https://api.github.com/repos/apache/spark/events","assignees_url":"https://api.github.com/repos/apache/spark/assignees{/user}","branches_url":"https://api.github.com/repos/apache/spark/branches{/branch}","tags_url":"https://api.github.com/repos/apache/spark/tags","blobs_url":"https://api.github.com/repos/apache/spark/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/spark/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/spark/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/spark/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/spark/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/spark/languages","stargazers_url":"https://api.github.com/repos/apache/spark/stargazers","contributors_url":"https://api.github.com/repos/apache/spark/contributors","subscribers_url":"https://api.github.com/repos/apache/spark/subscribers","subscription_url":"https://api.github.com/repos/apache/spark/subscription","commits_url":"https://api.github.com/repos/apache/spark/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/spark/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/spark/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/spark/issues/comments/{number}","contents_url":"https://api.github.com/repos/apache/spark/contents/{+path}","compare_url":"https://api.github.com/repos/apache/spark/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/spark/merges","archive_url":"https://api.github.com/repos/apache/spark/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/spark/downloads","issues_url":"https://api.github.com/repos/apache/spark/issues{/number}","pulls_url":"https://api.github.com/repos/apache/spark/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/spark/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/spark/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/spark/labels{/name}","releases_url":"https://api.github.com/repos/apache/spark/releases{/id}","created_at":"2014-02-25T08:00:08Z","updated_at":"2015-01-09T07:08:04Z","pushed_at":"2015-01-09T01:42:21Z","git_url":"git://github.com/apache/spark.git","ssh_url":"git@github.com:apache/spark.git","clone_url":"https://github.com/apache/spark.git","svn_url":"https://github.com/apache/spark","homepage":null,"size":1082468,"stargazers_count":2516,"watchers_count":2516,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":2230,"mirror_url":"git://git.apache.org/spark.git","open_issues_count":303,"forks":2230,"open_issues":303,"watchers":2516,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/spark/pulls/3720"},"html":{"href":"https://github.com/apache/spark/pull/3720"},"issue":{"href":"https://api.github.com/repos/apache/spark/issues/3720"},"comments":{"href":"https://api.github.com/repos/apache/spark/issues/3720/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/spark/pulls/3720/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/spark/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/apache/spark/pulls/3720/commits"},"statuses":{"href":"https://api.github.com/repos/apache/spark/statuses/a76da7bb4d3a3073999725f8c10c5c2443fd7839"}}}}