High Concurrent R-tree Operations when Tracking Continuous Movement in Main Memory
Authors
Chitac, Cezar ; Kerpys, Robertas ; Marcuta, Raluca
Term
1. term
Education
Publication year
2011
Submitted on
2011-01-10
Pages
19
Abstract
Mange systemer skal kunne spore bevægelige objekter og besvare spørgsmål som: 'Hvilke objekter er tæt på denne position lige nu?' For at gøre det hurtigt gemmes positioner i en specialiseret rumlig datastruktur, et indeks designet til positioner i rummet. Fordi objekterne bevæger sig, skal systemet ofte opdatere deres positioner, så data forbliver friske. Hovedhukommelsesdatabaser, som holder data i RAM, gør sådanne hurtige opdateringer mere mulige. For at udnytte moderne CPU’er med mange kerner fuldt ud skal systemet også håndtere samtidighed: mange operationer, der foregår samtidig. Traditionelle metoder bruger locking eller latching (korte låse inde i datastrukturer) til at koordinere samtidige læsninger, opdateringer og strukturelle ændringer. Disse mekanismer kan blive flaskehalse. Dette arbejde præsenterer en algoritme til samtidighed, der minimerer locking og latching og lader mange operationer køre parallelt. Det introducerer også to nye tilgange, som hjælper med at bevare høj samtidighed, selv når det rumlige indeks skal ændre form, ved at splitte noder, der er overfyldte, eller slå noder sammen, der er underfyldte. Tilsammen understøtter disse teknikker hurtige forespørgsler og aktuelle positioner uden at gå på kompromis med parallel ydeevne.
Many systems need to keep track of moving objects and answer questions like 'which objects are near this location right now?' To do this quickly, positions are stored in a specialized spatial data structure, an index designed for positions in space. Because the objects move, the system must update their positions frequently so the data stays fresh. Main-memory databases, which keep data in RAM, make such rapid updates more feasible. To fully use modern multi-core CPUs, the system must also handle concurrency: many operations happening at the same time. Traditional methods rely on locking or latching (short-term locks inside data structures) to coordinate concurrent reads, updates, and structural changes. These mechanisms can become bottlenecks. This work presents a concurrency algorithm that minimizes locking and latching, allowing many operations to proceed in parallel. It also introduces two new approaches that help maintain high concurrency even when the spatial index must change its shape, by splitting nodes that are overfull or merging nodes that are underfull. Together, these techniques support fast queries and up-to-date position data without sacrificing parallel performance.
[This abstract was generated with the help of AI]
Keywords
Documents