Ближайшая позиция между случайно движущимися объектами

Question

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

Таблица выглядит примерно так ...

CREATE TABLE positions (
  objectId              INTEGER,
  x_coord              INTEGER,
  y_coord              INTEGER,
  posTime             TIMESTAMP);

Я хочу найти, какие два объекта оказались ближе друг к другу и в какое время.

Найти расстояние между двумя исправлениями относительно легко - простой Пифагор для различий между значениями X и Y должен помочь.

Первая проблема, похоже, связана с объемом. Сетка сама по себе большая, 100 000 возможных X-координат и такое же количество Y-координат. Для любого заданного периода времени таблица может содержать 10 000 ссылочных позиций сетки для 1000 различных объектов - всего 10 миллионов строк. Само по себе это не так уж много, но я не могу придумать, как избежать «запроса продукта», чтобы сравнить каждое исправление с любым другим исправлением. Выполнение этого с 10 миллионами строк даст 100 миллионов результатов. Следующая проблема заключается в том, что меня интересуют не только два ближайших исправления, но и два ближайших исправления из различных объектов. Другая проблема заключается в том, что мне нужно сопоставлять время и положение - меня интересуют не только два объекта, которые посетили один и тот же квадрат сетки, они должны были сделать это в то же время .

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

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

Есть предложения?

Я не уверен, для какого форума SE это лучше всего подходит - база данных SQL? Программирование? Математика

ОБНОВЛЕНИЕ - Еще одна проблема, которая добавляет сложности: временная метка для каждого объекта и позиции нерегулярна, у одного элемента может быть позиция, записанная в 14:10:00, а другая - в 14:10:01. Если эти две позиции находятся рядом друг с другом и на расстоянии одной секунды, то они могут фактически представлять ближайшую позицию, хотя время не совпадает!

Answer 1

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

create index ix1_time on positions (postime);

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

with t as (
  select distinct(postime) as pt from positions
)
select *
  from t,
  (
  select * 
    from (
      select
        a.objectid as aid, b.objectid as bid,
        a.x_coord + a.y_coord + b.x_coord + b.y_coord as dist -- fix here!
      from t
      join positions a on a.postime = t.pt
      join positions b on b.postime = t.pt
      where a.objectid <> b.objectid
      ) x
    order by dist desc
    limit 1
  ) y;

Этот SQL должен сравнивать каждые 10000 объектов друг с другом по времени отправки. Он будет тестировать 10 миллионов комбинаций для каждого другого значения времени ожидания, но не против других значений времени ожидания.

Обратите внимание: Я использовал a.x_coord + a.y_coord + b.x_coord + b.y_coord в качестве формулы расстояния. Я оставляю правильный для вас здесь.

Всего будет вычислено 10 миллионов x 1000 значений времени: всего 10 миллиардов сравнений. Он вернет две ближайшие точки для каждого временного отрезка, то есть всего 1000 строк.