124
However,sincethetypicaldeletionwillbesmallcomparedtothetotalsizeofthese-
quence,anincrementalrebuildingstrategyismoresensible.Eachsegmentinthecomplete
deletiondatabasethatoverlapstheundoneoperationissimplyre-insertedintounionseg-
mentindex.Forshortdeletionsthisismuchfaster,butintheworstcase,theruntimefor
theincrementalstrategyisstillO(nlogn).Upton 1segmentsmighthavetobeinserted,
eachatacostofO(log n)time,ifthedeletionbeingundoneoverlapsallotherdeletions,and
theyaretotallydisjoint.
6.6 Indexingmoveoperations
Moveoperationsverysimilartodeletionoperations,butbuildinganefficientindexof
movesourcerangesistrickierproblem,sincemoveoperationsneedtobecomparedwith
eachotherforpriority.Whendeterminingifaregionhasbeenmovedelsewhere(sothatit
shouldbeignoredinthecurrentcontext),weneedtoperformamorecomplexquerythan
simplesegmentintersection.Whenexamininganaddressthatispartoftheresultofamove
operation,weneedtoknownotifthesourcerangeisquestionhasbeenmovedbyanyop-
eration,butifithasbeenmovedbyanyoperationwithahigherpriority.Theuseofpriori-
tiesensuresthatsourceregionsare“greedy,”witheachaddressinoverlappingmovescopes
beingclaimedbyonlyonemoveoperation.
Ifmoveprioritiesarecompletelyarbitrary(astheywereinthemodeldefinitions),then
thisisadifficultmultidimensionalsearchproblemonthestart,endandpriorityofthemove
operation.However,weobservedinSection3.3.3thatthechoiceofpriorityfunctionisal-
mostcompletelyarbitrary,exceptthatmovesourcesthatarecompletelycontainedwithin
anothermovesourcetoshouldtakepriorityoverthecontainingregion.Thisallowsthe
preservationofinternalrearrangementsevenwhenalargermoveshiftsalongsubsequence.
Givingprioritytoinnerregionsinnestedsourcescopescanbeassuredbygivingpriorityto
thosesourceregionswhoserightendpointissmaller.Whileoverlappingregionsthatarenot
125
containedinsideotherregionswillalsogethigherpriorities,therightendpointofaninter-
valwillalwaysbefurthertotheleftthantherightendpointofanintervalthatcontainsit.
Withthispriorityfunction,theproblemcansolvedwithaslightlynon-standardapplication
ofaprioritysearchtree.
Prioritysearchtreessupportwhatareknownastwoandahalf-dimensionalqueries.A
prioritysearchtreestoringpairs(x, y),cansupportqueriesaskingforallpairswith
x
1 £ x £ x
2 andy £ y
1 ,wherex
1 ,x
2 ,andy
1 arearbitraryqueryvalues.They-dimensionofthe
prioritysearchtreedoesnotsupportfullygeneralrangequeries,butfortunatelythequeries
itdoessupportaresufficient.Werepresentasegment(s, e)withstartsandendeasapair
(e,s).Totestforasegmentwithrightendpointlessthanorequaltopthatoverlapsapoint
atv,searchforallstoredpairswithv £ x £ pandwithy £ v.Theconditiononxandven-
suresthattheresultintervalendsafterthequerypoint,andtheconditiononxandpen-
suresthattheintervalhasahigherprioritythanp.Theconditiononyandvensuresthat
theresultintervalstartsbeforev.
Thisstructureenablesthedeterminationofwhetheranaddressisdeletedbyamoveop-
erationwithpriorityhigherthanagivenvalue,inlogarithmictime.Twosmallsubtletiesare
worthnoting.Prioritysearchtreesrequirethatallendpointsonthex-axisbeuniqueinor-
dertomaintaintheruntimeguarantees.Thiscanbeensuredinthestandardwaybymaking
they-valueasecondarykeyalongthex-axis.Butthereisanadditionalneed,imposedby
theconstraintthatPalimpsestmustworkinfullydistributedenvironmentswithoutrequir-
ingglobalcommunication.Twomovesmaywellbecreatedatseparatesiteswiththesame
rightendpoints,buttheymuststillhaveuniquepriorities,incasetheyaremergedintothe
sameversion.Theuniquenessoftheseprioritiesmustbeensuredbyadditionalinformation
tosupplementthepriorityinformationgivenbytherightendpointofthemove’ssource
range.FortunatelytheuniqueIDsofchangescanbeusedtoaugmentthepositionalorderof
Previous Page Next Page