דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

ceClub: The SkipTrie: Low-Depth Concurrent Search without Rebalancing
event speaker icon
רותם אושמן (אונ' טורונטו)
event date icon
יום רביעי, 2.1.2013, 11:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
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.
[בחזרה לאינדקס האירועים]