Interval Joins: Evaluation, Parallelization, Aggregation
Event details
| Date | 26.11.2018 |
| Hour | 14:00 › 15:00 |
| Speaker | Nikos Mamoulis joined the University of Ioannina in 2014. Before that he was a Professor of Computer Science at the University of Hong Kong. His main research interest is the management, search and analysis of complex data types with a focus on spatially enriched data. He served as PC co-chair of SSTD 2009, COMAD 2013, and HDMS 2014 and as a general chair of SSDBM 2008. He has been an Associate Editor of the VLDB Journal, IEEE Transactions on Knowledge and Data Engineering, Knowledge and Information Systems, and an Editorial Board Member of Geoinformatica Journal. |
| Location | |
| Category | Conferences - Seminars |
Abstract:
The interval join is a basic operation that finds application in temporal, spatial, and uncertain databases. In this talk, I will present our recent research findings on the evaluation of interval joins. In our work, we explore the applicability of a largely ignored forward scan (FS) based plane sweep algorithm, which is extremely simple to implement. We propose two optimizations of FS that greatly reduce its cost, making it competitive to the state-of-the-art single-threaded interval join algorithm while achieving a lower memory footprint. In addition, for the parallel processing of interval joins, we study a domain-based partitioning approach that does not produce duplicate results. Within our approach we propose a novel breakdown of the partition-level join into a small number of independent mini-join jobs with varying cost and manage to avoid redundant comparisons. We show how these mini-joins can be scheduled in multiple CPU cores and suggest an adaptive domain partitioning, aiming at load balancing. Finally, we study the evaluation of a temporal aggregation operation, which can be used for selecting or ranking intervals based on the number of join pairs they appear in. For this problem, we present an algorithm that generates the result at the cost of only scanning the sorted interval endpoints.
The interval join is a basic operation that finds application in temporal, spatial, and uncertain databases. In this talk, I will present our recent research findings on the evaluation of interval joins. In our work, we explore the applicability of a largely ignored forward scan (FS) based plane sweep algorithm, which is extremely simple to implement. We propose two optimizations of FS that greatly reduce its cost, making it competitive to the state-of-the-art single-threaded interval join algorithm while achieving a lower memory footprint. In addition, for the parallel processing of interval joins, we study a domain-based partitioning approach that does not produce duplicate results. Within our approach we propose a novel breakdown of the partition-level join into a small number of independent mini-join jobs with varying cost and manage to avoid redundant comparisons. We show how these mini-joins can be scheduled in multiple CPU cores and suggest an adaptive domain partitioning, aiming at load balancing. Finally, we study the evaluation of a temporal aggregation operation, which can be used for selecting or ranking intervals based on the number of join pairs they appear in. For this problem, we present an algorithm that generates the result at the cost of only scanning the sorted interval endpoints.
Practical information
- General public
- Free
- This event is internal
Organizer
- Prof. Anastasia Ailamaki
Contact
- Dimitra Tsaoussis-Melissargos