Patent ID: 6343288
Filing Date: 2002-01-29
Classification: G06F,Y10S

Abstract:
A computer system, comprising:a general purpose computer; one or more input devices associated with the computer for generating a user specification, the specification establishing at least one desired approximate &phgr;-quantile, a quantile approximation error &egr;, and a probability of failure &dgr;, wherein the approximate &phgr;-quantile is guaranteed to represent a true quantile of a data set and lie within the quantile approximation error &egr; with a probability of at least 1âˆ’&dgr;; a data set having a size, the size being unavailable to the computer in advance; and computer usable code means executable by the computer for determining a &phgr;-quantile data element in the data set, the computer usable code means having: means for determining a number b of buffers and a size k of each buffer, and a number h, based at least in part on the permissible approximation error &egr; and the probability of failure &dgr;; means for filling empty buffers with data elements to establish a plurality of input buffers; means for collapsing data elements in input buffers into at least one output buffer; and means for outputting, from an output buffer, at least one &phgr;-quantile data element.