Patent ID: 7783647

Claim:
A method for computing a local quantile summary, comprising: receiving an update value via an update stream; determining an actual rank of a local quantile value using said update value; computing a predicted rank of said local quantile value using a prediction model; computing a local quantile summary in response to a determination that a difference between said actual rank of said local quantile value and said predicted rank of said local quantile value exceeds an update threshold, wherein said local quantile summary is computed using a processor; and propagating the computed local quantile summary toward a remote system, wherein said remote system is configured for responding to a rank query request using said local quantile summary and information associated with said prediction model, wherein said responding comprises: determining, for each of at least one remote monitor, a predicted lower-bound rank value and a predicted upper-bound rank value, wherein said predicted lower-bound rank value and said predicted upper-bound rank value are determined according to at least one respective prediction model used by each of said at least one remote monitor to compute at least one local quantile summary; computing a predicted average rank value for each of said at least one remote monitor using said at least one predicted lower-bound rank value and said at least one predicted upper-bound rank value associated with respective said at least one remote monitor; and computing said absolute rank of said query value using said at least one predicted average rank value associated with respective said at least one remote monitor.