СПОСОБ ИНДЕКСАЦИИ И ПРОСТРАНСТВЕННОГО ПОИСКА ДАННЫХ НА ОСНОВЕ ХЭШИРОВАНИЯ Российский патент 2016 года по МПК G06F17/30 

Изобретение относится к вычислительной технике, в частности к алгоритмам и методам индексации и поиска информационных объектов, для которых задана метрика (функция вычисления расстояния). Изобретение может быть использовано при создании программного обеспечения, работающего с информационными объектами и осуществляющего их накопление, хранение, индексацию и поиск. Также изобретение может быть использовано при создании систем управления базами данных (СУБД), геоинфорационных систем (ТИС) и самообучающихся систем, основанных на вычислении степени похожести информационных объектов.

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

Существует строгое математическое определение метрики. Функция двух аргументов R(x,y) является метрикой, если, во-первых, она равна нулю только в том случае, если поданные на вход аргументы идентичны. Во-вторых, функция R(x,y)>0, если x и у представляют собой не идентичные объекты. В-третьих, функция R(x,y) симметрична, то есть R(x,y)=R(y,x) для любых x и y. В-четвертых, для функции R(x,y) выполняется неравенство треугольника: расстояние между двумя объектами всегда меньше либо равно сумме расстояний от этих объектов до любого третьего объекта. Наконец, функция R(x,y) определена для любых двух объектов x и y.

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

Способ Z-order заключается в проецировании пространственных объектов на числовую ось, а затем работе с полученными числами-проекциями. Это позволяет выполнять индексацию и поиск с помощью различных методов работы с числовыми данными. В частности, способ UB-Tree подразумевает использование В-деревьев [VOLKER GAEDE, Multidimensional Access Methods, URL: http://www-static.cc.gatech.edu/computing/Database/readinggroup/articles/p170-gaede.pdf].

Недостатком данного способа является то, что он применим только тогда, когда данные можно проецировать на ось.

Квадрантные деревья используются при работе с множествами точек на плоскости. Создание индекса заключается в построении дерева. Множество всех обрабатываемых точек соответствует корню дерева. Далее плоскость разбивается на четыре квадранта, а у корня дерева создается четыре дочерних узла, каждый из которых соответствует одному из квадрантов. Если в квадранте оказывается более одной точки, то операция построения дерева рекурсивно повторяется для этого квадранта: он разбивается на четыре части, а у узла дерева создается четыре подузла. Для работы с множествами трехмерных точек используются октантные деревья, принцип работы которых схож с квадрантными [Samet, Hanan; Webber, Robert (July 1985). "Storing a Collection of Polygons Using Quadtrees" URL: http://infolab.usc.edu/csci585/Spring2008/den_ar/p182-samet.pdf].

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

Способ R-tree (R-деревья) позволяет работать с множеством векторов в многомерном пространстве. Каждый узел дерева соответствует некоторому прямоугольному параллепипеду в данном пространстве и множеству точек, лежащему внутри этого параллепипеда. У узла может быть несколько подузлов, при этом соответствующие им параллепипеды могут пересекаться, но обязательно лежат внутри охватывающего паралепипеда, соответствующего данному родительскому узлу. Корень дерева соответствует прямоугольному параллепипеду, охватывающему все обрабатываемое множество векторов. Существуют различные модификации R-деревьев, среди которых следует упомянуть R+-деревья, R*-деревья, Гильбертовы R-деревья и Х-деревья.

[Antonin Guttman (1984). "R-trees: A Dymamic index structure for spatial searching" URL: http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf]

Недостатком является то, что R-деревья применимы только для случая числовых векторов. Кроме того, строение R-дерева существенно зависит от того, в каком порядке информация добавляется в дерево.

Достаточно распространенные М-деревья также можно считать модификацией R-деревьев, у которых узлы соответствуют не прямоугольным параллелепипедам, а шарам в пространстве объектов. Это позволяет применять М-деревья для информационных объектов, которые не представимы как векторы чисел, но для которых задана метрика [Guttman, А. (1984). "R-Trees: А Dynamic Index Structure for Spatial Searching" URL: http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf; Ciaccia, Paolo; Patella, Marco; Zezula, Pavel (1997). "M-tree An Efficient Access Method for Similarity Search in Metric Spaces" URL: http://www.v1db.org/conf/1997/P426.PDF].

Недостатком является то, что эффективность использования М-деревьев (прежде всего, скорость вставки и поиска значений) существенно зависит от выбора эвристических алгоритмов, используемых при работе с деревом.

KD-деревья имеют много общего с R-деревьями: происходит работа с векторами чисел, корень дерева соответствует множеству всех объектов, узел дерева - подмножеству, которое целиком входит в подмножество, соответствующее родительскому узлу. KD-деревья являются бинарными. Для каждого узла KD-дерева задается некоторая поверхность, разбивающая множество объектов на две части. Одна часть соответствует одному дочернему узлу, а другая часть - другому дочернему узлу [Chandran, Sharat. Introduction to kd-trees URL: http://www.cs.umd.edu/class/spring2002/cmsc420-0401/pbasic.pdf].

Недостатком является то, что KD-деревья применимы только для случая числовых векторов.

Наиболее близким аналогом является способ Grid, который применяется для работы с точками на поверхности, которая предварительно разбивается на множество непересекающихся ячеек, покрывающих всю поверхность и имеющих регулярную структуру: квадраты, прямоугольники, треугольники, шестиугольники и т.п. Форма ячеек может быть различной и выбирается исходя из реальных данных, а также постановки конкретной задачи. Любая точка всегда относится к одной и только одной ячейке, но при этом к одной и той же ячейке может относится сразу несколько точек. Для любой точки можно легко вычислить индекс соответствующей ей ячейки. При поиске сначала происходит определение индекса необходимой ячейки, а уже затем анализируются точки внутри этой и соседних с ней ячеек. Способ несложно обобщить для случая многомерных данных [Kevin Sahr, Denis White, and A. Jon Kimerling, Geodesic Discrete Global Grid Systems URL: http://www.sou.edu/cs/sahr/dgg/pubs/gdggs03.pdf#search=%22hexagonal%20grid%20kimerling%22].

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

Технический результат изобретения - повышение эффективности поиска информационных объектов, для которых задана метрика сравнения.

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

При сравнении с описанными выше подходами заявляемое изобретение больше всего похоже на подход Grid, но имеет существенное преимущество: оно позволяет работать с произвольными пространственными объектами, а не только точками на плоскости. Единственное условие применимости заявляемого изобретения состоит в том, что для информационных объектов должна быть задана функция вычисления расстояния (метрика).

Основная идея заявляемого изобретения состоит в следующем. Для работы с множеством пространственных объектов предварительно задается N фиксированных информационных объектов A₁, …, A_N, далее называемых опорными объектами. Для каждого из них задается набор положительных чисел R_i,1, …, R_i,k, где i - номер опорного объекта, а k - количество чисел. Число k может быть фиксированным, а может быть отличаться для различных опорных объектов. Числа R_i,1, …, R_i,k задают радиусы шаров с центром в A_i и, таким образом, разбивают пространство на k+1 областей, далее называемых кольцами опорного объекта A_i. В первом кольце лежат все объекты, находящиеся от A_i на расстоянии, не большем R_i,1. Во втором кольце лежат все объекты, находящиеся от A_i на расстоянии, большем R_i,1, но не большем R_i,2, и так далее. В последнем кольце лежат все объекты, находящиеся от A_i на расстоянии, большем R_i,k. Тогда для любого информационного объекта X известны натуральные числа I₁, …, I_N, где I_K - это номер кольца объекта A_K, в котором расположен объект X. Числа I₁, …, I_N представляют собой код области, в которой расположен объект X. Все пространство разбивается на конечное множество областей, каждая из которых однозначно идентифицируется своим кодом.

Коды областей обладают важным свойством. Пусть объект X расположен в области с кодом I₁, …, I_N, а объект Y - в области с кодом J₁, … ,J_N. Во-первых, если коды областей совпадают (то есть вектор I₁, …, I_N полностью совпадает с вектором J₁, …, J_N), то X и Y могут быть сколь угодно близки друг к другу. Во-вторых, если соответствующие друг другу компоненты векторов I₁, …, I_N и J₁, …, J_N различаются не более чем на 1, то X и Y также могут быть сколь угодно близки друг к другу, поскольку содержащие их области имеют общую границу. Наконец, если для некоторого i, обозначающего номер опорного информационного объекта, значение I_i отличается от J_i более чем на единицу, то можно вычислить нижнюю оценку расстояния между X и Y. Пусть число I_i меньше J_i. Тогда расстояние от X до Y не меньше, чем R_p-R_q, где p=J_i-1, a q=I_i. Фактически, число R_p-R_q представляет собой суммарную ширину колец, расположенных между кольцами I_i и J_i.

В заявляемом изобретении индексация заключается в построении N-мерного массива D, измерения которого соответствуют опорным информационным объектам, а значения индексов - номерам колец этих опорных объектов. В ячейках массива D хранятся информационные объекты.

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

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

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

При поиске М объектов, наиболее близких к заданному объекту X, сначала происходит определение кода области I₁…I_N, в которой располагается объект X. Затем осуществляется поиск объектов в этой области (т.е. в подмножестве объектов, содержащемся в ячейке массива D), а также в областях с кодами J₁…J_N, при этом области с кодами J₁…J_N рассматриваются в порядке увеличения минимального расстояния от объектов области J₁…J_N до объектов области I₁…I_N. Определение минимального расстояния происходит согласно сформулированному выше свойству кодов областей. По мере рассмотрения областей J₁…J_N все находящиеся в них объекты добавляются в список найденных объектов Y₁, …, Y_F Список объектов Y₁, …, Y_F автоматически сортируется в порядке возрастания расстояния от X до элементов этого списка.

Процедура поиска останавливается в следующем случае: список Y₁, …, Y_F содержит не меньше, чем М элементов, а расстояние от X до Y_M (М-й элемент списка Y₁, …, Y_F) меньше, чем минимально возможное расстояние от объекта из области I₁…I_N до объекта из рассматриваемой области J₁…J_N, рассматриваемой на текущей итерации алгоритма. Результатом поиска является список Y₁, …, Y_M. Также, процедура поиска заканчивается, если рассмотрены все возможные J₁…J_N.

Если выполняется поиск объектов, находящихся от X на расстоянии, не большем заданного Т, то поиск останавливается в случае, когда минимальное расстояние от объекта из области I₁…I_N до объекта из области J₁…J_N становится большим, чем Т. Результатом поиска являются все объекты из списка Y₁, …, Y_F, для которых выполняется R(X,Y)<=T.

Вместо многомерного массива D можно использовать ассоциативный массив, у которого ключом будет код области, а значением - соответствующее подмножество информационных объектов. Возможна любая известная реализация ассоциативного массива, начиная от линейного списка и заканчивая деревьями поиска [https://ru.wikipedia.org/wiki/%D0%90%D1%81%D1%81%D0%BE%D1%86%D0%B8%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2#.D0.A0.D0.B5.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D0.B8_.D0.B0.D1.81.D1.81.D0.BE.D1.86.D0.B8.D0.B0.D1.82.D0.B8.D0.B2.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81. D1.81.D0.B8.D0.B2.D0.B0)

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

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

Возможен способ, предполагающий подбор опорных векторов путем решения задачи минимизации с помощью генных алгоритмов, методов радиентного списка и других методов оптимизации (https://ru.wikipedia.org/wiki/%D0%9B%D0%BE%D0%BA%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA_(%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F); подбираемыми параметрами являются опорные информационные объекты и радиусы колец, а целевой функцией - количество коллизий, возникающих при индексации тестового множества объектов.

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

Изобретение относится к вычислительной технике, в частности к алгоритмам и методам индексации и поиска информационных объектов, для которых задана метрика (функция вычисления расстояния). Техническим результатом является повышение эффективности поиска информационных объектов, для которых задана метрика сравнения, за счет повышения скорости поиска и снижения требуемого объема вычислений. В способе индексации и поиска многомерных данных, для которых задана метрика и не накладывается никаких других ограничений, индекс строится на наборе предзаданных опорных объектов и радиусов колец вокруг каждого объекта. Способ индексации и поиска многомерных данных включает построение индекса, алгоритмы добавления и удаления объектов, алгоритмы поиска объектов, ближайших к заданному или находящихся на указанном расстоянии от заданного, выбор опорных объектов при построении индекса. 2 н. и 2 з.п. ф-лы.

1. Способ индексации и пространственного поиска данных на основе хэширования, согласно которому индекс строится на основе набора предзаданных опорных объектов, для каждого из которых задаются несколько колец указанного радиуса; у разных опорных объектов количество колец и их радиусы могут различаться; любой объект X подпадает в одно из колец каждого опорного информационного объекта в зависимости от расстояния от X до этого опорного объекта; код области объекта X представляет собой вектор натуральных чисел, длина которого равна количеству опорных объектов, а значения элементов которого - номера колец опорных объектов, в которые попал объект X; для кодов областей справедливо свойство, позволяющее по кодам двух областей определить минимальное расстояние между объектами, лежащими в этих областях; для хранения множества объектов используется многомерный массив, измерения которого соответствуют опорным объектам, значения индексов каждого измерения - номерам колец соответствующего опорного объекта, а ячейки - областям пространства информационных объектов; в ячейках многомерного массива хранятся подмножества объектов, расположенных в соответствующих областях пространства; способ выполняет алгоритм добавления информационного объекта, в ходе работы которого сначала вычисляется код добавляемого объекта, по коду из многомерного массива извлекается подмножество объектов и в него добавляется данный объект; способ выполняет алгоритм удаления информационного объекта, в ходе работы которого сначала вычисляется код добавляемого объекта, по коду из многомерного массива извлекается подмножество объектов и из него удаляется данный объект; способ выполняет алгоритм поиска объектов, наиболее близких к заданному объекту X, при этом в начале работы алгоритма поиска вычисляется код области, к которой относится объект X; затем рассматриваются все объекты множества, находящиеся в этой области; далее итеративно рассматриваются остальные области и находящиеся в них объекты в порядке возрастания минимального расстояния от объекта X до рассматриваемой области; алгоритм поиска заканчивает работу, либо когда рассмотрены все области, либо когда найдено необходимое количество объектов, а объекты текущей рассматриваемой области расположены заведомо дальше; способ выполняет алгоритм поиска объектов, расположенных на указанном расстоянии от заданного объекта X; в начале работы алгоритма поиска вычисляется код области, к которой относится объект X; затем итеративно рассматриваются все объекты множества, находящиеся в этой области; далее рассматриваются остальные области и находящиеся в них объекты в порядке возрастания минимального расстояния от объекта X до рассматриваемой области; алгоритм поиска заканчивает работу, либо когда рассмотрены все области, либо когда объекты текущей рассматриваемой области расположены заведомо дальше, чем указано в условиях поиска.

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

3. Способ по из любому из пп. 1, 2, предполагающий подбор опорных векторов путем решения задачи минимизации; подбираемыми параметрами являются опорные информационные объекты и радиусы колец, а целевой функцией - количество коллизий, возникающих при индексации тестового множества объектов.

4. Способ по любому из пп. 1, 2, предполагающий подбор опорных векторов на основе результатов кластеризации тестового множества объектов; центры кластеров выбираются в качестве опорных объектов, а количество и радиусы колец определяются так, чтобы все множество объектов было разделено на несколько подмножеств, содержащих примерно одинаковое количество объектов.