<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:11.0pt;
font-family:"Aptos",sans-serif;
mso-ligatures:standardcontextual;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#467886;
text-decoration:underline;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:11.0pt;
mso-ligatures:none;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="#467886" vlink="#96607D" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span style="color:#212121">This is an announcement of Gabriel Mersy's MS Presentation<br>
===============================================<br>
Candidate: Gabriel Mersy<br>
<br>
Date: Monday, April 29, 2024<br>
<br>
Time: 10:30 am CT<br>
<br>
Location: JCL 298<br>
<br>
Title: Optimizing Collections of Bloom Filters within a Space Budget<br>
<br>
Abstract: With a single Bloom filter, one can approximately answer set membership queries within a space budget. Practical systems often use collections of Bloom filters to facilitate applications such as data skipping, sideways information passing, and network
filtering. While the optimal space-to-accuracy allocation is well-understood for a single filter, jointly optimizing how space is used across a collection of filters is yet to be studied. We pose this problem in the following way: (1) let's assume that each
Bloom filter has some likelihood of being queried, and (2) given knowledge of this likelihood, how do we allocate space to minimize the expected false positive rate? In other words, “hot” filters are allocated more space, and “cold” filters are allocated less
space. In this paper, we show how to solve this optimization problem. We first develop the concept of a “truncated” Bloom filter and theoretically analyze its false positive rate. We then formulate an optimization problem for a collection of truncated Bloom
filters that minimizes the false positive rate across a utility distribution while meeting a strict space budget. Next, we show that the problem is convex and find a fast relaxation. Lastly, we apply our method to data skipping and full-text search, demonstrating
its effectiveness across the range of possible space budgets when compared to the state of the art.<br>
<br>
Advisors: Sanjay Krishnan<br>
<br>
Committee Members: Aaron Elmore, Sanjay Krishnan, and Raul Castro Fernandez<br>
<br>
_______________________________________________<br>
Colloquium mailing list - <span class="apple-converted-space"> </span></span><a href="mailto:Colloquium@mailman.cs.uchicago.edu" title="mailto:Colloquium@mailman.cs.uchicago.edu"><span style="color:#0078D7">Colloquium@mailman.cs.uchicago.edu</span></a><span style="color:#212121"><br>
</span><a href="https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium" title="https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium"><span style="color:#0078D7">https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium</span></a><span style="color:#212121"><br>
_______________________________________________<br>
staff mailing list - <span class="apple-converted-space"> </span></span><a href="mailto:staff@mailman.cs.uchicago.edu" title="mailto:staff@mailman.cs.uchicago.edu"><span style="color:#0078D7">staff@mailman.cs.uchicago.edu</span></a><span style="color:#212121"><br>
</span><a href="https://mailman.cs.uchicago.edu/mailman/listinfo/staff" title="https://mailman.cs.uchicago.edu/mailman/listinfo/staff"><span style="color:#0078D7">https://mailman.cs.uchicago.edu/mailman/listinfo/staff</span></a></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>