Я аспирант физики, и я работаю над написанием некоторого кода, чтобы сортировать несколько сотен гигабайт данных и возвращать фрагменты этих данных, когда я их запрашиваю. Вот хитрость, я не знаю хорошего метода для сортировки и поиска данных такого рода.
Мои данные в основном состоят из большого числа наборов чисел. Эти наборы могут содержать от 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, некоторую сборку, немного fortran и немного perl.
У кого-нибудь есть какие-нибудь подсказки, как это осуществить?
редактировать:
Чтобы ответить на пару вопросов и добавить несколько пунктов:
1.) Данные не меняются. Все это было сделано за один длинный набор прогонов (каждый разбит на 2 гигабайта).
2.) Что касается места для хранения. Необработанные данные занимают примерно 250 гигабайт. По моим оценкам, после обработки и удаления большого количества посторонних метаданных, которые меня не интересуют, я мог бы сократить их до 36-48 гигабайт в зависимости от того, сколько метаданных я решил сохранить (без индексов). Кроме того, если при первоначальной обработке данных я обнаружу достаточно одинаковых наборов, я смогу еще больше сжать данные, добавив счетчики для повторяющихся событий, а не просто повторяя события снова и снова.
3.) Каждое число в обработанном наборе фактически содержит по меньшей мере два числа 14 битов для самих данных (обнаруженная энергия) и 7 битов для метаданных (номер детектора). Так что мне понадобится как минимум три байта на число.
4.) Мой комментарий «хотя в 99,9% комплектов, n меньше 15» вводил в заблуждение. Предварительно просматривая некоторые фрагменты данных, я обнаружил, что у меня есть наборы, которые содержат целых 22 числа, но медиана составляет 5 номеров на набор, а среднее значение составляет 6 номеров на набор.
5.) Хотя мне нравится идея построения указателя указателей на файлы, я немного осторожен, потому что для запросов, включающих более одного числа, у меня остается полумедленная задача (по крайней мере, я думаю, что она медленная) найти набор всех указателей, общих для списков, то есть найти наибольшее общее подмножество для данного числа наборов.
6.) С точки зрения доступных мне ресурсов, я могу собрать приблизительно 300 гигабайт пространства после того, как у меня есть необработанные данные в системе (остаток моей квоты в этой системе). Система представляет собой двухпроцессорный сервер с 2 четырехъядерными процессорами и 16 гигабайтами оперативной памяти.
7.) Да, 0 может иметь место, это артефакт системы сбора данных, когда это происходит, но это может произойти.