<?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-22T21:43:43Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/18550" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/18550</identifier><datestamp>2025-03-26T23:33:31Z</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">Kerschbaum, Florian</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="fa1a42d4-da64-419d-bbd4-1708758f9176" confidence="600">Lepert, Emily</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2022-08-16T17:28:57Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2022-08-16T17:28:57Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2022-08-16</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2022-08-09</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/18550</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">We examine the problem of providing differential privacy for nearest neighbor queries. Very few mechanisms exist that achieve this, most notable geo-indistinguishability in the context of location privacy. However it uses an extended definition of differential privacy and restricts the sensitivity of queries.&#xd;
This work presents a new mechanism for DP nearest neighbor queries that is general to many applications and is based on tree data-structures and traversal. The biggest challenge with existing local differential private solutions is poor utility, requiring the addition of a restriction on the sensitivity of queries. We provide two variations, one which uses a similar restriction and one that does not. We explore different tree traversal algorithms. We evaluate our method on artificial datasets as well as real world location data. The results show that the variant using a restricted sensitivity does not perform better than geo-indistinguishability, while the unrestricted variant offers a method with good utility.</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">kd tree</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">differential privacy</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">nearest neighbors</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">private search</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Differential Privacy for Nearest Neighbor Queries</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">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Kerschbaum, Florian</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>