Параллельный динамический поиск

Существует ли естественный параллельный аналог красно-черных деревьев со схожими или даже не очень худшими свойствами для обновлений, хотя он достаточно эффективен для работы?

В целом, что мы можем сделать лучше для параллельного поиска с обновлениями?

ds.algorithms ds.data-structures dc.parallel-comp concurrency dynamic-algorithms Суреш Венкат
источник

Какие именно свойства вы хотите сохранить или превратить «не ужасно хуже»? Насколько важно, чтобы состояние равновесия оставалось для красно-черных деревьев? Будут ли ожидаемые границы, как в параллельных списках пропусков, приемлемыми?

jbapple

Я думаю, что ожидаемые границы будут в порядке. Это ситуация, когда мы очень часто попадаем на структуру данных с обновленными значениями ключа, так что, если быть точным, даже эффективные операции с ключом изменения в виде куч Фибоначчи вполне подходят. У вас есть хорошая ссылка для одновременного пропуска списков?

Суреш Венкат

Книга Херлихи и Шавита «Искусство многопроцессорного программирования» или «Связанные списки без блокировок и списки пропусков» или java.util.concurrent или Практическая свобода блокировок . Рассматривали ли вы использование параллельной хэш-таблицы, такой как хэш-таблица классиков ?

jbapple

Вообще-то, нет. Я, к сожалению, неграмотен в параллельных методах. Спасибо за ссылки.

Суреш Венкат

Ответы:

Из того, что я могу сказать, стратегии включают в себя смягчение условий баланса, а затем выполнение обновлений перебалансировки в пакетах. Вот статья из Hanke et al., 1997 [PDF] , в которой, я думаю, основное внимание уделяется их методике агрегирования и разрешения операций обновления, чтобы их можно было выполнять одновременно.

Джеймс Кинг
источник

Я думаю, что вы можете найти интересный ответ в книге Окасаки « Чисто функциональные структуры данных» . В этой книге показано много структур данных, так что каждое обновление не требует больших затрат (обычно занимает только постоянное или логарифмическое время).

$n$ $n$

Артур МИЛКИОР
источник

Я думаю, что без дальнейшей модификации чисто функциональные деревья поиска сериализуют все обновления и, таким образом, плохо работают при конфликте записи.

jbapple