como encontrar os 20 pontos mais próximos de forma eficiente [fechado]

9

Digamos que eu queira encontrar as 20 empresas mais próximas perto de mim.

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           

Existem 1,6 milhão de negócios. É claro que é estúpido calcular a distância para todos eles e depois classificá-lo.

É aí que o índice geoespacial entra em ação, certo?

Então, qual SQL Comman eu preciso lançar?

Nota:

  1. Eu estou usando o índice espacial mysql myisam . No entanto, eu não especifiquei isso antes. Por isso, aceitarei aqueles que responderem para mostrar minha gratidão e fazer outra pergunta.
  2. Eu não quero calcular a distância para toda a tabela
  3. Não quero calcular a distância para nenhuma região que ainda seja ineficiente
  4. Eu quero calcular a distância para um número razoável de pontos, porque quero classificar os pontos por distância e poder exibir os pontos 1-20, 21-40, 41-60 etc.
user4951
fonte
3
cruz pós dba.stackexchange.com/questions/19595/... (também parece ruim juju ter uma pergunta em que cada resposta é abordar PostGIS)
Evan Carroll

Respostas:

7

As consultas espaciais são definitivamente a melhor opção.

Com o PostGIS, primeiro tentaria algo simplista como esse e ajustaria o alcance conforme necessário:

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

Isso compararia pontos (na verdade, suas caixas delimitadoras) usando o índice espacial, portanto deve ser rápido. Outra abordagem que vem à mente é armazenar em buffer a sua localização e, em seguida, cruzar esse buffer com os dados originais, o que pode ser ainda mais eficiente.

lynxlynxlynx
fonte
9

Se tudo o que você procura são pesquisas de pontos de proximidade (consultas de vizinhos mais próximos), não será necessário usar os STs antigos ST_DWithin ou ST_Distance + ORDER BY para isso.

Não mais.

Agora que o PostGIS 2.0 foi lançado, você deve usar o suporte ao índice knngist (um recurso nativo do PostgreSQL). Serão ordens de magnitude mais rápidas.

Um trecho desta entrada do blog que descreve como usar o knn gist sem o 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)

Interessante o suficiente, a travessia do índice retornará os recursos em ordem de proximidade, portanto, não é necessário fazer uma classificação (ou seja, ordenar por) para os resultados!

No entanto, se você quiser usá-lo juntamente com o PostGIS, agora é realmente fácil. Basta seguir estas instruções .

A parte relevante é esta:

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

Mas não aceite minha palavra. Time it yourself :)

Ragi Yaser Burhum
fonte
Essa será uma boa resposta. No entanto, estou usando o mysql myisam. Eu esqueço de acrescentar isso.
usar o seguinte comando
Então, +1, mas não posso selecionar isso como minha resposta. Devo criar outra pergunta?
usar o seguinte comando
@ JimThio O MySQL não possui um índice de vizinho mais próximo, portanto você terá que confiar na abordagem semelhante ao PostGIS antes de haver uma consulta de vizinho mais próximo (ST_D dentro de ORDER BY ST_Distance). Volta Bem-vindo à Idade Média :)
Ragi Yaser Burhum
Então eu tenho que ir ao mongodb? Deixe-me adivinhar. Qual é o sentido de ter um índice espacial no mysql se você não consegue fazer a coisa mais simples como encontrar os 20 pontos mais próximos?
usar o seguinte comando
11
Você pode encontrar o ponto mais próximo usando uma janela. O mesmo vale para qualquer outro banco de dados espacial, conforme descrito por @lynxlynxlynx. Você pode continuar aumentando a janela multiplicando-a por dois. Sim, o mesmo vale para o Mongo ou qualquer outro banco de dados. O ponto é que você reduziu a maioria dos outros recursos. Além disso, todo mundo sabe que, até recentemente, o MySQL nunca foi um candidato sério a nada espacial.
Ragi Yaser Burhum
8

Com o PostGIS 2.0 no PostgreSQL 9.1, você pode usar o operador vizinho mais próximo indexado pelo KNN , por exemplo:

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

O acima deve consultar dentro de alguns milissegundos.

Para os próximos múltiplos de 20, modificar a OFFSET 20, OFFSET 40, etc ...

Mike T
fonte
Eu poderia saber qual é o significado <->? Obrigado.
Northtree
<->é um operador que retorna a distância 2D.
Mike T
1

MySQL Spatial

Todo mundo aqui está lhe dizendo como fazer isso com o PostgreSQL usando o KNN, sem lhe dizer as vantagens. Usando o MySQL, você não pode determinar o vizinho mais próximo sem calcular a distância para todos os vizinhos. Isso é extremamente lento. Com o PostgreSQL, isso pode ser feito em um índice. Nem o MySQL nem o MariaDB atualmente suportam o KNN

Evan Carroll
fonte