Differencing Data Streams.
Sudarshan S. Chawathe.
In Proceedings of the International Database Engineering and
Applications Symposium (IDEAS), pages 273-284, Montreal, Canada,
July 2005.
Paper;
Citation.
We present external-memory algorithms for differencing large hierarchical datasets. Our methods are especially suited to streaming data with bounded differences. For input sizes m and n and maximum output (difference) size e, the I/O, RAM, and CPU costs of our algorithm rdiff are, respectively, m+n, 4e+8, and O(MN). That is, given 4e+8 blocks of RAM, our algorithm performs no I/O operations other than those required to read both inputs. We also present a variant of the algorithm that uses only four blocks of RAM, with I/O cost 8me + 18m + n + 6e + 5 and CPU cost O(MN).