Nano Hash - криптовалюты, майнинг, программирование

Найдите расстояние между более чем 100 000 местоположений

У меня есть две таблицы MySQL с местоположениями, table1 и table2 (см. ниже). В каждой таблице > 100 тыс. строк. Я хотел бы найти расстояние между каждым местоположением в этих двух таблицах, используя их геолокации.

Вот запрос MySQL, чтобы найти расстояние между одной геолокацией, например (-37,22, 88,88), и всеми местоположениями в table1.

$lat = -37.22;
$long = 88.88;

SELECT id, latitude, longitude, name
        ((2 * 3960 *
          ATAN2(
            SQRT(
              POWER(SIN((RADIANS($lat - latitude))/2), 2) +
              COS(RADIANS(latitude)) *
              COS(RADIANS($long)) *
              POWER(SIN((RADIANS($long - longitude))/2), 2)
            ),
            SQRT(1-(
              POWER(SIN((RADIANS($lat - latitude))/2), 2) +
              COS(RADIANS(latitude)) *
              COS(RADIANS($long)) *
              POWER(SIN((RADIANS($long - longitude))/2), 2)
            ))
          )
        )) AS distance FROM table1 ORDER BY distance;

Table1
id name latitude longitude
1   foo1    -37.12   62.34
2   foo2    -47.12   72.34
3   foo3    -57.12   82.34

Table2
id name latitude longitude
1   bar1    -38.22   66.11
2   bar2    -48.22   76.11
3   bar3    -58.22   86.11

Учитывая, что это тоже большие данные, я не уверен, с чего начать. Мысли?

mysql php geolocation bigdata
22.06.2016

  • Важный вопрос: что вы хотите делать с расстояниями? 23.06.2016
  • Не уверен, что это сработает, но вы могли бы изучить решение ETL, например, Pentaho Data Integration? 23.06.2016
  • Вы запрашиваете расстояние между одним местом и всеми местами таблицы (1 и 2) или расстояния между таблицей 1 и таблицей 2? 23.06.2016
  • @mistermartin выглядит так, как будто это последнее, поэтому 100kx100k = 10 миллиардов вычислений. 23.06.2016
  • Да 10 миллиардов вычислений 23.06.2016
  • @KIKOSoftware почему? заключается в том, чтобы помочь людям в этих местах найти друг друга. Надеюсь, я представил в общем, так что это больше об алгоритмах 23.06.2016
  • @Maximus2012 Maximus2012 Я был бы счастлив с подмножеством 10B, меня больше интересует, как это сделать. 23.06.2016
  • Подумайте о том, чтобы определить «нахождение», чтобы упростить задачу. Иногда удивительно, чего можно добиться таким образом. Если вам все равно, просто рассчитайте все расстояния 10B. 23.06.2016
  • Тим, я написал свой ответ до того, как появился этот новый комментарий. То, что вы пытаетесь создать, представляет собой матрицу расстояний и используется в алгоритме кратчайшего маршрута или TRSP. Если вы хотите найти близлежащие местоположения, это другая проблема, и вы можете использовать пространственный индекс для достижения этого без матрицы расстояний. 23.06.2016
  • Пространственный индекс и матрица расстояний наивно кажутся мне похожими понятиями. Можете ли вы объяснить разницу. Если это уместно, я мог бы получить только 100 самых коротких расстояний между каждым местоположением, чтобы их можно было сократить до 10 миллионов вычислений. 23.06.2016

Ответы:


1

  • Если вы хотите оптимизировать путешествие или приблизиться к месту, вам следует использовать пространственные функции http://dev.mysql.com/doc/refman/5.7/en/spatial-extensions.html

  • Но похоже, что вам нужен каждый расчет, так что да, вам нужно будет выполнить 10 миллиардов операций.

    • I guess time isnt really a problem here. Because once you have it you can use it. And if new locations arrive just calculate distance against that location.
    • Но надо оптимизировать. Самая затратная часть запроса — вычислить SIN() и COS(), поэтому создайте дополнительное поле для каждой строки с этим значением. Поэтому вам нужно сделать это только один раз, а не 100 тысяч раз для каждой строки.
    • Наконец, запустите цикл, чтобы создать данные в блоках.

ИЗМЕНИТЬ:

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

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

  SELECT t1.name, t2.name,  mysql.Distancefunction(t1,t2) as distance
  from t1
  cross join t2
  WHERE t2.x between (t1.x - 0.001) and (t1.x + 0.001)   -- use x float index
    and t2.y between (t1.y - 0.001) and (t1.y + 0.001)   -- use y float index
    and mysql.Distancefunction(t1,t2) < 100 km           -- use spatial index

Вы можете играть с дельтой 0,001. Если вы получаете слишком много результатов, вы используете 0,0001. Если вы получаете мало результатов, вы делаете второй шаг с 0,01 только для тех мест, где нет 100 соседей.

22.06.2016
  • Да время не проблема. Я хотел бы иметь возможность запрашивать данные после создания. Спасибо за предложение сделать sin() и cos() только один раз. Можете ли вы подробно рассказать о цикле, который создает данные в блоках. Это просто простой цикл for на любом языке программирования, смешанный с limit offset в MySQL? Я никогда не занимался большими данными, поэтому предполагаю, что есть более причудливые решения (не то чтобы я хотел быть причудливым). 23.06.2016
  • Зависит от ваших потребностей и вычислительной мощности. Если вы можете сделать select distance(*) from table1, table 2 where table1 between 1 and 10.000 примерно за час, то просто скопируйте/вставьте 10 раз. Просто не запускайте все это вместе, иначе оно будет обрабатываться как транзакция и будет хранить временные таблицы для всего процесса. 23.06.2016
  • Если все работает медленнее и нужно выполнить 100 запросов по 1000 каждый, вы можете создать скрипт для отправки запроса. 23.06.2016
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..