Publication:
Building quadtrees for spatial data under local differential privacy

Placeholder

Organizational Units

Program

KU Authors

Co-Authors

Advisor

Publication Date

2023

Language

en

Type

Conference proceeding

Journal Title

Journal ISSN

Volume 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.

Description

Source:

Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Publisher:

Springer Science and Business Media Deutschland Gmbh

Keywords:

Subject

Computer science, Information systems, Theory, Methods, Telecommunications

Citation

Endorsement

Review

Supplemented By

Referenced By

Copy Rights Note

0

Views

0

Downloads

View PlumX Details