DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2023.5

An Optimal Algorithm for Sliding Window Order Statistics

Authors: Pavel Raykov

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract

Assume there is a data stream of elements and a window of size m. Sliding window algorithms compute various statistic functions over the last m elements of the data stream seen so far. The time complexity of a sliding window algorithm is measured as the time required to output an updated statistic function value every time a new element is read. For example, it is well known that computing the sliding window maximum/minimum has time complexity O(1) while computing the sliding window median has time complexity O(log m). In this paper we close the gap between these two cases by (1) presenting an algorithm for computing the sliding window k-th smallest element in O(log k) time and (2) prove that this time complexity is optimal.

Cite as

Pavel Raykov. An Optimal Algorithm for Sliding Window Order Statistics. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{raykov:LIPIcs.ICDT.2023.5,
  author =	{Raykov, Pavel},
  title =	{{An Optimal Algorithm for Sliding Window Order Statistics}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.5},
  URN =		{urn:nbn:de:0030-drops-177479},
  doi =		{10.4230/LIPIcs.ICDT.2023.5},
  annote =	{Keywords: sliding window, order statistics, median, selection algorithms}
}

Search Results

Documents authored by Raykov, Pavel

An Optimal Algorithm for Sliding Window Order Statistics

Abstract

Cite as

Thanks for your feedback!

Could not send message