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

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.