In-Memory Interval Joins
- Publication type:
- Journal article
- Metadata:
-
- Autoren
- Panagiotis Bouros
- Nikos Mamoulis
- Dimitrios Tsitsigkos
- Manolis Terrovitis
- Autoren-URL
- https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000639979800001&DestLinkType=FullRecord&DestApp=WOS_CPL
- DOI
- 10.1007/s00778-020-00639-0
- eISSN
- 0949-877X
- Externe Identifier
- Clarivate Analytics Document Solution ID: TB8WW
- ISSN
- 1066-8888
- Ausgabe der Veröffentlichung
- 4
- Zeitschrift
- VLDB JOURNAL
- Schlüsselwörter
- Interval data
- Join
- Query processing
- Plane sweep
- Parallel processing
- Main memory
- Paginierung
- 667 - 691
- Datum der Veröffentlichung
- 2021
- Status
- Published
- Titel
- In-Memory Interval Joins
- Sub types
- Article
- Ausgabe der Zeitschrift
- 30
Data source: Web of Science (Lite)
- Other metadata sources:
-
- Abstract
- <jats:title>Abstract</jats:title><jats:p>The interval join is a popular operation in temporal, spatial, and uncertain databases. The majority of interval join algorithms assume that input data reside on disk and so, their focus is to minimize the I/O accesses. Recently, an in-memory approach based on plane sweep (PS) for modern hardware was proposed which greatly outperforms previous work. However, this approach relies on a complex data structure and its parallelization has not been adequately studied. In this article, we investigate in-memory interval joins in two directions. First, we explore the applicability of a largely ignored forward scan (FS)-based plane sweep algorithm, for single-threaded join evaluation. We propose four optimizations for FS that greatly reduce its cost, making it competitive or even faster than the state-of-the-art. Second, we study in depth the parallel computation of interval joins. We design a non-partitioning-based approach that determines independent tasks of the join algorithm to run in parallel. Then, we address the drawbacks of the previously proposed hash-based partitioning and suggest a domain-based partitioning approach that does not produce duplicate results. Within our approach, we propose a novel breakdown of the partition-joins into mini-joins to be scheduled in the available CPU threads and propose an adaptive domain partitioning, aiming at load balancing. We also investigate how the partitioning phase can benefit from modern parallel hardware. Our thorough experimental analysis demonstrates the advantage of our novel partitioning-based approach for parallel computation.</jats:p>
- Autoren
- Panagiotis Bouros
- Nikos Mamoulis
- Dimitrios Tsitsigkos
- Manolis Terrovitis
- DOI
- 10.1007/s00778-020-00639-0
- eISSN
- 0949-877X
- ISSN
- 1066-8888
- Ausgabe der Veröffentlichung
- 4
- Zeitschrift
- The VLDB Journal
- Sprache
- en
- Online publication date
- 2021
- Paginierung
- 667 - 691
- Datum der Veröffentlichung
- 2021
- Status
- Published
- Herausgeber
- Springer Science and Business Media LLC
- Herausgeber URL
- http://dx.doi.org/10.1007/s00778-020-00639-0
- Datum der Datenerfassung
- 2021
- Titel
- In-Memory Interval Joins
- Ausgabe der Zeitschrift
- 30
Data source: Crossref
- Author's licence
- CC-BY
- Autoren
- Panagiotis Bouros
- Nikos Mamoulis
- Dimitrios Tsitsigkos
- Manolis Terrovitis
- Hosting institution
- Universitätsbibliothek Mainz
- Sammlungen
- JGU-Publikationen
- Resource version
- Published version
- DOI
- 10.1007/s00778-020-00639-0
- File(s) embargoed
- false
- Open access
- true
- ISSN
- 0949-877X
- Zeitschrift
- The VLDB Journal
- Schlüsselwörter
- 004 Informatik
- 004 Data processing
- Sprache
- eng
- Open access status
- Open Access
- Paginierung
- 667 - 691
- Datum der Veröffentlichung
- 2021
- Public URL
- https://openscience.ub.uni-mainz.de/handle/20.500.12030/7301
- Herausgeber
- Springer
- Datum der Datenerfassung
- 2022
- Datum, an dem der Datensatz öffentlich gemacht wurde
- 2022
- Zugang
- Public
- Titel
- In-Memory Interval Joins
- Ausgabe der Zeitschrift
- 30
Files
inmemory_interval_joins-20220701133214926.pdf
Data source: OPENSCIENCE.UB
- Beziehungen:
- Property of