Я нашел различные вопросы с решениями, аналогичными этой проблеме, но пока ничего не стоит. Очень благодарен за любую помощь.
У меня есть база данных mysql (v.5.6.10) с одной таблицей с именем POSTS, в которой хранятся миллионы и миллионы строк точек интереса широты/долготы на карте. Каждая точка классифицируется как один из нескольких различных типов. Каждая строка структурирована как id, type, coords:
idиunsigned bigint+ первичный ключ. Это значение автоматически увеличивается для каждой новой вставляемой строки.typeиunsigned tinyintиспользуются для кодирования типа точки интереса.coordsгеопространственныйPOINTтип данных mysql, представляющий широту/долготу точки интереса.
В «координатах» есть ПРОСТРАНСТВЕННЫЙ индекс.
Мне нужно найти эффективный способ сделать запрос к таблице и вернуть до X последних добавленных точек в радиусе ("R") определенной широты/долготы (" Позиция"). База данных очень динамична, поэтому, пожалуйста, предполагайте, что данные радикально отличаются каждый раз, когда запрашивается таблица.
Если X бесконечно, проблема тривиальна. Мне просто нужно выполнить запрос что-то вроде:
SELECT id, type, AsText(coords) FROM POSTS WHERE MBRContains(GeomFromText(BoundingBox, Position))
Где «BoundingBox» — это тип данных mysql POLYGON, который идеально окружает круг радиуса R от Position. Использование ограничительной рамки, конечно, не идеальное решение, но это не важно для конкретной проблемы, которую я пытаюсь решить. Я могу упорядочить результаты, используя «ORDER BY ID DESC», чтобы сначала получить и обработать самые последние добавленные точки.
Если X меньше бесконечности, мне просто нужно изменить приведенное выше:
SELECT id, type, AsText(coords) FROM POSTS WHERE MBRContains(GeomFromText(BoundingBox, Position)) ORDER BY id DESC LIMIT X
Проблема, которую я пытаюсь решить, заключается в том, как получить хороший репрезентативный набор результатов из заданного региона на карте, когда точки в этом регионе сильно сгруппированы (например, в пределах городов в области поиска карты). Например:
В приведенном выше примере я стою в точке X и ищу 5 недавно вставленных точек типа black в ограничительной рамке с черной рамкой. Если все эти точки были вставлены в кластер в правом нижнем углу (предположим, что кластер — это Лондон), то мой набор результатов не будет включать черную точку, которая находится в правом верхнем углу области поиска. Это проблема для моего приложения, так как я не хочу, чтобы у пользователей создавалось впечатление, что за пределами каких-либо областей, где точки сгруппированы, нет точек интереса.
Я рассмотрел несколько возможных решений, но не могу найти такое, которое эффективно работает, когда количество строк огромно (десятки миллионов). Подходы, которые я пробовал до сих пор, включают:
Разделение области поиска на S квадратов (т. е. превращение ее в сетку) и поиск до x/S точек в каждом квадрате — т. е. выполнение отдельного запроса mysql для каждого квадрата в сетке. Это работает нормально для небольшого количества строк, но становится неэффективным, когда количество строк велико, поскольку вам нужно разделить область на большое количество квадратов, чтобы подход работал эффективно. Имея небольшое количество квадратов, вы не можете гарантировать, что в каждом квадрате не будет густонаселенного кластера. Большое количество квадратов означает большое количество поисков mysql, что приводит к пыхтению.
Добавление столбца в каждую строку таблицы, в которой хранится расстояние до ближайшего соседа для каждой точки. Расстояние до ближайшего соседа для данной точки вычисляется, когда точка вставляется в таблицу. С помощью этой структуры я могу затем упорядочить результаты поиска по столбцу расстояния до ближайшего соседа, чтобы любые точки, находящиеся в кластерах, возвращались последними. Это решение работает только тогда, когда я ищу ВСЕ точки в области поиска. Например, рассмотрим ситуацию на диаграмме, показанной выше. Если я хочу найти 5 недавно вставленных точек типа зеленый, расстояние до ближайшего соседа, записанное для каждой точки, будет неправильным. Пересчет этих расстояний для каждого запроса будет слишком дорогим, даже с использованием эффективных алгоритмов, таких как деревья KD.
На самом деле, я не вижу никакого подхода, который требует предварительной обработки данных в строках таблицы (или, другими словами, «касания» каждой точки в соответствующем наборе данных области поиска), чтобы быть жизнеспособным, когда количество строк становится большим. Я рассмотрел такие алгоритмы, как k-means/DBSCAN и т. д., и не могу найти ничего, что будет работать с достаточной эффективностью, учитывая описанный выше вариант использования.
Любой жемчуг? Моя интуиция подсказывает мне, что это МОЖЕТ быть решено, но я пока в тупике.
