Bx-träd

Inom datavetenskap är ett Bx - träd en fråge-  och uppdateringseffektiv indexeringsstruktur för att flytta objekt baserat på B+‍‍-träd .

Indexstruktur

Grunden för B x- trädstrukturen är ett B+‍‍-träd, där interna noder behandlas som kataloger som innehåller pekare till den högra grannoden (med samma förälder). I tidiga versioner av B x -trädet [1] innehöll löven positionen för indexerade rörliga objekt och motsvarande indexeringstid. I den optimerade versionen [2] innehåller varje blad ett id, hastighet, ett endimensionellt (skalärt) värde för positionsfunktionen och objektets senaste uppdateringstid. Skillnaden ökas av bristen på lagring av positionen för rörliga objekt, eftersom den kan erhållas från värdet på funktionen .

Använda B+‍‍-träd för att flytta objekt

Som med många andra indexeringar av rörliga objekt, modelleras ett tvådimensionellt rörligt objekt av en linjär funktion O = ((x, y), (vx, vy), t), där (x, y) och (vx, vy) ) är objektets position och hastighet vid tidpunkten t , det vill säga vid tidpunkten för den senaste uppdateringen. B+‍‍-träd är en struktur för att indexera endimensionell data. För att tillgodose B+‍‍-trädet för att indexera rörliga objekt, använder Bx - trädet en linjäriseringsteknik som hjälper till att omvandla objektets position vid tidpunkten t till ett endimensionellt värde. I synnerhet bryts objekt först upp efter uppdateringstid. För objekt inom en tidspartition kommer B x -trädet ihåg objektets position vid en given tidpunkt, erhållen genom linjär interpolation . Genom att göra det bibehåller Bx - trädet en konsekvent bild av alla objekt inom det delade elementet utan att ändra uppdateringstiden för objekten.

Därefter delas utrymmet av ett gitter och objektens position linjäriseras för partitionselementet i tid enligt den rymdfyllande kurvan, till exempel Peano -kurvor eller Hilbert-kurvor .

Sedan, i kombination med det delade elementnumret (tidsinformation) och linjär ordning (positionsinformation), indexeras objektet i B x -trädet med ett endimensionellt nyckelvärde (B x - värde):

Här är index-partition indexet för partitionselementet som bestäms av uppdateringstiden, och xrep är värdet på objektets position på den rymdfyllande kurvan vid tidpunkten för indexering, betyder det binära värdet av x, "+" betyder sträng sammanlänkning.

Givet ett objekt O ((7, 2), (-0,1,0,05), 10), tmu = 120, kan värdet av B x för O beräknas enligt följande.

  1. O indexeras vid element 0 i tidspartitionen som beskrivits ovan. Så indexpartition = (00) 2 .
  2. Positionen för objektet O vid tidpunkten för inställning av tiden för partition 0 är (1,5).
  3. Med hjälp av en Z-kurva av ordning 3 är Z-värdet för objektet O, xrep, (010011) 2 .
  4. Vi kopplar ihop raderna indexpartition och xrep, vi får värdet B x (00010011) 2 =19.

Infoga, uppdatera och radera

Om ett nytt objekt ges, beräknas dess indexnyckel och objektet infogas i B x -trädet som i ett B+‍‍-träd. En uppdatering består av en radering följt av en infogning. Ytterligare strukturer används för att lagra den sista nyckeln i varje index så att objektet kan tas bort när nyckeln slås upp. Indexnyckeln beräknas innan den tas med i trädet. Således ärver ett B x- träd direkt de goda egenskaperna hos ett B+‍‍-träd och uppnår bra uppdateringsprestanda.

Förfrågningar

Fråga efter intervall

Områdesfrågan hämtar alla objekt vars plats faller inom det rektangulära området vid en tidpunkt inte tidigare än den aktuella tiden.

Bx - trädet använder en teknik för expansion av frågefönster för att svara på denna fråga. Förlängningen har två fall - platsen måste antingen beräknas vid någon tidigare tidpunkt, eller vid en senare tidpunkt. Huvudidén är att utöka frågefönstret på ett sådant sätt att det kommer att inkludera alla objekt som inte ingår i frågefönstret vid den tidpunkt som anges i objektnyckeln, men faller in i det för tidpunkten för begäran.

Efter att ha expanderat måste du titta igenom sektioner av B x -trädet för att hitta objekt som faller in i det utökade fönstret. I varje avsnitt innebär tillämpningen av en utrymmesfyllande kurva att frågeintervallet i naturligt 2D-utrymme blir uppsättningen av intervallfrågor i 1D-rymden [1] .

För att undvika alltför stora intervallfrågor efter att ha utökat frågefönstret i asymmetriska data, finns det en optimeringsalgoritm [3] som förbättrar frågeprestanda genom att eliminera onödiga expansioner.

Fråga efter K närmaste grannar

Frågan efter K närmaste grannar utförs genom att iterativt utföra intervallfrågor med ökande sökarea tills vi får k svar. En annan möjlighet är att använda liknande idéer tillsammans med tekniken iDistance .

Andra förfrågningar

Områdesfrågan och K närmaste grannförfrågealgoritmer kan enkelt utökas för att stödja intervallfrågor, kontinuerliga frågor, etc. [2] .

Anpassa relationsdatabaser för att ta emot rörliga objekt

Eftersom B x- trädet är ett index byggt ovanpå ett B+‍‍-träd, är alla operationer i ett B x- träd, inklusive infogning, borttagning och uppslag, desamma som i ett B+‍‍-träd. Det finns inget behov av att ändra genomförandet av dessa operationer. Den enda skillnaden i implementering ligger i implementeringen av proceduren för att erhålla indexeringsnyckeln som en lagrad procedur i den befintliga databasen . Således kan Bx -trädet enkelt integreras i en befintlig databas utan att påverka kärnan .

SpADE [4]  är ett hanteringssystem för rörliga objekt byggt ovanpå den populära MySQL-databasen som använder ett B x- träd för att indexera objekt. I implementeringen konverteras och lagras rörliga objektdata direkt i MySQL, och frågor omvandlas till standard SQL-frågor som effektivt bearbetas av relationsdatabasens körtid. Viktigast av allt, allt detta görs snyggt och oberoende utan att störa MySQL-kärnan.

Performance Tuning

Potentiella problem med dataskevning

Bx - trädet använder ett utrymmesallokeringsgitter för att omvandla en tvådimensionell position till en endimensionell nyckel. Detta kan leda till prestandaförsämring i både frågor och uppdateringar när man arbetar med asymmetrisk data. Om rutnätscellen är stor innehåller cellen många objekt. Eftersom objekten i en cell inte går att särskilja med index, kommer det att finnas något nodspill i det underliggande B+‍‍-trädet. Förekomsten av överfyllda sidor förstör inte bara balansen i trädet, utan ökar också kostnaden för uppdatering. Som med vanliga frågor, för en intervallfråga, resulterar större celler i fler falska sampel och ökar körningstiden. Å andra sidan, om utrymmet är uppdelat i ett mindre rutnät, det vill säga i mindre celler, innehåller varje cell färre objekt. Det är osannolikt att sidspill kommer att uppnås i det här fallet, och det kommer också att finnas färre falska prov, men fler celler kommer att behöva skannas. Att öka antalet celler att titta på ökar också frågans komplexitet.

Ställa in indexet

ST 2 B-trädet [5] introducerar ett självinställningsschema för att ställa in prestandan hos ett B x - träd när man hanterar icke-symmetriska data i rum och tid. För att arbeta med asymmetriska data i ST 2 -utrymme delar B-trädet upp hela utrymmet i regioner med olika densitet av objekt med hjälp av en uppsättning kontrollpunkter. Varje region använder ett individuellt rutnät vars cellstorlek bestäms av densiteten av objekt inom regionen.

B x -trädet har flera partitioner för olika tidsintervall. ST 2 B-trädet använder intervallökning eller minskning för att justera indexering för att anpassa utrymmesuppdelning och anpassa tidsförändringar. I synnerhet när partitionen töms och börjar växa, väljs en ny uppsättning kontrollpunkter och ett nytt rutnät för varje punkt väljs enligt den senaste datatätheten. Inställningen baseras på statistik som samlats in under en given tidsperiod, så att uppdelningen av utrymmet bättre matchar den senaste datadistributionen. I denna mening förväntas ST 2 B-trädet minimera effekten som orsakas av dataskevheter i rymden och dataförändringar över tiden.

Se även

Anteckningar

  1. ↑ 1 2 Jensen, Lin, Ooi, 2004 , sid. 768-779.
  2. ↑ 12 Dan Lin, 2006 .
  3. ↑ Jensen, Tiesyte, Tradisauskas, 2006 .
  4. ↑ SpADE Arkiverad från originalet den 2 januari 2009. : En rumslig och tidsmässig autonom databasmotor för platsmedvetna tjänster.
  5. ↑ Chen, Ooi, Tan, Nacismento, 2008 , sid. 29-42.

Litteratur