Abstract
We study streaming algorithms for partitioning integer sequences and trees. In the case of trees, we suppose that the input tree is provided by a stream consisting of a depthfirsttraversal of the input tree. This captures the problem of partitioning XML streams, among other problems.
We show that both problems admit deterministic (1+epsilon)approximation streaming algorithms, where a single pass is sufficient for integer sequences and two passes are required for trees. The space complexity for partitioning integer sequences is O((1/epsilon) * p * log(nm)) and for partitioning trees is O((1/epsilon) * p^2 * log(nm)), where n is the length of the input stream, m is the maximal weight of an element in the stream, and p is the number of partitions to be created.
Furthermore, for the problem of partitioning integer sequences, we show that computing an optimal solution in one pass requires Omega(n) space, and computing a (1+epsilon)approximation in one pass requires Omega((1/epsilon) * log(n)) space, rendering our algorithm tight for instances with p,m in O(1).
BibTeX  Entry
@InProceedings{konrad:LIPIcs:2016:5782,
author = {Christian Konrad},
title = {{Streaming Partitioning of Sequences and Trees}},
booktitle = {19th International Conference on Database Theory (ICDT 2016)},
pages = {13:113:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770026},
ISSN = {18688969},
year = {2016},
volume = {48},
editor = {Wim Martens and Thomas Zeume},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5782},
URN = {urn:nbn:de:0030drops57829},
doi = {10.4230/LIPIcs.ICDT.2016.13},
annote = {Keywords: Streaming Algorithms, XML Documents, Data Partitioning, Communication Complexity}
}
Keywords: 

Streaming Algorithms, XML Documents, Data Partitioning, Communication Complexity 
Seminar: 

19th International Conference on Database Theory (ICDT 2016) 
Issue Date: 

2016 
Date of publication: 

29.02.2016 