Local Differential Privacy and Its Applications: A Comprehensive Survey

1.2 Heavyhittersidentification

Naive method.Astheheavyhittersaretheitemswiththefrequencyoverathreshold,theaggregatorcancollecttheuser′sdataandcomputethefrequencyforeachitemusingfrequencyoracle,thenfindouttheheavyhitters.

Discussion.Naivemethodisaneffectivesolutionforheavyhitteridentificationforlowdimensionaldata.Butitisinefficientforhighdimensionaldata.Forexample,assumethereare1000websitesintotal,theaggregatorwantstoknowthetop-10frequentlyvisitedones,heneedstoquery21000timestogettheanswerjustusingfrequencyoracle.Andthestatisticalvariancewouldbeveryhigh,whichreducesthestatisticalaccuracysignificantly. Partition-based methodPartition-basedmethodtriestofindthefrequentoneswithoutgoingthroughallthepossiblevalues.Specifically,theuser′sdataisencodedasabinaryvectorusingone-hotencoding.Eachuserreportsasegmentoftheperturbedvectortotheaggregator.Iftheuser′svectorispartitionedintogsegments,eachuseronlyneedstoreports=d/gbits.Theprincipleisthatifavalueisfrequent,thesegmentofthevalueisalsofrequent.TheaggregatorfindsthefrequentstringsineachsegmentdenotesasCiandthencalculatestheCartesianproductofCiasC=C1×C2×…×Cg.ThefrequentitemsarefoundinthecandidatesetC.TofurtherreducethesizeofthecandidatesetC,Fantietal.[fanti2016building]lettheusersreporttwosegmentsrandomlyinsteadofone.Apotentialproblemofpartitionisthatifthenumberofsegmentgisbig,therewillbeasmallgroupofusersreportthesamesegment,whichreducesthestatisticalaccuracy.Wangetal.[wang2019locally]solvethisproblembyhavingthesegmentsoverlapping.Thatis,theylettheusersineachgroupreportaprefixoftheirvaluewithpredefinedlength.Thentheaggregatorfindsthefrequentitemsiteratively.Kimetal.[kim2018learning]proposeasimilarmethodtofindfrequentwordsfromusers′keystrokedata.Specifically,eachuserappendsahashvaluetotheword(enableintegritychecking)andsendsonerandomsegment(thesegmentcanstartformanypositionofthewordstring,andtherearepartialoverlappingbetweensegments)totheserver.Theserverselectsthefrequentstringsofthesegmentandcombinescandidatesegmentsperpositionside-by-sidefollowingthechainrule.

Discussion.Partition-basedmethodincreasestheefficiencyofheavyhittersestimationbyreducingthequerytimesfrom2dto2sg(ifreportonesegment).However,itincreasestheothercomputationalcost,suchastheconstructionofthecandidateset.Besides,thecandidatesobtainedfromthesegmentsoftendonotcorrespondtorealterms,whichaffectstheaccuracyofheavyhitterestimation. Tree-based methodThetree-basedmethodismainlyusedfor′stringdata′,suchastrajectoryandEnglishword.ThefrequentitemisidentifiedbyiterativelyconstructingatreeunderLDP,eachnoderepresentsaprefixofanitemandlessfrequentprefixesareprunedduringeachiteration.Similartopartition-basedmethod,theprincipleoftree-basedmethodisthatallprefixofafrequentitemmustbefrequentaswell,whichenableseffectivepruning.Therefore,thestatisticalcomputationofheavyhittersismuchmoreefficient.Aseachitemincludesmultiplecharacters,thedomainsizeisveryhigh,theestimatedfrequencymaynotbeasaccurateasexpected.Tosolvethisproblem,Bassilyetal.[bassily2017practical]invokethelocalrandomizertwiceinthefullprotocol,onceduringthepruningprocesswherethehigh-frequencyitemsareidentified,andasecondtimeduringtheestimationphase,invokesthefrequencyoracleoncemoreonthoseparticularitemstoenabletheprotocoltogetabetterestimation.Wangetal.[wang2018privtrie]presentacandidatesetconstructionmethodforeachnodeonthetree,whichrestrictsthateachusercanonlyreportonetimetothenodesonhisownpathtosavetheprivacybudget.

Discussion:Tree-basedmethodcanfindthefrequentitemsefficientlyandusersdonotneedtoknowthedomainsizeofdata.Thedrawbackisthealgorithmneedsmultipleiterations,whichincreasethecommunicationcostanddelay.Besides,currently,themainmethodtoreducethestatisticalvarianceistopartitionuserstodisjointgroups.Whenthedatadimensionislarge,theinsufficientnumberofusersineachgroupreducetheaccuracyaswell. Summary.Themainchallengeforheavyhitteridentificationishowtofindtheheavyhittersefficiently,andwithaccuracy.Thebasicideaofcurrentmethodistoremovesomeinfrequentitemsstepbystep.Ontheonehand,itsolvedtheefficiencyproblem,butontheotherhand,itintroducesnewproblems,suchascomplexcomputationorhighcommunicationcosts.Tofurtherimprovetheperformanceofheavyhitteridentificationisremainachallenge.

1.3 Frequencyestimationoversetvaluedata

Heavy hitters identification over set value data.Themainchallengeforidentifyingtheheavyhittersoversetvaluedataisthattheset-valuedatahasheterogeneoussize.Thatis,eachusermayhave0tolitems,whichmakesitdifficulttoaccesstheitemsampleprobability,thenmakeaccuratefrequencyestimationdifficult.

[qin2016heavy, wang2018privset].Specifically,theaggregatorassumesthevariablemtobethelargestnumberofuser′ssizeoftheset-valueddata.Ifthenumberofitemsinuser′sset-valueddataisbeyondm,thedataissimplytruncatedtom