Patent ID: 7756805
Filing Date: 2010-07-13
Classification: G06F

Abstract:
1. A method for tracking, comprising: monitoring a plurality of local update streams by a plurality of monitoring sites, each monitoring site tracks any deviation of a local distribution from a predicted distribution using a sketch prediction model, the local update streams being part of a global data distribution in a distributed system; sending a state update message from each monitoring site to a coordinator only when the local distribution differs from the predicted distribution by more than a predetermined amount, the state update message including a predicted sketch derived from the sketch prediction model wherein a fast-AGMS sketch is used to track any deviation of the local distribution from the predicted distribution by averaging over partitions of a domain generated randomly through a hash function, the fast-AGMS sketch including a plurality of counters arranged in a plurality of hash tables, each hash table having a plurality of hash buckets; and providing an approximation at a coordinator based on the state update messages from the monitoring sites.