Communication Efficient Data Analysis Systems

Abstract

Nowadays Cloud service providers like Google and Microsoft deploy distributed systems in their data centers(DCs) and also deploy geo-distributed DCs to serve their users. With the data scale growth, the query latency among all the distributed machines become more and more unacceptable. Thus a scheduler which reduces the latency is urgently needed. In this thesis, we present two novel communication efficient data analytics systems.

• C2Net: C2Net is a network-efficient solution focuses on collision counting LSH-based similarity join in MapReduce. The solution uses two graph partitioning schemes: (i) minimum spanning tree for organizing LSH buckets replication; and (ii) spectral clustering for runtime collision counting task scheduling.

• Bohr: Bohr is a similarity aware geo-distributed data analytics system that minimizes query completion time. The key idea is to exploit similarity between data in different data centers (DCs), and transfer similar data from the bottleneck DC to other sites with more WAN bandwidth. Though these sites have more input data to process, these data are more similar and can be more efficiently aggregated by the combiner to reduce the intermediate data that needs to be shuffled across the WAN. Thus our similarity aware approach reduces the shuffle time and in turn the query completion time (QCT).We design Bohr based on OLAP data cubes to perform efficient similarity checking among datasets in different sites.

We implemented and test both C2Net and Bohr with real datasets. The results show that both framework can processing the query more efficient compare to the state-of-the-art work.

Date of Award	22 May 2019
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Hong XU (Supervisor) & Sarana NUTANONG (Supervisor)