Структура данных, которая позволяет эффективный поиск на основе тегов

11

Я ищу высокоэффективную структуру данных для хранения данных, аналогичную следующей.

Идентификационные метки Order1 Order2 
--------------------------
1 1,2 1 1
2 2,5 2 3
3 1,7 4 7
4 6 3 0

Мне нужно иметь возможность запрашивать эту структуру таким образом, чтобы она выдала мне список всех идентификаторов, содержащих выражение тегов - поддержка ANDи ORи NOTоперации. Например. ((1 или 2) а не 7)

Мне также нужно иметь возможность указать порядок результатов (Order1 или Order2) и указать максимальное количество строк, возвращаемых с необязательным смещением. Производительность для получения первых 30-100 результатов является ключевой.

Наконец, мне нужен дешевый способ поиска «отношений тегов», например, я хочу знать, какие теги «связаны» с тегами (1 ИЛИ 2) и с какой частотой. Это означает, что теги появляются в том же наборе, что и 1 ИЛИ 2 ... упорядоченные по частоте.

Любая идея о том, какая структура данных (или набор структур) будет очень эффективной для такого рода работы?

(Я хотел бы использовать это в качестве доказательства концепции для редизайна тегированных страниц семейства сайтов SE)

Сэм Шафран
источник
1
Просто комментарий (возможно, банальный). Почему вы не полагаетесь на систему управления реляционными базами данных? Вы можете определить таблицу с парами <id, tag> и добавить индекс для столбца tag. Затем вы можете использовать стандартные запросы SQL для извлечения данных. СУБД будет эффективно выполнять «грязную» работу по оптимизации запросов и сортировке выходных данных.
Марцио Де Биаси
@Vor, выражения невероятно неэффективны в больших масштабах, самостоятельные объединения становятся кошмарными запросами.
Сэм Шафран
@ Сам: хорошо. Ваша задача довольно распространена, поэтому я подумал, что хорошая СУБД (с инструментом интеллектуального анализа данных) справится с этой задачей. Я предоставляю слово эксперту по структуре данных. :-)
Марцио Де Биаси
Я полагаю, что если разрешить все комбинации AND, OR, NOT, будет сложно создать структуру данных, которая не перечисляет все элементы (возможно, она может быть ограничена 3-CNF?). Если такого ограничения не существует, то, возможно, просто просматривайте записи (в указанном порядке), пока не найдете 30-100, которые соответствуют вашим требованиям к тегам. Хотя, в целом, я согласен с предложением Вора использовать базу данных для выполнения тяжелой работы за вас.
bbejot
Не эксперт, но я думаю, что если вы не наложите некоторые ограничения на то, как вы можете спрашивать о тегах, это будет сложно. Ограничение их CNF (как предположил bbejot) - это один из способов, другой ограничивает количество различных тегов, о которых может запрашиваться запрос, небольшим числом (скажем, 6).
Каве

Ответы:

6

Это не совсем ответ об эффективной структуре данных, а скорее проработка комментариев @bbejot и @Kaveh, в которых приводится аргумент для размахивания рукой, почему, учитывая текущий вопрос, мы не должны ожидать чего-то, что делает намного лучше, чем поиск в вся база данных. Аргумент основан на сокращении от SAT, экспоненциальной гипотезе времени и большом количестве размахиваний руками.

nx|x|=nxj=1jxj=012nkkANDORNOTn2n

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

n1

Артем Казнатчеев
источник
Хорошее наблюдение. Каждый вопрос имеет не более 5 тегов, поэтому запрос о тегах эквивалентен 5-CNF.
Каве
Спасибо! да, мы можем предположить, что 5-CNF здесь больше, поведение тегирования не является случайным. В общем, люди будут отмечать вещи наиболее распространенными тегами, так что это позволит использовать несколько других ярлыков.
Сэм Шафран
1
@Kaveh, мы закончили работу над структурой памяти. Есть несколько нетривиальных ярлыков, сортировка является узким местом, использование сортировки кучи или модифицированной быстрой сортировки позволяет эффективно выбирать верхнюю N без необходимости выполнять полную сортировку. Предварительный расчет сортировок позволяет более эффективно выбирать оси и избегать сортировок, когда требуется полное сканирование. многопоточность ускоряет выбор. большая часть работы может быть отложена до фона, прежде чем пользователи будут взаимодействовать со структурами. Удивительно, что наши структуры в памяти усредняют 0 мс для поиска в наборе данных переполнения стека.
Сэм Шафран
@SamSaffron - Где публикация MSO, детализирующая эту функцию? У нас есть сообщение об ошибке здесь .
Кевин Вермеер
5

Это довольно простой ответ, но я считаю эффективным:

Map Tag ([Id],[Id])O(log(n))

Map Id (Set Tag)IdO(nlog(m))

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