در تحقیقات پیشین انجام شده در زمینه حریم خصوصی محلی، به گونه خاصی از دادهها که از نوع hybrid/heterogeneous هستند کمتر پرداخته شده است. از جمله این گونه دادهها، میتوان به دادههای key/value اشاره کرد. مشکلی که در این گونه دادهها وجود دارد را می توان در دو گروه دسته بندی کرد: اول نیاز به افزایش اپسیلون که به معنای اضافه کردن نویز بیشتر است، دوم هم بستگی بین کلید و مقدار است که افشای اطلاعات در مورد مقدار، خود افشا دهنده اطلاعات در مورد کلید خواهد بود. روشهایی برای بهبود این موضوع پیشنهاد شده است که دارای محدودیتهایی از جمله غیر کاربردی بودن در محیطهای آنلاین، غیرقابل پیاده سازی بودن برای زمانی که کلیدهایی با دامنه بالا داریم و نیز عدم بهبود حریم خصوصی محلی.
در این مقاله یک تخمین زننده میانگین ارائه شده که تنها نیاز به یک دور برای ارائه نتیجه دارد، برخلاف روشهای پیشین که نیازمند تعداد دورهای زیادی برای اجرای الگوریتم داشت. برای این منظور کالیبره شده مجموع مقادیر یک کلید تقسیم بر کالیبره شده فرکانس آن کلید می شود. بدین منظور برای مقدار کلیدهای غیرواقعی، مقادیری انتخاب شد که دارای میانگین صفر باشند. همچنین از روش پیشرفته ای برای نمونه گیری با نام Padding-and-Sampling استفاده شده است. بعلاوه الگوریتم آشفتگی هم بسته جدیدی ارائه شد که نشان داده شده نسبت به الگوریتم های پایه پیشین، تریدآف بهتری برای حریم خصوصی و بهینگی ارائه میدهد. در نهایت با حداقل کردن حد بالای تقریبی خطای میانگین مربع، مقدار نزدیک به بهینه ای برای ثابت حریم خصوصی و پارامترهای آشفتگی به دست آمده است.
به طور خلاصه می توان این مقاله را به پنج قسمت تقسیم کرد:
اول چارچوب PCKV به همراه دو مکانیزم UE و GRP ذیل دو پروتکل اصلی نویز ارائه شده است. شمای ارائه شده در این مقاله تعاملی نیست به صورتی که میانگین مقادیر کلیدها در یک دور تخمین زده می شوند. در این بخش به صورت تئوری خطای میانگین مربع و مقادیر مورد انتظار تحلیل و بی طرفی تقریبی آن نشان داده شده است.
دوم از پروتکل Padding-and-Sampling برای داده کلید-مقدار استفاده شده است که برای دامنه های زیاد نسبت به پروتکلهای نمونه برداری استفاده شده در PrivKVM عملکرد بهتری دارد.
سوم مکانیزم میزان ترکیب نویز جدید ارائه شده است که نسبت به ترکیب متوالی LDP یک حد آستانه محکم تری دارد.
چهارم یک رویکرد نزدیک به بهینه برای budget allocation ارائه شده است.پنجم شمای ارائه شده توسط مجموعه داده های مصنوعی و نیز داده های دنیای واقعی مورد ارزیابی قرار گرفت که نشان دهنده افزایش بهینگی و به عبارتی کاهش خطای میانگین مربع نسبت به شماهای ارائه شده پیشین بوده است.
پنجم شمای ارائه شده توسط مجموعه داده های مصنوعی و نیز داده های دنیای واقعی مورد ارزیابی قرار گرفت که نشان دهنده افزایش بهینگی و به عبارتی کاهش خطای میانگین مربع نسبت به شماهای ارائه شده پیشین بوده است.
Xiaolan Gu, Ming Li, Yueqiang Cheng, “PCKV: Locally Differentially Private Correlated Key-Value Data Collection with Optimized Utility”, 29th USENIX Security Symposium, 2020