Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

ceClub: The SkipTrie: Low-Depth Concurrent Search without Rebalancing
event speaker icon
Rotem Osman (University of Toronto)
event date icon
Wednesday, 02.01.2013, 11:30
event location icon
Room 337-8 Taub Bld.
To date, all concurrent search structures that can support predecessor queries have had depth logarithmic in m, the number of elements. This work introduces the SkipTrie, a new concurrent search structure supporting predecessor queries in amortized expected O(log log u + c) steps, insertions and deletions in O( c log log u ), and using O(m) space, where u is the size of the key space and c is the maximum point contention during the operation.

The SkipTrie is a probabilistically-balanced version of a y-fast trie consisting of a very shallow skiplist from which randomly chosen elements are inserted into a hash-table based x-fast trie. By inserting keys into the x-fast-trie probabilistically, we eliminate the need for rebalancing, and can provide a lock-free linearizable implementation.