Paper Info
Title
Deterministic K-set structure
Abstract
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.
Year
DOI
Venue
2008
10.1016/j.ipl.2008.08.010
Symposium on Principles of Database Systems
Keywords
Field
DocType
deterministic k-set structure,s. muthukrishnan,s. agarwal,optimal communication complexity,efficient pda synchronization,sub-linear space data structure,multi-set insertion,ieee trans,data stream,k-set structure,data structure,information theory,linear space,distributed system,communication complexity
Discrete mathematics,Data structure,Synchronization,Data stream mining,Information processing,Linear space,Communication complexity,Linear complex structure,K-set,Mathematics
Journal
Volume
Issue
ISSN
109
1
0020-0190
ISBN
Citations 
PageRank 
1-59593-318-2
10
0.57
References 
Authors
22
2
Name
Order
Citations
PageRank
Sumit Ganguly1813236.01
Anirban Majumder21579.14