Generation-based update caching for robust scalable distributed gibbs sampling

A method for efficiently computing iterative functions over aggregate statistics of a distributed data set, said system comprising:

• performing by a plurality of processors 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 for a current iteration;
• for each of the plurality of processors:
• iteratively performing a plurality of sweeps over the data subset of the processor to update the statistic until a termination criteria is satisfied;
• computing a differential vector representing the changes made during the update;
• saving the differential vector of the processor for a predetermined number of past generations, each generation corresponding to an iteration of the processor;
• receiving 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;
• and
• aggregating the differential vector of the generation-specific update with the statistics of the receiving processor.

A system for Gibbs sampling comprising:

• a plurality of processors programmed to perform distributed Gibbs sampling on a data set, the data set partitioned into a plurality of subsets, one for each of the processors, wherein each of the processors includes local counts describing the subset of the processor and global counts describing the one or more other subsets;
• and,
• wherein each of the processors is programmed to:
• iteratively perform a plurality of Gibbs sampling sweeps over the subset of the processor to update the local counts of the processor, wherein each of the Gibbs sampling sweeps uses the global counts of the processor;
• save local counts of the processor describing the subset of the processor for each of a predetermined number of past generations, each generation corresponding to an iteration;
• subtract a saved past generation of local counts of the processor from a current generation of local counts of the processor to determine deviations of the processor;
• and,
• send the deviations of the processor to one of the other processors to update the global counts of the other processor.