MySQL

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

самый простой способ - это ХП, и внутри нее перебор всех строк таблицы и производство расчета но тут сразу возникают вопросы к производительности, а может есть какие-то хитрые способы реализации самого хранения которые позволят как-то хитро реализовать? ну что-то типа https://en.wikipedia.org/wiki/Perceptual_hashing

(0) Можно подробней правильно ли понял

Есть табличка в базе с длиной поля 50 байт, куда и записаны эти 50 однобайтовых чисел.
Строк-записей в табличке неизвестно сколько (но вероятно много) с этими 50 байтами.

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

А так да два варианта или тупое распараллеливание поиска - что прекрасно в данном случае выполняется.
Можно заюзать OpenCL или CUDA на GPU там вычислительных юнитов (универсальных процессоров) даже на дешевой видяхе сча от 300 штук и до нескольких тысяч штук на топовых видяхах.

Или да можно заюзать разные варианты предварительного хеширования, если база меняется не часто и можно выполнить предвычисления с сохранением в базе чтобы потом быстро подбирать.

(1) да

количество строк в базе думаю будет от 10 000 до 100 000 строк

"некой простой формуле значение отклонения" - какая формула или еще неизвестно?

(5)+ Хотя пофиг

Короче суть в чем.
Введем понятие шингла - это подстрока из k байт на которую разбиваем каждую 50 байт строку.
Будем считать что пара 50 байт строк похожи тем сильней чем больше у них похожих шинглов.

Для простоты возьмем длину шингла k = 10, тогда каждая 50 байт будет состоять из 5 шинглов.
Далее введением хэш функции (она должна быть максимально близка к твоей формуле) разобьем всевозможные шинглы на схожие кластеры.
Сами шинглы и их кластеры сохраним в базе.

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

В итоге кол-во вариантов для перебора сильно сокращается

пока в екселе экспериментирую, примерно так будет

результат = 0;
цикл
а=ABS(БайтИзБазы-БайтИзПараметра)*100/81
Если а < 5 Тогда
результат = результат + 0; // не учитываем
ИначеЕсли а < 10 Тогда
результат = результат + а; // учитываем
ИначеЕсли а < 25 Тогда
результат = результат + а*2; // учитываем в двойном размере
Иначе
результат = результат + 100;
КонецЕсли

Результат = 100 - Результат/50

(6) https://ru.wikipedia.org/wiki/Алгоритм_шинглов

(6) я думал создать дополнительное поле размером 1 или 2 байта и предворительно вычислять по нему выборку, но пока не понятно как именно это сделать

(9) Дык я же написал - кластеризация.

Эти твои 50 байт можно представить как точку (или вектор) в 50-мерном пространстве.
И имея 10к-100к точек, надо для новой подобрать ближайшие.

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

(10)+ Сделать количество кластеров 256 (1 байт) хорошая мысля, а вот 65536 (2 байта) уже не очень если исходно 10000 всего точек

(10) https://habr.com/ru/post/164417/

(12) https://ru.wikipedia.org/wiki/Метод_k-средних

(10) Вот даже на 1С http://catalog.mista.ru/public/444787/

Короче:
1. Случайно расставляешь (придумываешь) 256 точек из 50 байт
2. Вычисляешь расстояние от каждой точки из базы до каждой из 256 придуманных точек, до которой ближе к тому кластеру и относишь
3. Далее пошли циклические шаги k-means, берется каждый полученный кластер и вписывается в прямоугольник (чтобы все точки влезли), находится центр прямоугольника - теперь это новые 256 точек
4. Переходим к шагу 2
5. Если точки кластеров перестали меняться то мы нашли кластеры или ограничиваем по числу шагов в 30 например. Можно заново попробовать случайно расставить начальные точки и снова попробовать до "схождения" чтобы кластеры перестали меняться

И вот получается что каждая из 10к-100к точек в базе будет сопоставлена некоему кластеру из 256 - тупо записать в базу его номер и отдельно координаты другой табличке.

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

(15)+ Ну или платформу 1С 8 посвежее и https://master1c8.ru/platforma-1s-predpriyatie-8/rukovodstvo-razrabottchika/glava-14-analiz-dannh-i-pronozirovanie/analiz-dannh-i-prognozirovanie-klasterizatsiya/

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

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

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

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

(18) История с шинглами это сокращение размерности, вместо 50 измерений сделать всего 10 или даже 5
Общее значение шингла счтаешь и пишешь в базу как один байт например.

Откуда такая задача то? Что и зачем хочешь получить?

(21) да я все с фотками воюю, это домашнее хобби... пишу анализатор для поиска похожих.

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

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

(22) А в курсе что то с чем ты воюешь на очень высоком уровне делают большие парни?
Тот же гугл с его картинками и прочие яндексы?

Короче открой http://images.google.ru/advanced_image_search и увидишь там "Сайт или домен:"
Далее все логично же, выкладываешь свои картинки в паблик на свой сайт и вуаля.

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

(23)+ https://jarjad.ru/compare-images/

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

(24) загрузил им одно и то-же изображение но повернутое на 90 градусов, они мне выдали

Второе изображение 91.89% отличается от первого.
у меня результат 96% совпадений


загрузил два похожих

Второе изображение 69.47% отличается от первого.

у меня результат 85 совпадений

(26) короче у меня сильно круче чем в (23)

(25) Начни с классического ML.
Все начинается с признаков. Т.е. сначала придумываем какие признаки можно использовать а далее выделяем их.
И вот полученные признаки уже загоняем либо в алгоритмы либо в ИНС.

(27) Та не, они поворот не используют просто.

Попробуй на обрезанных фото или с надписями поверх или снятыми в тоже время но чуть отличающимися.

(29) С обрезанными интересно там внизу есть кнопки Рамка и Игнорировать после них результат есть.

(29) да пробовал

две фотки снятые одна за одной с одного места, ну люди чуток шевельнулись и ветер траву качает, их результат  различия в 69.47% а мой видит, что они похожи...

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

короче у меня первая половина алгоритма отвечает за цветность, вторая за форму, тем самым можно объединять разные алгоритмы по патенту "разделяй и властвуй", что точно даст нужный результат, вопрос только конкретной реализации а она будет зависеть от конкретности фотографий. Короче мне теория сейчас понятна, не понятны нюансы конкретной реализации :)

(31) Тогда рекомендую сделать это онлайн проектом и можно привлечь желающих для участия если нет цели монетизации.
Думаю еще много кто над этим думал и вот скооперировшись можно получить результат.

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

На тот же гитхаб например и страничку заведи на спецфоруме для обсуждения. Миста тут не очень актуальна. Тут больше нужен форум по обработке фото и по машинному обучению.

ночью и утром вся картина в голове сложилась, решил самую главную проблему для меня "проблема пограничных значений", ну и шинглы то-же помогли, я интуитивно двигался в этом направлении а почитал и вроде сходится :),

теперь осталось подобрать коэффициенты и оформить в коде, ну и проблема с быстродействием из сабжа то-же решилась, я понял чего мне делать есть несколько вариантов предварительного сужения поля поиска (думаю от 10 до 100 раз уменьшу выборку для детальной обработки) а дальше будет перебор в ХП, по предварительным оценкам поиск будет идти 1..5 сек, что вполне допустимо для массива в 100к фото