Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?

More generally, what's the best we can do for parallel search with updates ?

  • $\begingroup$ What properties in particular do you wish to preserve or turn "not-terribly-worse"? How important is it that the balance condition is still that of red-black trees? Would expected bounds, as in concurrent skip lists, be acceptable? $\endgroup$ – jbapple Oct 3 '10 at 15:39
  • $\begingroup$ I think expected bounds would be fine. This is a situation where we're hitting the data structure very often with updated key values, so to be precise, even efficient change-key operations a la fibonacci heaps are fine. Do you have a good ref for concurrent skip lists ? $\endgroup$ – Suresh Venkat Oct 3 '10 at 19:30
  • $\begingroup$ Herlihy & Shavit's book, The Art of Multiprocessor Programming, or "Lock-free linked lists and skip lists" or java.util.concurrent or Practical lock-freedom. Have you considered using a concurrent hash table like a hopscotch hash table? $\endgroup$ – jbapple Oct 3 '10 at 19:58
  • $\begingroup$ Actually no. I am sadly illiterate in concurrent methods. Thanks for the refs. $\endgroup$ – Suresh Venkat Oct 3 '10 at 20:40

From what I can tell, strategies involve relaxing balance conditions, then performing rebalancing updates in bursts. Here is a paper from Hanke et al., 1997 [PDF], which I think focuses on their technique of aggregating and resolving update operations so that they can be performed concurrently.


I think you may find interesting answer in Okasaki's book Purely Functional Data Structures. In this book, many data structures are shown, such that every updates are not expensive (usually only take a constant or logarithm time).

Let say that "d" is a structure just before the time you must rebalance. In a purely functional data structure you have got persistant data structures, hence you can add $n$ things to "d" and need to rebalance $n$ times. This is why amortized complexity does not work in this setting, and he created other way to obtains good algorithm where every step with updates are non-expensive.

  • 4
    $\begingroup$ I think that, without further modification, purely functional search trees serialize all updates, and thus perform poorly under write contention. $\endgroup$ – jbapple Oct 3 '10 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.