Deterministic K-set structure

A k-set structure is a sub-linear space data structure that supports multi-set insertion and deletion operations and returns the multi-set, provided the number of distinct items with non-zero frequency does not exceed k. This is a fundamental problem with applications in data streaming [S. Muthukrishnan, Data streams: Algorithms and applications, Foundations and Trends in Theoretical Computer Science 1 (2) (2005)], distributed systems [Y. Minsky, A. Trachtenberg, R. Zippel, Set Reconciliation with Nearly Optimal Communication Complexity, IEEE Trans. Inform. Theory 49 (9) (2003) 2213–2218; D. Starobinski, A. Trachtenberg, S. Agarwal, Efficient PDA synchronization, IEEE Trans. on Mob. Comp. 2 (1) (2003) 40–51], etc. In this paper, we present the design of a deterministic k-set structure.