Кластеризация латов / лонгов в базе данных

Question

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

Существует множество ресурсов о том, как кластеризовать, либо на стороне клиента, либо на стороне сервера (приложения) ... но не на стороне базы данных: (

Это похожий вопрос , заданный товарищем С.О. член. Решения основаны на стороне сервера (т. Е. Код C # позади).

Кто-нибудь имел удачу или опыт решения этой проблемы, но в базе данных? Есть ли какие-нибудь гуру баз данных, которые после боя и сексуального вызова БД?

пожалуйста, помогите:)

РЕДАКТИРОВАТЬ 1: Уточнение - путем кластеризации я надеюсь сгруппировать x количество точек в одну точку для области. Итак, если я скажу кластеризовать все в квадрате 1 миля / 1 км, то все результаты в этом «квадрате» будут GROUP'D в один результат (скажем ... в середине квадрата).

РЕДАКТИРОВАТЬ 2: Я использую MS Sql 2008, но я открыт для слушания, если есть другие решения в других БД.

Answer 1

Я бы, вероятно, использовал модифицированную * версию k - означает кластеризацию с использованием декартовых (например, WGS-84 ECF) координат для ваших точек. Его легко внедрить, он быстро сходится и адаптируется к вашим данным независимо от их внешнего вида. Кроме того, вы можете выбрать k в соответствии с вашими требованиями к пропускной способности, и у каждого кластера будет одинаковое количество связанных точек (мод k).

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

* «Модификация» будет заключаться в том, чтобы регулировать длину вычисленных векторов центроидов так, чтобы они находились на поверхности Земли. В противном случае вы получите кучу точек с отрицательной высотой (при конвертации обратно в LLH).

Answer 2

Если вы кластеризуетесь по географическому расположению, и я не могу представить, что это что-то еще :-), вы можете сохранить «идентификатор кластера» в базе данных вместе с координатами широты и долготы.

Под этим я подразумеваю разделение карты мира на (например) матрицу 100х100 (10 000 кластеров), и каждая координата присваивается одному из этих кластеров.

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

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

Yo всегда будет иметь граничные случаи, такие как две точки близко друг к другу, но в разных кластерах (один северный в своем кластере, другой самый южный в своем), но вы можете настроить размер кластера ИЛИ постобработка результаты на стороне клиента.

Answer 3

Я сделал то же самое для географического приложения, где я хотел убедиться, что могу легко кэшировать наборы точек. Мой геохэш-код выглядит так:

def compute_chunk(latitude, longitude)
  (floor_lon(longitude) * 0x1000) | floor_lat(latitude)
end

def floor_lon(longitude)
  ((longitude + 180) * 10).to_i
end

def floor_lat(latitude)
  ((latitude + 90) * 10).to_i
end

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

Answer 4

Для movielandmarks.com Я использовал код кластеризации от Майка Пурвиса , одного из авторов Начинающих приложений Google Maps с PHP и AJAX . Он строит деревья кластеров / точек для разных уровней масштабирования, используя PHP и MySQL, сохраняя их в базе данных, так что отзыв происходит очень быстро. Некоторые из них могут быть вам полезны, даже если вы используете другую базу данных.

Answer 5

Почему бы не протестировать несколько подходов?

1. перевод библиотеки weka в .NET CLI с IKVM.NET
2. добавить сборку, полученную из вашего кода и weka.dll (используйте ilmerge) в вашу базу данных

Проведите несколько тестов. Никакая конкретная кластеризация не работает лучше, чем кто-либо другой.

Answer 6

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