Блог

Представьте, что у вас есть большой набор #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 соответствует X-Y. В худших случаях (немногие объекты соответствуют диапазону X-Y или совпадения находятся в конце записей / индекса) это становится O(m) , что для больших наборов данных размера m недостаточно.

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

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

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

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

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

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

Я прав?

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

http://dhruvbird.com/autocomplete.pdf

(Я автор).

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

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

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

предполагая 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 элементов.

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

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

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

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

На самом деле это не полностью продуманное решение, просто идея. Как насчет построения квадрата по осям 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))) шагов всего … что является сублинейным в m.

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

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

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

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