<?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:33:12Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1147" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1147</identifier><datestamp>2017-03-21T19:03:12Z</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="author" lang="en" authority="054e5072-c4ee-47b9-b223-8d8eb089ec67" confidence="600">Mirzazadeh, Mehdi</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:28:29Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:28:29Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2004</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1147</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In this thesis we study a problem that arises in answering boolean queries submitted to a search engine.   Usually a search engine stores the set of IDs of documents containing each word in a pre-computed sorted order and to evaluate a query like &amp;quot;computer AND science&amp;quot; the search engine has to evaluate the union of the sets of documents containing the words &amp;quot;computer&amp;quot; and &amp;quot;science&amp;quot;.   More complex queries will result in more complex set expressions.   In this thesis  we consider the problem of evaluation of a set expression with union and intersection as operators and ordered sets as operands.       We explore properties of comparison-based algorithms for the  problem.   A &amp;lt;i&amp;gt;proof of a set expression&amp;lt;/i&amp;gt; is the set of comparisons that a comparison-based algorithm performs before it can determine the result of the expression.   We discuss the properties of the proofs of set expressions and based on how complex the smallest proofs of a set expression &amp;lt;i&amp;gt;E&amp;lt;/i&amp;gt; are, we define a measurement for determining how difficult it is for &amp;lt;i&amp;gt;E&amp;lt;/i&amp;gt; to be computed.   Then, we design an algorithm that is adaptive to the difficulty of the input  expression and we show that the running time of the algorithm is roughly proportional to difficulty of the input expression, where the factor is roughly logarithmic in the number of the operands of the input expression.</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">2370685 bytes</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</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="rights" lang="en">Copyright: 2004, 
  Mirzazadeh, Mehdi. All rights reserved.</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Adaptive algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">comparison-based algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">search engines</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">algorithms</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Adaptive Comparison-Based Algorithms for Evaluating Set Queries</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</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>