Hierarchical spatial decompositions under local differential privacy
Lokal diferansiyel mahremiyet korumalı hiyerarşik konumsal ayrışımlar
- Tez No: 905039
- Danışmanlar: DR. ÖĞR. ÜYESİ MEHMET EMRE GÜRSOY, DOÇ. DR. ALPTEKİN KÜPÇÜ, PROF. DR. YÜCEL SAYGIN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 61
Özet
Akıllı telefonlar, GPS donanımlı cihazlar, sosyal ağlar ve bağlantılı araçların popüler\-liğ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şlen\-mesine 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örsel\-leş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ştur\-manı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ışım\-ları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).
Özet (Çeviri)
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.
Benzer Tezler
- Spatial decompositions for geometric interpolation and efficient rendering
.
FATMA BETÜL ATALAY SATOĞLU
Doktora
İngilizce
2004
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolUniversity of Maryland College ParkPROF. DAVID M. MOUNT
- Entropy-based direction-of-arrival estimation methods for rigid spherical microphone arrays
Mikrofon dizinler ̇için entropi temelli varış yönükestirme yöntemleri
ORHUN OLGUN
Yüksek Lisans
İngilizce
2019
Bilim ve TeknolojiOrta Doğu Teknik ÜniversitesiModelleme ve Simülasyon Ana Bilim Dalı
DOÇ. DR. HÜSEYİN HACIHABİBOĞLU
- Integrating GIS and multi-criteria decision making techniques (AHP and TOPSIS) for earthquake hazard map generation and analysis: Case of Kucukcekmece region
Cbs ve çok ölçütlü karar verme tekniklerinin (AHY ve TOPSIS) deprem tehlike haritası üretimi ve analizi odaklı bütünleştirilmesi: Küçükçekmece örneği
PENJANI HOPKINS NYIMBILI
Yüksek Lisans
İngilizce
2017
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
DOÇ. DR. TURAN ERDEN
- İstatistiki bilgi işlemde veri bankaları ve veri tabanlarının analizde etkinlik bakımından değerlendirilmesi ve mekansal veriler
Assesment and efficiency analysis of databanks and data bases in statistical information processing for spatial data
MERT ECE
- Robotic exploration and navigation on hierarchical spatial maps
Sıradüzensel haritalarda robotik keşif ve hareket
KADİR TÜRKSOY
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. HURİYE IŞIL BOZMA AYDIN
