Practical adaptive search trees with performance bounds

Kevin Fray, Kerri Morgan, Anthony Wirth, Justin Zobel

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

Abstract

Dynamic binary search trees are a fundamental class of dictionary data structure. Amongst these, the splay tree is space efficient and has amortized running-time bounds. In practice, splay trees perform best when the access sequence has regions of atypical items. Continuing a tradition started by Sleator and Tarjan themselves, we introduce a relaxed version, the α-Frequent Tree, that performs fewer rotations than the standard splay tree. We prove that the α-frequent trees inherit many of the distribution-sensitive properties of splay trees. 

Meanwhile, Conditional Rotation trees [Cheetham et al.] maintain access counters - one at each node - and have an excellent experimental reputation. By adding access counters to α-frequent trees, we create Splay Conditional Rotation (SCR) trees. These have the experimental performance of other counter-based trees, and the amortized bounds of splay trees.

Original languageEnglish
Title of host publicationACSW '17 Proceedings of the Australasian Computer Science Week Multiconference
Subtitle of host publicationJanuary 31 – February 3, 2017. Deakin University Waterfront Campus
EditorsPeter Strazdins, Michael Hobbs
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages8
ISBN (Electronic)9781450347686
DOIs
Publication statusPublished - 2017
Externally publishedYes
EventAustralasian Computer Science Conference 2017 - Geelong, Australia
Duration: 31 Jan 20173 Feb 2017
Conference number: 40
https://cs.anu.edu.au/conf/acsc2017/

Conference

ConferenceAustralasian Computer Science Conference 2017
Abbreviated titleACSC 2017
CountryAustralia
CityGeelong
Period31/01/173/02/17
Internet address

Keywords

  • Amortized analysis
  • Search trees
  • Splay trees

Cite this

Fray, K., Morgan, K., Wirth, A., & Zobel, J. (2017). Practical adaptive search trees with performance bounds. In P. Strazdins, & M. Hobbs (Eds.), ACSW '17 Proceedings of the Australasian Computer Science Week Multiconference: January 31 – February 3, 2017. Deakin University Waterfront Campus [a23] New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/3014812.3014836
Fray, Kevin ; Morgan, Kerri ; Wirth, Anthony ; Zobel, Justin. / Practical adaptive search trees with performance bounds. ACSW '17 Proceedings of the Australasian Computer Science Week Multiconference: January 31 – February 3, 2017. Deakin University Waterfront Campus. editor / Peter Strazdins ; Michael Hobbs. New York NY USA : Association for Computing Machinery (ACM), 2017.
@inproceedings{b1bc7c6e965f49c5b098cb2599006e82,
title = "Practical adaptive search trees with performance bounds",
abstract = "Dynamic binary search trees are a fundamental class of dictionary data structure. Amongst these, the splay tree is space efficient and has amortized running-time bounds. In practice, splay trees perform best when the access sequence has regions of atypical items. Continuing a tradition started by Sleator and Tarjan themselves, we introduce a relaxed version, the α-Frequent Tree, that performs fewer rotations than the standard splay tree. We prove that the α-frequent trees inherit many of the distribution-sensitive properties of splay trees. Meanwhile, Conditional Rotation trees [Cheetham et al.] maintain access counters - one at each node - and have an excellent experimental reputation. By adding access counters to α-frequent trees, we create Splay Conditional Rotation (SCR) trees. These have the experimental performance of other counter-based trees, and the amortized bounds of splay trees.",
keywords = "Amortized analysis, Search trees, Splay trees",
author = "Kevin Fray and Kerri Morgan and Anthony Wirth and Justin Zobel",
year = "2017",
doi = "10.1145/3014812.3014836",
language = "English",
editor = "Strazdins, {Peter } and Hobbs, {Michael }",
booktitle = "ACSW '17 Proceedings of the Australasian Computer Science Week Multiconference",
publisher = "Association for Computing Machinery (ACM)",
address = "United States",

}

Fray, K, Morgan, K, Wirth, A & Zobel, J 2017, Practical adaptive search trees with performance bounds. in P Strazdins & M Hobbs (eds), ACSW '17 Proceedings of the Australasian Computer Science Week Multiconference: January 31 – February 3, 2017. Deakin University Waterfront Campus., a23, Association for Computing Machinery (ACM), New York NY USA, Australasian Computer Science Conference 2017, Geelong, Australia, 31/01/17. https://doi.org/10.1145/3014812.3014836

Practical adaptive search trees with performance bounds. / Fray, Kevin; Morgan, Kerri; Wirth, Anthony; Zobel, Justin.

ACSW '17 Proceedings of the Australasian Computer Science Week Multiconference: January 31 – February 3, 2017. Deakin University Waterfront Campus. ed. / Peter Strazdins; Michael Hobbs. New York NY USA : Association for Computing Machinery (ACM), 2017. a23.

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

TY - GEN

T1 - Practical adaptive search trees with performance bounds

AU - Fray, Kevin

AU - Morgan, Kerri

AU - Wirth, Anthony

AU - Zobel, Justin

PY - 2017

Y1 - 2017

N2 - Dynamic binary search trees are a fundamental class of dictionary data structure. Amongst these, the splay tree is space efficient and has amortized running-time bounds. In practice, splay trees perform best when the access sequence has regions of atypical items. Continuing a tradition started by Sleator and Tarjan themselves, we introduce a relaxed version, the α-Frequent Tree, that performs fewer rotations than the standard splay tree. We prove that the α-frequent trees inherit many of the distribution-sensitive properties of splay trees. Meanwhile, Conditional Rotation trees [Cheetham et al.] maintain access counters - one at each node - and have an excellent experimental reputation. By adding access counters to α-frequent trees, we create Splay Conditional Rotation (SCR) trees. These have the experimental performance of other counter-based trees, and the amortized bounds of splay trees.

AB - Dynamic binary search trees are a fundamental class of dictionary data structure. Amongst these, the splay tree is space efficient and has amortized running-time bounds. In practice, splay trees perform best when the access sequence has regions of atypical items. Continuing a tradition started by Sleator and Tarjan themselves, we introduce a relaxed version, the α-Frequent Tree, that performs fewer rotations than the standard splay tree. We prove that the α-frequent trees inherit many of the distribution-sensitive properties of splay trees. Meanwhile, Conditional Rotation trees [Cheetham et al.] maintain access counters - one at each node - and have an excellent experimental reputation. By adding access counters to α-frequent trees, we create Splay Conditional Rotation (SCR) trees. These have the experimental performance of other counter-based trees, and the amortized bounds of splay trees.

KW - Amortized analysis

KW - Search trees

KW - Splay trees

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

U2 - 10.1145/3014812.3014836

DO - 10.1145/3014812.3014836

M3 - Conference Paper

BT - ACSW '17 Proceedings of the Australasian Computer Science Week Multiconference

A2 - Strazdins, Peter

A2 - Hobbs, Michael

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

ER -

Fray K, Morgan K, Wirth A, Zobel J. Practical adaptive search trees with performance bounds. In Strazdins P, Hobbs M, editors, ACSW '17 Proceedings of the Australasian Computer Science Week Multiconference: January 31 – February 3, 2017. Deakin University Waterfront Campus. New York NY USA: Association for Computing Machinery (ACM). 2017. a23 https://doi.org/10.1145/3014812.3014836