Weighted dynamic finger in binary search trees

John Iacono; Stefan Langerman

doi:10.1137/1.9781611974331.ch49

Weighted dynamic finger in binary search trees

John Iacono, Stefan Langerman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

It is shown that the online binary search tree data structure GreedyASS performs asymptotically as well on a sufficiently long sequence of searches as any static binary search tree where each search begins from the previous search (rather than the root). This bound is known to be equivalent to assigning each item i in the search tree a positive weight w_i and bounding the search cost of an item in the search sequence si,..., s_m (Equation presented) This result is the strongest finger-type bound to be proven for binary search trees. By setting the weights to be equal, one observes that our bound implies the dynamic finger bound. Compared to the previous proof of the dynamic finger bound for Splay trees, our result is significantly shorter, stronger, simpler, and has reasonable constants.

Original language	English (US)
Title of host publication	27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Editors	Robert Krauthgamer
Publisher	Association for Computing Machinery
Pages	672-691
Number of pages	20
ISBN (Electronic)	9781510819672
DOIs	https://doi.org/10.1137/1.9781611974331.ch49
State	Published - 2016
Event	27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States Duration: Jan 10 2016 → Jan 12 2016

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume	1

Other

Other	27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Country	United States
City	Arlington
Period	1/10/16 → 1/12/16

ASJC Scopus subject areas

Software
Mathematics(all)

Access to Document

10.1137/1.9781611974331.ch49

Fingerprint Dive into the research topics of 'Weighted dynamic finger in binary search trees'. Together they form a unique fingerprint.

Cite this

Weighted dynamic finger in binary search trees. / Iacono, John; Langerman, Stefan.

27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. ed. / Robert Krauthgamer. Association for Computing Machinery, 2016. p. 672-691 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Iacono, J & Langerman, S 2016, Weighted dynamic finger in binary search trees. in R Krauthgamer (ed.), 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 1, Association for Computing Machinery, pp. 672-691, 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, United States, 1/10/16. https://doi.org/10.1137/1.9781611974331.ch49

@inproceedings{47772f01fa5045b0b5e2f377229371d8,

title = "Weighted dynamic finger in binary search trees",

abstract = "It is shown that the online binary search tree data structure GreedyASS performs asymptotically as well on a sufficiently long sequence of searches as any static binary search tree where each search begins from the previous search (rather than the root). This bound is known to be equivalent to assigning each item i in the search tree a positive weight wi and bounding the search cost of an item in the search sequence si,..., sm (Equation presented) This result is the strongest finger-type bound to be proven for binary search trees. By setting the weights to be equal, one observes that our bound implies the dynamic finger bound. Compared to the previous proof of the dynamic finger bound for Splay trees, our result is significantly shorter, stronger, simpler, and has reasonable constants.",

author = "John Iacono and Stefan Langerman",

year = "2016",

doi = "10.1137/1.9781611974331.ch49",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "672--691",

editor = "Robert Krauthgamer",

booktitle = "27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016",

note = "27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 ; Conference date: 10-01-2016 Through 12-01-2016",

}

TY - GEN

T1 - Weighted dynamic finger in binary search trees

AU - Iacono, John

AU - Langerman, Stefan

PY - 2016

Y1 - 2016

N2 - It is shown that the online binary search tree data structure GreedyASS performs asymptotically as well on a sufficiently long sequence of searches as any static binary search tree where each search begins from the previous search (rather than the root). This bound is known to be equivalent to assigning each item i in the search tree a positive weight wi and bounding the search cost of an item in the search sequence si,..., sm (Equation presented) This result is the strongest finger-type bound to be proven for binary search trees. By setting the weights to be equal, one observes that our bound implies the dynamic finger bound. Compared to the previous proof of the dynamic finger bound for Splay trees, our result is significantly shorter, stronger, simpler, and has reasonable constants.

AB - It is shown that the online binary search tree data structure GreedyASS performs asymptotically as well on a sufficiently long sequence of searches as any static binary search tree where each search begins from the previous search (rather than the root). This bound is known to be equivalent to assigning each item i in the search tree a positive weight wi and bounding the search cost of an item in the search sequence si,..., sm (Equation presented) This result is the strongest finger-type bound to be proven for binary search trees. By setting the weights to be equal, one observes that our bound implies the dynamic finger bound. Compared to the previous proof of the dynamic finger bound for Splay trees, our result is significantly shorter, stronger, simpler, and has reasonable constants.

UR - http://www.scopus.com/inward/record.url?scp=84963522569&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84963522569&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974331.ch49

DO - 10.1137/1.9781611974331.ch49

M3 - Conference contribution

AN - SCOPUS:84963522569

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 672

EP - 691

BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

A2 - Krauthgamer, Robert

PB - Association for Computing Machinery

T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

Y2 - 10 January 2016 through 12 January 2016

ER -