Быстрый (э) способ сопоставления функции с базой данных

Question

Я работаю над проектом, в котором у меня есть элемент изображения, описанный как набор координат X & Y (5-10 точек на элемент), которые являются уникальными для этой функции. У меня также есть база данных с тысячами функций, каждый из которых имеет один и тот же тип дескриптора. Результат выглядит так:

myFeature: (x1,y1), (x2,y2), (x3,y3)...

myDatabase: Feature1: (x1,y1), (x2,y2), (x3,y3)...
            Feature2: (x1,y1), (x2,y2), (x3,y3)...
            Feature3: (x1,y1), (x2,y2), (x3,y3)...
            ...

Я хочу найти лучшее соответствие myFeature в функциях в моей базе данных.

Какой самый быстрый способ сопоставить эти функции? В настоящее время я перехожу к каждой функции в базе данных и сравниваю каждую отдельную точку:

bestScore = 0
for each feature in myDatabase:
    score = 0
    for each point descriptor in MyFeature:
        find minimum distance from the current point to the...
          points describing the current feature in the database
        if the distance < threshold:
            there is a match to the current point in the target feature
            score += 1

    if score > bestScore:
        save feature as new best match

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

Answer 1

Создайте набор битов (массив из 1 и 0) для каждой функции.

Создайте такую ​​битовую маску для ваших критериев поиска, а затем просто используйте побитовое и сравнить маску поиска с вашими функциями.

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

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

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

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

Сила этого в побитовых сравнениях.

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

Answer 2

В целом это выглядит как проблема пространственного индекса.Это не моя область, но вам, вероятно, потребуется создать своего рода индекс дерева, например, quadtree, который вы можете использовать для удобного поиска объектов.Вы можете найти некоторые ссылки из этой статьи википедии: http://en.wikipedia.org/wiki/Spatial_index

Возможно, это проблема, которую вы можете легко реализовать в существующей пространственной базе данных.Он очень похож на ГИС в своем описании.

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