Random sampling techniques for space efficient online computation of order statistics of large datasets
Published 1 June 1999
Gurmeet Singh Manku, Sridhar Rajagopalan, Bruce G. Lindsay
Citations90
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A novel non-uniform random sampling scheme and an extension of this framework are presented which form the basis of a new algorithm which computes approximate quantiles without knowing the input sequence length.
Abstract
In a recent paper [MRL98], we had described a general framework for single pass approximate quantile finding algorithms. This framework included several known algorithms as special cases. We had identified a new algorithm, within the framework, which had a significantly smaller requirement for main memory than other known algorithms. In this paper, we address two issues left open in our earlier paper.
Keywords
Computer Science
Springer series in statisticsProbability Inequalities for sums of Bounded Random Variables
6,947 Citations1994Wassily Hoeffding
Access path selection in a relational database management system
2,153 Citations1979Patricia G. Selinger, M. M. Astrahan +3 more
This paper describes how System R chooses access paths for both simple (single relation) and complex queries (such as joins) given a user specification of desired data as a boolean expression of predicates.
ACM Transactions on Mathematical SoftwareRandom sampling with a reservoir
1,759 Citations1985Jeffrey Scott Vitter
Theoretical and empirical results indicate that Algorithm Z outperforms current methods by a significant margin, and an efficient Pascal-like implementation is given that incorporates these modifications and that is suitable for general use.
Journal of Computer and System SciencesTime bounds for selection
1,249 Citations1973Manuel Blum, Robert W. Floyd +3 more
The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm-PICK.
Journal of the American Statistical AssociationProbability Inequalities for Sums of Bounded Random Variables
1,127 Citations1963Wassily Hoeffding
Improved histograms for selectivity estimation of range predicates
557 Citations1996Viswanath Poosala, Peter J. Haas +2 more
A taxonomy of histograms that captures all previously proposed histogram types and indicates many new possibilities is provided, which introduces novel choices for several of the taxonomy dimensions, and derive new histograms types by combining choices in effective ways.
New sampling-based summary statistics for improving approximate query answers
454 Citations1998Phillip B. Gibbons, Yossi Matias
This paper introduces two new sampling-based summary statistics, concise samples and counting samples, and presents new techniques for their fast incremental maintenance regardless of the data distribution, and considers their application to providing fast approximate answers to hot list queries.
Theoretical Computer ScienceSelection and sorting with limited storage
426 Citations1980J. Ian Munro, Mike Paterson
Random sampling for histogram construction
236 Citations1998Surajit Chaudhuri, Rajeev Motwani +1 more
A conservative error metric is introduced capturing the intuition that for an approximate histogram to have low error, the error must be small in all regions of the histogram and an optimal bound on the amount of sampling required for pre-specified error bounds is presented.
ACM SIGMOD RecordApproximate medians and other quantiles in one pass and with limited memory
81 Citations1998Gurmeet Singh Manku, Sridhar Rajagopalan +1 more
A One-Pass Space-Efficient Algorithm for Finding Quantiles.
48 Citations1995Rakesh Agrawal, Arun Swami
An algorithm fording the quantile values of a large unordered dataset with unknown distribution that requires only one pass over the data and the true quantile is guaranteed to lie within the lower and upper bounds produced by the algorithm.