Geri Dön

Answering spatial density queries under local differential privacy

Konumsal yoğunluk sorgularının lokal diferansiyel mahremiyet korumalı cevaplanması

PDF İndir

  1. Tez No: 774189
  2. Yazar: EKİN TİRE
  3. Danışmanlar: DR. ÖĞR. ÜYESİ MEHMET EMRE GÜRSOY
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2022
  8. Dil: İngilizce
  9. Üniversite: Koç Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 65

Özet

Konumsal yoğunluk sorguları, birçok coğrafi veri analizi işinde temel bir yapıtaşı olmakla birlikte, kalabalık alanların belirlenmesi, trafik yoğunluğunun tahmini, navigasyon, yolcu talep analizi gibi gerçek hayatta çok sayıda uygulama alanına sahiptir. Öte yandan, konumsal yoğunluk sorgularının kullanıcı verileri kullanılarak cevaplanması, kullanıcıların gerçek konumlarını güvenilir olmayan üçüncü kişilere (örneğin, servis sağlayıcı veya veri toplayıcı görevi gören bir sunucuya) ifşa ederek kullanıcı mahremiyetini ihlal edebilir. Bu tezde, konumsal yoğunluk sorgularının modern bir mahremiyet koruma standardı olan Lokal Diferansiyel Mahremiyet (LDP) korumalı cevaplanması için bir çözüm öneriyoruz. Çözümümüz dört ana adımdan oluşmaktadır: bölümleme, hassasiyet bulma, kullanıcı tarafı gürültülü cevap hesaplaması ve sunucu tarafı tahminleme. İlk adım için, öncelikle üç temel bölümleme stratejisi öneriyoruz: Tekil Bölümleme, Bütünsel Bölümleme ve Rastgele Bölümleme. Üç temel bölümleme stratejisi üzerinde yaptığımız nitel ve deneysel analizlere dayanarak, Gelişmiş Bölümleme adlı iyileştirilmiş bir strateji öneriyor ve geliştiriyoruz. İkinci adım için, merkezi DP literatüründen sorgu kümelerinin çizge-tabanlı modellemesi tekniğini kullanıyoruz. Gelişmiş Bölümleme yöntemi de çizge-tabanlı modelleme tekniğini kullanmakta ve bölümleme problemini sorgu kümesinin çizge modeli üzerinde düğüm renklendirme problemi olarak çözümleyerek geliştirmektedir. Üçüncü ve dördüncü adımlar için, çözümümüze iki popüler LDP protokolünü (GRR ve RAPPOR) uyarlamaya ek olarak, çözümümüze uygulanabilir hale gelmesi için Optimized Unary Encoding (OUE) protokolüne bir genişletme öneriyoruz. Genişletilmiş protokolümüzün ismi Optimized Bitvector Encoding (OBE)'dir. OBE sadece konumsal sorguların cevaplanması problemiyle sınırlı olmayıp, bitvektör kodlaması içeren herhangi bir LDP probleminde de kullanıma uygundur. OBE'nin kullanıcı tarafı gürültülü cevap hesaplamasının LDP'yi sağladığını ve sunucu tarafı tahminlemesinin tarafsız olduğunu matematiksel olarak kanıtlıyoruz. Farklı bölümleme stratejileri ve LDP protokollerinin kombinasyonları kullanılarak, konumsal sorguların LDP ile cevaplanması için 8 farklı yaklaşım elde edilmiştir; bu yaklaşımların hepsi dört-adımlı çözümümüzün adımlarında farklı seçimler yapılarak elde edilen örnekleri olarak incelenebilir. Elde edilen yaklaşımların kapsamlı deneysel değerlendirmesini, gerçek dünyadan alınmış 4 veri seti, değişen sayıda sorgu, değişen sayıda sorgu boyutu, değişen mahremiyet dereceleri ve birden fazla hata metriği kullanarak yapıyoruz. Sonuçlar, Gelişmiş Bölümleme stratejisi ve OBE protokolünün genelde en düşük hatayı verdiğini göstermekte, bu durum da önerdiğimiz yöntemlerin üstünlüğünü gözler önüne sermektedir.

Özet (Çeviri)

Spatial density queries are fundamental in many geospatial data analysis tasks and have numerous applications in the real world, such as determining crowded areas, estimating traffic density, navigation, passenger demand analysis, and so forth. However, answering spatial density queries based on users' data may violate users' privacy by exposing their true locations to an untrusted third party (e.g., a server acting as the service provider or data collector). In this thesis, we propose a solution for answering spatial density queries while preserving Local Differential Privacy (LDP), a state-of-the-art privacy protection standard. Our solution consists of four main steps: partitioning, finding sensitivity, user-side noisy response computation, and server-side estimation. For the first step, we initially propose three basic partitioning strategies: Singleton Partitioning, Holistic Partitioning and Random Partitioning. Based on our qualitative and empirical analysis of the three basic strategies, we design and implement an improved strategy called Advanced Partitioning. For the second step, we adapt graph-based modeling of query sets from the centralized DP literature. Advanced Partitioning also leverages and extends this technique by formulating the partitioning problem as a vertex coloring problem on the graph representation of a query set. For the third and fourth steps, in addition to adapting two popular LDP protocols (GRR and RAPPOR) to our solution, we propose an extension for the Optimized Unary Encoding (OUE) protocol so that it can be employed in our solution. We call the extended protocol Optimized Bitvector Encoding (OBE). OBE is applicable to not only the problem of answering spatial density queries, but also in arbitrary LDP problems with bitvector encodings. We formally prove that the user-side perturbation step of our OBE protocol satisfies LDP and its server-side estimation step produces unbiased estimates. Combining the different partitioning strategies and LDP protocols, we obtain a total of 8 different approaches for answering spatial density queries under LDP, all of which can be parsed as instances of our four-step solution with different choices in the individual steps. We perform an extensive experimental evaluation of these approaches using 4 real-world datasets, varying number of queries, varying query sizes, varying degrees of privacy, and multiple error metrics. Results show that Advanced Partitioning and OBE protocol typically yield the lowest error, demonstrating the superiority of our proposed methods.

Benzer Tezler

  1. Tez No

    905039

    Hierarchical spatial decompositions under local differential privacy

    Lokal diferansiyel mahremiyet korumalı hiyerarşik konumsal ayrışımlar

    ECE ALPTEKİN

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKoç Üniversitesi

    Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ MEHMET EMRE GÜRSOY

    DOÇ. DR. ALPTEKİN KÜPÇÜ

    PROF. DR. YÜCEL SAYGIN

  2. Tez No

    550043

    Street as playground

    Oyun alanı olarak sokak

    ASLI CEREN MAVİKURT

    Yüksek Lisans

    İngilizce

    İngilizce

    2019

    Şehircilik ve Bölge PlanlamaOrta Doğu Teknik Üniversitesi

    Şehir ve Bölge Planlama Ana Bilim Dalı

    PROF. DR. ELA BABALIK

  3. Tez No

    757359

    Sosyal bilgiler öğretmen adaylarının mekânsal okuryazarlık düzeylerinin belirlenmesi (MAKÜ örneği)

    Determining the spatial literacy levels of social studies teacher candidates (MAKÜsample)

    HAKAN ATAÇ

    Yüksek Lisans

    Türkçe

    Türkçe

    2022

    CoğrafyaBurdur Mehmet Akif Ersoy Üniversitesi

    Sosyal Bilimler ve Türkçe Eğitimi Ana Bilim Dalı

    PROF. DR. OSMAN YILMAZ

  4. Tez No

    432118

    Sayısal ortamda oluşturulan kentsel tasarım yaklaşımları

    Urban design approach in computational environment

    SERDAR KÖROĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2016

    MimarlıkYıldız Teknik Üniversitesi

    Mimarlık Ana Bilim Dalı

    PROF. DR. MERYEM BİRGÜL ÇOLAKOĞLU

  5. Tez No

    75244

    Yerleşmelerde kültürel yapıya bağlı mekansal farklılaşmalar Eyüp-Balat örneği

    Differences of spatial organizations of settlements according to cultural structure- A case study Eyup-Balat

    NEŞEGÜL R. ERBAKAN

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    Şehircilik ve Bölge Planlamaİstanbul Teknik Üniversitesi

    Şehir ve Bölge Planlama Ana Bilim Dalı

    PROF. DR. CENGİZ CİRİTOĞLU

Geri Dön