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

Publication:
Hierarchical spatial decompositions under local differential privacy

dc.contributor.advisorGürsoy, Mehmet Emre
dc.contributor.departmentGraduate School of Sciences and Engineering
dc.contributor.kuauthorAlptekin, Ece
dc.contributor.programComputer Sciences and Engineering
dc.contributor.refereeKüpçü, Alptekin||Saygın, Yücel
dc.contributor.schoolcollegeinstituteGRADUATE SCHOOL OF SCIENCES AND ENGINEERING
dc.coverage.spatialİstanbul
dc.date.accessioned2025-06-30T04:36:14Z
dc.date.available2025-03-25
dc.date.issued2024
dc.description.abstractThe 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.
dc.description.abstractAkı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).
dc.description.fulltextYes
dc.format.extentxi, 50 leaves : illustrations ; 30 cm.
dc.identifier.embargoNo
dc.identifier.endpage61
dc.identifier.filenameinventorynoT_2024_143_GSSE
dc.identifier.urihttps://hdl.handle.net/20.500.14288/29807
dc.identifier.yoktezid905039
dc.identifier.yoktezlinkhttps://tez.yok.gov.tr/UlusalTezMerkezi/TezGoster?key=LY6e5xGA7WWUpEdrBmEPLkQ2Ins5or1IkrBH3dK7KyYmZ7zEanfh1lIHvYO9RiSs
dc.language.isoeng
dc.publisherKoƧ University
dc.relation.collectionKU Theses and Dissertations
dc.rightsrestrictedAccess
dc.rights.copyrightsnote© All Rights Reserved. Accessible to Koç University Affiliated Users Only!
dc.subjectComputer networks, Security measures
dc.subjectComputer communication systems
dc.subjectComputer security
dc.subjectComputational intelligence
dc.subjectArtificial intelligence
dc.subjectInformation visualization
dc.subjectComputer vision, Mathematical models
dc.subjectGeospatial data
dc.subjectGeographic information systems
dc.titleHierarchical spatial decompositions under local differential privacy
dc.title.alternativeLokal diferansiyel mahremiyet korumalı hiyerarşik konumsal ayrışımlar
dc.typeThesis
dspace.entity.typePublication
local.contributor.kuauthorAlptekin, Ece
relation.isAdvisorOfThesisa9bdc1a3-2301-428e-9c3b-57ff24265cac
relation.isAdvisorOfThesis.latestForDiscoverya9bdc1a3-2301-428e-9c3b-57ff24265cac
relation.isParentOrgUnitOfPublication434c9663-2b11-4e66-9399-c863e2ebae43
relation.isParentOrgUnitOfPublication.latestForDiscovery434c9663-2b11-4e66-9399-c863e2ebae43

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
T_2024_143_GSSE.pdf
Size:
975.17 KB
Format:
Adobe Portable Document Format