Patent Document ID: 9058220
Application ID: 13726818
Patent Flag: 1

Claim One:
1. A system for efficiently computing iterative functions over aggregate statistics of a distributed data set, said system comprising: a plurality of processors programmed to perform distributed computations, the distributed data set partitioned into a plurality of data subsets, one for each of the plurality of processors, wherein each of the plurality of processors includes: 1) statistics describing a current best estimate of the aggregate statistics; and 2) a differential vector describing changes to the statistics describing a current best estimate of the aggregate statistics for a current iteration; wherein each of the plurality of processors is programmed to: iteratively perform a plurality of sweeps over the data subset of the processor to update the statistic until a termination criteria is satisfied; compute a differential vector representing the changes made during the update; save the differential vector of the processor for a predetermined number of past generations, each generation corresponding to an iteration of the processor; receive a generation-specific update from a sending one of the plurality of processors, the generation-specific update including a differential vector of the sending processor corresponding to the specific generation of the generation-specific update, wherein differential logic used to generate the differential vector is located on the sending one of the plurality of processors; and aggregate the differential vector of the generation-specific update with the statistics of the receiving processor, wherein the processor receiving the generation-specific update does not require main memory to store complete copies of the statistics one of the plurality of from sending processors, as the update includes sparse differential vectors which are aggregated component by component as received.