In-Memory Interval Joins

Publikationstyp:
Zeitschriftenaufsatz
Metadaten:
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

Datenquelle: Web of Science (Lite)

Andere Metadatenquellen:
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

Datenquelle: 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

Datenquelle: OPENSCIENCE.UB

Beziehungen:
Eigentum von

Werkzeuge