Master’s Thesis Presentation • Algorithms and Complexity • Extremely Fast (a,b)-trees at all Contention LevelsExport this event to calendar

Monday, August 16, 2021 — 1:00 PM EDT

Please note: This master’s thesis presentation will be given online.

Anubhav Srivastava, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Trevor Brown

The ordered dictionary is one of the most fundamental abstract data types. It stores a set of key-value pairs, and supports operations to insert, remove and retrieve key-value pairs. It can also support range query operations.

In this thesis presentation, I will describe how (a,b)-trees (a generalization of B-trees) with simple optimistic locking can yield concurrent dictionaries that outperform state-of-the-art implementations. The trees perform particularly well under update-heavy workloads (in some cases outperforming all leading trees by a factor of 2). I also describe how elimination, a well-known idea in concurrent stacks, can be applied to further accelerate performance in skewed access distributions (in which some keys are accessed/updated more often than others).


To join this master’s thesis presentation on MS Teams, please go to https://teams.microsoft.com/l/meetup-join/19%3ameeting_NWQ1OTFiOTctYTllMS00MTE5LTk2Y2UtMWRiNDZhMTc4NmM5%40thread.v2/0?context=%7b%22Tid%22%3a%22723a5a87-f39a-4a22-9247-3fc240c01396%22%2c%22Oid%22%3a%221083eef2-81b4-42c4-a900-c879b9204119%22%7d.

Location 
Online master’s thesis presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2021 (178)
    1. November (2)
    2. October (12)
    3. September (21)
    4. August (20)
    5. July (17)
    6. June (11)
    7. May (16)
    8. April (27)
    9. March (20)
    10. February (13)
    11. January (19)
  2. 2020 (217)
    1. December (18)
    2. November (12)
    3. October (7)
    4. September (21)
    5. August (28)
    6. July (14)
    7. June (18)
    8. May (16)
    9. April (20)
    10. March (16)
    11. February (25)
    12. January (22)
  3. 2019 (255)
  4. 2018 (217)
  5. 2017 (36)
  6. 2016 (21)
  7. 2015 (36)
  8. 2014 (33)
  9. 2013 (23)
  10. 2012 (4)
  11. 2011 (1)
  12. 2010 (1)
  13. 2009 (1)
  14. 2008 (1)