Sedan M-trädet infördes 1997 blev det en respekterad metrisk åtkomstmetod (MAM), samtidigt som det tillsammans med sina ättlingar fortfarande är den enda databasvänliga MAM, dvs. en dynamisk struktur som finns kvar i sidindex. Även om det har funnits många andra MAM som utvecklats under det senaste årtiondet, de flesta av dem kräver antingen statiska eller dyra indexering. Däremot gör den dynamiska M-tree konstruktionen det möjligt för oss att indexera mycket stora databaser i subkvadratisk tid, och samtidigt indexet kan upprätthållas up-to-date (d.v.s. stöder godtyckliga in- och utmatningar). I den här artikeln föreslår vi två nya tekniker som förbättrar dynamiska insättningar i M-tree-den påtvingade återinsättningsstrategier och så kallade hybrid-way blad val. Båda teknikerna bevarar logaritmisk asymptotisk komplexitet av en enda insättning, medan de syftar till att producera mer kompakta M-tree hierarkier (vilket leder till snabbare frågebehandling). I synnerhet den tidigare tekniken återanvänder den välkända principen om påtvingade återinsättningar, där den nya införandealgoritmen försöker återinföra innehållet i ett M-tree blad som är på väg att delas för att undvika denna uppdelning. Den senare tekniken utgör ett effektivitetsskalbart urval av lämplig bladnod där ett nytt objekt måste infogas. I experimenten visar vi att de föreslagna teknikerna ger en tydlig förbättring (snabba upp både indexering och frågebehandling) och även ger ett inställningsverktyg för indexering vs. frågeeffektivitet kompromiss. Dessutom uppvisar en kombination av de nya teknikerna en synergistisk effekt som resulterar i den bästa strategin för dynamisk M-tree konstruktion som hittills föreslagits.
I arbetet inom REF presenteras två nya tekniker för att möjliggöra dynamiska tillägg till MTree.
New dynamic construction techniques for M-tree
{'venue': 'J. Discrete Algorithms', 'journal': 'J. Discrete Algorithms', 'mag_field_of_study': ['Computer Science']}