СПОСОБ ИНДЕКСАЦИИ И ПРОСТРАНСТВЕННОГО ПОИСКА ДАННЫХ НА ОСНОВЕ ХЭШИРОВАНИЯ

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