Vi definierar en ny interaktiv, differentierad privat mekanism - medianmekanismen - för att besvara godtyckliga predikatfrågor som kommer online. Med tanke på den fasta noggrannheten och integriteten, kan denna mekanism svara exponentiellt fler frågor än den tidigare mest kända interaktiva integritetsmekanismen (Laplace-mekanismen, som självständigt stör varje frågeresultat). När det gäller antalet frågor, vår garanti är nära till bästa möjliga, även för icke-interaktiva integritetsmekanismer. Konceptuellt är medianmekanismen den första integritetsmekanismen som kan identifiera och utnyttja korrelationer mellan frågor i en interaktiv miljö. Vi ger också ett effektivt genomförande av medianmekanismen, med körtid polynom i antalet frågor, databasens storlek, och domänstorlek. Detta effektiva genomförande garanterar integritet för alla indatadatabaser, och korrekta frågeresultat för nästan alla indatadistributioner. Beroendet av integriteten på antalet frågor i denna mekanism förbättras jämfört med den mest kända effektiva mekanismen genom en super-polynom faktor, även i den icke-interaktiva inställningen.
Roth och Roughgarden Ref föreslår en medianmekanism som förbättrar Laplace-mekanismen.
Interactive privacy via the median mechanism
{'venue': "STOC '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}