'Generating and Indexing Multi-Dimensional Moving Regions in Spatio-Temporal Databases'
Authors
Frøkjær, Jens ; Hansen, Palle B. ; Larsen, Ivan V. S. ; Oddershede, Tom
Term
4. term
Education
Publication year
2006
Abstract
Mange databaser lagrer bevægelige regioner—områder der ændrer position eller størrelse over tid. I sådanne systemer er der typisk langt flere ændringer (indsætninger, opdateringer, sletninger) end rumlige forespørgsler. Den udbredte R+-tree-indeksstruktur håndterer forespørgsler godt, men er mindre effektiv ved hyppige ændringer. Denne afhandling introducerer Layered Shifted Space-filling curves (LSS), en indekseringsteknik designet til at gøre ændringer hurtigere. LSS organiserer data i forskudte lag og tildeler hver region én enkelt indeksværdi. Forskydningen sikrer, at regioner af en bestemt størrelse altid passer på et bestemt lag, hvilket mindsker omkostningen ved opdateringer. Klassiske space-filling curves (en metode til at afbilde flerdimensionelle data til én dimension) kræver ofte forhåndskendskab til data, fx koordinatområde. Vi foreslår en selvvedligeholdelsesmetode, så LSS kan fungere uden at kende world size på forhånd. Vi evaluerer LSS i Oracle DBMS og sammenligner med Oracles R+-trees og eksisterende space-filling curve-tilgange. I vores tests var LSS op til 35 gange hurtigere ved ændringer, men op til 11 gange langsommere ved forespørgsler—en tydelig afvejning, som kan være fordelagtig når opdateringer dominerer. For at understøtte afprøvning foreslår vi også generatorer til syntetiske n-dimensionelle bevægelige objekter og til blandede arbejdsbelastninger (indsætninger, opdateringer, sletninger og rumlige forespørgsler). Datageneratoren bruger statistiske fordelinger til at styre bevægelse og ændring af størrelse, og arbejdsbelastningsgeneratoren producerer en blanding af operationer. En ydelsesundersøgelse viser, at STDW kan fremstille cirka 27.000 objekt-snapshots i sekundet på en standard-pc.
Many databases store moving regions—areas that change position or size over time. In such systems, there are typically far more modifications (inserts, updates, deletes) than spatial queries. The widely used R+-tree index handles queries well but is less efficient when data changes frequently. This thesis introduces Layered Shifted Space-filling curves (LSS), an indexing technique designed to speed up modifications. LSS organizes data in shifted layers and assigns each region a single index value. The shifting guarantees that regions of a given size fit a specific layer, which reduces update cost. Traditional space-filling curves (a way to map multi-dimensional data to one dimension) often require prior knowledge of the data, such as the coordinate range. We propose a self-maintenance method so LSS adapts and works without knowing the world size in advance. We evaluate LSS in the Oracle DBMS and compare it with Oracle’s R+-trees and existing space-filling curve approaches. In our tests, LSS was up to 35 times faster for modifications, but up to 11 times slower for queries—a clear trade-off that suits workloads dominated by updates. To support testing, we also introduce generators for synthetic n-dimensional moving objects and for mixed workloads (inserts, updates, deletes, and spatial queries). The data generator uses statistical distributions to control movement and resizing, and the workload generator produces a mix of operations. A performance study shows that STDW can produce about 27,000 object snapshots per second on a standard PC.
[This abstract was generated with the help of AI]
Documents