Main-Memory Operation Buffering for Efficient R-Tree Update
Author
Biveinis, Laurynas
Term
10. Term
Education
Publication year
2007
Abstract
Nye kommunikations- og sensorteknologier skaber datamængder, der kræver, at databaser hurtigt kan håndtere mange opdateringer i rumlige indeks (indeks for sted- eller positionsdata). Mange eksisterende løsninger har væsentlige begrænsninger: de kræver meget hovedhukommelse (RAM), udnytter ikke den tilgængelige hukommelse fuldt ud, eller understøtter ikke alle standard indeksoperationer. Under antagelsen om, at opdateringer ikke behøver at blive skrevet til disk med det samme, præsenterer vi en R-tree-baseret indekseringsteknik, som undgår disse problemer. Hovedideen er at buffer opdateringer i hukommelsen og udføre dem gruppevis, så flere operationer kan dele den samme disk-I/O (læse/skrivetrafik). Tømning af bufferne styres af en analytisk omkostningsmodel, der bestemmer, hvornår det bedst kan betale sig at skrive til disk. Empiriske studier viser, at modellen effektivt styrer bufferudtømningen, og at teknikken i miljøer med hyppige opdateringer giver bedre (ofte markant bedre) opdaterings-I/O end både et LRU-cachet R-tree og et tidligere forslag til et opdateringseffektivt R-tree.
New communication and sensor technologies create data streams that require databases to handle very high rates of updates to spatial indexes (structures that organize data by location). Many existing approaches have key drawbacks: they need large amounts of main memory (RAM), do not fully use the memory that is available, or fail to support all standard index operations. Assuming updates do not have to be written to disk immediately, we present an R-tree-based indexing technique that avoids these limitations. The core idea is to buffer updates in memory and process them in batches, so multiple operations can share the same disk input/output (I/O). An analytical cost model decides when to flush buffers to disk. Empirical studies show that the model effectively controls buffer flushing and that, in workloads with frequent updates, the technique delivers better (often significantly better) update I/O performance than both an LRU-cached R-tree and a prior update-efficient R-tree.
[This abstract was generated with the help of AI]
Documents