<p>I think you may find interesting answer in Okasaki's book <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.64.3080&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Purely Functional Data Structures</a>. In this book, many data structures are shown, such that every updates are not expensive (usually only take a constant or logarithm time). </p>

<p>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.</p>

CC BY-SA 2.5
2010-10-03T20:48:05.183Z
I think that, without further modification, purely functional search trees serialize all updates, and thus perform poorly under write contention.
jbapple
CC BY-SA 2.5
2010-08-23T07:45:28.440Z
2010-08-23T07:45:28.440Z
Arthur MILCHIOR
<p>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 <a href="http://algo.informatik.uni-freiburg.de/mitarbeiter/ottmann/lokale_publikationen/relaxed_balanced.pdf">[PDF]</a>, which I think focuses on their technique of aggregating and resolving update operations so that they can be performed concurrently.</p>

CC BY-SA 2.5
2010-08-20T20:38:01.607Z
2010-08-20T20:38:01.607Z
James King
<p>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 ? </p>

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

CC BY-SA 2.5
2010-10-03T15:39:36.900Z
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?
jbapple
CC BY-SA 2.5
2010-10-03T19:30:16.170Z
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 ?
Suresh Venkat
CC BY-SA 2.5
2010-10-03T19:58:00.013Z
Herlihy & Shavit's book, The Art of Multiprocessor Programming, or ["Lock-free linked lists and skip lists"](http://www.cse.yorku.ca/~ruppert/Mikhail.pdf) or [java.util.concurrent](http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html) or [Practical lock-freedom](http://www.cl.cam.ac.uk/research/srg/netos/lock-free/). Have you considered using a concurrent hash table like a [hopscotch hash table](https://sites.google.com/site/cconcurrencypackage/hopscotch-hashing)?
jbapple
CC BY-SA 2.5
2010-10-03T20:40:57.007Z
Actually no. I am sadly illiterate in concurrent methods. Thanks for the refs.
Suresh Venkat
<ds.algorithms><ds.data-structures><dc.parallel-comp><concurrency><dynamic-algorithms>
Parallel Dynamic Search
Suresh Venkat
# Parallel Dynamic Search

(Asked by: username_0 on 2010-08-18)

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 ?

**Tags:** ds.algorithms, ds.data-structures, dc.parallel-comp, concurrency, dynamic-algorithms

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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 ?  
> **username_1**: Herlihy & Shavit's book, The Art of Multiprocessor Programming, or ["Lock-free linked lists and skip lists"](http://www.cse.yorku.ca/~ruppert/Mikhail.pdf) or [java.util.concurrent](http://download.oracle.com/javase/6/docs/api/java/util/concurrent/ConcurrentSkipListMap.html) or [Practical lock-freedom](http://www.cl.cam.ac.uk/research/srg/netos/lock-free/). Have you considered using a concurrent hash table like a [hopscotch hash table](https://sites.google.com/site/cconcurrencypackage/hopscotch-hashing)?  
> **username_0**: Actually no. I am sadly illiterate in concurrent methods. Thanks for the refs.  

---

## 2 answers

### Answer by username_3 on 2010-08-20. Score: 8 | Accepted answer

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]](http://algo.informatik.uni-freiburg.de/mitarbeiter/ottmann/lokale_publikationen/relaxed_balanced.pdf), which I think focuses on their technique of aggregating and resolving update operations so that they can be performed concurrently.


---

### Answer by username_2 on 2010-08-23. Score: 5

I think you may find interesting answer in Okasaki's book [Purely Functional Data Structures](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.64.3080&rep=rep1&type=pdf). 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.

> **Comments:**
> **username_1**: I think that, without further modification, purely functional search trees serialize all updates, and thus perform poorly under write contention.  

---

