Spring til hovednavigation Spring til søgning Spring til hovedindhold

Relaxed Multi-Way Trees with Group Updates

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

Data structures with relaxed balance differ from standard structures in that rebalancing can be delayed and interspersed with updates. This gives extra flexibility in both sequential and parallel applications. We study the version of multi-way trees called (a,b)-trees (which includes B-trees) with the operations insertion, deletion, and group insertion. The latter has applications in for instance document databases, WWW search engines, and differential indexing. We prove that we obtain the optimal asymptotic rebalancing complexities of amortized constant time for insertion and deletion and amortized logarithmic time in the size of the group for group insertion. These results hold even for the relaxed version. This is an improvement over the existing results in the most interesting cases.
OriginalsprogEngelsk
TitelProceedings of the Twentieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
Antal sider8
ForlagAssociation for Computing Machinery
Publikationsdato2001
Sider93-101
DOI
StatusUdgivet - 2001
BegivenhedTwentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - Santa Barbara, USA
Varighed: 21. maj 2001 → 23. maj 2001

Konference

KonferenceTwentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
Land/OmrådeUSA
BySanta Barbara
Periode21/05/2001 → 23/05/2001

Fingeraftryk

Dyk ned i forskningsemnerne om 'Relaxed Multi-Way Trees with Group Updates'. Sammen danner de et unikt fingeraftryk.

Citationsformater