Есть таблица фирм с их географическими координатами.

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

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

Как изменить эту операцию чтобы она ускорилась?

а нельзя координаты сравнивать? не вычисляя расстояния

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

+(2) В принципе, можно и не сортировать, а просто создать БД с индексами по широте и долготе и выбрать попадающие в окно. Это если быстро.

(1) Все равно придется все фирмы проверить. Не то

(2) Ширина окна не известна заранее.

(5) Почему неизвестна? +10 км от точки в каждую сторону.

(6) Почему +10 км?

(4) Не все, количество сравнений будет log2(n).

(8) почему не все?

(7) Потому что если уж по 1 координате расстояние больше 10 км, то по двум и подавно. Т.е. эти организации заведомо не попадают в наше условие.

(10) Нет условия на 10 км. Иначе бы было слишком просто.

(9) Потому что они отсортированы, а ты ищешь двичным поиском.

(11) Ну не нашел в 10 км 10 организаций - увеличивай окно до 20 км.

(13) запрос в цикле?

(14) И что? Просто получаешь данные по частям.

+(15) Можешь оптимизировать размер окна в зависимости от средней плотности огранизаций в заданных координатах, чтобы за минимальное количество итераций находить нужное количество.

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

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

Геосервисы Яндекса или гугла можно попробовать использовать. У Яндекса есть - Географическая область поиска объекта. Не подойдет для этой задачи?

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

Можно сразу ввести ограничение на близость, типа если по какой то координате есть превышение в 100км, то даже если ближе этой точки нет фирм, мы все равно не считаем ее близкой. Ответ алгоритма "По близости нет фирм"

Еще как вариант -
0) отобрать первые попавшиеся 10 фирм,
1) отбросить из оставшейся кучи все те, у кого и широта и долгота дальше (то есть заведомо расстояние будет выше),
2) проверить первую фирму из кучи, если расстояние получилось меньше, чем в отобранных, то переходим в 1), если нет, отбрасываем эту фирму и переходим к 2)

(17) Можно. https://en.wikipedia.org/wiki/R-tree

(21) >> "По близости нет фирм"
это очень просто, и так у меня уже было. Думал вдруг есть более красивый вариант

(23) Спасибо!

(0) Применить (23), затем https://en.wikipedia.org/wiki/Selection_algorithm

Что-то не пойму - в чем проблема. Фирмы постоянно двигаются что-ли? Что вы ерундой занимаетесь?

(27) Двигается точка, к которой нужно находить ближайшие.

(27) то есть надо посчитать расстояние каждой фирмы с каждой? и не заниматься ерундой.

(29) Нужно выбирать координаты от ближайших к точке до более дальних, проверять наличие фирм в полученных координатах. Как только наберется 10 фирм или расстояние превысит предел останавливаться.

(30) Да, именно это надо сделать. Так и написано в вопросе (0)

(31) Так сделай. В чем вопрос? Как построить индекс по координатам?

(30) (32) +1

не понял вообще проблемы...

1. Берем точку (X,Y)
2. Далее цикл R=R+1 (приращение можно не 1 а сразу побольше делать)
3. Получаем границы квадрата (X-R;Y-R)-(X+R;Y+R) - это если направления осей нормальные
4. Запросом(ами) ищем все фирмы с координатами попадающими в заданный квадрат, если их меньше 10 то цикл по 2.
5. Если фирм в квадрате больше 10 то считаем до них расстояния и сортируем по нему

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

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

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

ВЫБРАТЬ
    0 КАК Ц,
    454 КАК x,
    23.9 КАК y
ПОМЕСТИТЬ Цифры

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    1,
    434,
    656

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    2,
    12,
    87

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    3,
    4088,
    9776

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    4,
    76,
    2385

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    5,
    9765,
    9787

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    6,
    3656,
    66888

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    7,
    4545,
    7564

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    8,
    7660,
    2324

ОБЪЕДИНИТЬ ВСЕ

ВЫБРАТЬ
    9,
    34,
    4324
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ
    Цифры.Ц + 10 * Цифры1.Ц + 100 * Цифры2.Ц + 1000 * Цифры3.Ц + 10000 * Цифры4.Ц КАК ч,
    Цифры.x + Цифры1.x + Цифры2.x + Цифры3.x + Цифры4.x КАК x,
    Цифры.y + Цифры1.y + Цифры2.y + Цифры3.y + Цифры4.y КАК y
ПОМЕСТИТЬ Точки
ИЗ
    Цифры КАК Цифры,
    Цифры КАК Цифры1,
    Цифры КАК Цифры2,
    Цифры КАК Цифры3,
    Цифры КАК Цифры4
;

////////////////////////////////////////////////////////////////////////////////
ВЫБРАТЬ ПЕРВЫЕ 10
    Точки.ч,
    Точки.x,
    Точки.y,
    (Точки.x - &x) * (Точки.x - &x) + (Точки.y - &y) * (Точки.y - &y) КАК Поле1
ИЗ
    Точки КАК Точки

УПОРЯДОЧИТЬ ПО
    Поле1

(0) Решал такую задачу с применением VP-дерева
Материал брал тут: http://technomag.bmstu.ru/doc/624368.html
Если надо, могу поделится кодом на 77

+(35) на миллион 2-3 сек.
(0) что в твоем понятии "быстро"?

(37) У тебя упрощенная формула расчета расстояния, и то выдает время 2-3 секунды на миллион записей. У меня более сложная, соответственно еще медленнее работает.

Если запрос выполняется дольше 0.01 секунды - то это для меня медленно. Я сайты делаю, а не в 1С программирую, тут совсем другие понятия медленности.

(36) Спасибо, тоже хороший материал. Код не нужен, я сам напишу.

имитируйте пространственный индекс.