Adaptive Location Constraint Processing Zhengdao Xu and Hans-Arno Jacobsen UniversityofToronto [email protected], [email protected] ABSTRACT andpreviouslyunthinkablepotentialsfortracking,correlating,and filtering of informationabout moving objects. Forexample, it is Animportantproblemformanylocation-basedapplicationsisthe possibletotrackthelocationofmobileusersinawirelessnetwork, continuous evaluation of proximity relations among moving ob- evenacrosswirelesscoverageareas,andinbuildingsacrosscam- jects. These relations express whether a given set of objects is pus[28,19],totrackthediscretelocationofvehiclesorpackages in a spatial constellation or in a spatial constellation relative to indelivery[1],andeventrackthemovementoflivestockorfishfor a given point of demarcation in the environment. We represent environmentalpurposes[2]. proximityrelationsaslocationconstraints,whichresemblestand- Animportantprobleminthecontextofapplicationsthatleverage ingqueriesovercontinuouslychanginglocationpositioninforma- thistrackingpotentialishowtoefficientlydeterminewhetherfor tion.Thechallengeliesinthecontinuousprocessingoflargenum- anygivennumberofsetsofmovingobjects,theobjectspersetare bersoflocationconstraintsasthelocationofobjectsandthecon- closeto,nocloserthan,orfurther-away-thanaspecifieddistance straint load change. In this paper, we propose an adaptive loca- toeachotherortoagivenpointofdemarcationintheenvironment. tion constraint indexing approach which adapts as the constraint Werefertothisproblemasthelocationconstraintmatchingprob- load and movement pattern of the objects change. The approach lem.Agivensetofobjectsspecifyingaproximityrelationthatmust takes correlations between constraints into account to further re- beenforcedisreferredtoasalocationconstraint. Therearemany duce processing time. We also introduce a new location update applicationsthatrequireasolutiontothisproblem. Thechallenge policy that detects constraint matcheswith fewer location update istodevicealgorithmsthatcanefficientlymonitorlargenumbers requests. Ourapproachstabilizessystemperformance,avoidsos- oflocationconstraintsoverlargernumbersofcontinuouslymoving cillation,reducesconstraintmatchingtimeby70%forin-memory objects. processing, and reduces secondary storage accesses by 80% for Inacellularnetwork,forexample,anoperatormaywanttoof- I/O-incurringenvironments. feralertingservicesthatnotifymembersofagroup(e.g.,agroup CategoriesandSubjectDescriptors of friends or family), if they are close to each other (e.g., friend H.[InformationSystems];H.2.8[DatabaseApplications]: Spa- finderandbuddytrackingapplications)orareclosetoadesignated tialdatabasesandGIS;H.3.3[InformationSearchandRetrieval]: pointintheenvironment(e.g.,theCNTowerinTorontooraroad Information Filtering; H.4[Information SystemsApplications]: congestiononHighway407.) Inmetropolitanareasthenumberof Location-basedServices objectstrackedcaneasilyreachhundredsofthousands,specifying GeneralTerms asimilarnumberoflocationconstraints. Otherexamplesdrawfromprotectingsecuritysensitiveareasin Algorithms,Design,Experimentation,Performance citiesbyspecifyingthatnoairplaneistocomecloserthanaspec- Keywords ifieddistancefromdesignatedpoints,suchasnuclearplants,tow- ers,stadiumsetcetera.Airtrafficcontrollersandpilotsmaybenefit Location-basedServices,LocationConstraintProcessing,Moving fromalertingservicesthatwarnifdesignatedplanescometooclose ObjectIndexing,AdaptiveIndexing,LocationUpdatePolicy,Lo- toeachother.Similarly,majorproductionplantsmayspecifypoli- cation Query, Standing Query, Continuous Location Query, and ciesthatrestrictpersonnelfromenteringrestrictedareasorenforce ConstraintMatching. constraintsthataspecificareamustbeguardedbyasetnumberof personnel. Again, these scenarios may involve large numbers of 1. INTRODUCTION continuously moving objects with many associated location con- Thepervasivepresenceofwirelessnetworkscombinedwithad- straints. Altogether different applications can be found in multi- vances in location positioning technology [28] gives rise to new playeronlinegames, wherefriendorfoemaywanttosetupcon- straintstonotifyandwarnofeachothers’presenceandproximity inthegameworldorpartsofthevirtualspace.Multi-playeronline gamesareplayedby thousandsof playersatthe sametime. The Permissiontomake digital orhardcopies ofallorpartofthisworkfor efficienttrackingofconstraintsamongplayersandamongplayers personalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesare andthegameworldisofcriticalimportancetothesuccessofthe notmadeordistributedforprofitorcommercialadvantageandthatcopies game. bearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,to Tomodelthesescenariosandtoexpressvarioustypesofprox- republish,topostonserversortoredistributetolists,requirespriorspecific imity relations, we introduce two classes of location constraints, permissionand/orafee. the n-body constraint and the n-body staticconstraint. Werefer SIGMOD’07,June11–14,2007,Beijing,China. Copyright2007ACM978-1-59593-686-8/07/0006...$5.00. to these constraints as location constraints, as they are evaluated itors whether a specific set of objects are in a given spatial con- overthelocationdataoftheassociatedobjects.Theconstraintsare stellation to each other or to a given point of demarcation in the definedasfollows: environment. Then-bodyconstraintisoftheform p t;p t;:::;p t <(or> Inthispaperweproposeanadaptivespacepartitioningscheme 1 2 n j j )d,andalsoabbreviatedasP <(or>)dforobjectsetP(= p ;p ; andalgorithmstosolvethelocationconstraintmatchingproblem. 1 2 f :::;p ). Theconstraintwithoperator<issatisfiedifthenmov- Weexperimentwithtwospacepartitioningschemes,oneisatree- n g ingobjects,identifiedby,p ;p ;:::;p ,canbeenclosedbyacircle basedorganizationofthespaceandtheotheroneagridfile-based 1 2 n withadiametersmallerthandattimet.Theconstraintwithopera- organization.Oursolutionsupportsthecontinuoustrackingoflarge tor>issatisfiedifthediameterofthesmallestcircleenclosingthe numbers of location constraints for large populations of moving objectsisgreaterthandattimet. p (1 i n)istheidentifier objects. Ouralgorithmsaredesignedtoadapttochangesinloca- i ofobjecti. Inournotationp t isinterpr(cid:20)eted(cid:20)asthecoordinateof tionconstraintloadsandchangesinmovementpatternsofobjects. i objectiattimet.disreferredtoasthealertingdistance. In particular, our solution adapts to clusters of objects changing Then-bodystaticconstraintisoftheform A;p t;p t;:::;p t overtimeinsize,skewnessandtheformationofnewclusters.Fur- 1 2 n j j < (or >)d, alsoabbreviated as A;P < (or >)dforobject thermore,oursolutionconstitutesaframeworkcustomizablefora j j setP (= p ;p ;:::;p ). Aisthecoordinateofsomestaticpoint. wide-rangeofquerytypesexpressingdifferentgeometricrelations 1 2 n f g The constraint is satisfied if the n moving objects, identified by, among moving objects. We demonstrate and evaluate alternative p ;p ;:::;p ,arewithin(foroperator<)oroutside(foroperator query types such as the continuous reverse range query and the 1 2 n >)thecircledefinedbydaroundthestaticpointAattimet. continuous reverse k nearest neighbor query. We also introduce Theaboveconstraintdefinitionsdonotinclude=, and ,as thenotionofconflictingandharmoniousconstraintstocapturede- (cid:20) (cid:21) theresultingconstraintscanbeeasilyexpressedwiththenegation pendencyrelationsamongconstraintsthathelpinconstraintprun- oftheconstraintitself.Forexample,P dissimply (P >d) ing.Wedevelopadetailedanalyticalmodeltoassesstheconstraint ci (cid:20) : ci andP = disequivalent to (P > d) (P < d),where evaluationcostforin-memoryandI/O-incurringenvironments.Fi- ci : ci ^: ci P denotesthemovingobjectsassociatedwithconstraintc . This nally, weexperimentallyvalidatetheefficiencyofouralgorithms ci i simplifiesthedesignoftheconstraintmatcher. based on various movement patterns, compare to alternative ap- Thelocationconstraintmatchingproblemcanthenbeformally proaches,anddemonstratescalability. statedasfollows:Givenasetoflocationconstraints,C = c ;c ; InSection2,wedescribetheadaptivelocationconstraintmatch- 1 2 f :::;c , which designate the location relationshipamong a set of ing algorithm. In Section 3, we develop the analytical model to k g m possibly moving objects, P = p ;p ;:::;p , continuously assesstheconstraintevaluationcost,determinesystemparameters, 1 2 m f g determineallconstraintsc inCthataresatisfied. andestimatesecondarystorageaccesscost. Thesystemarchitec- i Location constraints arelikecontinuousqueries thatoncesub- tureofafullyimplementedlocationconstraintprocessingsystemis mittedtothesystemremainactiveuntilexplicitlyrevoked. Fig.1 reviewedinSection4.Section5presentstheexperimentalevalua- showsthedataflowofatypicallocation-basedserviceemploying tionofouralgorithms.InSection6,weputourworkinperspective location constraint matching, as defined in this paper. Location torelatedapproaches. updates of mobile objects are streamed into the system and trig- 2. MATCHINGALGORITHM ger the evaluation of constraints and the constraint satisfaction is Oursolutiontothelocationconstraintmatchingproblemisbased communicatedbacktotheinterestedsubscribersvianotifications. onspacepartitioning. Theintuitionisthatspacepartitioningcan Existing data management and indexing techniques for moving approximatethelocationofthemovingobjects,withouttheneed fortheexactlocationofobjectsallthetime,toresolvemanycon- 3-body constraint (matched)(cid:13) straintswithcertainty. Inthissectionwedescribeourapproachin <d(cid:13) Location Constraint(cid:13) detail. Location Updates(cid:13) Matcher(cid:13) <obj_id, x, y>(cid:13) 2.1 Background &BasicAlgorithms constraint 1(cid:13) constraint 2(cid:13) static point(cid:13) Location based(cid:13) constraint 3(cid:13) Asolutiontothelocationconstraintmatchingprobleminprior Comm. Tower(cid:13) Applications(cid:13) ...(cid:13) work[23]dividesthewholespaceintopartitionsthatareindexed with a k-d-tree [5] or a multi-layered grid file structure [13]. To 2-<bdod(cid:13)y static constraint (matched)(cid:13) NoStiefircvaictieo(cid:13)nWo/r(cid:13)kstation(cid:13) MRaetscuhlitnsg(cid:13)(cid:13) cavhoanidgethpeaorvtietirohne,aadboafcakttorapc-kdionwgnaslgcoanritihnmthiesku-sde-dtretoeqwuhiceknloybajsescots- ciate theobject with the new partition. In amulti-layer gridfile, Figure1:DataFlowforLocationConstraintProcessing thespaceispartitionedwithdifferentlayersofgrids, thegridsin thesamelevelareequal-sizedcellswhicharefurtherindexedwith objects[11,3,16,17,14]aremainlyfocusingontheefficientpro- hashtables. cessing of a single spatio-temporal query, such as a range query WeassumethatthepositionofeachobjectisretrievedwithGPS, and the k nearest neighbor query (kNN). However, the location ground-basedsensorsorotherlocationpositioningtechnology. We constraintmatchingproblemdealswiththeconcurrentandcontin- calleachpositionretrievalalocationupdateandwecallthemove- uousevaluationofmanyconstraintsatthesametime(i.e.,hundreds mentofanobjectfromonepartitiontoanotherapartitionupdate. of thousand of location constraints for the applications we advo- Constraintevaluation consistsoftwoparts,theconstrainteval- cate.) Due to the continuous and frequent movement of objects, uationbasedonexactpositioninformationandthepartition-based anunderlyingdatabasewouldbemostlybusyupdatingtheobjects’ constraint evaluation given partition information. Fortheevalua- locationwithoutbeingabletoevaluatetheconstraints. Moreover, tionbasedontheexactposition,Welzl’salgorithm[20]isadopted, thelocationconstraintmatchingproblemisdifferentfromthekNN whichcomputesthesmallestcirclethatenclosesnpointsinO(n) problem[10,27]inthatthekNNproblemdeterminestheknear- time. Below, weintroducepartition-based evaluation thatis trig- est object(s) among all the objects in the space to a given point, gered when an object updates its partition or when the partition whilethelocationconstraintmatchingproblemcontinuouslymon- schemeisadjustedbytheadaptiveadjustmentalgorithm. Thepar- titioninformationisusedasaroughapproximationfortheposition Sri(cid:13)oj(cid:13):Pwa (cid:13)jr(cid:13)tthit icoonl uinm (cid:13)ni(cid:13)th(cid:13)(cid:13) O(cid:13)1(cid:13)((cid:13)d=81 / 2)(cid:13)(cid:13) ofthemovingobjectsandformanyconstraints,thisapproximation j(cid:13)i(cid:13) 1(cid:13) 2(cid:13) 3(cid:13) 4(cid:13) 5(cid:13) 6(cid:13) n-(cid:13)body constraint:(cid:13) isePnaorutgithiotno-dBeatseermdiEnevaalureastuioltn. for n-body Constraints: For n- 1(cid:13) p1(cid:13)(cid:13) O(cid:13)5(cid:13)((cid:13)r=1.5)(cid:13)A(cid:13) (c(cid:13)s1(cid:13)(cid:13):a |tpis1 f(cid:13),ipe 2d,(cid:13)p(cid:13)) 3(cid:13)|(cid:13) < 3, c(cid:13)2:(cid:13) |p2 (cid:13),p 3,(cid:13)p5 (cid:13)| > 3(cid:13) p(cid:13) bothonedtychoecnopsnatrsrattriitaniiotnsnt,iitinfifssooarmmsseaotocioibanjte.ecdStupwpiiptmhoosnveeeteshdainttotcojbaeisnretewh-eepvcaaorlutniastittoreandinSbtiat,shaealdlt 23(cid:13)(cid:13) p2(cid:13)(cid:13) 3(cid:13) p4(cid:13)(cid:13) p(cid:13) (c(c(cid:13)(cid:13)uu53(cid:13)(cid:13)(cid:13)(cid:13)::nn ||csppea2 5(cid:13),,(cid:13)rtppitsa 36f,,(cid:13)(cid:13)iippne 5(cid:13)7)d||(cid:13)(cid:13)(cid:13) (cid:13)<<)(cid:13) 33,, cc(cid:13)(cid:13)64::(cid:13)(cid:13) ||pp15 (cid:13)(cid:13),,pp2 6(cid:13),,(cid:13)pp3 7(cid:13)||(cid:13) >> 33(cid:13)(cid:13) p isassociatedwithandP = p ;p ;:::;p isthesetofbodies 7(cid:13) n-(cid:13)body static constraint:(cid:13) inivolved incj (pi2Pcj). Acjfterfthe1pa2rtitionnsgthatcontainobjects 4(cid:13) O(cid:13)2(cid:13)((cid:13)d=101 / 2)(cid:13)(cid:13) p5(cid:13)(cid:13) (c(cid:13)s7(cid:13)(cid:13):a |tAis,f ipe 4d|(cid:13) (cid:13))<(cid:13) 1.5, c(cid:13)8(cid:13): |A, p5 (cid:13)| > 1.5(cid:13) itcbniootimuoPnnpcdsjutoaeanfdrde.thitTedhheesenisztmsiefiizaeoeldfle,otshftthetcehaiercsscmtelueaatllwilnecotsiertcrcsiclreeicrclcttehilnseagtaerenaenlclcltohltohsesieneusgsepptaphelaelrrtatoihntbeidojsenelcsotpswaaeirrne-r 5(cid:13) M1(cid:13) (cid:13)u(cid:13)n(cid:13)i(cid:13)t(cid:13)obile poinOt(cid:13)(cid:13)3(cid:13)((cid:13)d=S1ta0ti1 c/ 2 )(cid:13)p(cid:13)Ooi(cid:13)4n(cid:13)(td(cid:13) =1)(cid:13) p6(cid:13)(cid:13) cc(((cid:13)(cid:13)uu19(cid:13)(cid:13)1(cid:13):nn(cid:13): |scA|Aae,tr, i ptspa5 f7(cid:13) |iin(cid:13) |e <)<d(cid:13) 1(cid:13))1(cid:13)..55,, cc(cid:13)1(cid:13)01(cid:13):2 (cid:13):| A|A, ,p p4 (cid:13)|7 (cid:13)|> > 1 1.5.5(cid:13)(cid:13) P .Basedonthisupperandlowerbound,theresultofmanycon- stcrajintcanbedetermined. Figure2:IllustrationofPartition-basedEvaluation For instance, the Partition Based NB Algorithm for the con- straints with the ”<” operator (p t;p t;:::;p t < d) is shown 1 2 n below. If the diameter of the sjmallest intersectjing circle (lower unsatisfied(Line4); ifallobjectsareintheinternalpartition,the bound)islargerthand(checkedbyfunctionIntersectinLine3), constraintissatisfied(Line6);iftheconstraintdoesnotbelongto c isunsatisfied.Ifthesmallestenclosingcircle(upperbound)has theabovetwocases,theconstraintisuncertain(Line8). Theso- j adiametersmallerthand(checkedbyfunctionEncloseinLine lutiontotheconstraintwiththe”>”operatorcanbederivedina 5),c issatisfied. Ifdisbetweenthislowerandupperbound,the similarfashionduetoitssymmetrywith”<”. j InFig.2,the1-bodystaticconstraintc andc aresatisfiedbe- constraint is uncertain (Line 8). Due to the symmetry, the con- 7 8 causew.r.t.circleO ,partitionS (containsp )isaninternalpar- straint p1t;p2t;:::;pnt > dcanbesolvedbyexchangingLine4 titionandS (cont5ainsp )isan25externalpart4ition. Similarly,we j j 45 5 withLine6. canverifiedthatc andc areunsatisfied. However, constraints 9 10 The result of an evaluation is valid as long as the objects re- c andc areuncertainbecauseS (containsp )isabounding 11 12 36 7 mainintheirpartitionsandthepartitionschemedoesnotchange. partitionsw.r.t.O . 5 Fig.2illustratespartition-basedevaluation. The3-bodyconstraint Algorithm Partition Based NBS(MobileObjectp) c (p ;p ;p <3,rightsideofthefigure)issatisfiedbecausethe d1iamj e1ter2of3thjecircleO whichenclosespartitionsS , S and 1. foreachConstraintcthatpisassociated 1 11 21 2. letP = p ;p ;:::;p bethesetofbodiesinc; Sun2s2a1tis(cfioendtabiencianugspe1t,hpe2dainadmpet3e)riosfpth8e(c<irc3l)e.OTh2ewchoincshtrianitnetrsce3citss 34.. if(9cp:ir2efsPu1l;tp=i22unesxattenirsgnfiaedl;partition) S21, S22 and S45 is p10 (> 3). However, the constraint c5 is 5. else if( pi P;pi internalpartition) uncertainbecausethediameterofthecircleO3enclosingS36,S45 6. 8c:r2esult=2satisfied; andS isp10andthediameterofthecircleO intersectingthese 7. else //inboundingpartition 56 4 partitionsis1,butthealertingdistance3isbetweenthelowerand 8. c:result=uncertain; upperbound(p10 > 3 > 1). Furthercomputationbasedonthe precise object position reveals that c5 is actually satisfied (circle ConstraintEvaluationAlgorithm:Alocationupdatetriggerscon- notshownforclarity). Butthiscannotbeestablishedwithparti- straintevaluation(i.e.,Evaluation).Wedistinguishthecaseswhere tioninformationalone. Similarly,onecanverifytheevaluationof thelocationchangeleadstoapartitionupdateandwherenosuch constraintsc ,c andc . 2 4 6 partitionupdateisincurred. Algorithm Partition Based NB(MobileObjectp) Forapartitionupdate,allconstraintsanobjectisassociatedwith 1. foreachConstraintcthatpisassociatedwith havetobeevaluatedusingthepartition-basedevaluationfunction 2. letP = p1;p2;:::;pn bethesetofbodiesinc; (Lines4,5)andtheuncertainconstraintsinvolvingthatobjecthave 3. if(Intefrsect((cid:0) ni=1gpi:current partition)>c:d)) tobeexplicitlyevaluated basedontheexactlocation positionin- 4. c:result=unsatisfied; formationafterwards(withMatch Uncertain Constraints 5. else if(Enclose((cid:0) ni=1pi:current partition)<c:d) in Line 6). The number of uncertain constraints (expressed as 6. c:result=satisfied; Uparti tionid) in the previous and current partitions are updated 7. else afterwards(Line7).Ontheotherhand,ifthelocationupdatedoes 8. c:result=uncertain; notincurapartitionupdate,onlyuncertainconstraintsneedtobe evaluated(Line9).Partition-basedevaluationisinvokedeverytime Partition-BasedEvaluationforn-bodyStaticConstraints:The anobjectchangesapartitionorwhenthepartitionisadjusted,but n-body static constraint, A;p1t;p2t;:::;pnt < d, is matchedif notforeverylocationupdate. j j and onlyifallpi (i 1::n) areinthecircleO withstaticpointA Algorithm Evaluation(MobileObjectp) 2 as center and das radius. Dependingon whether the partition is 1. p:previous partition=p:current partition; inside,intersecting,oroutsidetheboundaryofO,weidentifythe 2. p:current partition=Find New Partition(p); internal,bounding,andexternalpartitionsw.r.t. O(e.g.,theparti- 3. ifp:previous partition=p:current partition tioncompletelyinsideOisdefinedasaninternalpartitionandso 4. Partition Based6 NB(p); 5. Partition Based NBS(p); on.)ThedistancebetweenthemovingobjectandthestaticpointA 6. Match Uncertain Constraints(p); canbetrackedaccordingtothetypeofthepartitiontheobjectisin 7. updateU andU ; p:currentpartition p:previouspartition (i.e.,”internal”,”external”,or”bounding”). 8. else *ifp:previous partition=p:current partition* Thepartition-basedevaluation(Partition Based NBS)forcon- 9. Match Uncertain Constraints(p); straintswiththe”<”operatorworksasfollows: ifsomeobjectin 2.2 Adaptive SpacePartitioning P = p ;p ;:::;p isintheexternalpartition, theconstraintis 1 2 n f g Thestaticspacepartitioningdescribedabovesuffersinenviron- 1S representsthepartitionintheithrowandjthcolumn mentswhereboththeconstraintsandthemovementpatternsofthe ij objects are continuously changing. For many applications, con- wheretheyleadtothegreatestreductioninthenumberofuncertain straints are continuously updated based on changing user prefer- constraints(recordedbyset(cid:0)U inLine4)andthesmallestincrease ences(i.e.,insertsanddeletes.)Thus,apartitionschemeoptimized in partition update rate (recorded in (cid:0)PUR in Line 5). Only the tentativesplittinglinesinsidepartitions(cid:0) (cid:0) areconfirmed foronesetofconstraintsandmovementpatternmaynotbeopti- (Line6).ThefinalnumberofpartitionsspUlit\depPeUnRdsonthesizeof malforanothersetofconstraintsandadifferentmovementpattern. (cid:0) and(cid:0) thatarecontrolledbythewindowsizew,whichis U PUR Also,partitionupdatesincuroverheadwhenalargenumberofob- themainindicatoroftheadaptationspeedandisdirectlycoupled jects are moving between partitions, which is to be expected for with, and therefore adjustedaccording to, the linear combination applications with varying movement patterns. These characteris- oftheaveragespeedofmovementandtheconstraintupdaterate, tics arethe motivations to develop an adaptive spacepartitioning a1v+a2r.Thereductioninthenumberofuncertainconstraintsis computedinLine3.Fig.3illustratesthesplitadjustment. schemethatevolveswithchange. The AKDT and AMLG Index: We propose the adaptive k- Algorithm Split Adjust(intw) 1. foreachcandidateleafnodeS d-tree (AKDT) index and the adaptive multi-layer grid (AMLG) 0 i 2. S =S splitbytentativesplittinglines; indextoaccommodatethissituation. AKDTisfundamentallyak- i i 0 d-tree,exceptthatitpartitionsthespaceratherthantheobjectsin 34.. (cid:0) =4tUopSiw=praerdtiuticotniosnwoifthunhcigehrteasitncoUnstr;aintfr.SitoSi ; the space. In AKDT, eachleafnode representsa single partition 5. (cid:0)U =topwpartitionswithlowe4stPSUiR ; inthespace. Eachinternalnodestoresinformationaboutasplit- PUR 0 Si 6. replaceS withS ifS (cid:0) (cid:0) ; tinglineandrepresentstheunionofpartitionsofthe(leaf)nodes i i i U PUR 2 \ underneathit. Similarly, inAMLG, eachgrid atthelowestlayer presentsasinglepartitioninspaceandthehigherlayergridstores top w(cid:13) the informationof thegrid layout and representsthe union ofall Partition i(cid:13)1(cid:13)Partition i(cid:13)2(cid:13)Partition i(cid:13)3(cid:13) partitionsunderneaththislayer. AKDTandAMLGadaptivelyset U(cid:13)i1(cid:13)(cid:13) U(cid:13)i2(cid:13)(cid:13) U(cid:13)i3(cid:13)(cid:13) >(cid:13) andrelinquishthesplittinglines. Candidates(cid:13) (sorted)(cid:13) The adaptive space partition algorithm consists of two stages, Partition j(cid:13)1(cid:13)Partition j(cid:13)2(cid:13) Partition j(cid:13)3(cid:13) namely,theinitialpartitioningstageandtheadjustmentstage.The PUR(cid:13)j1(cid:13)(cid:13) PUR(cid:13)j2(cid:13)(cid:13) PUR(cid:13)j3(cid:13)(cid:13) <(cid:13) initialpartitioningsimplydividesthewholespaceintosmallcells top w(cid:13) with arbitrary granularity. The adjustment stage tunes the parti- Partitions for Adjustment(cid:13) tionschemewithanadjustmentfrequencyproportionaltothelin- ear combination of the average velocity over all moving objects Figure3:SplitAdjustment tracked,v,andtheaveragerateofconstraintupdates,r,i.e.,a v+ 1 a r,forconstantsa anda . Theaveragevelocityisderivedfrom 2 1 2 TheMerge AdjustAlgorithmperformsaninverseoperationto the location updates recorded over time. In this way, the parti- thesplitalgorithm.Itremovesthecurrentsplittinglinesandmerges tionschemeevolves asthemovement patternand constraintload theleafnodepartitions. Themergealgorithmaimsatreducingthe change. We formally show with Lemma 2 in Section 3 that the partitionupdaterateatthecostofaminorincreaseinthenumber splitting of a partition can reduce the number of uncertain con- ofuncertainconstraints. straintsandcanincreasethepartitionupdaterate,whilethemerg- Algorithm Merge Adjust(intw) ing of partitions can reduce the partition update rate and can in- 1. foreachcandidatesecondlevelnodeS i 0 crease the numberof uncertain constraints. The objective is to 2. S =S withsplittinglinestentativelyremoved; i i balancethetrade-offbetweensplittingandmergingsuchthatboth 3. U =increaseofuncertainconstraintfr.S toS 0; the number of uncertain constraints and the partition update rate 4. (cid:0) =4topSiwpartitionswithlowest U ; i i decreasetothegreatestextentpossible. 5. (cid:0)UPUR=topwpar0titionswithhigh4estPSiURSi; Fortheefficientadjustment,eachpartitionSi (iisthepartition 6. replaceSiwithSi ifSi (cid:0)U (cid:0)PUR; 2 \ ID)maintainsthefollowingadditionalinformation:1.PUR ,the Si OverheadReductionforSplit&MergeCountingthechange estimatedpartitionupdaterateinsideS .Itequals(cid:26) v L , i Si(cid:3) Si(cid:3) Si inthenumberofuncertainconstraintsbyrecomputingallthecon- where(cid:26)Si,vSi andLSi aretheobjectdensity,theaverageveloc- straints associated with the partition (Line 3 in Split Adjust and ityandthetotallengthofthesplittinglinesinsideSi,respectively. Merge Adjust)istoocostly.Lemma2inSection3showsthatthe 2. U : Thenumberofuncertainconstraints associatedwith the Si uncertain constraints after the split are a subset of the uncertain objectsinpartitionS . Theadjustmentprocessiscomposedofthe i constraints before splitting, therefore, only the original uncertain splitSplit AdjustAlgorithmandthemergeMerge AdjustAlgo- constraintsareconsideredwhencomputingthenumberofuncertain rithm. The split algorithm creates new smaller partitions from a constraints after splitting. A similar property holds for merging. leaf node partition by adding tentative splitting lines(Line 2) in- Thisreducestheoverheadofthesplitandmergeprocess,however, sidethecandidateleafnode.ForAKDT,thetentativesplittingline therearebetterwaystofurtherreducethiscost. generatedinthesplitprocessisrandomintermsofitsorientation Anuncertainconstraintmaybeassociatedwithmultipleobjects (horizontalorvertical)anditspositionisstrict(e.g.,bisectsthepar- indifferentpartitionsandaddingsplittinglinesintothesepartitions tition)orfollowssomegivendistribution(e.g.,uniformornormal mayhavedifferenteffectsonthisconstraint.Forexample,inFig.4, distribution). Therandomizationofthesplittinglinesreducesthe c (p , p , p < 6) isassociatedwithpartitionsS , S andS 1 1 2 3 1 2 4 potentialforoscillationofthealgorithm. ForAMLG,thesplitting j j (where p , p and p are located). c is uncertain because the 1 2 3 1 lines do not have thisdegree offreedom, they have todivide the circle, O , enclosing these partitions has a diameter p52 (> 6) 1 spaceintoequal-sizedpartitions.However,theobjectsineachpar- andthecircle,O ,intersectingthesepartitionshasadiameterp10 2 tition are in the same grid file indexed by a hashtable. The split (< 6). After splittingS , byaddingtwolinesegmentsl andl 1 1 2 processreducesthenumberofuncertainconstraints,butitalsoin- 0 (dashedlines),p fallsinsidepartitionS andtheenclosingcircle ducesmore partitionupdateoverhead. Weevaluate thistrade-off 1 1 becomesO .O ’sdiameterisp34(<6),thereforec issatisfied. lateron. 3 3 1 IfwefurtherpartitionS ,whichcontainsp ,c remainsuncertain The algorithm only commits the splitting lines in the partition 2 2 1 becauseS isboundingneitherO norO . Mergingalltheparti- 2 1 2 tionsinS rendersc uncertainagain. However,mergingS and bodystaticconstraintcanbederivedinasimilarfashion[25]).The 1 1 2 S doesnothaveanyeffectonc . Thepartitionsplittingprocess firstandsecondcolumninthetablearethedescriptionoftwocon- 3 1 may affect the result of the constraint when the partition bounds straints, the third column are the conditions based on which the intersecteithertheenclosingcircleortheintersectingcircle(i.e., conflictingandharmoniousrelationisidentified. Thelastcolumn S boundsbothcircles). Thepartitionmergingprocessmayaffect specifiesthetransitconditionbetweenthetwoconstraints. Forin- 1 theresultoftheconstraintwhenthepartitionafteramergeisin- stance, the relationamong c and c (if c is satisfied, c is also 3 4 3 4 tersectedbytheenclosingorintersectingcircle(i.e.,S intersects satisfied) is identified with the rule in Line 1, because c and c 1 3 4 withO ).Wecallaconstraintsplitaffectedw.r.t.acertainpartition havethesamealertingdistanceandtheobjectsetforc isasuper- 3 3 iftheconstraintisuncertain,andhassomebodiesinvolvedinside setoftheobjectsetforc . 4 thepartition,andthepartitionboundseithertheintersectingcircle Table1:ConflictingandHarmoniousRules(ExplanationinText) ortheenclosingcircle. Aconstraintismergeaffectedw.r.t. acer- c1 c2 conditions transitcondition tainpartitioniftheconstraintissatisfiedorunsatisfied, hassome P1<d1 P2<d2 d1(cid:20)d2,P1(cid:19)P2 c1issatisfied! bodiesinvolved insidethepartition thatis beingmerged, and the P1>d1 P2>d2 d1(cid:21)d2,P1(cid:18)P2 c2issatisfied mergedpartition(asecondlevelnode)isintersectedbyeitherthe P1<d1 P2>d2 d1(cid:20)d2,P1(cid:19)P2 c1issatisfied! enclosingortheintersectingcircle. P1>d1 P2<d2 d1(cid:21)d2,P1(cid:18)P2 c2isunsatisfied Intheaboveexample,c issplitaffectedw.r.t.S andmergeaf- P1>d1 P2<d2 d1<d2,P1(cid:19)P2 c1isunsatisfied fectedw.r.t.S10.Sincethes1plitaffectedconstraintsa1retheonlycon- PP11<<dd11 PP22><dd22 dd11>(cid:21)dd22,,PP11(cid:18)(cid:18)PP22 !c1ics2uinsssaatitsisfifieedd straintswhoseresultsmightchangeinthesplitadjustment, when P1>d1 P2>d2 d1(cid:20)d2,P1(cid:19)P2 !c2isunsatisfied computingthereductionoftheuncertainconstraintsafterthesplit- ting (Line 3 in Split Adjust), only the split affected constraints Fortheconditioncolumn,itmustholdthattheobjectsetofone are considered because no other constraint changes its result due constraintisthesubsetorthesupersetoftheobjectsetofanother tothesplit. Similarly, onlymerge affectedconstraintshavetobe constraint.IfP isnotasubsetorasupersetofP andyettheirin- 1 2 considered(Line3inMerge Adjust)forcountingtheincreasein tersectionP (=P P )containsmorethantwoobjects,thereis 1;2 1 2 uncertainconstraintsafteramerge. Thisgreatlyreducestheover- \ stillapotentialdependency betweentheseobjects. Consequently, headofrecountinginthesplitandmergeprocesses. theresultofoneconstraintmaybepartiallyvaluablefortheeval- Also, since the purpose of splitting is to reduce the uncertain uationofotherconstraints. Tofullyexploitthecorrelationofcon- constraints, the candidate nodes for a split are selected such that straints with intersecting object sets, the notion of a virtual con- theycontainthelargestnumberofsplitaffectedconstraints(Line1 straintisdeveloped.Avirtualconstraint,c ,involvestheintersect- v in Split Adjust). This improves the performance of the partition ingobjectsP (=P P ).Therulesthatdefinethegenerationof 1;2 1 2 adjustmentbecauseonlytheconstraintsthatmaybeaffectedbythe \ c aregiveninTable2.(cid:15)belowdenotesthesmallestpositivevalue v splitarecounted.Thepurposeofmergingistoreducethepartition allowedbythecomputer.Itishardwaredependent. update rate, therefore the candidate nodes (second level partition Table2:VirtualConstraintGenerationRules S )formergeareselectedsuchthatthesenodescontainthelargest i c1 c2 cv transitcondition estimatedpartitionupdaterate,PURSi(Line1inMerge Adjust.) P1>d1 P2>d2 P1;2>max(d1;d2) cvissatisfied!c1 andc2aresatisfied O(cid:13)1(cid:13)(d=521 / 2)(cid:13)(cid:13) P1<d1 P2<d2 P1;2>max(d1;d2) cvissatisfied!c1 2(cid:13) (cid:13)u(cid:13)n(cid:13)i(cid:13)t(cid:13)S(cid:13)1(cid:13) l(cid:13)21(cid:13) (cid:13)u(cid:13)n(cid:13)i(cid:13)t(cid:13)(cid:13) l(cid:13)1(cid:13)p1(cid:13)(cid:13) OS(cid:13)3(cid:13)1(cid:13)((cid:13)’d(cid:13)=3O41 (cid:13)2/ 2(cid:13)()(cid:13)d(cid:13) =101 / 2)(cid:13)(cid:13) M1Sais(cid:13)n2(cid:13) oBu(cid:13)(cid:13)d bwne il(cid:13)lci(cid:13)2felole(cid:13), rnprceto(cid:13)o1a (cid:13) tsiib nnpmet(cid:13).l(cid:13) ciaAtotkifnmeteg etr h SsSi s(cid:13)1(cid:13)s(cid:13)1 (cid:13),a(cid:13) d icstifi(cid:13)1 sf(cid:13):sef pi|repel1id tn(cid:13), (cid:13).pwc 2S e,(cid:13)itp.ph(cid:13)3 l |(cid:13)i(cid:13) tl(cid:13)1<ti(cid:13)n 6g(cid:13)(cid:13) PP11><dd11 PP22><dd22 P+P11(cid:15);;(22(cid:15)<<>mm0aa)xx((dd11;;dd22)) accaannnvvdddiissccc222uunnaaassrrraaeeettiisuussannfifitsseeiaasddfittii!!essdfifieeccdd11 p2(cid:13)(cid:13) P1>d1 P2<d2 P1;2>max(d1;d2) cvissatisfied!c1is p(cid:13) 2(cid:13) Merging S(cid:13)1(cid:13)' (cid:13)by removing (cid:13)l(cid:13)1(cid:13) and (cid:13)l(cid:13)2(cid:13),(cid:13) satisfied,butc2isnot 3(cid:13) changes c(cid:13)1(cid:13) from (cid:13)satisfied(cid:13) back to(cid:13) P1>d1 P2<d2 P1;2<max(d1;d2) cvissatisfied!c1is S(cid:13)2(cid:13) S(cid:13)3(cid:13) S(cid:13)4(cid:13) unnoc eefrfteacint (cid:13)o, nb uct(cid:13)1 m(cid:13).(cid:13) erging S(cid:13)2(cid:13) and S(cid:13)3(cid:13) has(cid:13) +(cid:15)((cid:15)>0) satisfied,butc2isnot Toamortizetheevaluation cost, asecondarygraphstructureis Figure4:Split/MergeAffectedConstraints usedtoindexconflictingandharmoniousconstraints. Thisgraph structureisconstructedandincrementallyupdatedwhennewcon- 2.3 Conflicting andHarmonious Constraints straints are inserted or removed from the system. At the start, There can be constraints that are in conflict with each other. toconstructthegraphstructure,eachconstraint(includingvirtual For instance, if c (p t;p t > d) is satisfied, c (p t;p t < constraints) are regarded as nodes in the graph. Each constraint 1 1 2 2 1 2 j j j j d)must be unsatisfied. Similarly, constraints can alsobe in har- connects to its associated conflicting and harmonious constraints monywitheachother. Ifaconstraintissatisfied(unsatisfied),this (othernodes)withunidirectionallinks(representingtheasymmet- could imply that another constraint is satisfied (unsatisfied). For ricrelation).Eachlinkisappropriatelylabeledwithatransitcondi- instance,ifc (p t;p t;p t < d)issatisfied,thenitfollowsthat tion,forexample,satisfied unsatisfied(shorthandedass u) 3 1 2 3 c (p t;p t <j d) is also sjatisfied. The conflicting and harmo- etcetera.Thenodeswiththe!sameneighborsandsametransit!con- 4 1 2 j j nious relationis asymmetric. c is unsatisfied mightnotindicate ditionlabelsaremergedintoacompoundnode. Ifaconstraintis 2 that c is satisfied. Also, even if c is satisfied, c might stillbe removed,thecorrespondingnodemayneedtobedeleted. 1 4 3 unsatisfied. Forthediscussionbelow, weassumeconstraintc is In the evaluation stage, after the result for one of the indexed 1 associatedwithobjectsetP andconstraintc is associatedwith constraints is computed, a breadth-first transversal of the graph 1 2 objectsetP etcetera. startingfromthatconstraintisperformed,immediatelygivingrise 2 Conflictingandharmoniousrelationsforn-bodyconstraintsare totheresultsofassociatedconstraints(i.e.,representedbylinked identified with asetofrulessummarized inTable1(rulesfor n- nodes in the graph.) Virtual constraints are evaluated based on adaptivespacepartitioning,justasanordinaryconstraint,butthey tionandarecapableofsimplecomputationforcheckingwhether have higher evaluation priority and will always be evaluated be- coordinatesareinsideacertainpartition(rectangularregion).2 foretheoriginalconstraintsbasedonwhichtheyareconstructed. If the currentresult ofthe constraint basedon the partition in- Conflictingandharmoniousconstraintmanagementisorthogonal formationissatisfied,wesetacirclewiththealertingdistanceas to partition-based pruning performed by the indexes. The graph thediametersuchthatitcoversthemaximalnumberofpartitions index canpruneuncertainconstraintswhichspacepartitioningis includingallthepartitionscontaininginvolvedobjects. Then,the incapableofpruning. partitionscoveredbythiscircleareregardedasasaferegionand InFig.5,wegiveanexampleofconflictingorharmoniouscon- returnedtothedevice, whichdoesnotneedtoupdateitslocation straintsrepresentedbyourgraphindex. Thefiveconstraintsbeing aslongasitismovingwithinthesaferegion,becauseinthiscase indexedareshowninnodeN ,N ,N N andN .Theconstraints theconstraintsarealwayssatisfied(seeFig.6(A)). 1 3 4 5 6 innodeN andN sharethesameobjectsp andp ,thereforea If the result is unsatisfied, we first identify the objects p and 3 4 2 3 i virtualnodeN representingconstraint p ;p >disconstructed p (called sentinel objects) that are located inside two partitions 2 2 3 j j j (ruleinLine2ofTable2). IfthevirtualnodeN issatisfied,N withadistancegreaterthanthealertingdistance. Then, abisect- 2 3 and N are unsatisfied (unidirectional edge s u from N to ing stripe is set. It is defined as a stripe with width equal to the 4 2 ! both N and N ). Also, if N or N is satisfied, then N must alertingdistance. Itbisectsthedistancebetweenthetwopartitions 3 4 3 4 2 beunsatisfied (unidirectionaledges ufromboth N and N (seeFig. 6(B)).Aslong as eachsentinel object ismoving within 3 4 ! to N ). Since the two unidirectional edges between N and N thepartitionsonitssideofthestripe(regardedassaferegion),the 2 2 3 (N )havethesamelabel(s u),theyarecombinedasasingle constraints are unsatisfied. Therefore, p and p track their own 4 i j ! bi-directional edge. Observe thatN and N areconnectedwith positionanddonotneedtoupdatetheirlocationunlesstheygobe- 3 4 the edgesofthe samelabel toothernodes, therefore they canbe yondthesaferegionontheirsides. Atthesametime,alltheother combinedtoformacompoundnode.Alltheothertransitedgesare objectswaitfortheirpositionprobe. Uponnotificationthateither basedontheruleslistedinTable1. p orp areoutsidethesaferegion,theconstraintmatcherforcesall i j Anexampleofconstraintprocessingisthatwhentheobjectp theinvolvedobjectstoupdatetheirlocations,andvalidatesthenew 2 updatesitslocation,thevirtualconstraint p ;p > dinN will sentinelobjectsandthestripe. Itispossiblethatsuchsentinelob- 2 3 2 j j beevaluatedfirst(givenitisuncertain)becauseavirtualnodehas jectsdonotexist. Inthiscase,thedeviceupdatesitslocationwith higher evaluation priority. If it is unsatisfied, then the constraint somedefaultrate. Thissaferegionpolicyisverycosteffectivein in N is satisfiedbecausethe transit conditionfrom N toN is thatitcapturesmostconstraintmatcheswithsignificantreduction 1 2 1 u s. SincethereisnoedgecomingoutfromN labeledwith oftherequiredlocationupdates. 1 ! s , thetransversalterminates. Ontheotherhand,ifthecon- ! (cid:3) straintsinN2 issatisfied,thenconstraintsinN3,N4 andN5 must Stripe bisecting the distance bw.(cid:13) beunsatisfied(s u). Alerting distance(cid:13) partitions containting p(cid:13)i(cid:13) and p(cid:13)j(cid:13) ! p(cid:13) i(cid:13) |p2(cid:13)N,(cid:13) p(cid:13)13(cid:13)(cid:13)(cid:13)|<du(cid:13)(cid:13)+ (cid:13)(cid:13) (cid:13)s(cid:13) (cid:13) (cid:13)s (cid:13)(cid:13)s(cid:13)u(cid:13) (cid:13) (cid:13)V|upi(cid:13)rt2(cid:13)u,(cid:13)aN lp N3(cid:13)2b(cid:13)(cid:13)(cid:13)(cid:13)i(cid:13)|od>(cid:13)d(cid:13)ir(cid:13)ede(cid:13)(cid:13)c(cid:13)(cid:13)(cid:13)t(cid:13)iso(cid:13)s(cid:13)n (cid:13)(cid:13)(cid:13) (cid:13)a(cid:13) (cid:13)(cid:13)luu(cid:13)(cid:13) (cid:13)e(cid:13)(cid:13)d(cid:13)g(cid:13)e|(cid:13)p2(cid:13)(cid:13),| ppC 13(cid:13)s(cid:13)(cid:13),o, (cid:13) m pp (cid:13)N bu(cid:13)42(cid:13)(cid:13)o,(cid:13) |(cid:13)(cid:13)3 u< (cid:13)p n 3dd(cid:13)(cid:13)| (cid:13)n<oddse(cid:13)(cid:13)s (cid:13)(cid:13)u (cid:13)(cid:13) (cid:13) (cid:13) (cid:13) (cid:13)s(cid:13)s (cid:13)(cid:13)(cid:13)u (cid:13)u(cid:13) (cid:13)(cid:13) u(cid:13)(cid:13)|p1(cid:13)(cid:13),p s(cid:13)p (cid:13)|5 (cid:13) u(cid:13)p2(cid:13)|(cid:13), <4(cid:13) NN, (cid:13) p d 3p(cid:13)(cid:13)56(cid:13)(cid:13) 5,(cid:13)(cid:13) (cid:13) (cid:13)| p> 4(cid:13)(cid:13)d(cid:13) Safe region(cid:13)FpM1(cid:13)i(cid:13)og(bAuil)er(cid:13) peO3(cid:13)p(cid:13)b62(cid:13)j(cid:13)e:ctS(cid:13) afeRSaefeg rieognionC foor mp(cid:13)i(cid:13)puA(cid:13)l(cid:13)te(cid:13)(cid:13)r(cid:13)ti(cid:13)n(cid:13)ag(cid:13)(cid:13) d(cid:13)(i(cid:13)s(cid:13)(cid:13)ta(cid:13)Bn(cid:13)tc(cid:13)e(cid:13))i(cid:13)onSafe prej(cid:13)(cid:13)gion for p(cid:13)j(cid:13) N(cid:13)4(cid:13) u u(cid:13) 2.5 ExtendedConstraints s(cid:13) (cid:13) (cid:13) (cid:13)u(cid:13) s s(cid:13) d (cid:13) +>(cid:13) d (cid:13)u(cid:13): (cid:13)unsatisfied(cid:13) s(cid:13): (cid:13)satisfied(cid:13) Inthissubsection weillustrate how thepartition-basedevalua- tionalgorithmcanbeappliedtootherconstraints. Theillustration is based on a continuous reverse range query (CRR) and a con- Figure5:IndexforConflictingandHarmoniousConstraints tinuousreversek-nearest neighborquery(CRKNN), whichare definedasfollows: 2.4 Location UpdatePolicy 1. GivenarectangularregionR,aContinuousReverseRange Thelocationupdatepolicymanagestheconsistencybetweenthe query,CRR(R;p )continuouslycheckswhetheramoving i lastpositionassumedbytheconstraintsolverandtheactualposi- objectsp isinsideR. i tionofthemovingobject.Eachlocationupdateexertscertainload ontothesystem(e.g.,network,power,computeresources,andeco- 2. GivenastaticpointA,aContinuousReversek-NearestNeigh- nomical.Thelocationupdatepolicyistherulethatspecifieswhen borquery,CRKNN (A;p ),continuouslycheckswhether i theupdateshouldbescheduled. Thepolicybalancesthetrade-off Aisoneoftheknearestneighborsofp . i betweenthe resourcesconsumedand the accuracy represented in Inthediscussionbelowwerefertothesequeriesasconstraintsto thesystemandachievableintheresults. emphasize the continuous character of the problem, i.e., given a Inpractice,therearemanydifferentwaystoobtainlocationdata potentiallylargesetofconstraintsandchangingobjectlocationin- andpowerisaconcernthatrequiresthelocationupdatepolicytobe formation, wearelookingforthematchedconstraints. Asinthe adjustedtothecharacteristicsofthemobiledevice.Here,weadopt previoussubsection,theobjectiveofthepartition-basedevaluation thenotionofasaferegiontodefineadevice-dependentlocationup- datepolicy[9].Theobjectivesaretomaintainup-to-dateconstraint 2ThedevicecouldeitherobtainitslocationviaGPSorrequestit results,andreducewirelesscommunicationandre-evaluationcost. fromthenetworkinginfrastructure.Bothareviablemodelsinprac- Weassumethatthemobiledevicesareabletotracktheirposi- tice. is to reduce the number of constraints that have to be evaluated with atotalof omoving objects. Supposethateachconstraint is againstprecisepositioninformation. associatedonaveragewithoobjectsandamongthecconstraints, Withoutlossofgenerality,supposethatp islocatedinsidepar- u are uncertain. The model estimates the matching cost for in- i titionS . Thepartition-basedevaluationforCRR(R;p )works memory and I/O-incurring environments and formalizes algorith- pi i asfollows. IfS isdisjointwithR,theconstraintisunsatisfied. micproperties. Duetospacelimitations,theproofsofallthethe- pi IfS iscompletelyenclosedbyR,theconstraintissatisfied.Oth- orems and lemmas below are omitted. They can be found inthe pi erwise(S intersectsR),itisuncertain. Fig.7showsthreerange technicalreport[25]. pi queries, R , R and R . Since partition S , which accommo- 1 2 3 53 3.1 Cost forIn-memory Processing dates p , is disjoint with R , the constraint CRR(R ;p ) must 1 1 1 1 beunsatisfied. CRR(R ;p )issatisfiedsinceS iscompletely AllcomputationsaredoneinmainmemoryandnodiskI/Oisin- 2 1 53 insideR andCRR(R ;p )isuncertainsinceR partiallyinter- curred. Onaverageeachobjectisassociatedwithco=oconstraints 2 3 1 3 sectsS . anduo=oofthemareuncertain. Sincethefrequencyoftheparti- 53 tionadjustmentprocessesismuchlowerthanthelocationupdate 1(cid:13) 2(cid:13) 3(cid:13) 4(cid:13) 5(cid:13) 6(cid:13) 7(cid:13) Mobile point(cid:13) frequency, thecostformaintainingtheindex data structureis ig- p(cid:13) nored. Theconstraintevaluationcostiscomprisedoftwofactors: 1(cid:13) 2(cid:13) A(cid:13)2(cid:13) Static point(cid:13) thecostforevaluatingaconstraintbasedonpreciselocationposi- S(cid:13)15(cid:13) 234(cid:13)(cid:13)(cid:13) SS(cid:13)(cid:13)5111Or(cid:13)(cid:13)(cid:13)(cid:13)r(cid:13) A(cid:13)1(cid:13)Rth(cid:13)(cid:13)2(cid:13)e(cid:13)(cid:13) n(cid:13)S(cid:13)e(cid:13)a(cid:13)1(cid:13)r1e(cid:13)(cid:13) (cid:13)s (cid:13)t (cid:13) d(cid:13) O(cid:13)i(cid:13)st(cid:13)t(cid:13)(cid:13)ar(cid:13)h(cid:13)(cid:13)n(cid:13)e(cid:13)c(cid:13) (cid:13)e(cid:13)n(cid:13) (cid:13)e(cid:13)b(cid:13)a(cid:13)wb(cid:13)r(cid:13).(cid:13)w(cid:13)eR (cid:13)(cid:13)S(cid:13)s(cid:13).(cid:13) (cid:13)(cid:13)13(cid:13)t(cid:13)S1(cid:13)((cid:13)(cid:13)f(cid:13)(cid:13)(cid:13)1(cid:13)ua1(cid:13)(cid:13)r(cid:13)n(cid:13)(cid:13)ta(cid:13)d(cid:13)h(cid:13)n(cid:13) (cid:13)e(cid:13)S(cid:13)d(cid:13)s4(cid:13)(cid:13) (cid:13)t(cid:13)7(cid:13)S)(cid:13)(cid:13) (cid:13)1(cid:13)(cid:13)d(cid:13)5(cid:13)i(cid:13)(cid:13)s(cid:13)t(cid:13)a(cid:13)An(cid:13)c(cid:13)4(cid:13)e(cid:13)(cid:13)S(cid:13)47(cid:13) CCCCCCRRRRRR222RRRNNN(cid:13)(cid:13)(cid:13)(((RRRNNN(cid:13)(cid:13)(cid:13)321(cid:13)(cid:13)(cid:13)((((cid:13)(cid:13)(cid:13) AAA,,,ppp(cid:13)(cid:13)(cid:13)431111 (cid:13)(cid:13)(cid:13) (cid:13)(cid:13)(cid:13)))),,,(((ppp(cid:13)(cid:13)(cid:13)usu222 (cid:13)(cid:13)(cid:13)a)))nn(((tcs(cid:13)(cid:13)(cid:13)uusiseaannfrttisciteisasaedffitrini(cid:13)eit)esa(cid:13)(cid:13)d)df(cid:13)ii(cid:13)n)e(cid:13))(cid:13)(cid:13)(cid:13))d(cid:13)(cid:13))(cid:13) taSrtbihetaouicesonpenenpiidvntocheofsoedoens,rtctmnhpwoeaaswhtttoieffoflnooonwrrca(aanhadtiteoiclionobmhnocjeetaidenctdaditcotuuuaanrprsatdautCpikapoateodrnestsas,itatttieilpt,ouspadn)pruatoauornxriptdtniaidmgtltiahooatoeefntnespl(el.yadlorue(cid:11)Itcnniftaiopitteotiraeoonocdfn-chbeatuaissempssCveidenadaolgteueseqtvatsiutapmiaulaourel)nes-,. 5(cid:13) A(cid:13)3(cid:13) p1(cid:13)S(cid:13) (cid:13)53(cid:13) R(cid:13)1(cid:13) 1(cid:13) (cid:13)u(cid:13)n(cid:13)i(cid:13)t(cid:13) f(u).o=Wto)i(cid:11)thl.thNios,tethtehaatbooltveislothceataiovneruapgdeautepdcaotsetfcraenqubeensciym(pdleifinoedtetdoa:s Cost =uo(cid:11)f (1) lu When the object is moving into a new partition, all the con- Figure7:CRRQueryandCRKNNQuery straintsitis associatedwitharesubjectedtopartition-basedeval- uation. Ifpartition-basedevaluationincurs(cid:12) processingtime,the The partition-based evaluation for CRKNN(A;pi) works as cost of apartition update perunit of time is (co=o)(cid:12)p. p=l is the follows. SupposeAisinsidethepartitionSA andpi islocatedin probabilityofanobjectupdatingitspartition(denottedasPpu)and Spi.ThesystemmaintainsacurrentlistofkNNsandthepartitions thepartitionupdatecostcanberewrittenas: wheretheyarelocated(supposetheyareSlj(1 (cid:20) j (cid:20) k).) Ifthe Costpu =co(cid:12)fPpu (2) nearest distance between Spi and SA is greater than the furthest Thevalueof(cid:11)and(cid:12) dependonthehardwareusedandcanbe distance between Spi and Slj, or more formally, infp2Spi;q2SA estimatedexperimentally. FromEq.1andEq.2,itfollowsthatthe jjp;qjj2 > max1(cid:20)j(cid:20)k supp2Spi;q2Sljjjp;qjj2, then A can not averagecostperunitoftimefortheadaptivealgorithmisgivenby: beoneofthek nearestneighborsofp , andCRKNN(A;p )is Cost =Cost +Cost =uo(cid:11)f +co(cid:12)fP (3) i i adapt lu pu pu unsatisfied.Letr=sup p;A andO isacirclewithras The per unit of time cost for the na¨ıve approach is simply the theradius.TheniftheMpin2kSopwijsjkisujmj2ofS randO (S O )3 costforevaluatingallconstraints: pi r pi (cid:8) r Cost =co(cid:11)f (4) containsatmostkneighbors,CRKNN(A;p )mustbesatisfied. na(cid:127)(cid:16)ve i InEq.3,ifP issmall,thesecondtermcanbeignored,andthe Ifaconstraintisneitherunsatisfiednorsatisfied,itisuncertain. pu costcanbeapproximatedto: InFig.7,supposethecurrenttwonearestneighborsofmoving u objectp2 areA1 andA2. Sinceinfp2S11;q2S47(p;q) = p29 > Costadapt(cid:25)uo(cid:11)f = cCostna(cid:127)(cid:16)ve (5) max(sup p;q )= p26, A cannotbeone Discussion:Ouralgorithmoutperformsthena¨ıveapproachwhen p2fS22;S15g;q2S11 jj jj2 4 ofp2’s2nearestneighbors,CR2NN(A4;p2)isunsatisfied.How- Costadapt < Costna(cid:127)(cid:16)ve. However,withstaticspacepartitioning, ever,constraintCR2NN(A ;p )mustbesatisfied,becauseA is thiscannotbeguaranteed.Forinstance,ifthemajorityofthecon- 1 2 1 theonlyneighborinsidetheregionS11(cid:8)Orwherer=supp2S11 straintsareuncertain(largeru)orPpuistoohigh,thentheperfor- p;A . AnditcanbeverifiedthattheconstraintCR2NN(A ; manceofthealgorithmdegenerates.Givenastaticspacepartition- 1 2 3 jj jj p2)isuncertain. Infact,ifp2ismovingtothebottom-leftofS11, ing,Ppudependsonlyonthemovementpattern(e.g.,thevelocity A willreplaceA tobethesecondnearestneighborofp . The andtheposition)oftheobjectswhilethenumberofuncertaincon- 3 2 2 resultofconstraintCR2NN(A ;p )istrulyundeterminedunless straintsdependsonthecorrelationofthepositionofobjects.There 3 2 theprecisepositionofp2isgiven. isnodirectrelationshipbetweenPpuandthenumberofuncertain Bear in mind that for location change within the partition, ex- constraints.Also,derivingtheoptimalpartitionschemeisdifficult, plicit computation is only required for the constraints previously becausethereisnodirectdependencybetweenP andtheparti- pu classified as uncertain and the constraint classification only hap- tionscheme.Forexample,evenifthespaceispartitionedsparsely, pensinresponsetoapartitionupdate. theobjectcouldstillgeneratealargenumberofpartitionupdatesby movingback-and-forthacrossasplittingline.Ontheotherhand,an 3. ANALYTICALMODEL objectcouldmovefastwithoutgeneratinganypartitionupdatesin adenselypartitionedregionbyremaininginsideasinglepartition. In this section, we develop an analytical model for the cost of Weaddressthischallengeinthenextsubsection. evaluatingn-bodyconstraints. Theanalysisforn-bodystaticcon- straintsissimilar.Inourmodel,atotalofcconstraintsisassociated 3.2 Determiningthe OptimalPartitionSize 3M M = p+qp M ;q M ,wherep+qisthevector Inthissectionwedevelopamodeltoestimatetheoptimalparti- 1 2 1 2 sumo(cid:8)fthevectforspajnd2q. 2 g tionsize. Theideaistosampleanumberofpartitionschemesand selectthebestone(i.e.,theonethatleadstoasmallerCost .) constraints. By continuousadjustment, the algorithm adapts toa adapt Thisiswhatouralgorithmdoesbytentativelysplittingandmerg- non-uniformenvironmentandevolveswiththechangeofthemove- ing partitions to determine a partition change that ultimately re- mentpatternsandreachesalocallyoptimalpartitioning. duces the overall cost. The change aimsto reduceboth P and pu 3.3 Cost underSecondary StorageAccess thenumberofuncertainconstraints,andaimstobalancethetrade- offbetweenthem. Ouranalyticalmodelisbasedonthefollowing For applications that need to manage a large number of loca- assumptions: tionconstraintswithalargenumberofmovingobjects,secondary 1. Allobjectsfollowtherandommovementpattern.Asaresult, storageaccesscostofthealgorithmmaybecomeaperformancede- thedistributionoftheobjectsontheplaneisuniform. gradingfactor. Forinstance,objectsmaybeassociatedwithlarge 2. Thepartitionsareequal-sizedsquareswiththelengthofeach profiles, as is common in telecommunicationapplications, or the sideequaltoa,whichismuchsmallerthantheextent4ofthe applicationmaybecollocatedwithotherapplications,thusnothave wholespaces(a s). exclusiveaccesstomainmemory. TheI/Ocostforaccessingdata (cid:28) insecondarystorageis typicallyordersofmagnitudehigherthan 3. Alltheconstraintshaveauniquealertingdistances,denoted accessing data residing in main memory and it becomes the ma- asd(d s). (cid:28) joroverhead. Thereforereducingthenumberofsecondarystorage First,weestablishthatthesizeofthediameterofthesmallestcircle accessesbecomesaprimaryconcerninthisenvironment. enclosingasetofobjectsisuniformlydistributed. Therefore,the Foreverysecondarystorageaccess,dataisfetchedinpagesrather probabilityofaconstraintbeinguncertain(satisfiedorunsatisfied) than in records and each access to secondary storage transfers a is an expression of the partition size, space size and the alerting constantamountofdataintomemory. TheI/Ocostismeasuredas distance.ThisiscapturedinLemma1. thenumberofaccessestothedataonthesecondarystoragedevice. LEMMA 1. Under random movement of objects in Euclidean Foroptimizingsecondarystorageaccesses,ouralgorithmaimsat 2Dspace,thedistributionofthesizeofthediameterofthesmallest holdingasmanyuncertainconstraintsaspossibleinmainmemory circleenclosingasetofobjectsisuniform.Therefore,aconstraint because they are the most frequently accessed data. Constraints isunsatisfiedwithprobability1 add=ae,issatisfiedwithproba- thatdonotfitintomainmemoryresideondiskandarebroughtin (cid:0) s bility abd=ac andisuncertainwithprobability a. ondemand.Thefollowingtheoremquantifiesthecost(thenumber s s ofI/Oaccessespertimeunit)ofouralgorithmrelativetothena¨ıve Basedon Lemma1and theaforementionedassumptions, wecan approach.Aproofcanbefoundin[25]. estimatetheoptimalsizeofthepartitionthatminimizestheevalu- ationcost.Thisisstatedinthefollowingtheorem. THEOREM 2. If all the uncertain constraints can be held in main memory, thecostof thematching algorithm is thepartition THEOREM 1. UnderrandommovementofobjectsinEuclidean updateprobability(P )timesthecostofthena¨ıveapproach(Co- pu 2Dspace,thereexistsauniquelocal(thereforealsoglobal)optimal stI=O =P *CostI=O ). partitionsize,whichis kv(cid:12)s forsomeconstantk.(recallthat(cid:11)and adapt pu na(cid:127)(cid:16)ve (cid:12)aretheaveragecostfor(cid:11)evaluationbasedonprecisepositionand This result is somewhat surprising, it means that even with lim- partitioninformation,respectively.) itedmemory,reducingthepartitionupdateratebysomeproportion causestheevaluationcosttobereducedwiththesameproportion, Discussion: If the movement pattern is not random, we can not giventhatalluncertainconstraintsareheldinmemory. Underthe compute a globally optimal partition size. However, if we inter- randommovementpattern,thenumberofuncertainconstraintsis pret a local distribution as random, then there still exists a local onlyasmallportionofthetotalnumberofconstraints(a asstated optimum, which gives us a locally optimal partitioning. We ap- s inLemma1).Itcanthereforeoftenfitintomainmemory,evenfor proximate this local optimum by rescheduling the partitioning in largeconstraintloadsgoingbeyondmainmemorycapacities.Also theareathatisnotyetoptimizedbasedonthemergingandsplit- anefficientalgorithmshouldstopfurtherreducingthenumberof tingalgorithm,introducedintheprevioussection. uncertainconstraintsbysplittingaslongastheyallfitintomem- We say a partition scheme, ps, is the ancestor of a partition ory.Merginginthatcasemayactuallydampenthepartitionupdate scheme, ps0, (ps0 is the descendantof ps), if ps0 can be reached rateandhelptolowertheI/Oaccesscostfurther. frompsbyaddingsplittinglines. Thisdescendantrelationshipis denotedasps0 ps.InSection2.2,toreducethecomputation,we (cid:31) 4. SYSTEM IMPLEMENTATION mentionedthattheuncertainconstraintsafterthesplitting(merg- ing)processmustbeasubset(superset)oftheuncertainconstraints Phone Network Carrier(cid:13) beforethesplitting(merging). Thispropertyisformallycaptured inLemma2.Proofdetailscanbefoundinthetechnicalreport[25]. App.L Coogngtirnogll(cid:13)er &(cid:13) P&S Staging(cid:13) Publications & Subscriptions(cid:13) PrDoaxyta S Leinrvke(cid:13)r(cid:13) W (cid:13)A (cid:13)P iaTasllhssaeLoolsiEaanoMntsauaMunittniAisuosfinane2ctdib.eserficIthoefaidnipnnssdct0croLaon(cid:31)einsnmtstrptamrisnai,naipntt2hstie0nii;nnspatpasnhns0da;.tuaawnnssiutaahnttiicassefifimreetddaoirccneoocpnnorssenttrcrsaaitsriienantitaniiptnnpinrpposspxsiiiss-0 Database((cid:13)UsBLeLoorooP agItD&dsgti,Sinr naC(cid:13)ggpo(cid:13)(cid:13)(cid:13)nsLtraoMinctaa ItDtci)oh(cid:13)ninP Cg&S oE(cid:13)nnsgtrinaein(cid:13)t(cid:13) MLUoapcndaaaOtgiotpeeen(cid:13)rn(cid:13)(cid:13)wave P&So DrseKipt(cid:13)iPloyno(cid:13) sqLituo(iloeconarny tgSi(cid:13)o.e nlra(cid:13)vte. ra(cid:13)ltN.)(cid:13)(cid:13))(cid:13)(cid:13)0(cid:13).(cid:13)(cid:13)(cid:13)2(cid:13)WAP (cid:13)(cid:13)( (cid:13)r(cid:13)(cid:13)e(cid:13)ws(cid:13)(cid:13)(cid:13)o(cid:13)Br(cid:13) muainmastaisotianstfi(aewdirtebhdyputscht0ie)o,pnmaoortfriettihoceonn-nbsuatrmsaeibdnetersvcoaaflunuabntiecoerner.tsaoTilnhveecdsopnalssittsrtaianitnigstfisperadotcaetnhsdes ApSpLeliBrcvaSet(cid:13)iro(cid:13)n(cid:13) (URseelra ItDed, SMeSrvGic)(cid:13)e(cid:13) NoEtinfigcianteio(cid:13)n(cid:13) WAP PNuosthif icRaetqioune(cid:13)st for(cid:13) NoStieficrvaetiro(cid:13)n(cid:13) (cid:13)n(cid:13)o(cid:13)i(cid:13)t(cid:13)(cid:13)ac(cid:13)(cid:13)if(cid:13)i(cid:13)(cid:13)t(cid:13)oCell phone(cid:13) represents data flow(cid:13) costofaslightincreaseinthepartitionupdaterate. Ontheother hand,themergingprocessaimsatareductionofthepartitionup- Figure8:End-to-endSystemArchitecture(fullyimplemented) daterateatthecostofaslightincreaseinthenumberofuncertain 4Theextentofthespaceisdefinedasthemaximumpossibledis- We have developed a complete end-to-end location-based ser- tancebetweentwopointsinsidethespace. vice prototype incorporating the location constraint matcher de- scribedinthispaper. Moreinformationaboutanearlierversionof doesnotevolveatallovertimetobetteraccommodatethemove- theprototypeissummarizedin[23]andisknownastheLocation- ment pattern, the matching time for both AKDT and AMLG is based Toronto Publish/Subscribe System (L-ToPSS). The system around 250ms and the partition size is 25km2. When the win- wasdeployedasaproofofconceptonamobilecellularnetwork. dow size (which controls the speed of adjustment) is adjusted to TheoverallsystemarchitectureisshowninFig.8. 25,AKDTandAMLGactivelyevolvetolowertheevaluationload Inourimplementation, thesystemusesthecellularnetwork to throughsplitting.Withinsevenminutes,thematchingtimeofboth obtain location position informationof subscribers. The network indexes is reduced by 60% and stabilizes below 100ms, and the exportslocationtrackingcapabilitiesviaaWebservice. Location partitionsizeisadjustedtoaround5km2. Thisperformancegain position data is retrieved through a location position server over comes about through the pruning of large numbers of uncertain theInternet. Boththeserver andthe subscribercan initiateposi- constraints (by about 60%) at the cost of a moderate increase in tionrequests.Whenthelocationupdatestreamsintotheconstraint partitionupdates(toabout5%)(graphsomittedduetospacelim- matching engine, it is evaluated against the location constraints itation). Thisshowsthattheadaptivealgorithmsfindtheoptimal stored in the system and the matches are communicated back to partitionsizethroughself-adjustment. thesubscribersviathenotificationserveronthecarrier’sside.Dif- On the other hand, if the initial partition size is set to 1km2 ferentsolutionsforobtaininglocationpositiondataareavailablein (Fig.9(C,D)),partitionadjustment(w =25)evolvestomergethe practice. Inourcase, theoperatorcombinedGPS,networktrian- partitionstoanaveragesizeofabout5km2.Theaveragematching gulation,andcellsitelocationtechnologiestopositionsubscribers, timeisreducedfrom350mstobelow100ms(byabout70%).This aimingtoprovidethemostaccuratepositionforarequiredpreci- performancegainisduetothereductioninthepartitionupdaterate sion, specifiedaspartofthelocationrequestinput. Abriefeval- (byabout90%)ofthemergeprocess.Thematchingtimeresulting uationoftheaccuracyofthesystemunderdifferentexperimental from the na¨ıve approach, where all the constraints are evaluated conditionsissummarizedin[22]. without partition-based pruning, is an order of magnitude higher (notshowninthegraphsforclarity.) 5. EXPERIMENTS InFig.10(A),wevarythemeanofthevelocity(v = 5;10;15) andrunthedatasetagainstadaptiveindexing withdifferentwin- Inthissection,wepresenttheexperimentalresultsthatdemon- dowsizes.(Forclarityofpresentation,weonlyshowresultsforthe strate the performance of the algorithms. All experiments were AKDT;resultsforAMLGaresimilar.) Thefigureshowsthatthe conductedonaPentium4with2GHzand2GRAM)runningun- adjustmentcost(theoverheadofsplittingandmerging)increases derLinux. Intheexperimentswesimulatemobileobjectsmoving linearlyasthewindowsizeincreasesfordifferentvelocities.How- in a test field of size 40km 40km. We model two movement ever, the adjustment cost is negligible compared to the time for (cid:2) patterns,randommovementandclusteredmovement. Therandom constraint evaluation. To obtain the same evaluation time in the movementpatternmaintainsauniformdistributionoftheobjectsin threescenariosshown,alargerwindowsizeisrequiredforhigher thetestfield. Theclusteredpatternmaintainsanumberofclusters velocity. ofobjectsinthetestfield,wherethepositionoftheobjectinthe Giventhedistributionofthevelocity, theoptimalpartitionsize clusterfollowsanormaldistributionwithmean,(cid:22),asarandomly canbefoundwiththesteepestdescentmethod(SDM[7])bysam- selectedpointinthetestfield. Wevarythestandarddeviation,(cid:27), plingdifferentpartitionsizesapproachingtheoptimum,whichbased ofthedistributiontomodeldifferentdegreesofskewness. Inthe onTheorem1isunique.InFig.10(B),wevalidatetherelationship extremecase,wherethestandarddeviationissufficientlylarge,the between the average velocity of the objects and the optimal par- clustered movement pattern is reduced to the random movement tition size and show that the optimal partition size obtained with pattern. Tomodelthemovementofclusters,(cid:22)isdeterminedasa SDMisnearlyproportionaltotheaveragevelocityoftheobjects functionoftime,t. (asconfirmedbyTheorem1). Moreover,thefigureshowsthatthe Prior to the experiment, constraints are generated; each con- adaptiveprocessingeventuallyresultsinapartitionschemethatis straint is associated with n bodies among all the moving objects closetotheoptimum. inthefield. Thealertingdistancesareuniformlydistributedwith InFig.10(C),weevaluatetheadaptationofthealgorithmwith acertainmean(e.g.,500m). Bychangingthemean,thematching the evolution of the clustered movement pattern. 50 clusters are load5canbeadjusted.Thevelocityofthemovingobjectsfollows generated with constant standard deviation (400), the means of anormaldistributionwithagivenmean(5m/sorasspecified). theseclustersaremovingwithrandomspeed(uniformintherange Thepartitionadjustmentisperformedonceeveryminutetoop- [20,50])anddirection. Asevidentfromthemovingclusterwork- timizethepartitionschemeasneeded. Forsakeoffairnessinthe load,thestaticindexcannotkeepupandperformancedeteriorates. comparison, wemaintain the same adjustmentspeed for both in- The matching time is not only high but also very unstable with dexesbysplittingandmergingthesamenumberofcandidatepar- many spikes resulting fromlargepartition updateoverhead when titions. the clusters move across splitting lines. AKDT and AMLG han- dle this situation well. The matching time is relatively low and 5.1 Effect ofAdaptation muchmorestable.Whenweadjusttheskewnessofthecluster(by This experimentisconductedunderrandommovement pattern varyingthestandarddeviation(cid:27)),weobtainsimilarresults,except wheretheobjectsareuniformlydistributed. ItshowshowAKDT thathigherskewness(smaller(cid:27))exacerbatestheinstabilityforthe andAMLGadapttotherandommovementpatterns.Theresultsare static indexing. Fig. 10(D) shows the superiority of the adaptive comparedagainstanon-adaptivesolution(w = 0). With100,000 indexingfortheCRRandCRKNN constraints.Comparedwith constraintsand 10,000uniformlydistributedobjects, wemeasure thebasicprocessingwithoutconstraintpruning,thematchingtime thematchingtimeandtheaveragepartitionsizeovertime.Fig.9(A, isgreatlyreduced(to14%forCRKNN andto9%forCRR)for B)showstheresultsduringthefirst12minutesoftheexperiment theadaptivepartition-basedapproach. whentheinitialpartitionsizeis25km2. Thestaticindex(w =0) Fig. 11(A) demonstrates the cost of indexing for different lo- cation update loads (i.e., number of location updates incurred.) 5The matching load is the ratio between the average number of With static indexing (w = 0), for AKDT with backtracking op- satisfiedconstraintsandthetotalnumberofconstraints. (A) (B) (C) (D) 300 25 400 7 matching time (ms)112205050000 AAAAKMKMDDLLTGTG((((wwww====0202)5)5)) 2partition size (km)1120505 AAAAKMKMDDLLTGTG((((wwww====0202)5)5)) matching time (ms)112233050505000000 AAAAKMKMDDLLTGTG((((wwww====0202)5)5)) 2partition size (km)23456 AAAKMKDDLTGT(((www===020)5)) AMLG(w=25) 500 2 4 6 8 10 12 00 2 4 6 8 10 12 500 2 4 6 8 10 12 10 2 4 6 8 10 12 time (minutes) time (minutes) time (minutes) time (minutes) Figure9:AdaptationtotheUniformMovementPattern (A) (B) (C) (D) time (ms)234567890000000000000000 aaaeeedddvvvaaajjjuuullluuussstttaaammmtttiiioooeeennnnnn(((ttt(((vvvvvv======511511)05)05)))) 2partition size (km)111112222024680246 oAApKMtDiLmTGa((wlw s==iz22e55)) matching time (ms)123456000000000000 AAAAKMKMDDLLTGTG((((wwww====0202)5)5)) matching time(ms)11114680246000000000000000000000 CCCCCCRRRRRRRRRKKKNNN AANNNKM DAALTGKM(D(LwwTG==((2w2w55==))2255)) 100 8 2000 05 10 15 20 25 30 35 40 45 65 10 15 20 00 20 40 60 80 100 120 01 2 3 4 5 6 7 window size average velocity (m/s) time (minutes) number of constraints x 105 Figure10:AdjustmentCost(A),OptimalPartitionSize(B),AdaptationtoClusteredPattern(C),andCRR/CRKNNqueries(D) timization,6 theoverheadisreducedby50%ascomparedtonon- 5.2 Effect ofSecondaryStorageAccess backtracking-basedindexing. Foradaptiveindexing(w=25),the Inthis subsection wemeasurethe number ofdisk accesses re- costofAKDT(withorwithoutbacktracking)isveryclosetothat quiredforprocessing10,000objectsand100,0002-bodyconstraints, of AMLG, because adaptive spacepartitioning avoids high parti- withstrictlimitsimposedontheavailablememory.Weassumethat tion updaterates and themaintenance differencebetweenAKDT theindexingstructure,thepositioninformationoftheobjectsand andAMLGissmall. Bothcostareabout10%ofthecostofstatic acertainnumberoflocationconstraintsareheldinmemory.Other indexing. locationconstraintshavetobepagedinandoutofmemoryonde- WealsoobserveinFig.11(B)thatthematchingtimedecreases mand(weassumetheLRUpagereplacementpolicyandapagesize linearlyasthepercentageoftheconflictingand harmoniouscon- of4k). Thealgorithmtriestostoreasmanyuncertainconstraints straints increases. These constraints are pruned directly through inmemoryaspossible,sothatdiskaccessisminimized. the secondary graph-structured index and do not need to be re- Fig.12(A)plotsthenumberofsecondarystorageaccessesagainst evaluated. available memory. For this experiment, we test the AKDT and Fig. 11(C) shows the adaptation of the algorithms to different AMLG indexes against objects with various movement patterns. constraint sets. Three constraint sets are deliberately generated Fig.12(A)showsthatthenumberofdiskaccessesforbothindexes such that for static indexing (w = 0), the sets contain different aremuchlowerthanforthena¨ıvealgorithm. Thisisbecausethere number of uncertain constraints (set 1 < set 2 < set 3), there- arefewer constraints thatneedtobe accesseddue to thepruning fore,weobserveanincreaseinmatchingtimefromconstraintset1 capabilitiesoftheindexes. Thepartition-basedalgorithmsexhibit to set 3. With adaptive indexing (w = 25), the matching time a point in memory use after which the number of disk accesses stabilizesaround100msforallsets,becausethepartitionscheme is nearlyproportionaltothediskaccessesforthena¨ıve approach evolvestoreducetheuncertainconstraintstothesamelevel. (around80pagesforw=25,120pagesforw=12and160pages Now, withalltheconstraintmatchesdetected, wecomparethe forw =0). Thisisthepointwheretheavailablememorysuffices number oflocation updatesissued by the saferegion policy with toloadalluncertainconstraints.Theadaptivealgorithmswithwin- thefrequency-basedpolicy. Thelocationupdatefrequencyofthe dow size25reducetheuncertainconstraints (by60%), therefore frequency-based policy is adjusted (to around 1/s) such that all lessmemoryisrequiredtostorethem.Ifthepagenumberexceeds thematchesaredetected(withlowerfrequency,somematchesare thisamount,thenumberofdiskaccessesequalsP CostI=O ,as missed). Fig. 11(D) shows that, for all three constraint sets, the pu na(cid:127)(cid:16)ve predicted by Theorem 2. The graph for the adaptive algorithms safe region policy is the most cost effective in that it detects the (w > 0) ismuchflatterthanthenon-adaptive one(w = 0)after samenumberofmatcheswithonly10%ofthelocationupdatecost thispoint. BasedonTheorem2,wecandeducethattheadaptive ofthefrequency-basedpolicy. Thisisasignificantsavingthatcan algorithmshavepartitionupdateratesthataremuchlower(about directlytranslatetodollarvalue. 60% lower for w = 25 and 30% lower for w = 12) than the non-adaptive algorithms. Therefore, the adaptive algorithms out- performthenon-adaptiveones,alsoinI/Oincurringenvironments. 6Thesearchbacktrackslevel-by-levelupthek-d-treefromtheorig- Furthermore,inFig.12(B),wesuppressthesplittingprocessas inalleavenodewheretheobjectislocateduntilthenodeisfound soon as the memory can hold all the uncertain constraints. This thatcontainstheobject. Insertionproceedsdownfromthisnode, means,ifmemoryisavailable,thealgorithmdeliberatelyincreases ratherthanfromtherootofthetree. Thisapproachavoidsthetop- theuncertainconstraintsinordertoreducethepartitionupdaterate bottomscanofthetreeforalocationupdate.