Bilkent University
Department of Computer Engineering
Ph.D Dissertation
Utilizing Query Logs For Data Replication and Placement in Big Data Applications
Ata Türk
PhD Student
Computer Engineering Department
Bilkent University
The growth in the amount of data in today's computing problems and the level of parallelism dictated by the large-scale computing economics necessitates high- level parallelism for many applications. This parallelism is generally achieved via data-parallel solutions that require effective data clustering (partitioning) or declustering schemes (depending on the application requirements). In addition to data partitioning/declustering, data replication, which is used for data avail- ability and increased performance, has also become an inherent feature of many applications. The data partitioning/declustering and data replication problems are generally addressed separately. This thesis is centered around the idea of performing data replication and data partitioning/declustering simultaneously to obtain replicated data distributions that yield better parallelism. To this end, we utilize query-logs to propose replicated data distribution solutions and ex- tend the well known Fiduccia-Mattheyses (FM) iterative improvement algorithm so that it can be used to generate replicated partitioning/declustering of data.
For the replicated declustering problem, we propose a novel replicated declus- tering scheme that utilizes query logs to improve the performance of a parallel database system. We also extend our replicated declustering scheme and pro- pose a novel replicated re-declustering scheme such that in the face of drastic query pattern changes or server additions/removals from the parallel database system, new declustering solutions that require low migration overheads can be computed. For the replicated partitioning problem, we show how to utilize an e?ective single-phase replicated partitioning solution in two well-known applications (keyword-based search and Twitter). For these applications, we provide the algorithmic solutions we had to devise for solving the problems that replication brings, the engineering decisions we made so as to obtain the greatest benefits from the proposed data distribution, and the implementation details for realistic systems.
Obtained results indicate that utilizing query-logs and performing replication and partitioning/declustering in a single phase improves parallel performance.
DATE: 03 September, 2012, Monday @ 17:00
PLACE: EA409