Поиск по подобию в реляционных и NoSQL базах данных?

Question

[pancakes]

Еще во время обучения в магистратуре я наткнулся на целый класс задач, который сводится к поиску похожих объектов. Это также называется поиском по подобию или задачей поиска ближайшего соседа. Количество приложений, в которых может применяться этот метод, поражает воображение: проверка правописания, сравнение документов, распознавание образов и поиск похожих изображений, системы рекомендаций и кластерный анализ данных… Я нашел ряд библиотек и описаний алгоритмов для решения задачи поиска по подобию, таких как Kd-деревья, перцептивные хеши и т.д.

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

Ну и напоследок, приведу пример конкретной задачи, которую мне хотелось бы решить используя методы поиска по подобию:

Допустим, есть веб-сервис, вроде биржи труда, который позволяет людям найти подходящую им работу, а работодателям позволяет быстро найти наиболее подходящих сотрудников под имеющиеся вакансии. Люди, ищущие работу, размещают свои резюме, где в структурированном виде указывают о себе данные (заполняют формы), указывают свои навыки и т.д. Работодатели, с другой стороны размещают информацию об открытых вакансиях. Сервис, по запросу может найти для выбранной вакансии

Дано:

• Массив данных о потенциальных сотрудниках (ну скажем об IT специалистах) – их резюме, содержащие имя, возраст и набор навыков с указанием степени владения каждым навыком (для простоты – число от нуля до ста единиц «опыта»).
• Массив данных об открытых вакансиях. Для каждой вакансии указываются желаемые характеристики сотрудника, для простоты: набор требуемых навыков.

Найти:

• Найти для выбранной вакансии k наиболее подходящих резюме.
• Найти по выбранному резюме k наиболее подходящих вакансий.

Мысли по решению:
Так как решается задача поиска по подобию, необходимо будет рассчитывать меру расстояния между элементами данных. В нашем случае есть два класса элементов данных: резюме и вакансия. Для простоты можно оба этих класса объектов представить в виде векторов навыков (сравнение по таким параметрам как возраст, пол и т.п. опустим для простоты и для того, чтобы не быть обвиненными в дискриминации).

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

Далее, можно сравнивать резюме и вакансии сравнивая полученные вектора навыков, соответствующие им, аналогично тому, как сравнивают документы в Векторной модели.

Расстояние между двумя элементами можно определить как угол между двумя соответствующими векторами:


где p_i и p_j – вектора представляющие резюме / вакансию,
w_k,i и w_k,j – значение k-го навыка сравниваемых векторов,
n – число всех возможных навыков.

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

Answer 1

[ztxn]

Нет, не то, тогда полное соответствие требованиям будет равняться по рангу полному не соответствию. Надо еще подумать

Answer 2

[ztxn]

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

select навыки_вакансии.вакансия
       ,требования_резюме.резюме
       ,count(*) as ранг
from навыки_вакансии,требования_резюме
where  навыки_вакансии.показатель = требования_резюме.показатель
group by навыки_вакансии.вакансия, требования_резюме.резюме
order by ранг desc

Comments

[ztxn]

>>степени владения
Упустил этот момент :facepalm

[ztxn]

C учетом степени владения ,count(*) as ранг заменить на sum(требования_резюме.степень владения-навыки_вакансии.степень_владения)

[ztxn]

Еще попытка

select навыки_вакансии.вакансия
       ,требования_резюме.резюме
       ,sum(требования_резюме.степень_владения - abs(требования_резюме.степень_владения-навыки_вакансии.степень_владения)) as ранг
from навыки_вакансии,требования_резюме
where  навыки_вакансии.показатель = требования_резюме.показатель
group by навыки_вакансии.вакансия, требования_резюме.резюме
order by ранг desc