Эффективная работа с большими объемами данных

Изначальная архитектура приложения была построена ошибочно - все данные сливались в один файл, размер которого перевалил теперь за отметку 950ГБ.
Есть ли какой-нибудь эффективный метод (из области big-data) выделения из этого массива данных групп сущностей, состоящих из одних и тех же символов (так называемых анаграмм)?

Ответ

Стандартная идея вот какая:
К каждой сущности дописать её номер в исходном списке. У каждой сущности отсортировать символы. Отсортировать сущности. Теперь анаграммы будут находиться рядом. Теперь для нахождения анаграмм нужен лишь один пробег по данным.
Все эти операции хорошо «параллелятся», Кроме, пожалуй сортировки.
С учётом этого можно изменить немного алгоритм:
Распартиционировать данные как угодно. Пронумеровать сущности и отсортировать их символы на каждом хосте по отдельности (номеру назначать уникальный префикс, чтобы не смешивать) Отсортировать данные каждого хоста. Смёржить все данные. Сначала заливать результат на первый хост, когда 1/n всех данных зальётся — на второй хост и т. д. (Это по сути перепартиционирование.) Далее пробег по данным на каждом хосте.
Вместо пункта 4, возможно, более эффективно будет не сливать данные вместе, а делать многохостовый пробег:
string currentValue = null; int anagramCount = 0; string[] nextByHost = new string[N]; for (i = 0..n-1) { currentByHost[i] = ""; nextByHost = fetch from host[i]; }
while (any of hosts has data) { if any of nextByHost[i] equals to currentValue, anagramCount++ fetch next from host[i] to nextByHost[i] else store currentValue and anagramCount currentValue = min(nextByHost) }