<?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-22T12:10:28Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/6883" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/6883</identifier><datestamp>2017-03-21T20:10:57Z</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" authority="c0581259-61da-4f1e-b106-ae605f9f5479" confidence="600">Zhou, Gelin</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2012-08-24T19:54:16Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2012-08-24T19:54:16Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2012-08-24T19:54:16Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2012</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/6883</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Trees are fundamental structures in computer science, being widely used in modeling &#xd;
and representing different types of data in numerous computer applications. In many cases,&#xd;
properties of objects being modeled are stored as weights or labels on the nodes of trees.&#xd;
Thus researchers have studied the preprocessing of weighted trees in which each node is&#xd;
assigned a weight, in order to support various path queries, for which a certain function&#xd;
over the weights of the nodes along a given query path in the tree is computed [3, 14, 22, 26].&#xd;
&#xd;
In this thesis, we consider the problem of supporting several various path queries over&#xd;
a tree on n weighted nodes, where the weights are drawn from a set of σ distinct values.&#xd;
One query we support is the path median query, which asks for the median weight on a&#xd;
path between two given nodes. For this and the more general path selection query, we&#xd;
present a linear space data structure that answers queries in O(lg σ) time under the word&#xd;
RAM model. This greatly improves previous results on the same problem, as previous data&#xd;
structures achieving O(lg n) query time use O(n lg^2 n) space, and previous linear space data&#xd;
structures require O(n^ε) time to answer a query for any positive constant ε [26].&#xd;
&#xd;
We also consider the path counting query and the path reporting query, where a path&#xd;
counting query asks for the number of nodes on a query path whose weights are in a&#xd;
query range, and a path reporting query requires to report these nodes. Our linear space&#xd;
data structure supports path counting queries with O(lg σ) query time. This matches&#xd;
the result of Chazelle [14] when σ is close to n, and has better performance when σ is&#xd;
significantly smaller than n. The same data structure can also support path reporting&#xd;
queries in O(lg σ + occ lg σ) time, where occ is the size of output. In addition, we present&#xd;
a data structure that answers path reporting queries in O(lg σ + occ lg lg σ) time, using&#xd;
O(n lg lg σ) words of space. These are the first data structures that answer path reporting&#xd;
queries.</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">Data Structures</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Path Queries</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Path Counting</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Path Reporting</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Path Median</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Path Selection</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Tree Extraction</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Path Queries in Weighted Trees</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>