<?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-22T13:44:37Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/1085" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/1085</identifier><datestamp>2017-03-21T19:03:26Z</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="bdd04789-caed-4481-996f-2ac14f0545dd" confidence="600">Lim, Heechul</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2006-08-22T14:28:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2006-08-22T14:28:35Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued" lang="en">2003</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted" lang="en">2003</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/1085</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Many variations of algorithms for finding the shortest path in a large graph have been introduced recently due to the needs of applications like the Geographic Information  System (GIS) or Intelligent Transportation System (ITS).   The primary subjects of those algorithms are materialization and hierarchical path views.   Some studies focus on the materialization and sacrifice the pre-computational costs and storage costs for faster computation of a query.   Other studies focus on the shortest-path algorithm, which has less pre-computation and storage but takes more time to compute the shortest path.   The main objective of this thesis is to accelerate the computation time for the shortest-path queries while keeping the degree of materialization as low as possible.       This thesis explores two different categories: 1) the reduction of the I/O-costs for multiple queries, and 2) the reduction of search spaces in a graph.   The thesis proposes two simple algorithms to reduce the I/O-costs, especially for multiple queries.   To tackle the problem of reducing search spaces, we give two different levels of materializations, namely, the &amp;lt;i&amp;gt;boundary set distance matrix&amp;lt;/i&amp;gt; and &amp;lt;i&amp;gt;x-Hop sketch graph&amp;lt;/i&amp;gt;, both of which materialize the shortest-path view of the boundary nodes in a partitioned graph.   Our experiments show that a combination of the suggested solutions for 1) and 2) performs better than the original Disk-based SP algorithm [7], on which our work is based, and requires much less storage than &amp;lt;i&amp;gt;HEPV&amp;lt;/i&amp;gt; [3].</dim:field>
   <dim:field mdschema="dc" element="format" lang="en">application/pdf</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="extent">649693 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: 2003, 
  Lim, Heechul. 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">Shortest Path Query</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Spatial Database</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Pruning Algorithm</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Evaluation of Shortest Path Query Algorithm in Spatial Databases</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>