k-Nearest Neighbor Query Processing Algorithm for Cloaking Regions

Abstract

Duetotheadvancementofwirelessinternetandmobilepositioningtechnology,theapplicationoflocation-basedservices(LBSs)hasbecomepopularformobileusers.Sinceusershavetosendtheirexactlocationstoobtaintheservice,itmayleadtoseveralprivacythreats.Tosolvethisproblem,acloakingmethodhasbeenproposedtoblurusers’exactlocationsintoacloakedspatialregionwitharequiredprivacythreshold(k).Withthecloakedregion,anLBSservercancarryoutak-nearestneighbor(k-NN)searchalgorithm.Somerecentstudieshaveproposedmethodstosearchk-nearestPOIswhileprotectingauser’sprivacy.However,theyhaveatleastonemajorproblem,suchasinefficiencyonqueryprocessingorlowprecisionofretrievedresult.Toresolvetheseproblems,inthispaper,weproposeanovelk-NNqueryprocessingalgorithmforacloakingregiontosatisfybothrequirementsoffastqueryprocessingtimeandhighprecisionoftheretrievedresult.Toachievefastqueryprocessingtime,weproposeanewpruningtechniquebasedona2D-coodinatescheme.Inaddition,wemakeuseofaVoronoidiagramforretrievingthenearestPOIsefficiently.Tosatisfytherequirementofhighprecisionoftheretrievedresult,weguaranteethatourk-NNqueryprocessingalgorithmalwayscontainstheexactsetofknearestneighbors.OurperformanceanalysisshowsthatouralgorithmachievesbetterperformanceintermsofqueryprocessingtimeandthenumberofcandidatePOIscomparedwithotheralgorithms.