Estimated quantiles and/or percentiles for streaming data are computed over a sliding window. An exemplary method comprises obtaining a stream of data values; obtaining a summary of a distribution of previously processed data values; adding streamed data values to a buffer; and when the buffer reaches a predefined fullness threshold, performing the following steps: processing tuples in the summary to apply a decay function to each tuple using the number of items in the stream in the stream at the time the tuple is created and a minimal rank bound; for each item in the buffer, creating a tuple; adding the tuple to the summary, and removing the item from the buffer; and building a search tree that is used to process one or more of percentile queries and quantile queries. The summary is optionally compressed by merging consecutive tuples that satisfy a predefined invariant constraint. The decay function maintains, for example, one or more of a predefined recent number of items or a predefined recent time window of items in the summary.