Update-Efficient Main-Memory Indexing of Moving Objects

Johansen, Jan Maffert ; Saulys, Donatas ; Christiansen, Christian

2. term

Computer Science, Master

2008

26

Stadigt flere tjenester bruger position (location-based services, LBS) til at overvåge og forespørge mange bevægende objekter. De bygger på spatio-temporale databaser (systemer der lagrer hvor og hvornår), som løbende modtager opdaterede positionsdata. Det kræver indekseringsstrukturer (måder at organisere data, så søgninger går hurtigere), der tåler hyppige ændringer. Traditionelle rumlige indeks får enten høje opdateringsomkostninger eller svag forespørgselsydelse i sådanne miljøer. Hukommelse er blevet billigere, så hovedhukommelsesdatabaser (RAM-baserede) er nu realistiske. Overgangen fra disk til hukommelse ændrer indeksernes adfærd, og tidligere viden skal genvurderes. Der er foreslået flere optimeringer til memory-implementering, men resultaterne er svære at sammenligne, fordi hver undersøgelse bruger sit eget setup. Vi imødekommer dette ved at tilpasse en kendt, disk-baseret benchmark, så den kan sammenligne spatio-temporale indeks i hovedhukommelse. Vi laver og tester hukommelsesbaserede varianter af et Grid, et R-tree og en simpel Array og måler deres ydeevne under forskellige forhold. Vores resultater: Grid'et leverer generelt de hurtigste forespørgsler. R-tree'et har langsommere ikke-lokale opdateringer, fordi træstrukturen skal vedligeholdes, når objekter flytter sig. Array'en opdaterer hurtigst, men besvarer forespørgsler langsomst; for visse arbejdsbelastninger kan den samlede ydeevne være sammenlignelig. Da LBS-brugere typisk vægter hurtige forespørgsler, er Array'en ikke egnet til services, der kræver hurtige svar. Givet R-tree'ets større alsidighed vurderer vi, at både Grid og R-tree er velegnede til at indeksere positioner for dynamiske, bevægende objekter.

Location-based services (LBS) that track and query large numbers of moving objects are growing rapidly. They rely on spatio-temporal databases (systems that store where things are and when) that receive continuous position updates. This requires indexing structures (ways of organizing data to make searches faster) that handle frequent changes. Traditional spatial indexes either become costly to update or perform poorly on queries in such time-varying settings. Memory has become inexpensive, making main-memory (RAM) databases practical. Moving from disk to memory changes how indexes behave, so earlier findings need to be revisited. Several memory-optimized designs have been proposed, but their results are hard to compare because each study uses a different setup. We address this by adapting a known disk-based benchmark to fairly compare spatio-temporal indexes in main memory. We implement and test memory-based versions of a Grid, an R-tree, and a simple Array, and measure their performance under different conditions. Our findings: the Grid generally delivers the fastest queries. The R-tree has slower non-local updates because its tree structure must be maintained as objects move. The Array updates fastest but answers queries slowest; for some workloads its overall performance can be comparable. Since LBS users typically value quick queries, the Array is not suitable for query-efficient services. Given the R-tree's greater versatility, we find that both the Grid and the R-tree are well suited for indexing the positions of dynamic, moving objects.

[This abstract was generated with the help of AI]

GPS ; Indexing ; main-memory ; moving objects ; Grid ; R-tree ; Indeksering

Download
View record in AAU Student Projects