Single pass space efficent system and method for generating approximate quantiles satisfying an apriori user-defined approximation error
Number of patents in Portfolio can not be more than 2000
United States of America Patent
Stats
-
Aug 22, 2000
Grant Date -
N/A
app pub date -
Mar 30, 1998
filing date -
Mar 30, 1998
priority date (Note) -
Expired
status (Latency Note)
Importance
Abstract
A system and method for finding an .epsilon.-approximate .phi.-quantile data element of a data set with N data elements in a single pass over the data set. The .epsilon.-approximate .phi.-quantile data element is guaranteed to lie within a user-specified approximation error .epsilon. of a true .phi.-quantile data element being sought. B buffers, each having a capacity of k elements, initially are filled with sorted data elements from the data set, with the values of b and k depending on .epsilon. and N. The buffers are then collapsed into an output buffer, with the remaining buffers then being refilled with data elements, collapsed (along with the previous output buffer), and so on until the entire data set has been processed and a single output buffer remains. A data element of the output buffer corresponding to the .epsilon.-approximate .phi.-quantile is then output as the approximate .phi.-quantile data element. If desired, the system and method can be practiced with sampling to even further reduce the amount of space required to find a desired .epsilon.-approximate .phi.-quantile data element.
First Claim
Family
International Classification(s)
Cited Art Landscape
Patent Citation Ranking
Advertisement
Advertisement
Advertisement
Recipient Email Address
Recipient Email Address
Comment
Recipient Email Address
Add to Portfolio(s)
To add this patent to one, or more, of your portfolios, simply click the add button.
This Patent is in these Portfolios:
Add to additional portfolios:
Last Refreshed On:
Changes done successfully