Publication: Hierarchical spatial decompositions under local differential privacy
Loading...
Program
Computer Sciences and Engineering
KU-Authors
Organization Authors
Co-Authors
Author
Advisor
item.page.yoktezid
905039
Approval Date
Date
Language
Type
Embargo Status
No
Journal Title
Journal ISSN
Volume Title
Alternative Title
Lokal diferansiyel mahremiyet korumalı hiyerarÅik konumsal ayrıÅımlar
Abstract
The popularity of smartphones, GPS-equipped devices, social networks, and connected vehicles continues to increase the volume of spatial data available for collection and analysis. Spatial decompositions assist in handling big spatial data, and they have been commonly used in the centralized differential privacy (DP) literature for range query answering, spatial indexing, count-of-counts histograms, data summarization, and visualization. However, their applications under the emerging local differential privacy (LDP) notion are relatively scarce. In this thesis, we study the problem of building hierarchical spatial decompositions under LDP, focusing on two methods: quadtrees and kd-trees. We develop two solutions for quadtrees: a baseline solution that is inspired by the centralized DP literature, and a proposed solution that utilizes a single data collection step from users, propagates density estimates to remaining nodes, and performs structural corrections to the quadtree. Since kd-trees rely on node medians which are data-dependent, we observe that it is not feasible to build kd-trees using a single data collection step. We therefore propose an iterative solution that constructs kd-trees in top-down fashion by utilizing a novel algorithm for estimating node medians at each tree depth. We experimentally evaluate our quadtree and kd-tree algorithms using four real-world spatial datasets, multiple utility metrics, varying privacy budgets, and tree parameters. Results demonstrate that our algorithms enable the building of accurate spatial decompositions that provide high utility in practice. Notably, our quadtrees and kd-trees achieve substantially lower errors in answering spatial density queries (up to 10-fold improvement) when compared with a state-of-the-art method.
Akıllı telefonlar, GPS donanımlı cihazlar, sosyal aÄlar ve baÄlantılı araƧların popülerliÄi, toplanması ve analiz edilmesi mümkün olan konumsal verinin hacmini arttırmaya devam etmektedir. Konumsal ayrıÅımlar, büyük konumsal verilerin iÅlenmesine yardımcı olur ve merkezi diferansiyel mahremiyet (DP) literatüründe aralık sorgusu yanıtlama, konumsal dizinleme, sayım-histogramlar, veri ƶzetleme ve gƶrselleÅtirme iƧin sıklıkla kullanılmıÅtır. Ancak, yeni geliÅen lokal diferansiyel mahremiyet (LDP) kavramı altındaki uygulamaları nispeten azdır. Bu tezde, hiyerarÅik konumsal ayrıÅımların LDP altında oluÅturulması problemini inceleyerek, ƶzellikle iki yƶnteme odaklanıyoruz: dƶrdüzaÄaƧlar ve kd-aÄaƧları. DƶrdüzaÄaƧlar iƧin iki Ƨƶzüm geliÅtiriyoruz: merkezi DP literatüründen esinlenen bir temel Ƨƶzüm ve kullanıcılardan tek bir veri toplama adımı kullanan, yoÄunluk tahminlerini diÄer düÄümlere ileten ve dƶrdüzaÄaƧ üzerinde yapısal düzeltmeler gerƧekleÅtiren bir ƶnerilen Ƨƶzüm. Kd-aÄaƧları, veriye baÄımlı olan düÄüm medyanlarına dayandıÄı iƧin, tek bir veri toplama adımını kullanarak kd-aÄaƧları oluÅturmanın mümkün olmadıÄını gƶzlemliyoruz. Bu nedenle, her aÄaƧ derinliÄinde düÄüm medyanlarını kestirmek iƧin yeni bir algoritma kullanan, üstten aÅaÄıya doÄru kd-aÄaƧları oluÅturan iteratif bir Ƨƶzüm ƶneriyoruz. Dƶrt gerƧek konumsal veri kümesi, ƧeÅitli fayda ƶlçütleri, deÄiÅen mahremiyet bütƧeleri ve aÄaƧ parametreleri kullanarak dƶrdüzaÄaƧ ve kd-aÄacı algoritmalarımızı deneysel olarak deÄerlendiriyoruz. SonuƧlar, algoritmalarımızın pratikte yüksek fayda saÄlayan doÄru konumsal ayrıÅımların oluÅturulmasını mümkün kıldıÄını gƶstermektedir. Ćzellikle, dƶrdüzaÄaƧlarımız ve kd-aÄaƧlarımız mevcut bir yƶntemle karÅılaÅtırıldıÄında, konumsal yoÄunluk sorgularını yanıtlarken ƶnemli ƶlçüde daha düÅük hata oranlarına ulaÅmaktadır (10 kata kadar iyileÅme).
Akıllı telefonlar, GPS donanımlı cihazlar, sosyal aÄlar ve baÄlantılı araƧların popülerliÄi, toplanması ve analiz edilmesi mümkün olan konumsal verinin hacmini arttırmaya devam etmektedir. Konumsal ayrıÅımlar, büyük konumsal verilerin iÅlenmesine yardımcı olur ve merkezi diferansiyel mahremiyet (DP) literatüründe aralık sorgusu yanıtlama, konumsal dizinleme, sayım-histogramlar, veri ƶzetleme ve gƶrselleÅtirme iƧin sıklıkla kullanılmıÅtır. Ancak, yeni geliÅen lokal diferansiyel mahremiyet (LDP) kavramı altındaki uygulamaları nispeten azdır. Bu tezde, hiyerarÅik konumsal ayrıÅımların LDP altında oluÅturulması problemini inceleyerek, ƶzellikle iki yƶnteme odaklanıyoruz: dƶrdüzaÄaƧlar ve kd-aÄaƧları. DƶrdüzaÄaƧlar iƧin iki Ƨƶzüm geliÅtiriyoruz: merkezi DP literatüründen esinlenen bir temel Ƨƶzüm ve kullanıcılardan tek bir veri toplama adımı kullanan, yoÄunluk tahminlerini diÄer düÄümlere ileten ve dƶrdüzaÄaƧ üzerinde yapısal düzeltmeler gerƧekleÅtiren bir ƶnerilen Ƨƶzüm. Kd-aÄaƧları, veriye baÄımlı olan düÄüm medyanlarına dayandıÄı iƧin, tek bir veri toplama adımını kullanarak kd-aÄaƧları oluÅturmanın mümkün olmadıÄını gƶzlemliyoruz. Bu nedenle, her aÄaƧ derinliÄinde düÄüm medyanlarını kestirmek iƧin yeni bir algoritma kullanan, üstten aÅaÄıya doÄru kd-aÄaƧları oluÅturan iteratif bir Ƨƶzüm ƶneriyoruz. Dƶrt gerƧek konumsal veri kümesi, ƧeÅitli fayda ƶlçütleri, deÄiÅen mahremiyet bütƧeleri ve aÄaƧ parametreleri kullanarak dƶrdüzaÄaƧ ve kd-aÄacı algoritmalarımızı deneysel olarak deÄerlendiriyoruz. SonuƧlar, algoritmalarımızın pratikte yüksek fayda saÄlayan doÄru konumsal ayrıÅımların oluÅturulmasını mümkün kıldıÄını gƶstermektedir. Ćzellikle, dƶrdüzaÄaƧlarımız ve kd-aÄaƧlarımız mevcut bir yƶntemle karÅılaÅtırıldıÄında, konumsal yoÄunluk sorgularını yanıtlarken ƶnemli ƶlçüde daha düÅük hata oranlarına ulaÅmaktadır (10 kata kadar iyileÅme).
Source
Publisher
KoƧ University
Citation
item.page.haspartof
Source
item.page.ispartofseries
item.page.edition
DOI
item.page.datauri
item.page.link
Rights
restrictedAccess
Copyrights Note
© All Rights Reserved. Accessible to Koç University Affiliated Users Only!
Rights and licensing
restrictedAccess
© All Rights Reserved. Accessible to Koç University Affiliated Users Only!
© All Rights Reserved. Accessible to Koç University Affiliated Users Only!
Collections
Endorsement
Review
Supplemented By
Referenced By
Google Scholar
Scholar'da Ara ā Bu yayında DOI yok ā Altmetric/Dimensions/PlumX/BIP! rozetleri DOI gerektirir.
