Намерих различни въпроси с решения, подобни на този проблем, но нищо съвсем за парите досега. Много благодарен за всяка помощ.
Имам база данни mysql (v.5.6.10) с една таблица, наречена POSTS, която съхранява милиони и милиони редове от интересни точки по ширина/дължина на карта. Всяка точка се класифицира като един от няколко различни типа. Всеки ред е структуриран като id, type, coords:
idanunsigned bigint+ първичен ключ. Това се увеличава автоматично за всеки нов ред, който се вмъква.typeanunsigned tinyintизползван за кодиране на типа на интересната точка.coordsmysql геопространственPOINTтип данни, представляващ ширината/дължината на интересната точка.
Има индекс SPATIAL за „коорди“.
Трябва да намеря ефективен начин да направя заявка в таблицата и да върна до X от най-скоро вмъкнатите точки в радиус („R“) на конкретна позиция по ширина/дължина („ Позиция"). Базата данни е много динамична, така че, моля, приемете, че данните са радикално различни всеки път, когато таблицата се запитва.
Ако X е безкрайно, проблемът е тривиален. Просто трябва да изпълня заявка като:
SELECT id, type, AsText(coords) FROM POSTS WHERE MBRContains(GeomFromText(BoundingBox, Position))
Където „BoundingBox“ е тип данни на mysql POLYGON, който идеално затваря кръг с радиус R от позицията. Използването на ограничителна кутия, разбира се, не е идеалното решение, но това не е важно за конкретния проблем, който се опитвам да разреша. Мога да подредя резултатите с помощта на „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-те най-скоро вмъкнати точки от тип черно в рамката с черна рамка. Ако всички тези точки бяха вмъкнати в клъстера в долния десен ъгъл (да приемем, че клъстерът е Лондон), тогава моят набор от резултати няма да включва черната точка, която е близо до горния десен ъгъл на областта за търсене. Това е проблем за моето приложение, тъй като не искам потребителите да остават с впечатлението, че няма интересни точки извън зони, където точките са групирани.
Обмислих няколко потенциални решения, но не мога да намеря такова, което да работи ефективно, когато броят на редовете е огромен (десетки милиони). Подходите, които съм опитвал досега, включват:
Разделяне на областта за търсене на S брой квадрати (т.е. превръщането му в решетка) и търсене на до x/S точки във всеки квадрат - т.е. изпълнение на отделна mysql заявка за всеки квадрат в мрежата. Това работи добре за малък брой редове, но става неефективно, когато броят на редовете е огромен, тъй като трябва да разделите региона на голям брой квадрати, за да работи подходът ефективно. Само с малък брой квадрати не можете да гарантирате, че всеки квадрат няма да съдържа гъсто населен клъстер. Големият брой квадрати означава голям брой търсения в mysql, което кара нещата да се забиват.
Добавяне на колона към всеки ред в таблицата, която съхранява разстоянието до най-близкия съсед за всяка точка. Най-близкото съседно разстояние за дадена точка се изчислява, когато точката се вмъкне в таблицата. С тази структура след това мога да подредя резултатите от търсенето по колоната за разстояние на най-близкия съсед, така че всички точки, които са в клъстери, да се връщат последни. Това решение работи само когато търся ВСИЧКИ точки в района на търсене. Например, разгледайте ситуацията в диаграмата, показана по-горе. Ако искам да намеря 5-те най-скоро вмъкнати точки от тип зелено, най-близкото съседно разстояние, което се записва за всяка точка, няма да е правилно. Преизчисляването на тези разстояния за всяка заявка ще бъде твърде скъпо, дори при използване на ефективни алгоритми като KD дървета.
Всъщност не мога да видя никакъв подход, който изисква предварителна обработка на данни в редовете на таблицата (или, казано по друг начин, „докосване“ на всяка точка в съответния набор от данни за регион на търсене), за да бъде жизнеспособен, когато броят на редовете стане голям. Обмислях алгоритми като k-средства / DBSCAN и т.н. и не мога да намеря нищо, което да работи с достатъчна ефективност, като се има предвид случая на използване, обяснен по-горе.
Някакви бисери? Моята интуиция ми казва, че това МОЖЕ да бъде решено, но досега съм объркан.
