Welcome to DiSC 2002
SIGMOD 2001
PODS 2001
= PODS'01 Website
= SIGMOD/PODS'01 Plena
<<< = PODS'01 Papers>>>
= Invited Talks
= Award Talks
= Tutorials
SIGMOD RECORD 2001
CIKM 2001
CoopIS 2001
DASFAA 2001
DASFAA 2000
DBPL 2001
Data Engineering Bul
DEXA_EC-WEB 2001
DMKD 2001
DPDJ 2001
HYPERTEXT 2001
ICDE 2001
ICDM 2001
ICDT 2001
JCDL 2001
KDD 2001
KDD_EXPLORATIONS 20
KRDB 2001
MDM 2001
MIR 2001
MIS 2001
RIDE 2001
SBBD 2001
SIGIR 2001
SIGIR FORUM 2001
SSDBM 2001
SSTD 2001
TODS 2001
TIME 2001
VLDB 2001
VLDBJ 2001

Relaxed Multi-Way Trees with Group Updates


Kim S. Larsen

  View Paper (PDF)  

Return to Award Talks


Abstract

Data structures with relaxed balance differ from standard structures in that rebalancing can be delayed and interspersed with updates. This gives extra exibility 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 and WWW search engines. 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. Our results also demonstrate that a binary tree scheme with the same complexities can be designed. This is an improvement over the existing results in the most interesting cases.


DiSC'02 © 2003 Association for Computing Machinery