24
$\begingroup$

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 ?

$\endgroup$
4
  • $\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, 2010 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$ Oct 3, 2010 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, 2010 at 19:58
  • $\begingroup$ Actually no. I am sadly illiterate in concurrent methods. Thanks for the refs. $\endgroup$ Oct 3, 2010 at 20:40

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • 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, 2010 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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