Hierarchical spatial decompositions under local differential privacy

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