To search, Click below search items.


All Published Papers Search Service


A Reversible Sketch Based on Chinese Remainder Theorem: Scheme and Performance Study


B.S. Adiga, Ravishankara Shastry, M. Girish Chandra, M.A. Rajan


Vol. 11  No. 8  pp. 59-65


In recent times, sketch based techniques are emerging as useful data stream computation techniques towards processing massive data. In many applications, finding heavy hitters and heavy changers is essential and this task demands reversibility property of sketches. Continuing the trend of arriving at newer reversible sketch, this paper presents a scheme based on Chinese Remainder Theorem. The scheme also involves the usage of two sketches based on two different prime-number sets for reducing the false positives. An attempt is made to present the technique on sound arguments by bringing in the relevant concepts from the existing literature. Simulation results, including how the data distribution affects the performance of the scheme, are presented as well.


Data streams, sketch, heavy hitters, reversible sketch, Chinese remainder theorem, Zipfian data distribution