Optimizing queue-based semi-stream joins with indexed master data

M. Asif Naeem, Gerald Weber, Christof Lutteroth, Gillian Dobbie

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

5 Citations (SciVal)


In Data Stream Management Systems (DSMS) semi-stream processing has become a popular area of research due to the high demand of applications for up-to-date information (e.g. in real-time data warehousing). A common operation in stream processing is joining an incoming stream with disk-based master data, also known as semi-stream join. This join typically works under the constraint of limited main memory, which is generally not large enough to hold the whole disk-based master data. Many semi-stream joins use a queue of stream tuples to amortize the disk access to the master data, and use an index to allow directed access to master data, avoiding the loading of unnecessary master data. In such a situation the question arises which master data partitions should be accessed, as any stream tuple from the queue could serve as a lookup element for accessing the master data index. Existing algorithms use simple safe and correct strategies, but are not optimal in the sense that they maximize the join service rate. In this paper we analyze strategies for selecting an appropriate lookup element, particularly for skewed stream data. We show that a good selection strategy can improve the performance of a semi-stream join significantly, both for synthetic and real data sets with known skewed distributions.
Original languageEnglish
Title of host publicationData Warehousing and Knowledge Discovery
Subtitle of host publicationProceedings of the 16th International Conference, DaWaK 2014, Munich, Germany, September 2-4, 2014
EditorsL. Bellatreche, M. K. Mohania
PublisherSpringer India
Number of pages12
ISBN (Print)9783319101590
Publication statusPublished - 2014

Publication series

NameLecture Notes in Computer Science


Dive into the research topics of 'Optimizing queue-based semi-stream joins with indexed master data'. Together they form a unique fingerprint.

Cite this