Deterministic k-set structure

摘要

A k-set structure over data streams is a bounded-space data structure that supports stream insertion and deletion operations and returns the set of (item, frequency) pairs in the stream, provided, the number of distinct items in the stream does not exceed k; and returns nil otherwise. This is a fundamental problem with applications in data streaming [14], data reconciliation in distributed systems [12] and mobile computing [16], etc. In this paper, we present a deterministic algorithm for the k-set problem that matches the space lower bound to within a logarithmic factor.