Структуры данных и алгоритм поиска для нескольких предикатов

Question

Кто-нибудь знает какую-либо хорошую структуру данных и алгоритм для поиска с несколькими предикатами.

например. Предположим, у меня есть набор данных заголовка tcp (при условии, что нет дубликатов). Если бы я искал заголовок tcp списка по src ip, я мог бы отсортировать набор по src IP и выполнить бинарный поиск.

Какую структуру данных / алгоритм мне следует использовать, если я хочу найти заголовок tcp из набора, который соответствует всем src / dst ip / port? (помимо перебора всех наборов).

Answer 1

Это именно то, с чем поставщики баз данных сталкивались годами. Если вы собираетесь последовательно искать по src / dst IP / порту, вы можете использовать это в качестве критерия для сортировки и искать его более или менее напрямую.

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

Конечно, если вы предпочитаете, вы также можете уменьшить количество индексов, поэтому (например) вы можете использовать индексы, чтобы получить набор записей с правильными исходными и целевыми IP-адресами, а затем просто просмотреть их (возможно, довольно маленький), чтобы получить те с правильным номером порта.

Answer 2

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

Вы также можете использовать индекс для (a, b, c), чтобы запросить (a, б) или просто (а), поэтому разумный выбор индексов может позволить вам избежать необходимости объединения слиянием.

Answer 3

В C ++ Boost есть нечто, называемое многоиндексным контейнером. По сути, это группа хеш-таблиц, по одной для каждого ключа, с некоторым кодом для обеспечения их согласованности.

Answer 4

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