CoTS: A Scalable Framework for Parallelizing Frequency Counting over Data Streams

TitleCoTS: A Scalable Framework for Parallelizing Frequency Counting over Data Streams
Publication TypeConference Paper
Year of Publication2009
AuthorsDas, S, Antony S, Agrawal D, El Abbadi A
Conference NameICDE
Pagination1323-1326
PublisherIEEE
KeywordsScale
Abstract

Frequency counting, frequent elements and top-k queries form a class of operators that are used for a wide range of stream analysis applications. In spite of the abundance of these algorithms, all known techniques for answering data stream queries are sequential in nature. The imminent ubiquity of Chip Multi-Processor (CMP) architectures requires algorithms that can exploit the parallelism of such architectures. In this paper, we first evaluate different naive techniques for intra-operator parallelism, and summarize the insights obtained from the naive techniques. Our experimental analysis of the naive designs shows that intra-operator parallelism is not straightforward and requires a complete redesign of the system. We then propose an efficient and scalable framework for parallelizing frequency counting, frequent elements and top-k queries over data streams. The proposed CoTS (Co-operative Thread Scheduling) framework is based on the principle of threads co-operating rather than contending. Our experiments on a state-of-the-art quad-core chip-multiprocessor architecture and synthetic data sets demonstrate the scalability of the proposed framework, and the efficiency is demonstrated by peak processing throughput of more than $60$ million elements per second.

URLhttp://www.cs.ucsb.edu/~sudipto/papers/ICDEResearchShort-Das-CoTS.pdf
DOIhttp://dx.doi.org/10.1109/ICDE.2009.231
Refereed DesignationRefereed