2026-08-25T15:33:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27178 2026-08-25T13:18:16Z ddc:004 open_access

Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams Ta, Hoang Vu, Hoa T. Decision trees Streaming algorithms Lower bounds We establish nearly optimal upper and lower bounds for approximating decision tree splits in data streams. For regression with labels in the range {0,1,…,M}, we give a one-pass algorithm using 𝒪̃(M²/ε) space that outputs a split within additive ε error of the optimal split, improving upon the two-pass algorithm of Pham et al. (ISIT 2025). Furthermore, we provide a matching one-pass lower bound showing that Ω(M²/ε) space is indeed necessary. For classification, we also obtain a one-pass algorithm using 𝒪̃(1/ε) space for approximating the optimal Gini split, improving upon the previous 𝒪̃(1/ε²)-space algorithm. We complement these results with matching space lower bounds: Ω(1/ε) for Gini impurity and Ω(1/ε) for misclassification (which matches the upper bound obtained by sampling). Our algorithms exploit the Lipschitz property of the loss functions and use reservoir sampling along with Count-Min sketches with range queries. Our lower bounds follow from careful reductions from the Index problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hoang Ta and Hoa T. Vu 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.42 urn:nbn:de:0030-drops-271785 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.42 eng https://creativecommons.org/licenses/by/4.0/legalcode