Vi presenterar en ny flerdimensionell datastruktur, som vi kallar skip quadtree (för punktdata i R 2 ) eller skip octree (för punktdata i R d, med konstant d > 2). Vår datastruktur kombinerar de bästa egenskaperna hos två välkända datastrukturer, genom att den har de väldefinierade "box"-formade regionerna i regionen quadtrees och logaritmisk-höjd sökning och uppdatera hierarkisk struktur av hoppa listor. Faktum är att den nedre nivån av vår struktur är exakt en region quadtree (eller bläckfisk för högre dimensionella data). Vi beskriver effektiva algoritmer för att infoga och ta bort punkter i en skip quadtree, samt snabba metoder för att utföra punkt plats, ungefärligt område, och ungefärliga närmaste grannfrågor. finns i en given frågeregion. Vi är intresserade av detta dokument i datastrukturer för flerdimensionella punktuppsättningar som är dynamiska, genom att de möjliggör snabb punktinsättning och radering, såväl som effektiv, genom att de använder linjärt utrymme och möjliggör snabba frågetider. • k-d träd [10]: regioner definieras av hyperrektanglar i R d, som är indelade i två hyperrektanglar med hjälp av en axelperpendikulär skärhyperplane genom medianpunkten, för regioner som innehåller mer än två punkter. Så det underliggande trädet kan göras ett balanserat binärt träd med log n djup för en statisk uppsättning punkter. Tyvärr kan regionerna ha godtyckligt stora proportioner, vilket kan påverka effektiviteten i vissa frågor negativt. Även om vissa varianter föreslogs för att hjälpa, såsom genom att skära längs den längsta sidan i stället för längs varje axel rekursivt [15], de bara förbättra proportionerna aspekt experimentellt eller statistiskt. Dessutom är upprätthållandet av ett effektivt k-d-träd som omfattas av punktinsättningar och avlägsnandet inte trivialt. • komprimerade quad/octrees [2, [11] [12] [13]: regioner definieras på samma sätt som i en quadtree eller octree (beroende på dimensionaliteten), men stigar i trädet som består av noder med endast ett icke-tomma barn komprimeras till enskilda kanter.
En annan datastruktur för effektiv lagring och snabba frågetider är skip quadtree REF, som kombinerar de bästa funktionerna i regionen quadtrees och skip lists.
The skip quadtree: a simple dynamic data structure for multidimensional data
{'venue': "SCG '05", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}