Publisher Summary This chapter presents a new algorithm for dynamically computing
quantiles of a relation subject to insert as well as delete operations. Order statistics
(quantiles) are frequently used in databases at both the database server as well as the
application level. For example, they are useful in selectivity estimation during query
optimization, in partitioning large relations, in estimating query result sizes when building
user interfaces, and in characterizing the data distribution of evolving datasets in the process …