2026-08-04T17:37:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17747 2024-03-06T11:00:23Z ddc:004 open_access

An Optimal Algorithm for Sliding Window Order Statistics Raykov, Pavel sliding window order statistics median selection algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pavel Raykov 2023 Is Part Of LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2023.5 urn:nbn:de:0030-drops-177479 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.5 eng https://creativecommons.org/licenses/by/4.0/legalcode