<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">

Publication:
Building quadtrees for spatial data under local differential privacy

Loading...
Thumbnail Image

Departments

Item type:Organizational Unit,

School / College / Institute

Item type:Organizational Unit,

Program

Organization Authors

Co-Authors

Date

Language

Embargo Status

N/A

Journal Title

Journal ISSN

Volume Title

Alternative Title

Abstract

Spatial decompositions are commonly used in the privacy literature for various purposes such as range query answering, spatial indexing, count-of-counts histograms, data summarization, and visualization. Among spatial decomposition techniques, quadtrees are a popular and well-known method. In this paper, we study the problem of building quadtrees for spatial data under the emerging notion of Local Differential Privacy (LDP). We first propose a baseline solution inspired from a state-of-the-art method from the centralized DP literature and adapt it to LDP. Motivated by the observation that the baseline solution causes large noise accumulation due to its iterative strategy, we then propose a novel solution which utilizes a single data collection step from users, propagates density estimates to all nodes, and finally performs structural corrections to the quadtree. We experimentally evaluate the baseline solution and the proposed solution using four real-world location datasets and three utility metrics. Results show that our proposed solution consistently outperforms the baseline solution, and furthermore, the resulting quadtrees provide high accuracy in practical tasks such as spatial query answering under conventional privacy levels.

Source

Publisher

Springer Nature

Citation

item.page.haspartof

Source

Lecture Notes in Computer Science

item.page.ispartofseries

item.page.edition

DOI

10.1007/978-3-031-37586-6_2

item.page.datauri

item.page.link

Rights

N/A

Copyrights Note

Rights and licensing

N/A

Endorsement

Review

Supplemented By

Referenced By

Related Patent

Related Goal

Google Scholar
Scholar'da Ara ↗
Altmetric
Dimensions
PlumX Metrikleri
BIP! Indicators