Эффективный запрос дерева B+ с многомерными данными

Question

У меня есть коллекция кортежей (x,y) 64-битных целых чисел, которые составляют мой набор данных. У меня есть, скажем, триллионы этих кортежей; невозможно сохранить набор данных в памяти на любой машине на земле. Однако вполне разумно хранить их на диске.

У меня есть хранилище на диске (дерево B+), которое позволяет быстро и одновременно запрашивать данные в одном измерении. Тем не менее, некоторые из моих запросов основаны на обоих измерениях.

Примеры запросов:

• Найдите кортеж, чей x больше или равно некоторому заданному значению
• Найдите кортеж, чей x как можно меньше, но это y больше или равно некоторому заданному значению
• Найдите кортеж, чей x как можно меньше, но это y меньше или равно некоторому заданному значению
• Выполните операции обслуживания (вставьте несколько кортежей, удалите некоторые кортежи)

Лучшая ставка, которую я нашел, - это кривые Z-порядка, но я не могу понять, как выполнять запросы, учитывая мой двумерный набор данных.

Неприемлемые решения включают последовательное сканирование данных, это может быть слишком медленным.

Answer 1

Я думаю, наиболее подходящими структурами данных для ваших требований являются R-дерево и его варианты (R*-дерево, R+-дерево, R-дерево Гильберта). R-дерево похоже на B+-дерево, но также допускает многомерные запросы.

Другая важная структура данных - это дерево приоритетного поиска. Это хорошо для запросов, подобных вашим примерам 1 .. 3, но не очень эффективно, если вам нужны частые обновления или хранение на диске. Подробнее см. Этот документ или эту книгу: "Справочник по структурам данных и приложениям" (глава 18.5).

Answer 2

Вы говорите, что не знаете, как запросить кривые z-порядка? Страница Wikipedia описывает, как вы выполняете поиск по диапазону.

Z-кривая делит ваше пространство на вложенные прямоугольники, где каждый дополнительный бит в ключе делит пространство пополам. Чтобы найти точку:

Start with the largest rectangle that might contain your point.

    Recursively:

        Create a result set of rectangles    

    For each rectangle in your set        
        If the rectangle is a single point, you are done, it is what you are looking for.
        Otherwise, divide the rectangle in two (specify one additional bit of the z-curve)
            If both halves contain a point
                If one half is better 
                    Add that rectangle to your result set of rectangles
                Otherwise
                    Add both rectangles to your result set of rectangles
            Otherwise, only one half contains a point
                    Add that rectangle to your result set of rectangles

    Search your result set of rectangles

В худшем случае, производительность плохая, конечно. Вы можете настроить его, изменив способ построения индекса z-порядка.

Answer 3

В настоящее время я работаю над созданием структуры данных, которая по сути представляет собой "сложенное" дерево B+ (или дерево d+, где d - число измерений) для многомерных данных. Я считаю, что он идеально подходит для ваших данных и разрабатывается специально для вашего случая использования.

Основная идея заключается в следующем:

Каждое измерение является деревом B+ и связано с деревом B+ следующего измерения. Поиск по первому измерению обычно, как только лист достигнут, он содержит указатель на корень следующего дерева B+, которое принадлежит следующему измерению. Все во втором дереве B+ принадлежит одному x значение.

Первоначальный план состоял в том, чтобы хранить только уникальные значения для каждого измерения вместе с его количеством. Это использует очень простой алгоритм сжатия (если вы можете даже назвать его так), в то же время позволяя представлять весь набор данных. Эта "связанная" схема измерений может позволить добавить дополнительные измерения позднее, поскольку они просто добавляются в стек деревьев B+.

Общее время вставки / поиска / удаления для двух измерений будет примерно таким:

log b(card(x)) + log b(card(y))

где b - основание каждого дерева B+, а card(x) - мощность элемента x.

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

Answer 4

http://fallabs.com/tokyocabinet/

Tokyo Cabinet - это библиотека процедур для управления базой данных. База данных представляет собой простой файл данных, содержащий записи, каждая из которых представляет собой пару ключа и значения. Каждый ключ и значение являются последовательными байтами с переменной длиной. В качестве ключа и значения могут использоваться как двоичные данные, так и символьная строка. Нет ни понятия таблиц данных, ни типов данных. Записи организованы в хеш-таблицу, дерево B+ или массив фиксированной длины.

Tokyo Cabinet написан на языке C и предоставляется как API C, Perl, Ruby, Java и Lua. Tokyo Cabinet доступен на платформах, API которых соответствует C99 и POSIX. Токийский Кабинет - это бесплатное программное обеспечение, лицензируемое по лицензии GNU Lesser General Public License.

может ли вам легко встраивать?