Структура данных / алгоритм для запроса: фильтр по A, сортировка по B, возврат N результатов

Question

Представьте, что у вас есть большой набор #m объектов со свойствами A и B.Какую структуру данных вы можете использовать в качестве индекса (ов) (или какой алгоритм) для повышения производительности следующего запроса?

find all objects where A between X and Y, order by B, return first N results;

То есть фильтровать по диапазону A и сортировать по B,но верните только первые несколько результатов (скажем, не более 1000).Вставки очень редки, поэтому допускается интенсивная предварительная обработка.Я не доволен следующими опциями:

1. С записями (или индексами), отсортированными по B : сканировать записи / индексы вB заказ, верните первый N, где A соответствует XY.В худших случаях (несколько объектов соответствуют диапазону XY или совпадения находятся в конце записей / индекса), это становится O(m), что для больших наборов данных размером m недостаточно.

2. С записями (или индексами), отсортированными по A : Выполняйте двоичный поиск до тех пор, пока не будет найден первый объект, соответствующий диапазону XY.Сканирование и создание массива ссылок на все k объекты, которые соответствуют диапазону.Сортируйте массив по B, верните первое N.Это O(log m + k + k log k).Если k мало, то это действительно O(log m), но если k велико, тогда стоимость сортировки становится даже хуже, чем стоимость линейного сканирования по всем m объектам.

3. Adaptive 2/1 : выполнить двоичный поиск первого совпадения диапазона XY (используя индекс выше A);сделать бинарный поиск для последнего соответствия диапазона.Если диапазон мал, перейдите к алгоритму 2;в противном случае вернемся к алгоритму 1. Проблема здесь в том случае, когда мы возвращаемся к алгоритму 1. Хотя мы проверили, что «многие» объекты проходят фильтр, что является хорошим случаем для алгоритма 1, это «много» является не более чем постоянной (Асимптотически сканирование O(n) всегда побеждает сортировку O(k log k)).Таким образом, у нас все еще есть алгоритм O(n) для некоторых запросов.

Существует ли алгоритм / структура данных, которая позволяет отвечать на этот запрос в сублинейное время?

Если нет,Какие могут быть хорошие компромиссы для достижения необходимой производительности?Например, если я не гарантирую возвращение объектов с лучшим ранжированием для их свойства B (напомним, <1,0), тогда я могу сканировать только часть индекса B.Но могу ли я сделать это, ограничивая качество результатов каким-либо образом? </p>

Answer 1

Вопрос, который вы задаете, по сути является более общей версией:

Q.У вас есть отсортированный список слов с весом, связанным с каждым словом, и вы хотите, чтобы все слова имели общий префикс с данным запросом q , и вы хотите, чтобы этот список был отсортирован по ассоциированному weight .

Я прав?

Если это так, вы можете проверить этот документ, в котором обсуждается, как это сделать за O (k log n) время, где k - количество элементов в желаемом выходном наборе, а n - количество записей в исходном входном наборе.Мы предполагаем, что k> log n .

http://dhruvbird.com/autocomplete.pdf

(я автор).

Обновление: я могу добавить еще одно уточнениезаключается в том, что вопрос, который вы задаете, связан с поиском в двумерном диапазоне, где вы хотите, чтобы все находилось в заданном X-диапазоне и верхнем K из предыдущего набора, отсортированного по Y-диапазону.

2D диапазонФункция поиска позволяет найти все в диапазоне X / Y (если оба диапазона известны).В этом случае вы знаете только X-диапазон, поэтому вам потребуется многократно выполнять запрос и выполнять двоичный поиск по Y-диапазону, пока вы не получите K результатов.Каждый запрос может быть выполнен с использованием времени O (log n), если вы используете дробное каскадирование, и O (log ² n), если используется наивный подход.Любой из них является сублинейным, поэтому с вами все будет в порядке.

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

Answer 2

Установите дерево сегментов на A и для каждого сегмента предварительно вычислите верхний N в диапазоне.Для запроса разбить входной диапазон на O (log m) сегментов и объединить предварительно вычисленные результаты.Время запроса O (N log log m + log m);пробел O (m log N).

Answer 3

Если количество элементов, которые вы хотите вернуть, невелико - примерно до 1% от общего количества элементов - тогда хорошо работает простой алгоритм выбора кучи. См. Когда теория встречается с практикой . Но это не сублинейный.

Для ожидаемых сублинейных показателей вы можете отсортировать элементы по A. При запросе используйте бинарный поиск, чтобы найти первый элемент, где A >= X, а затем последовательно сканируйте элементы до A > Y, используя технику выделения кучи, описанную в этом сообщении в блоге.

Это должно дать вам O(log n) для начального поиска, а затем O(m log k), где m - это количество предметов, где X <= A <= Y, а k - количество предметов, которые вы хотите вернуть. Да, для некоторых запросов он все равно будет O(n log k). Решающим фактором будет размер m.

Answer 4

при условии N << k < n, это можно сделать в O(logn + k + NlogN), аналогично тому, что вы предложили в варианте 2, но экономит некоторое время, вам не нужно сортировать все k элементов, а только N, что значительноменьше!

база данных отсортирована по A.

(1) find the first element and last element, and create a list containing these
    elements.
(2) find the N'th biggest element, using selection algorithm (*), and create a new 
    list of size N, with a second iteration: populate the last list with the N highest 
    elements.
(3) sort the last list by B.

Алгоритм выбора : найти N-й по величине элемент.здесь O(n) или O(k), потому что размер списка k.

сложность :
Шаг первый тривиален O(logn + k).
Шаг 2 - O(k) [выбор], а другая итерация - также O(k), поскольку в этом списке только k элементов.
Шаг 3 - O(NlogN), простая сортировка, и последний список содержит только N элементов.

Answer 5

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

Answer 6

Это не совсем конкретное решение, просто идея. Как насчет построения quadtree по осям A и B? Вы бы пошли вниз по дереву, скажем, в ширину; тогда:

• всякий раз, когда вы найдете поддерево со значениями A, выходящими за пределы заданного диапазона [X, Y], вы отбрасываете это поддерево (и не повторяете);
• всякий раз, когда вы обнаруживаете поддерево с A-значениями внутри заданного диапазона [X, Y], вы добавляете это поддерево в набор S, который вы строите, и не рекурсивно;
• всякий раз, когда вы находите поддерево с некоторыми значениями A внутри диапазона [X, Y], а некоторые снаружи, вы возвращаетесь в него.

Теперь у вас есть множество S всех максимальных поддеревьев с A-координатами между X и Y; существует не более O (sqrt (m)) из этих поддеревьев, что я покажу ниже.

Некоторые из этих поддеревьев будут содержать записи O (m) (разумеется, они будут содержать все записи O (m), добавленные вместе), поэтому мы не можем ничего сделать со всеми записями всех поддеревьев. Теперь мы можем создать кучу поддеревьев в S, так что B-минимум каждого поддерева меньше, чем B-минимумы его дочерних элементов в куче. Теперь извлекаем B-минимальные элементы из верхнего узла кучи, пока у вас не будет N из них; всякий раз, когда вы извлекаете элемент из поддерева с k элементами, вам необходимо разложить это поддерево на O (log (k)) поддеревьев, не содержащих недавно извлеченный элемент.

Теперь давайте рассмотрим сложность. Поиск O (sqrt (m)) поддеревьев займет не более O (sqrt (m)) шагов (упражнение для читателя, используя аргументы в доказательстве ниже). Мы, вероятно, должны вставить их в кучу, когда мы их найдем; это займет O (sqrt (m) * log (sqrt (m))) = O (sqrt (m) * log (m)) шагов. Извлечение одного элемента из поддерева k-элемента в куче занимает O (sqrt (k)) время, чтобы найти элемент, а затем вставляет O (log (sqrt (k))) = O (log (k)) назад. в кучу размером O (sqrt (m)) требуется O (log (k) * log (sqrt (m))) = O (log (k) * log (m)) шагов. Вероятно, мы можем быть умнее, используя потенциалы, но мы можем, по крайней мере, связать k с m, так что получается N * (O (sqrt (k) + log (k) * log (m))) = O (N * (sqrt ( m) + log (m) ^ 2) = O (N * sqrt (m)) шагов для извлечения и O (sqrt (m) * (N + log (m))) всего шагов ... что составляет сублинейный в м.

---

Вот доказательство границы O (sqrt (m)) поддеревьев. Существует несколько стратегий построения квадродерева, но для простоты анализа, скажем, мы создаем двоичное дерево; в корневом узле мы разделяем набор данных в соответствии с A-координатой вокруг точки с медианной A-координатой, затем на один уровень вниз мы разделяем набор данных в соответствии с B-координатой вокруг точки с медианной B-координатой (то есть медиана для половины точек, содержащихся в этой половине дерева), и продолжайте чередовать направление на уровень.

Высота дерева - бревно (м). Теперь давайте рассмотрим, сколько поддеревьев нам нужно рекурсировать. Нам нужно выполнить рекурсию, только если поддерево содержит A-координату X или A-координату Y, или оба. На (2 * k) -ом уровне вниз, есть 2 ^ (2 * k) поддеревья в общей сложности. К тому времени каждое поддерево уже имеет свой A-диапазон, подразделяемый уже k раз, и каждый раз, когда мы делаем это, только половина деревьев содержит A-координату X. Таким образом, не более 2 ^ k поддеревьев содержат A-координату X. Аналогично, в самое большее 2 ^ k будет содержать A-координату Y. Это означает, что в общей сложности мы вернемся в самое большее 2 * сумма (2 ^ k, k = 0 .. log (m) / 2) = 2 * (2 ^ ( log (m) / 2 - 1) + 1) = O (sqrt (m)) поддеревьев.

Поскольку мы исследуем не более 2 ^ k поддеревьев на (2 * k) -ом уровне вниз, мы также можем добавить не более 2 ^ k поддеревьев на этом уровне в S. Это дает окончательный результат.