как найти 20 ближайших точек эффективно [закрыто]

9

Скажем, я хочу найти 20 ближайших к себе дел.

My table structure is like this:

    BusinessID  varchar(250)    utf8_unicode_ci         No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
    Prominent   double          No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
    LatLong     point           No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
    FullTextSearch  varchar(600)    utf8_bin        No  None        Browse distinct values  Change  Drop    Primary     Unique  Index   Fulltext
With selected: Check All / Uncheck All With selected:
Print viewPrint view Propose table structurePropose table structureDocumentation
Add new fieldAdd field(s) At End of Table At Beginning of Table After
Indexes: Documentation
Action  Keyname Type    Unique  Packed  Field   Cardinality Collation   Null    Comment
Edit    Drop    PRIMARY BTREE   Yes No  BusinessID  1611454 A       
Edit    Drop    Prominent   BTREE   No  No  Prominent   0   A       
Edit    Drop    LatLong BTREE   No  No  LatLong (25)    0   A       
Edit    Drop    sx_mytable_coords   SPATIAL No  No  LatLong (32)    0   A       
Edit    Drop    FullTextSearch  FULLTEXT    No  No  FullTextSearch  0           

Есть 1,6 миллиона бизнесов. Конечно, глупо вычислять расстояние для всех и затем сортировать его.

Вот где гео пространственный индекс пинает правильно?

Так какого SQL-комманина мне нужно привести?

Замечания:

  1. Я использую MySQL пространственный индекс MySQL . Однако я не уточнил это раньше. Поэтому я приму тех, кто на него ответит, чтобы выразить свою признательность и задать еще один вопрос.
  2. Я не хочу вычислять расстояние для всей таблицы
  3. Я не хочу вычислять расстояние для любого региона, который все еще неэффективен
  4. Я хочу вычислить расстояние для разумного количества точек, потому что хочу отсортировать точки по расстоянию и иметь возможность отображать точки 1-20, 21-40, 41-60 и т. Д.
user4951
источник
3
перекрестная публикация dba.stackexchange.com/questions/19595/… (также кажется плохим, что у Джуджу есть вопрос, где каждый ответ
Эван Кэрролл

Ответы:

7

Пространственные запросы, безусловно, то, что нужно использовать.

С PostGIS я бы сначала попробовал что-то упрощенное, подобное этому, и настроил бы диапазон по мере необходимости:

SELECT * 
FROM table AS a
WHERE ST_DWithin (mylocation, a.LatLong, 10000) -- 10km
ORDER BY ST_Distance (mylocation, a.LatLong)
LIMIT 20

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

lynxlynxlynx
источник
9

Если все, что вам нужно, - это поиск точек приближения (запросы ближайших соседей), то вы не хотите использовать для этого старые ST_DWithin или ST_Distance + ORDER BY.

Уже нет.

Теперь, когда поставляется PostGIS 2.0, вы должны использовать поддержку индекса knngist (встроенная функция PostgreSQL). Это будет на порядки быстрее.

Выдержка из этой записи блога, которая описывает, как использовать knn gist без PostGIS :

$ create table test ( position point );

CREATE TABLE
Table created. Now let’s insert some random points:
$ insert into test (position) select point( random() * 1000, random() * 1000) from generate_series(1,1000000);

INSERT 0 1000000
1 million points should be enough for my example. All of them have both X and Y in range <0, 1000). Now we just need the index:
$ create index q on test using gist ( position );

CREATE INDEX
And we can find some rows close to center of the points cloud:
$ select *, position <-> point(500,500) from test order by position <-> point(500,500) limit 10;

              position               |     ?column?

-------------------------------------+-------------------

 (499.965638387948,499.452529009432) | 0.548548271254899

 (500.473062973469,500.450353138149) |  0.65315122744144

 (500.277776736766,500.743471086025) | 0.793668174518778

 (499.986605718732,500.844359863549) | 0.844466095200968

 (500.858531333506,500.130807515234) | 0.868439207229501

 (500.96702715382,499.853323679417)  | 0.978087654172406

 (500.975443981588,500.170825514942) | 0.990289007195055

 (499.201623722911,499.368405900896) |  1.01799596553335

 (498.899147845805,500.683960970491) |  1.29602394829404

 (498.38217580691,499.178630765527)  |  1.81438764851559

(10 rows)
And how about speed?
$ explain analyze select *, position <-> point(500,500) from test order by position <-> point(500,500) limit 10;

                                                        QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------

 Limit  (cost=0.00..0.77 rows=10 width=16) (actual time=0.164..0.475 rows=10 loops=1)

   ->  Index Scan using q on test  (cost=0.00..76512.60 rows=1000000 width=16) (actual time=0.163..0.473 rows=10 loops=1)

         Order By: ("position" <-> '(500,500)'::point)

 Total runtime: 0.505 ms

(4 rows)

Интересно, что при обходе индекса функции будут возвращаться в порядке близости, поэтому нет необходимости выполнять сортировку (то есть, упорядочивать) для результатов!

Однако, если вы хотите использовать его вместе с PostGIS, теперь это действительно легко. Просто следуйте этим инструкциям .

Соответствующая часть это:

SELECT name, gid
FROM geonames
ORDER BY geom <-> st_setsrid(st_makepoint(-90,40),4326)
LIMIT 10;

Но не верьте мне на слово. Время это сам :)

Раги Язер Бурхум
источник
Это будет хороший ответ. Тем не менее, я использую MySQL MySAM. Я забыл добавить это.
user4951
+1, но я не могу выбрать это как мой ответ. Должен ли я создать еще один вопрос?
user4951
@JimThio MySQL не имеет индекса ближайшего соседа, поэтому вам нужно будет полагаться на PostGIS-подобный подход до того, как будет выполнен запрос ближайшего соседа (ST_Dwithin с ORDER BY ST_Distance). Добро пожаловать обратно в средневековье :)
Раги Язер Бурхум
Так я должен идти в Mongodb? Дай угадаю. Какой смысл иметь пространственный индекс на mysql, если вы не можете даже сделать простейшую вещь, например, найти 20 ближайших точек?
user4951
1
Вы можете найти ближайшую точку, используя окно. То же самое верно для любой другой пространственной базы данных, как описано @lynxlynxlynx. Вы можете продолжать увеличивать окно, умножая его на два. Да, то же самое верно для Монго или любой другой базы данных. Дело в том, что вы сократили большинство других функций. Кроме того, все знают, что до недавнего времени MySQL никогда не был серьезным претендентом на что-то пространственное.
Раги Язер Бурхум
8

С PostGIS 2.0 на PostgreSQL 9.1 вы можете использовать индексированный оператор KNN ближайшего соседа , например:

SELECT *, geom <-> ST_MakePoint(-90, 40) AS distance
FROM table
ORDER BY geom <-> ST_MakePoint(-90, 40)
LIMIT 20 OFFSET 0;

Выше запрос должен в течение нескольких миллисекунд.

В течение следующих кратных 20, изменить до OFFSET 20, OFFSET 40и т.д ...

Майк Т
источник
Могу ли я знать, в чем смысл <->? Спасибо.
Northtree
<->является оператором, который возвращает 2D-расстояние.
Майк Т,
1

MySQL Spatial

Все здесь говорят вам, как сделать это с PostgreSQL, используя KNN, не говоря вам о преимуществах. Используя MySQL, вы не можете определить ближайшего соседа, не рассчитав расстояние для всех соседей. Это очень медленно. С PostgreSQL это можно сделать для индекса. Ни MySQL, ни MariaDB в настоящее время не поддерживают KNN

Эван Кэрролл
источник