Алгоритм несвязанного множества для больших наборов данных

Question

В настоящее время я работаю над проблемой, которая включает создание непересекающихся наборов из большого набора данных размером 165 ГБ.Используемый в настоящее время алгоритм является алгоритмом объединения по рангу.Однако размер набора данных не позволяет одновременно хранить все данные в памяти (часть данных находится в базе данных, а другая часть обрабатывается в памяти).

Но проблема в том, чтозанимает много времени при поиске существования элемента в уже созданных наборах (это занимает время O (n2)).

Цените, если кто-нибудь может предоставить решение вышеуказанной проблемы

Answer 1

Есть много способов нарезать и нарезать кубиками.

Я бы предложил за один проход назначить инкрементный индекс каждому элементу большого набора данных.Затем создайте битовый вектор правильного размера, чтобы указать «в объединении всех в настоящее время назначенных наборов».Этот битовый вектор должен быть достаточно маленьким, чтобы помещаться в память.