Differentiell integritet är ett lovande privacy-bevarande paradigm för statistisk frågebehandling över känsliga data. Det fungerar genom att injicera slumpmässigt buller i varje frågeresultat, så att det är bevisligen svårt för motståndaren att dra slutsatsen förekomsten eller frånvaron av någon enskild post från publicerade bullriga resultat. Det huvudsakliga målet i differentialt privat frågebehandling är att maximera riktigheten av frågeresultaten, samtidigt som integritetsgarantierna uppfylls. Tidigare arbete, särskilt matrismekanismen [16], har föreslagit att bearbetning av ett parti korrelerade frågor som helhet kan potentiellt uppnå betydande noggrannhetsvinster, jämfört med att besvara dem individuellt. Men, som vi påpekar i detta dokument, är matrismekanismen huvudsakligen av teoretiskt intresse; i synnerhet, flera inneboende problem i dess utformning begränsar dess exakthet i praktiken, som nästan aldrig överstiger den för naiva metoder. I själva verket är vi inte medvetna om någon befintlig lösning som effektivt kan optimera en frågeparti under differential integritet. Motiverade av detta föreslår vi Low-Rank Mechanism (LRM), den första praktiska differentialt privata tekniken för att besvara batch frågor med hög noggrannhet, baserat på en låg rang approximation av arbetsbördan matris. Vi bevisar att noggrannheten som tillhandahålls av LRM är nära den teoretiska lägre gränsen för varje mekanism för att svara på ett parti frågor under differential integritet. Omfattande experiment med hjälp av verkliga data visar att LRM konsekvent överträffar state-of-theart frågebehandlingslösningar under differential integritet, med stora marginaler.
I det senaste arbetsprogrammet fastställs dock flera inneboende begränsningar i matrismekanismen som minskar noggrannheten i praktiken och som följaktligen presenterar mekanismen med låga rankningar.
Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy
{'venue': 'Proceedings of the VLDB Endowment (PVLDB), Vol. 5, No. 11, pp. 1352-1363 (2012)', 'journal': None, 'mag_field_of_study': ['Computer Science']}