Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Альтернативы
Недавние
Show all languages
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

В информатике Bx дерево — это эффективная для запросов и обновления структура индексирования для движущихся объектов, основанная на B+‍‍-деревьях.

Структура индекса

Основой структуры Bx-дерева является B+‍‍-дерево, в котором внутренние узлы обрабатываются как каталоги, содержащие указатели на правый соседний узел (с тем же родителем). В ранних версиях Bx-дерева[1] листья содержали положение индексируемых движущихся объектов и соответствующее время индексирования. В оптимизированной версии[2] каждый лист содержит id, скорость, одномерное (скалярное) значение функции положения и последнее время обновления объекта. Различие увеличивается отсутствием хранения положения движущихся объектов, поскольку оно может быть получено из значения функции.

Использование B+‍‍-деревьев для движущихся объектов

Пример Bx-дерева с числом индексированных разбиений, равным 2 с одним максимальным интервалом обновления tmu. В этом примере существует максимум три разбиения, существующие в одно и то же время. После линеаризации положение объекта, вставленное в момент 0, индексируется в раздел 0 с меткой времени 0.5 tmu, положение объекта, обновлённое в момент времени от 0 до 0.5 tmu, индексируется в раздел 1 с меткой времени 1.0 tmu, и так далее. По истечении интервала времени первый период завершается (закрашенная область) и новый период добавляется (пунктирная линия).
Пример Bx-дерева с числом индексированных разбиений, равным 2 с одним максимальным интервалом обновления tmu. В этом примере существует максимум три разбиения, существующие в одно и то же время. После линеаризации положение объекта, вставленное в момент 0, индексируется в раздел 0 с меткой времени 0.5 tmu, положение объекта, обновлённое в момент времени от 0 до 0.5 tmu, индексируется в раздел 1 с меткой времени 1.0 tmu, и так далее. По истечении интервала времени первый период завершается (закрашенная область) и новый период добавляется (пунктирная линия).

Как и при многих других индексациях движущихся объектов, двумерный движущийся объект моделируется линейной функцией O = ((x, y), (vx, vy), t), где (x, y) и (vx, vy) являются положением и скоростью объекта в момент времени t, то есть в момент последнего обновления. B+‍‍-дерево является структурой для индексации одномерных данных. Чтобы приспособить B+‍‍-дерево для индексации движущихся объектов, Bx-дерево использует технику линеаризации, которая помогает преобразовать положение объекта в момент t в одномерное значение. В частности, объекты сначала разбиваются по времени обновления. Для объектов внутри разбиения по времени Bx-дерево запоминает положение объекта в данный момент времени, полученное линейной интерполяцией. Делая так, Bx-дерево сохраняет согласованное изображение всех объектов внутри элемента разбиения без изменения времени обновления объектов.

Далее пространство разбивается решёткой и положение объектов линеаризуется для элемента разбиения по времени согласно заполняющей пространство кривой, например, кривых Пеано или кривых Гильберта.

Затем, комбинируя с номером элемента разбиения (информация о времени) и линейным порядком (информация о положении), объект индексируется в Bx-дереве с одномерным значением ключа (Bxvalue):

Здесь index-partition — это индекс элемента разбиения, определённого временем обновления, а xrep — значение положения объекта на заполняющей пространство кривой в момент индексирования, означает двоичное значение x, «+» означает конкатенацию строк.

Если задан объект O ((7, 2), (-0.1,0.05), 10), tmu = 120, значение Bx для O можно вычислить следующим образом.

  1. O индексируется в элементе 0 разбиения по времени, как описано выше. Таким образом, indexpartition = (00)2.
  2. Положение объекта O в момент установки времени для раздела 0 равно (1,5).
  3. Используем Z-кривую порядка 3, Z-значение объекта O, xrep, равно (010011)2.
  4. Соединяем строки indexpartition и xrep, получаем значение Bx (00010011)2=19.

Вставка, обновление и удаление

Если дан новый объект, вычисляется его ключ индексирования и объект вставляется в Bx-дерево как в B+‍‍-дерево. Обновление состоит из удаления с последующей вставкой. Используются дополнительные структуры для хранения последнего ключа каждого индекса, чтобы иметь возможность удалить объект при поиске ключа. Ключ индексирования вычисляется до включения в дерево. Таким образом, Bx-дерево напрямую наследует хорошие свойства B+‍‍-дерева и позволяет достичь хорошей производительности при обновлении.

Запросы

Запрос по диапазону

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

Bx-дерево использует технику расширения окна запроса, чтобы ответить на этот запрос. Расширение имеет два случая — расположение либо должно вычисляться в некоторый предыдущий момент времени, либо в более поздний момент. Основная идея заключается в том, чтобы расширить окно запроса таким образом, что оно будет включать все объекты, не входящие в окно запроса в момент, указанный в ключе объекта, но попадают в него для момента времени запроса.

После расширения нужно просмотреть разделы Bx-дерева, чтобы найти объекты, попадающие в расширенное окно. В каждом разделе применение заполняющей пространство кривой означает, что диапазон запроса в естественном двумерном пространстве становится множеством запросов по диапазону в одномерном пространстве [1].

Во избежание чересчур больших запросов по диапазону после расширения окна запроса в асимметричных данных существует алгоритм оптимизации[3], который улучшает эффективность запроса путём исключения излишних расширений.

Запрос K ближайших соседей

Запрос K ближайших соседей выполняется итеративным выполнением запросов по диапазону с увеличением области поиска, пока не получим k ответов. Другая возможность — использовать аналогичные идеи вместе с техникой iDistance[en].

Другие запросы

Алгоритмы запроса по диапазону и запроса K ближайших соседей можно легко расширить для поддержки интервальных запросов, непрерывных запросов, и т. д.[2].

Адаптация реляционных баз данных для размещения движущихся объектов

Поскольку Bx-дерево является индексом, построенным на основе B+‍‍-дерева, все операции в Bx-дереве, включая вставку, удаление и поиск, являются теми же, что и в B+‍‍-дереве. Нет необходимости изменять реализацию этих операций. Единственное отличие в реализации заключается в имплементации процедуры получения ключа индексирования в виде хранимой процедуры существующей базе данных. Таким образом, Bx-дерево можно легко интегрировать в существующую базу данных, не затрагивая ядра.

SpADE[4] — это система управления движущимися объектами, построенная поверх популярной базы данных MySQL, использующая Bx-дерево для индексирования объектов. В реализации данные движущихся объектов преобразуются и запоминаются прямо в MySQL, а запросы трансформируются в стандартные SQL-запросы, которые эффективно обрабатываются исполняющей системой реляционной базы данных. Что наиболее важно, всё это делается аккуратно и независимо без вмешательства в ядро MySQL.

Настройка производительности

Потенциальные проблемы с расфазировкой данных

Bx-дерево использует решётку для распределения пространства, чтобы преобразовать двумерное положение в одномерный ключ. Это может привести к деградации производительности как в запросах, так и в операциях обновления, если работают с асимметричными данными. Если ячейка решётки имеет большой размер, в ячейке содержатся много объектов. Поскольку объекты в ячейке неразличимы по индексу, будет некоторое переполнение узлов в низлежащем B+‍‍-дереве. Существование страниц переполнения не только разрушает балансировку дерева, но и увеличивает стоимость обновления. Как и для обычных запросов, для запроса по диапазону, большие ячейки приводят к большему числу ложных выборок и увеличивает время выполнения. С другой стороны, если пространство разбить на более мелкую решётку, то есть на более мелкие ячейки, каждая ячейка содержит меньше объектов. Вряд ли в этом случае будет достигнуто переполнение страниц, а также будет меньше ложных выборок, однако нужно будет просматривать большее число ячеек. Увеличение числа просматриваемых ячеек также увеличивает трудоёмкость запроса.

Настройка индекса

ST2B-дерево[5] вводит самонастраивающуюся схему для настройки производительности Bx-дерева при работе с несимметричными данными в пространстве и во времени. Для работы с асимметричными данными в пространстве ST2B-дерево разбивает всё пространство на области с различной плотностью объектов при помощи множества контрольных точек. Каждая область использует индивидуальную решётку, величина ячеек которой определяется плотностью объектов внутри области.

Bx-дерево имеет несколько разбиений для различных интервалов времени. ST2B-дерево использует увеличение или сокращение интервала для настройки индексации, чтобы согласовываться с разбиением пространства и приспособиться к изменению времени. В частности, когда разбиение опустошается и начинает расти, выбирается новое множество контрольных точек и новая решётка для каждой точки согласно последней плотности данных. Настройка основывается на статистике, собранной за данный период времени, так что разбиение пространства лучше соответствует самому последнему распределению данных. В этом смысле ожидается, что ST2B-дерево минимизирует эффект, вызванный несимметричностью данных в пространстве и изменениям данных по времени.

См. также

Примечания

  1. 1 2 Jensen, Lin, Ooi, 2004, с. 768-779.
  2. 1 2 Dan Lin, 2006.
  3. Jensen, Tiesyte, Tradisauskas, 2006.
  4. SpADE Архивировано 2 января 2009 года.: A SPatio-temporal Autonomic Database Engine for location-aware services.
  5. Chen, Ooi, Tan, Nacismento, 2008, с. 29-42.

Литература

  • Christian S. Jensen, Dan Lin, Beng Chin Ooi. Proceedings of 30th International Conference on Very Large Data Bases (VLDB). — 2004.
  • C.S. Jensen, D. Tiesyte, N. Tradisauskas. Proceedings of the Seventh International Conference on Mobile Data Management. — Nara, Japan, 2006.
  • Dan Lin. Indexing and Querying Moving Objects Databases. — National University of Singapore, 2006. — (PhD thesis).
  • Su Chen, Beng Chin Ooi, Kan-Lee Tan, Mario A. Nacismento. Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD). — 2008.
Эта страница в последний раз была отредактирована 12 марта 2021 в 18:39.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).