Búsqueda dinámica paralela

24

¿Existe un análogo paralelo natural a los árboles rojo-negros con propiedades similares o incluso no terriblemente peores para las actualizaciones, mientras que es razonablemente eficiente en el trabajo?

En términos más generales, ¿qué es lo mejor que podemos hacer para la búsqueda paralela con actualizaciones?

ds.algorithms ds.data-structures dc.parallel-comp concurrency dynamic-algorithms Suresh Venkat
fuente
¿Qué propiedades en particular desea preservar o convertir en "no terriblemente peor"? ¿Cuán importante es que la condición de equilibrio siga siendo la de los árboles rojo-negros? ¿Serían aceptables los límites esperados, como en las listas de omisión simultáneas?
jbapple
Creo que los límites esperados estarían bien. Esta es una situación en la que estamos golpeando la estructura de datos muy a menudo con valores clave actualizados, por lo que para ser precisos, incluso las operaciones de cambio de teclas eficientes a la fibonacci están bien. ¿Tiene una buena referencia para las listas de omisión concurrentes?
Suresh Venkat
El libro de Herlihy y Shavit, El arte de la programación multiprocesador, o "Listas enlazadas sin bloqueo y listas de salto" o java.util.concurrent o Practical-freedom . ¿Has considerado usar una tabla hash concurrente como una tabla hash de rayuela ?
jbapple
En realidad no. Soy tristemente analfabeta en los métodos concurrentes. Gracias por las referencias.
Suresh Venkat

Respuestas:

8

Por lo que puedo decir, las estrategias implican condiciones de equilibrio relajantes, luego realizar actualizaciones de reequilibrio en ráfagas. Aquí hay un artículo de Hanke et al., 1997 [PDF] , que creo que se centra en su técnica de agregar y resolver operaciones de actualización para que puedan realizarse simultáneamente.

James King
fuente
5

Creo que puede encontrar una respuesta interesante en el libro Estructuras de datos puramente funcionales de Okasaki . En este libro, se muestran muchas estructuras de datos, de modo que cada actualización no es costosa (por lo general, solo toma un tiempo constante o de logaritmo).

nortenorte

Arthur MILCHIOR
fuente
44
Creo que, sin más modificaciones, los árboles de búsqueda puramente funcionales serializan todas las actualizaciones y, por lo tanto, funcionan mal bajo la contención de escritura.
jbapple