Методы индексирования на основе функции расстояния. Универсальное деление гиперплоскостями. Дерево биссектрис и МВ-дерево

@CrazyBlood32 · Регистрация: 17.08.2012

Студворк — интернет-сервис помощи студентам

Доброго времени суток.
В поисках информации для курсовика жизнь занесла сюда

Поделитесь информацией, литературой

Тема: "Методы индексирования на основе функции расстояния. Универсальное деление гиперплоскостями. Дерево биссектрис и МВ-дерево."

@asidorchenko · 12.01.2013, 12:24

Возможно этот документ может быть полезным:
http://arxiv.org/pdf/1108.0028v1.pdf
Там есть немного про дерево биссектрис.

Добавлено через 8 часов 8 минут
Вот то, что надо: http://www.google.ru/url?sa=t&... 0187,d.bGE

BM+-Tree: A Hyperplane-Based Index Method

То же самое на другом сайте http://itee.uq.edu.au/~zxf/_pa... angmin.pdf

M+-tree
crpit.com/confpapers/CRPITV17Zhou.pdf
http://en.wikipedia.org/wiki/M-tree

B-tree
en.wikipedia.org/wiki/B-tree
en.wikipedia.org/wiki/B%2B_tree
habrahabr.ru/post/114154/

Добавлено через 59 минут
Вам нужна помощь с переводом?

Добавлено через 15 часов 19 минут
Возможно будет полезной статья http://www.gamedev.ru/code/articles/BSP про деревья двоичного разбиения пространства

BM+-дерево: метод индексирования, основанный на гиперплоскостях в метрических пространствах с большой размерностью.
Xiangmin Zhou, Guoren Wang, Xiaofang Zhou, Ge Yu

В данной работе рассматривается новый метод индексирования, BM+ дерево для поддержки эффективной обработки поисковых запросов на совпадение в пространствах с большой размерностью. Основная идея предлагаемого метода индексирования это улучшение эффективности разбиения данных в пространстве с большой размерностью с использованием вращающейся двоичной гиперплоскости с дальнейшим разбиением подпространств с использованием преимуществ концепции двойного узла, используемой в M-дереве. В сравнении с концепцией ключевой размерности в M-дереве, двоичная гиперплоскость более эффективная в фильтрации данных. Высокая утилизация пространства достигается динамическим осуществлением перемещения данных между двумя двойными узлами. В дополнение, используется шаг пост-обработки после индексирования для того, чтобы удостовериться в эффективной фильтрации. Экспериментальные результаты, полученные на двух типах реальных наборов данных иллюстрируют значитально улучшенную эффективность фильтрации.

Ключевые слова: поиск сопадений (similarity search), многомерный индекс, двоичная гиперплоскость, запрос в диапазоне (range query) , K-NN запрос

1. Введение

Нужда в быстрой обработке поисковых запросов на совпадение содержимого к большим базам данных сильно увеличилась с быстрым ростом мультимедиа информации разных типов и будет увеличиваться в ближайшем будущем. Так как получение многомерных данных всегда требует очень больших и иногда запретно больших затрат на крупных наборах данных, поиск эффективных структур индексирования для поддержки запросов находится на передовой разработок в области баз данных в последнюю декаду.[13] Самые эффективные многомерные структуры индексирования, полученные при управления географическими данными с небольшой размерностью (такие как R-дерево и его варианты[1][2][3][4]), неэффективны при управлении многомерными данными.

Две категории подхода к поиску совпадения: индексирование на основе метрики, индексирование на основе позиции. В прошлом R-дерево и его варианты имели дело с относительными позициями в векторном пространстве. Второй тип индексирования включает VP-дерево, MVP-дерево и M-дерево и их оптимизированные индексы. Эти индексы управляют данными, основываясь на относительных расстояниях между объектами. Среди индексов, основанных на метрике, VP-дерево это первая в иерархии структура индексирования, которая поддерживает поиск, утилизируя относительное расстояния между объектами и неравенство треугольника. Это большая подмога для уменьшения затрат на поиск. Однако, высокая производительность VP-дерева сильно страдает от высокого количества вычислений расстояний из-за небольшого разветвления (это очень высокое дерево индексирования). MVP-дерево предназначено, чтобы решить эти проблемы, используя множественные точки вместо одной. Эта идея значительно уменьшает высоту. И VP-дерево и MVP-дерево конструируются сверху-вниз. Это значит они не поддерживают вставку и удаления данных после создания индекса.

M-дерево это значительный шаг вперед и представляется на основе индексов основанных на метрике. Это страничное и сбалансированное дерево, которое принимает стратегию конструирования снизу-вверх с механизмом разделения и продвижения узлов. Оно может быть использовано в качестве вторичной структуры индексирования данных и может легко поддерживать обновления данных без реконструирования всего индексирования, когда вставляется или удаляется объект мультимедия. M-дерево распознает высокие затраты на вычисление расстояний, поэтому большая часть расстояний предварительно вычисляется и хранится в дереве индексирования, чтобы избежать вычисления расстояний во время запроса. Значительной проблемой является высокая степень наложения подпространств в разных узлах M-дерева. Однако в отличие от других методов индексирования, М+-дерево имеет минимизацию наложения подпространств и как цель минимизацию высоты дерева. Оно улучшает M-дерево следующим:
(1) концепция ключевой размерности, чтобы убрать наложение между двойными узлами и уменьшить наложение подпространств
(2) концепция двойного узла представлена, чтобы снизить высоту дерева
(3) идея сдвига ключевой размерности для достижения оптимального разбиения пространства
(4) совершенно новая идея ассоциирования вхождения индекса с двойными под-деревьями для более эффективной фильтрации во время поиска

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

Оставшаяся часть этой работы организована следующим образом. В секции 2 рассматриваются определения для поиска совпадени. В секции 3 представляется новая стратегия разбиения. Мы описываем BM+-дерево в секции 4, включая техники создания ключа и лагоритмы. В секции 5 представлены уравнения производительности. Секция 6 - заключительная.

2. Запросы

2. Запросы
В этом разделе следуя конвенциям используемым в [8] даются базовые определения, относящиеся к BM+-дереву, включая r-поиск соседа, k-поиск ближайшего соседа
r-поиск соседа, k-поиск ближайшего соседа (k-NN запрос) это два основных типа запросов на совпадение. Первая цель - получить все объекты в пределах определенного расстояния от объекта запроса, вторая цель - найти k объектов, которые имеют минимальные расстояния к заданному объекту поиска.

Определение 1. r-поиск соседа. Пусть дан объект запроса $https://www.cyberforum.ru/cgi-bin/latex.cgi?q\in O$ и неотрицательный радиус запроса r, r-поиск соседа для получения всех объектов $https://www.cyberforum.ru/cgi-bin/latex.cgi?o\in O$ таких что $https://www.cyberforum.ru/cgi-bin/latex.cgi?d(q, o) \leq r$
Определение 2. k-поиск ближайшего соседа. Пусть дан объект запроса $https://www.cyberforum.ru/cgi-bin/latex.cgi?q\in O$ и целое число k>=1, k-NN Запрос для получения k объектов из O с минимальным расстоянием от q.

Назначение индексирования пространства данных это обеспечение эффективной поддержки получения объектов, подобных шаблонному объекту запроса (для r-поиска соседа и k-NN поиска). Для заданного запроса, главная цель - минимизировать количество вычислений расстояний, операций ввод-вывода и доступа к приоритетной очереди, которые очень затратны для большинства приложений.

... продолжение следует

Список литературы:
[1] N.Berkmann, H.-P.Krigel, R.Schneider, B.Seeger (1990) R-дерево: эффективный метод доступа к точкам и прямоугольникам
[2] N.Katayama, S.Satoh (1997) SR-дерево: структура индексирования для запросов ближайшей окрестности большой размерности
[3] D.A.White, R,Jain(1996) Индексирования в SS-дереве
[4] K.-I. Lin, H.V.Jagadish, C.Faloutsos(1994) TV-дерево: структура индексирования для данных с большой размерностью
[8] P.Giaccia, M.Patella, P.Zezula (1997) M-дерево: эффективный метод доступа для поиска совпадений в метрических пространствах http://www.vldb.org/conf/1997/P426.PDF

Добавлено через 6 минут
[13] C.Bohm, S.Berchtold, D.A.Keim (2002) Пространства с большой размерностью - структуры индексирования для улучшения производительности мультимедийных баз данных http://trac.astrometry.net/exp... hm2001.pdf

Добавлено через 19 минут
БДдля которых применяется BM+ дерево это например БД данных фото или видео-съемки со спутников.

***

k-NN запрос

1. http://en.wikipedia.org/wiki/K... _algorithm
2. http://www.cs.umd.edu/~mount/ANN/ (есть исходный код)
3. http://www.mysmu.edu/faculty/b... 9_VRNN.pdf
4. http://seer.lcc.ufmg.br/index.... oad/143/92
5. http://itee.uq.edu.au/~zxf/_papers/SKNN.pdf
6. http://www.comp.nus.edu.sg/~ooibc/bohm.pdf
7. http://resjournals.com/ITJ/Pdf... t%20al.pdf
8. http://web.mst.edu/~lindan/pub... tica06.pdf
9. http://www.vldb.org/pvldb/1/1453966.pdf
10. http://vldb.org/pvldb/vol5/p11... db2012.pdf
11. http://www4.comp.polyu.edu.hk/... icde11.pdf
12. http://www.cse.unsw.edu.au/~lxue/paper/rankKNN.pdf
13. http://infolab.usc.edu/DocsDemos/vldb08_knn.pdf
14. http://citeseerx.ist.psu.edu/v... 1&type=pdf
15. http://www.cs.cmu.edu/~aarnold/cald/fp025-geng.pdf
16. http://www.lsdsir.org/wp-conte... ir10-2.pdf

r-neighbor query ( в R-деревьях)
1. http://www.cse.msu.edu/~praman... poulos.pdf
2. http://delab.csd.auth.gr/papers/ICDT97pm.pdf
3. http://postgis.refractions.net... ighbor.pdf
4. http://people.csail.mit.edu/indyk/p117-andoni.pdf
5. http://www.mysmu.edu/faculty/b... 9_CVNN.pdf

Добавлено через 6 минут
17. ftp://www.learning.cs.toronto.... 93/main.ps
18. http://dsl.serc.iisc.ernet.in/... motley.pdf
19. http://postgis.refractions.net... ighbor.pdf
20. http://www.db.itc.nagoya-u.ac.... m-long.pdf
21. http://www.vldb.org/pvldb/1/1453970.pdf
22. http://www-users.cs.umn.edu/~m... /mdm10.pdf

Добавлено через 1 час 55 минут
3. Разбиение данных с использованием двоичной гиперплоскости

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

3.1 Конструирование двоичных гиперплоскостей
Из-за различного распределения данных, разные размерности имеют разный вес при вычислении расстояний. Основываясь на этом факте, M+-дерево разбивает подпространства на два двойных подпространства в соответствии с выбранной ключевой размерностью, то есть той размерностью, которая наибольшим образом влияет на вычислени ерасстояния. В отличие от M+-дерева BM+дерево использует двоичную гиперплоскость для разбиения подпространства на два двойных подпространства. двоичная гиперплоскость расширяет концепцию ключевой размерности M+дерева чтобы использовались две ключевых размерности. Новая стратегия разбиения данных основывается на следующем наблюдении.

Наблюдение 1. Для большинства приложений помимо ключевой размерности есть другая размерность, которая может содержать большой объем информации. Отмена использвоания второй размерности вызовет большую потерю информации. В процессе уменьшения количества размерностей, мы получаем только первые несколько размерностей вместо первой размерности. Для осуществления дальнейшего разбиения данных, полезно использовать две размерности, которые имеют максимальное количество вариантов и сконструировать двоичную гиперплоскость, используя две размерности.

На рисунке 1 показан набор данных (закращенная область) для примера. Очевидно, распространение объектов вдоль x1 больше чем вдоль x ( которое больше чем вдоль y). Ключевая размерность разбиения данных будет делить данные по размерности x. Ясно, что намного больше информации может быть получено, если разбиение будет делаться двоичной гиперплоскостью вертикальной к x1.

Выбор гиперплоскости должен соовтетствовать следующим правилам для того, чтобы достигнуть оптимальное разбиение данных, то еесть пытаясь сохранять объекты, имеющие минмиальные расстояния в одном и том же подпространстве и минимизируя наложение двух подпространств. В процессе конструирования двоичной гиперплоскости, выбор ключевых размерностей и определение их коэффициентов - две основных задачи. Мы рассматривали две стратегии конструирования двоичной гиперплоскости: стратегия m-RAD-2 и стратегия, основывающаяся на максимальном расстоянии. Первая основывается на факте, что M-дерево имеет оптимальный индекс произовдительности, когда использует стратегию разбиения m-RAD-2. При этой стратегии гарантируется максимум радиусов двух подпространств, разбитых минимально(?). Вторая стратегия основана на наблюдении, что расстояния между объектами вдоль размерности с максимальным расстоянием может содержать максимальное количество информации.

BM+-дерево использует следующие шаги для определения гиперплоскости
1. Выбрать две точки-ориентира следующим образом. Использовать центральные точки двух подпространств в соответствии со стратегией разбиения m-RAD-2 [8] и когда эти точки имеют одно и то же feature значение, можно вычислить расстояния между объектами подмножества и выбрать две точки из подмножества такие что расстояние между выбранными точками максимально
2. Вычислить расстояние по каждой размерности между этими 2 точками
3. Выбрать две размерности, которые имеют максимальное значение по модулю в качестве ключевых размерностей и рассматривая различие между двумя центральными точками двух ключевых размерностей как соответствующие им коэффициенты.

3.2 Дальнейшее разбиение данных с использованием двоичной гиперплоскости

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

Определение. Двойные узлы. В M+ и BM+-дереве внутренне вхождение имеет два указателя на два под-дерева. Эти два под-дерева называются двойными поддеревьями и корни двойных под-деревьев называются двойными-узлами (twin nodes)

На рисунке 2 (a) и (b) подпространства 1 и 2 соответствуют двойным узлам дерева. Рисунок 2 (a), (b), (c) показывает разбиение данных с использованием BM+-дерева, M+-дерева и M-дерева соответственно. M-дерево принимает стратегию разбиения данных на основе расстояния, которая разбивает пространство данных на два подпространства в соответствии с расстояниями между объектами. Среди предлагаемых методов разбиения M-дерева, разбиение с помощью m-RAD-2 является лучшим. M+-дерево улучшает методы разбиения данных M-дерева, используя двухшаговую стратегию разбиения, сначала разбивая с помощью m-RAD-2 и затем далее разбивает два подпространства на две пары двойных узлов соответствующих выбранным ключевым размерностям. Двойные узлы выражены с помощью двух граничных значений ключевой размерности, которые являются значением максимальной ключевой размерности левого двойного подпространства и значение минимальной ключевой размерности правого двойного подпространства

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

Стратегия разбиения данных в BM+-дереве может быть описана следующим образом:
(1) двойные пространства рассматриваются вместе как целое пространство и затем оно разбивается способом m-RAD-2 как и в M-дерее. Как результат проихводятся два новых подпространства
(2) каждое подпространство дальше разбивается на двойные подпространства в соответствии с выбранной двоичной гиперплоскостью

Рисунок 2 показывает, что для того,ч тобы добиться того же уровня группировки данных, M-дерево нуждается в трех уровнях разбиений, в то время как BM+-дерево и M+-дереву нуждаются только в двух уровнях. Явно, что стратегия разбиения данных с помощью BM+-дерева имеет лучший эффект кластеризации. расстояние между объектами вдоль размерности разбиения данных больше чем та же самая в M+-дереве. Этот рисунок дает интуитивное представление, что разбиение данных с помощью двоичной гиперплосости может сохранять больше информации о расстоянии.

3.3 Фильтрация данных с использованием двоичной гиперплоскости

Фильтрация с помощью двоичной гиперплоскости основыавется на расстоянии от объекта до гиперплоскости и на свойстве неравенства треугольника. В сравнении со стоимостью вычисления расстояния между двумя точками в многомерном пространстве, стоимость вычисления расстояния к двоичной гиперплоскости пустяковая. Неактивные поддеревья могут быть отфильтрованы гиперплоскостями, таким образом избегаются некоторые вычисления расстояний. Процесс фильтрации двоичной гиперплоскостью некомплексный. Мы сделаем наметку этого процесса ниже.

Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{l}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{N}_{r}$ - двойные узлы, $https://www.cyberforum.ru/cgi-bin/latex.cgi?{k}_{1}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{k}_{2}$ - ключевые размерности подпространства, $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{1}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{C}_{2}$ - коэффициенты гиперплоскости в размерностях $https://www.cyberforum.ru/cgi-bin/latex.cgi?{k}_{1}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{k}_{2}$ соответственно.

$https://www.cyberforum.ru/cgi-bin/latex.cgi?{L}_{max}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{min}$ - максимальные значения двоичной гиперплоскости для левого узла и минимальное значение двоичной гиперплоскости для правого узла соответственно. Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?C = \sqrt{{{C}_{1}}^{2} + {{C}_{2}}^{2}}$ .

Тогда гиперплоскость данного подпространства имеет следующее уравнение:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{X}_{k1}*{C}_{1} + {X}_{k2}*{C}_{2} = HP$ (1)
Для левой части HP идентично $https://www.cyberforum.ru/cgi-bin/latex.cgi?{L}_{max}$ . Для правой части HP это $https://www.cyberforum.ru/cgi-bin/latex.cgi?{R}_{min}$

Предположим, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?O({x}_{1}..{x}_{n})$ это n-мерный объект запроса, $https://www.cyberforum.ru/cgi-bin/latex.cgi?r$ - радиус поиска. Тогда расстояние от $https://www.cyberforum.ru/cgi-bin/latex.cgi?O$ к левым и правым ограничивающим гиперплоскостям может быть вычислено соответственно как 2(a) и 2(b)
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{d}_{L}=\frac{\begin{vmatrix}HP - {L}_{max}\end{vmatrix}}{C}$ (2a)
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{d}_{R}=\frac{\begin{vmatrix}HP - {R}_{min}\end{vmatrix}}{C}$ (2b)

При фильтрации, если $https://www.cyberforum.ru/cgi-bin/latex.cgi?HP \geq {L}_{max}$ то объект запроса вне пределов зоны слева, таким образом возможно отсечь левую область. Подобно этому, если $https://www.cyberforum.ru/cgi-bin/latex.cgi?HP \leq {R}_{min}$ то может быть отсечена правая часть. В дальнейшем мы рассматриваем следующий случай.

$https://www.cyberforum.ru/cgi-bin/latex.cgi?{{d}_{L}}^{'} = \frac{(HP - {L}_{max})}{C}$ (3a)
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{{d}_{R}}^{'} = \frac{({R}_{min} - HP)}{C}$ (3b)

Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?{{d}_{L}}^{'}\geq r$ то левый узел не содержит никаких результатов поискового запроса и может быть отсечено. Подобно этому, если $https://www.cyberforum.ru/cgi-bin/latex.cgi?{{d}_{R}}^{'}\geq r$ то правая часть может быть отсечена. Очевидно, что стоимость вычисления $https://www.cyberforum.ru/cgi-bin/latex.cgi?{{d}_{L}}^{'}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{{d}_{R}}^{'}$ намного меньше чем вычисление расстояния в пространстве с большой размерностью. Это похоже на обработку k-NN следуя выше указанному процессу фильтрации.

@asidorchenko · 12.01.2013, 12:40

4. BM+-дерево

Есть два типа узловых объектов в BM+-дереве: объекты-пути и объекты-листья. Каждый лист имеет ту же структуру, что и в M-дереве. Объект-путь включает следующие части: feature-значение объекта-пути $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{r}$ , радиус покрытия $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{r}$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?r({O}_{r})$ , расстояние от $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{r}$ к родителю $https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{r}, P({O}_{r}))$ , массив $https://www.cyberforum.ru/cgi-bin/latex.cgi?{D}_{NO}$ содержащий два числа ключевых размерностей. Другой массив $https://www.cyberforum.ru/cgi-bin/latex.cgi?C$ содержит коэффициенты, относящиеся в двум числам ключевых размерностей соовтетственно. Указатель lTwinPtr на левое двойное под-дерево. Указатель rTwinPtr на правое под-дерево. Максимальное значенине двоичной гиперплоскости к левому двойному под-дереву $https://www.cyberforum.ru/cgi-bin/latex.cgi?{M}_{lmax}$ и минимальное значение двоичной гиперплоскости к правому под-дереву $https://www.cyberforum.ru/cgi-bin/latex.cgi?{M}_{rmin}$ .

@asidorchenko · 12.01.2013, 14:59

4.1 Построение BM+-дерева

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

Когда вставляется новый узел, способ выбора соответствующего узла жизненно важен для производительности индекса. Выбор поддерева следует оптимальному принципу:
(1) Выбирается узел, расстояние от объекта запроса до объекта-пути минимально если радиус покрытия не нуждается в увеличении.
(2) Выбирается под-дерево, с которым радиус покрытия увеличивается незначительно если ни одно из под-деревьев не содержит тоже самое, когда вставляется объект
(3) Пытаясь сохранять промежуток между двойными под-деревьями максимальными, когда из них выбирается под-дерево
BM+-дерево растет снизу-вверх и принимает двухшаговую стратегию разбиения. Оно использует ту же самую стратегию продвижения, что и M-дерево и наследует двухшаговую стратегию разбиения:
1. разбиение с использованием стратегии m-RAD-2
2. разбиение с использованием двоичной гиперплоскости
При разбиении узлов BM+-дерево принимает две стратегии выбора гиперплоскости:
1. основанная на m-RAD-2
2. основанная на максимальном расстоянии

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
РАЗБИТЬ(вхождение([LATEX]{O}_{n}[/LATEX]), PEntry)
1 Пусть S - множество,  [LATEX]{N}_{p}[/LATEX] - узел-родитель
2 [LATEX]S\leftarrow[/LATEX]вхождения [LATEX](PEntry\rightarrow lTNode)\bigcup[/LATEX]вхождения [LATEX](PEntry\rightarrow rTNode)\bigcup[/LATEX] вхождения [LATEX]{O}_{n}[/LATEX]
3 выделить пространство под новый узел [LATEX]{N}^{'}[/LATEX]
4 ПродвинутьВхожденияИРазбитьРасстоянием
5 ВыбратьB-ГиперплоскостьИРазбитьГиперплоскостью
6 if   [LATEX]{N}_{p}[/LATEX] не корень
7       then switch
8           case TwinsOf( [LATEX]{N}_{p}[/LATEX] ) - полное : Разбить
9           case [LATEX]{N}_{p}[/LATEX] не полное : ВставитьВРодительскийУзел       
10        case default : ПереместитьДвойныеУзлы
11 else if  [LATEX]{N}_{p}[/LATEX] не полное
12        then РазбитьКореньИспользуяB-Гиперплоскость
13       else ВставитьВРодительскийУзел

Code
1
2
3
4
5
6
7
ВЫБРАТЬ_ДВОИЧНУЮ_ГИПЕРПЛОСКОСТЬ[LATEX]({D}_{1NO},{D}_{2NO}, {C}_{1},{C}_{2})[/LATEX]
1 ПолучитьДваОбъектаИспользуяM-RAD
2 ПолучитьДваМаксимальноеРазличиеВычисленияИСортировки
3 if Различие[0] == Различие[1]
4   then ПолучитьДваОбъектаМаксимальнымРасстоянием
5           ПолучитьДваМаксимальноеРазличиеВычисленияИСортировки
6 УстановитьМаксимальныеРазмерностиИИхКоэффициенты

Добавлено через 1 час 14 минут
Функция расстояния
Пусть
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{x} = ({x}_{1}..{x}_{n})$ - искомый объект запроса
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{y} = ({y}_{1}..{y}_{n})$ - объект данных в n-мерном метрическом пространстве
$https://www.cyberforum.ru/cgi-bin/latex.cgi?r$ - радиус поиска

Тогда евклидово расстояние между $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{x}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{y}$ можнт быть вычислено по формуле
$https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x},{O}_{y}) = \sqrt{{(x1-y1)}^{2} + {(x2-y2)}^{2} + ... + {(xn-yn)}^{2} }$
Так как
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{(xk-yk)}^{2} \leq {(x1-y1)}^{2} + {(x2-y2)}^{2} + ... + {(xn-yn)}^{2}$
то $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{vmatrix}xk-yk\end{vmatrix}\leq d({O}_{x}, {O}_{y})$
Для любой размерности k если $https://www.cyberforum.ru/cgi-bin/latex.cgi?(xk-yk)\geq r$ то $https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x}, {O}_{y})\geq r$
В этом случае объект $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{y}$ может быть отфильтрован без вычисления расстояния между $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{x}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{y}$ .

Если евклидово пространство взвешенное, то расстояние вычисляется по формуле
$https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x},{O}_{y}) = \sqrt{{W}_{1}{(x1-y1)}^{2} + {W}_{2}{(x2-y2)}^{2} + ... + {W}_{n}{(xn-yn)}^{2} }$
В этом случае $https://www.cyberforum.ru/cgi-bin/latex.cgi?{W}_{k}{(xk-yk)}^{2} \leq {W}_{1}{(x1-y1)}^{2} + {W}_{2}{(x2-y2)}^{2} + ... + {W}_{n}{(xn-yn)}^{2}$
Как результат $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{{W}_{k}} \begin{vmatrix}(xk-yk)\end{vmatrix} \leq d({O}_{x}, {O}_{y})$
Если $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{{W}_{k}} \begin{vmatrix}(xk-yk)\end{vmatrix} \geq r$ то $https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x}, {O}_{y})\geq r$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{y}$ может быть отфильтровано без повторногов ычисления расстояния.

В некоторых приложениях размерности сильно зависят друг от друга. Евклидова функция вычисления расстояния будет неэффективной. В таком случае будет необходимым использование обобщенной функции расстояния. Формулой (3) определяется обобщенная функция расстояния:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x}, {O}_{y}) = \sqrt{({O}_{x} - {O}_{y}).A.{({O}_{x} - {O}_{y})}^{T}} = \sqrt{\sum_{i-1}^{N}\sum_{j-1}^{N}{a}_{ij}({x}_{i} - {y}_{i})({x}_{j} - {y}_{j})}$ (3)
Если A-диагональная $https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x}, {O}_{y}) = \sqrt{{a}_{11}{({x}_{1}-{y}_{1})}^{2} + {a}_{22}{({x}_{2}-{y}_{2})}^{2} + ... + {a}_{nn}{({x}_{n}-{y}_{n})}^{2} }$ Это называется взвешенной функцией расстояния в евклидовом пространстве.
Фильтрация по ключевому расстоянию основвывается на следующей теореме
Теорема: Любая квадратичная форма $https://www.cyberforum.ru/cgi-bin/latex.cgi?XA{X}^{T}$ может быть редуцирована ортогональным преобразованием к диагональной форме $https://www.cyberforum.ru/cgi-bin/latex.cgi?{\lambda }_{1}{{z}_{1}}^{2} + {\lambda }_{2}{{z}_{2}}^{2} + ... + {\lambda }_{n}{{z}_{n}}^{2}$ где $https://www.cyberforum.ru/cgi-bin/latex.cgi?{\lambda }_{i}$ - корни характеристического уравнения $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{vmatrix}A - {\lambda }_{1}\end{vmatrix} = ({\lambda }_{1} - \lambda )...({\lambda }_{n} - \lambda )$
В соответствии с теоремой 1, обобщенная функция расстояния может быть преобразована в форму взвешенной функции расстояния в евклидовом пространстве.

Пример. Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?A=\begin{pmatrix}1 & 0.8 & 0\\ 0.8 & 1 & 0\\ 0 & 0 & 1\end{pmatrix}$
тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x}, {O}_{y}) = \sqrt{({O}_{x} - {O}_{y}).A.{({O}_{x} - {O}_{y})}^{T}}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?= \sqrt{({x}_{1}-{y}_{1},{x}_{2}-{y}_{2},{x}_{3}-{y}_{3}).A.{({x}_{1}-{y}_{1},{x}_{2}-{y}_{2},{x}_{3}-{y}_{3})}^{T}}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?= \sqrt{{({x}_{1} + 0.8 {x}_{2} - ({y}_{1}+ 0.8{y}_{2} ) )}^{2} + {(0.6{x}_{2} - 0.6{y}_{2})}^{2} + {({x}_{3} - {y}_{3})}^{2}}$

Валидность может быть продемонстрирована преобразованием пространства. Пусть оригинальное пространство $https://www.cyberforum.ru/cgi-bin/latex.cgi?({d}_{1},{d}_{2},{d}_{3})$ . Сконструируем преобразование
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{D}_{1} = {d}_{1} + 0.8{d}_{2}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{D}_{2} = 0.6{d}_{2}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{D}_{3} = {d}_{3}$

Т.о. фильтрация валидна

Для любой функции расстояния $https://www.cyberforum.ru/cgi-bin/latex.cgi?d$ в пространстве данных, принцип фильтрации по ключевой размерности валидным является тогда и только тогда, когда $https://www.cyberforum.ru/cgi-bin/latex.cgi?\begin{vmatrix}{x}_{k} - {y}_{k}\end{vmatrix} \leq d({O}_{x},{O}_{y})$

http://www.dirf.org/jdim/v3n412.pdf

Использованная литература:
[5] J.K.Uhlmann (1991) Удовлетворение результатов условиям общей близости / запросы на совпадение в метрических деревьях http://trac.astrometry.net/exp... nn1991.pdf
http://130.203.133.150/showcit... cid=117749
[6] P.Zezula, P.Сiaccia, F.Rabitti (1996) M-дерево: динамический индекс для запросов на совпадение в мультимедийных базах данных http://www-db.deis.unibo.it/re... VLDB97.pdf
[7] T.Bozkaya, M.Ozsoyoglu (1997) Индексирование на основе функции расстояния в многомерных метрических пространствах
[9] M.Ishikawa, H.Chen, K.Furuse, J.X.Yu, N.Ohbo (2000) MB+-дерево: динамическое обновляемый метрический индекс для поиска подобий
[10] C.Traina Jr, A.Traina, B.Seeger, C.Faloutsos (2000) Slim-trees Метрические деревья с большой производительностью, минимизирующие наложение узлов
[11] X.Zhou, G.Wang, J.X.Yu, G.YU (2003) M+-дерево: новый динамический метод индексирования метрических пространств
[12] G.Wang, H.LU, G.YU, Y.Bao (2003) Управление большой коллекцией документов используя семантику

MS-tree http://itee.uq.edu.au/~zxf/_papers/EMMA05.pdf
MK-tree http://www.dirf.org/jdim/v3n412.pdf
http://www.google.ru/url?sa=t&... 0187,d.bGE
http://theses.insa-lyon.fr/pub... /these.pdf
http://liris.cnrs.fr/Documents/Liris-4516.pdf

Добавлено через 30 минут
Пространство M определено следующим образом $https://www.cyberforum.ru/cgi-bin/latex.cgi?M = (O,d)$ и удовлетворяет следующим свойствам:
1. $https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x},{O}_{y}) = d({O}_{y}, {O}_{x})$
2. $https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x},{O}_{y}) > 0 ({O}_{x}\neq {O}_{y}), d({O}_{x},{O}_{x}) = 0$
3. $https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{x},{O}_{y}) \leq d({O}_{x},{O}_{z}) + d({O}_{z},{O}_{y})$
где $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{x},{O}_{y}, {O}_{z}$ объекты $https://www.cyberforum.ru/cgi-bin/latex.cgi?O$

Добавлено через 6 минут
M+-дерево Новый динамический индекс для метрических пространств
Xiangmin Zhou, Guoren Wang, Jeffrey Xu Yu, Ge Yu
http://crpit.com/confpapers/CRPITV17Zhou.pdf

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Programma_Boinc 01.01.2026 Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

@CrazyBlood32 0 / 0 / 0 Регистрация: 17.08.2012 Сообщений: 24

	Методы индексирования на основе функции расстояния. Универсальное деление гиперплоскостями. Дерево биссектрис и МВ-дерево 09.01.2013, 20:39. Показов 3443. Ответов 3 Метки нет (Все метки) Доброго времени суток. В поисках информации для курсовика жизнь занесла сюда Поделитесь информацией, литературой Тема: "Методы индексирования на основе функции расстояния. Универсальное деление гиперплоскостями. Дерево биссектрис и МВ-дерево." 0

@asidorchenko 387 / 214 / 102 Регистрация: 09.04.2012 Сообщений: 635
	12.01.2013, 12:40
	4. BM+-дерево Есть два типа узловых объектов в BM+-дереве: объекты-пути и объекты-листья. Каждый лист имеет ту же структуру, что и в M-дереве. Объект-путь включает следующие части: feature-значение объекта-пути $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{r}$ , радиус покрытия $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{r}$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?r({O}_{r})$ , расстояние от $https://www.cyberforum.ru/cgi-bin/latex.cgi?{O}_{r}$ к родителю $https://www.cyberforum.ru/cgi-bin/latex.cgi?d({O}_{r}, P({O}_{r}))$ , массив $https://www.cyberforum.ru/cgi-bin/latex.cgi?{D}_{NO}$ содержащий два числа ключевых размерностей. Другой массив $https://www.cyberforum.ru/cgi-bin/latex.cgi?C$ содержит коэффициенты, относящиеся в двум числам ключевых размерностей соовтетственно. Указатель lTwinPtr на левое двойное под-дерево. Указатель rTwinPtr на правое под-дерево. Максимальное значенине двоичной гиперплоскости к левому двойному под-дереву $https://www.cyberforum.ru/cgi-bin/latex.cgi?{M}_{lmax}$ и минимальное значение двоичной гиперплоскости к правому под-дереву $https://www.cyberforum.ru/cgi-bin/latex.cgi?{M}_{rmin}$ . Миниатюры Изображения 0