<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T18:11:03Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/15938" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/15938</identifier><datestamp>2025-03-26T23:33:36Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Daudjee, Khuzaima</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="0134f22f-47d4-4aa2-8bc6-e0c68eb2d4cb" confidence="600">Farhat, Omar</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2020-05-28T16:30:44Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2020-09-26T04:50:05Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2020-05-28</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2020-05-20</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/15938</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Modern stream processing engines (SPEs) process large volumes of events propagated at high velocity through multiple queries. By continuously receiving watermarks, which are marker events injected into the stream to signify that no further events are expected beyond a designated timestamp, SPEs can infer stream progress to correctly process window operators. While stream progress is useful information for query execution, it is only utilized to ensure input completion. We argue that to improve performance, stream progress should be leveraged in the design of SPE subsystems. In this thesis, we demonstrate the significant advantages of leveraging stream progress to solve two important SPE problems: query scheduling, and query sample processing.&#xd;
&#xd;
First, existing SPE schedulers generally aim to minimize query output latency by minimizing, in turn, the mean propagation delay of events in query pipelines. However, for queries containing commonly used blocking operators such as windows, we show that a superior approach would be to prioritize the queries based on stream progress. Through the design and development of Klink, we leverage stream progress to unblock window operators and to rapidly propagate the events to output operators. &#xd;
Secondly, sample query processing limits input to only a subset of events such that the sample is statistically representative of the input while ensuring output accuracy guarantees. However, output latency can be significantly increased because relevant watermarks can suffer from large ingestion delay due to long or bursty network latencies. Window computations that account for stragglers can add significant latency while providing inconsequential accuracy improvement. We propose Aion, an algorithm that utilizes sampling to provide approximate answers with low latency by minimizing the effect of stragglers through leveraging control over stream progress.&#xd;
&#xd;
We integrate Klink and Aion into the popular open-source SPE Apache Flink. We demonstrate that Klink delivers hefty performance gains on benchmark workloads, reducing mean and tail query latencies by up to 60% over existing scheduling policies. Similarly, using different benchmark workloads, we demonstrate that Aion reduces stream output latency by up to 85% while providing 95% accuracy guarantees.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Streaming Systems</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Out-of-order</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Punctuations</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Watermarks</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">scheduling</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Sample Processing</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">sampling</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">approximate query processing</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Leveraging Watermarks to Improve Performance of Streaming Systems</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws-etd" element="embargo" qualifier="terms" lang="en">4 months</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Daudjee, Khuzaima</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>