Поиск наборов, которые имеют определенные подмножества

https://stackoverflow.com/questions/494502

20-08-2019
|

Вопрос

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

Мои данные по существу состоят из большого количества наборов чисел.Эти наборы могут содержать от 1 до n чисел (хотя в 99,9% наборов n меньше 15), и таких наборов примерно 1,5–2 миллиарда (к сожалению, этот размер исключает перебор).

Мне нужно иметь возможность указать набор из k элементов и вернуть мне каждый набор из k+1 элементов или более, содержащий указанное подмножество.

Простой пример:
Предположим, у меня есть следующие наборы данных:
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
(5,8,11)

Если бы я дал запрос (1,3), у меня были бы наборы:(1,2,3), (1,2,3,4,5) и (1,3,8,9).
Запрос (11) вернет набор:(5,8,11).
Запрос (1,2,3) вернет наборы:(1,2,3) и (1,2,3,4,5)
Запрос (50) не вернет наборов:

К настоящему времени закономерность должна быть ясна.Основное различие между этим примером и моими данными заключается в том, что наборы в моих данных больше, числа, используемые для каждого элемента наборов, варьируются от 0 до 16383 (14 бит), и существует еще много, много, много других наборов.

Если это имеет значение, я пишу эту программу на C++, хотя я также знаю Java, C, немного ассемблера, немного Фортрана и немного Perl.

Есть ли у кого-нибудь подсказки, как это осуществить?

редактировать:
Отвечу на пару вопросов и добавлю несколько замечаний:

1.) Данные не меняются.Все это было снято за один длинный набор прогонов (каждый разбит на файлы по 2 гигабайта).

2.) Что касается места для хранения.Необработанные данные занимают примерно 250 гигабайт.По моим оценкам, после обработки и удаления большого количества посторонних метаданных, которые меня не интересуют, я могу сократить это значение до 36–48 гигабайт в зависимости от того, сколько метаданных я решу сохранить (без индексов).Кроме того, если при первоначальной обработке данных я столкнусь с достаточным количеством одинаковых наборов, я смогу еще больше сжать данные, добавив счетчики для повторяющихся событий, а не просто повторяя события снова и снова.

3.) Каждое число в обрабатываемом наборе фактически содержит как минимум два числа: 14 бит для самих данных (обнаруженная энергия) и 7 бит для метаданных (номер детектора).Поэтому мне понадобится МИНИМУМ три байта на номер.

4.) Мой комментарий «хотя в 99,9% наборов n меньше 15» ввел в заблуждение.Предварительно просмотрев некоторые фрагменты данных, я обнаружил, что у меня есть наборы, содержащие до 22 чисел, но медиана составляет 5 чисел в наборе, а среднее значение — 6 чисел в наборе.

5.) Хотя мне нравится идея создания индекса указателей в файлах, я немного насторожен, потому что для запросов, включающих более одного числа, мне остается полумедленная задача (по крайней мере, я думаю, что она медленная) по поиску набора всех указателей, общих для списков, т.е. поиск наибольшего общего подмножества для заданного числа наборов.

6.) Что касается доступных мне ресурсов, я могу собрать примерно 300 ГБ пространства после того, как у меня появятся необработанные данные в системе (оставшаяся часть моей квоты в этой системе).Система представляет собой двухпроцессорный сервер с двумя четырехъядерными процессорами AMD и 16 гигабайтами оперативной памяти.

7.) Да, 0 может произойти, это артефакт системы сбора данных, но это может произойти.

Решение 4

Недавно я обнаружил методы, которые используют кривые заполнения пространства для преобразования многомерных данных в одно измерение.Затем можно индексировать данные на основе их 1D-индекса.Запросы диапазона можно легко выполнить, найдя сегменты кривой, пересекающие прямоугольник, представляющий кривую, а затем извлекая эти сегменты.

Я считаю, что этот метод намного превосходит предлагаемое создание безумных индексов, потому что, посмотрев на него, индекс будет такого же размера, как и данные, которые я хотел сохранить, а это вряд ли хорошо.Несколько более подробное объяснение этого можно найти по адресу:

http://www.ddj.com/184410998
и
http://www.dcs.bbk.ac.uk/~jkl/publications.html

Другие советы

Ваша проблема такая же, как и у поисковых систем.«У меня есть миллиард документов.Мне нужны те, которые содержат этот набор слов». У вас просто (очень удобно) целые числа вместо слов и небольшие документы.Решение представляет собой инвертированный индекс. Введение в поиск информации Автор: Manning et al (по этой ссылке) доступен бесплатно в Интернете, легко читается и содержит множество подробностей о том, как это сделать.

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

Если предположить случайное распределение 0–16383, с постоянными 15 элементами в наборе и двумя миллиардами наборов, каждый элемент появится примерно в 1,8 млн наборов.Рассматривали ли вы (и есть ли у вас возможность) создать таблицу поиска размером 16384x~1,8M (30B записей по 4 байта каждая)?Имея такую таблицу, вы можете запросить, какие наборы содержат (1), (17) и (5555), а затем найти пересечения этих трех списков из ~ 1,8 млн элементов.

Мое предположение заключается в следующем.

Предположим, что у каждого набора есть имя, идентификатор или адрес (4-байтовое число подойдет, если их всего 2 миллиарда).

Теперь просмотрите все наборы один раз и создайте следующие выходные файлы:

Файл, содержащий идентификаторы всех наборов, содержащих «1».
Файл, содержащий идентификаторы всех наборов, содержащих цифру «2».
Файл, содержащий идентификаторы всех наборов, содержащих цифру «3».
...и т. д ...

Если в наборе 16 записей, то в среднем каждый из этих 2^16 файлов будет содержать идентификаторы 2^20 наборов;поскольку каждый идентификатор составляет 4 байта, для этого потребуется 2 ^ 38 байт (256 ГБ) памяти.

Вы сделаете это один раз, прежде чем обрабатывать запросы.

При получении запросов используйте эти файлы следующим образом:

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

Я предполагаю, что если вы сделаете вышеописанное, создание индексов будет (очень) медленным, а обработка запросов будет (очень) быстрой.

Создайте 16383 индексных файла, по одному на каждое возможное значение поиска.Для каждого значения во входном наборе запишите позицию начала набора в соответствующий индексный файл.Важно, чтобы каждый из индексных файлов содержал одинаковые номера для одного и того же набора.Теперь каждый индексный файл будет состоять из возрастающих индексов в главном файле.

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

Если ваши значения распределены равномерно, каждый индексный файл будет содержать 1/16383 входных наборов.Если ваш средний набор поиска состоит из 6 значений, вы будете выполнять линейный проход по 6/16383 исходного ввода.Это по-прежнему решение O(n), но теперь ваше n немного меньше.

P.S.Ноль — невозможное значение результата, или у вас действительно есть 1638?4 возможности?

Просто играю в адвоката дьявола за подход, который включает в себя грубую силу + поиск по индексу:

Создайте индекс с min , max и no элементов наборов.
Затем примените грубую силу, исключая наборы, где max < max (искомый набор) и min > min (искомый набор)
При полном переборе также исключаются наборы, количество элементов которых меньше, чем в искомом наборе.

95% ваших поисков на самом деле будут грубым перебором очень небольшого подмножества.Просто мысль.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow