Single-pass low-storage arbitrary probabilistic location...

Details Single-pass low-storage arbitrary probabilistic location... Single-pass low-storage arbitrary probabilistic location...

2006-07-11

2006-07-11

Wassum, Luke S (Department: 2167)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

07076487

ABSTRACT:
The present invention includes a method and system for providing an estimate of a summary of a data set generated by an unknown distribution. The method includes selecting a subset of data points from the data set, applying a scoring rule to each data point of the subset of data points based on an estimated relative location and an assigned weight for each data point to provide a score for each data point, selectively retaining data points to track based on the score for each data point; and determining an estimate of the summary of the data set based on the retained data points.

REFERENCES:
patent: 5664171 (1997-09-01), Agrawal et al.
patent: 5809499 (1998-09-01), Wong et al.
patent: 5864841 (1999-01-01), Agrawal et al.
patent: 6108658 (2000-08-01), Lindsay et al.
patent: 6343288 (2002-01-01), Lindsay et al.
patent: 6363371 (2002-03-01), Chaudhuri et al.
Tierney, L. “A Space-Efficient Recursive Procedure for Estimating a Quantile of an Unknown Distribution”, SIAM Journal on Scientific and Statistical Computing, vol. 4, No. 4, Dec. 1983, pp. 706-711.
Jain, R. and Chlamtac, I. “The P2 Algorithm for Dynamic Calculation of Quantiles and Histograms Without Storing Observations”, Communications of the ACM, vol. 28, No. 10, Oct. 1985, pp. 1076-1085.
Agrawal, R. and Swami, A. “A One-Pass Space-Efficient Algorithm for Finding Quantiles”, Proceedings of the 7thInternational Conference on Management of Data (COMAD), 1995.
Hurley, C. and R. Modarres “Low-Storage Quantile Estimation”, Computational Statistics, vol. 10, No. 4, 1995, pp. 311-325.
Alsabti, K., S. Ranka and V. Singh “A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data”, Proceedings of the 23rdVLDB Conference, 1997, pp. 346-355.
Manku, G.S., S. Rajagopalan and B.G. Lindsay “Approximate Medians and other Quantiles in One Pass and with Limited Memory”, Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, Jun. 1998, pp. 426-435.
Manku, G.S., S. Rajagopalan and B.G. Lindsay “Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets”, Proc. of the 1999 ACM SIGMOD International Conference on Management of Data, Jun. 1999, pp. 251-262.
Greenwald, M. and S. Khanna “Space-Efficient Online Computatuon of Quantile Summaries”, Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, May 2001, pp. 58-66.
Gilbert, A.C., Y. Kotidis, S. Muthukrishnan and M.J. Strauss “How to Summarize the Universe: Dynamic Maintenance of Quantiles”, Proceedings of the 28thVLDB Conference, Aug. 2002, pp. 454-465.
Liechty, J.C., D.K.J. Lin and J.P. McDermott “Single-Pass Low-Storage Arbitrary Quantile Estimation for Massive Datasets”, Statistics and Computing, vol. 13, No. 2, 2003, pp. 91-100.
Babu, G.J. and J.P. McDermott “Statistical Methodology for Massive Datasets and Model Selection”, In Astronomical Data Analysis II, J-L Starck and F.D. Murtagh (Eds. ), Proceedings of SPIE, vol. 4847 (2002), pp. 228-237.
Merriam-Webster Online “Definition of ‘subset’”, downloaded from www.m-w.com, Apr. 26, 2005.
Oxford University Press “Definition of ‘subset’”, downloaded from www.askoxford.com, Apr. 26, 2005.
InfoPlease “Definition of ‘subset’”, downloaded from www.infoplease.com, Apr. 26, 2005.
Ultralingua “Definition of ‘subset’”, downloaded from www.ultralingua.net, Apr. 26, 2005.
Mathematical Concepts, Inc. “Definition of ‘subset’”, downloaded from mathnstuff.com, Apr. 26, 2005.
MathWorld “Definition of ‘subset’”, downloaded from mathworld.wolfram.com Apr. 26, 2005.
MathWorld “Definition of ‘proper subset’”, downloaded from mathworld.wolfram.com, Apr. 26, 2005.
“Sequential Estimation of Quantiles”, Technical Report TR-COSC May 1998.
“Incremental Quantile Estimation for Massive Tracking” 2000 Proceedings of the Sixth International Conference in Knowledge Discovery and Data Mining.

Affiliated with

Also associated with

Rating

Single-pass low-storage arbitrary probabilistic location... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Single-pass low-storage arbitrary probabilistic location..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single-pass low-storage arbitrary probabilistic location... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3550739