Существует ли какой-либо усовершенствованный алгоритм непересекающихся множеств для действительно больших данных (например, более 2^32 элементов и более 2^32 пар для объединения)?
Очевидно, самая большая проблема заключается в том, что я не могу создать такой большой массив, поэтому мне интересно, есть ли лучший алгоритм или лучшая структура данных для выполнения моей задачи?
Один из способов работы с действительно большими данными — запускать их во внешней памяти. http://terrain.cs.duke.edu/pubs/union-find.pdf (I/O-Efficient Batched Union-Find и его приложения к анализу рельефа) содержит как теоретический алгоритм, состоящий из довольно сложной последовательности вызовов других пакетных алгоритмов, так и (раздел 3) автономный рекурсивный алгоритм. алгоритм, который не так асимптотически эффективен, но выглядит так, как будто он может быть практичным.
