TY - JOUR
T1 - A unified access bound on comparison-based dynamic dictionaries
AU - Bǎdoiu, Mihai
AU - Cole, Richard
AU - Demaine, Erik D.
AU - Iacono, John
N1 - Funding Information:
We thank Michael L. Fredman for helpful discussions. Research of the second author was supported in part by NSF grants CCR-0105678 and CCF-0515127. Research of the third author was supported in part by NSF grant CCF-0430849. Research of the fourth author was supported in part by NSF grants CCF-0430849 and CCF-9732689.
PY - 2007/8/31
Y1 - 2007/8/31
N2 - We present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. The unified bound specifies that it is quick to access an element that is near a recently accessed element. More precisely, if w (y) distinct elements have been accessed since the last access to element y, and d (x, y) denotes the rank distance between x and y among the current set of elements, then the amortized cost to access element x is O (miny log [w (y) + d (x, y) + 2]). This property generalizes the working-set and dynamic-finger properties of splay trees.
AB - We present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. The unified bound specifies that it is quick to access an element that is near a recently accessed element. More precisely, if w (y) distinct elements have been accessed since the last access to element y, and d (x, y) denotes the rank distance between x and y among the current set of elements, then the amortized cost to access element x is O (miny log [w (y) + d (x, y) + 2]). This property generalizes the working-set and dynamic-finger properties of splay trees.
UR - http://www.scopus.com/inward/record.url?scp=34547532086&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34547532086&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2007.03.002
DO - 10.1016/j.tcs.2007.03.002
M3 - Article
AN - SCOPUS:34547532086
SN - 0304-3975
VL - 382
SP - 86
EP - 96
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
ER -