Миграция данных: различия между версиями

Голубчик и др. [3] провели обширное исследование эффективности алгоритмов миграции данных при различных изменениях схем доступа пользователей. Они сравнивали алгоритм 9,5-аппроксимации [11] и несколько других эвристических алгоритмов. Некоторые из этих эвристических алгоритмов не могут предоставить константные гарантии аппроксимации, для других алгоритмов такие гарантии вообще неизвестны. Алгоритм Хуллера и др. [11] имеет коэффициент 9,5 в наихудшем случае, однако в экспериментах количество необходимых раундов превышало нижнюю границу менее чем в 3,25 раз.

Они также сформулировали проблему соответствия, в которой вычисляется сопоставление дисков в исходном расположении с дисками в целевом расположении, обеспечивающее минимальное количество изменений. Как показали их эксперименты, хорошее решение задачи соответствия может повысить эффективность алгоритмов миграции данных в 4,4 раза по сравнению с плохим решением.