'TRP-tree Running in Main Memory'
Authors
Nitkiewicz, Beata ; Panczyk, Michal
Term
10. Term
Education
Publication year
2006
Abstract
Efterhånden som lokationsbaserede tjenester vokser, stiger behovet for rum-tids-databaser—systemer, der håndterer data knyttet til både sted og tid—og for indeksstrukturer, der kan følge med løbende ændringer i data. Kun få eksisterende datastrukturer opfylder disse krav, så forskere undersøger nye, pålidelige løsninger. En lovende retning er at køre traditionelle, disklagringsorienterede databaser helt i hovedhukommelsen (RAM), hvilket bliver mere realistisk i takt med faldende hukommelsespriser. Denne afhandling undersøger, hvordan TPR-træet, en disklagringsorienteret indeksstruktur, klarer sig i hovedhukommelsen. Vi tester den udbredte påstand om, at hukommelsesadgangstid er den primære flaskehals for in-memory-indeks, ved at udføre eksperimenter på TPR-træet. Vi fremhæver også, at ydeevne i hovedhukommelse bør vurderes anderledes og med andre indikatorer end i disklagringssystemer. Vores eksperimentelle analyser peger på, at TPR-træet er CPU-tungt: de største omkostninger skyldes beregninger snarere end hukommelsesadgang. Derfor kan simple forbedringer opnås ved at reducere antallet af beregninger. For at pege på fremtidige analyser introducerer vi tre ændringer af opdateringsalgoritmer: lazy delete, bottom-up delete og en ny penalty insert.
As location-based services expand, there is growing demand for spatio-temporal databases—systems that handle data tied to both place and time—and for indexes that can keep up with constantly changing data. Few existing data structures meet these needs, so researchers are exploring reliable solutions. One promising direction is to run traditional, disk-oriented databases entirely in main memory (RAM), which is becoming more feasible as memory prices fall. This thesis studies how the TPR-tree, a disk-oriented index structure, performs when moved to main memory. We test the common claim that memory access time is the primary bottleneck for in-memory indexes by running experiments on the TPR-tree. We also highlight that performance in main memory should be evaluated differently and with other indicators than in disk-based systems. Our experimental analysis indicates that the TPR-tree is CPU-heavy: the main costs come from computation rather than memory access. Therefore, straightforward improvements focus on reducing the number of calculations. To guide future analyses, we introduce three changes to the update algorithms: lazy delete, bottom-up delete, and a new penalty insert.
[This abstract was generated with the help of AI]
Documents