Comment calculer efficacement Yelp distance dans la base de données?

Question

Par exemple, dire que j'ai une table:

Business(BusinessID, Lattitude, Longitude)

Tous sont bien sûr indexées. En outre il y a 1 million d'enregistrements

dis que je veux trouver des entreprises le plus proche de 106,5, par exemple, comment pourrais-je le faire?

Si je fais

SELECT *
FROM Business
WHERE (Some formula to compute distance here) < 2000

par exemple, ou si je fais

SELECT *
FROM Business
TOP 20

En théorie, l'ordinateur aura à la distance Compute pour tous biz alors qu'en pratique seuls ceux qui ont Lattitude et longitude dans une certaine plage qui doit être calculé.

Alors, comment puis-je faire ce que je veux en Php, ou SQL, par exemple?

Je suis reconnaissant de la réponse à ce jour. J'utilise MySQL et ils n'ont rien de plus efficace que la solution évidente. MySQL spatiale ne pas fonction de distance Compute soit.

Answer 1

Si je comprends bien la question (et je ne suis pas sûr que je fais), vous êtes inquiet au sujet du calcul "(Some formula to compute distance here)" pour chaque ligne de la table chaque fois que vous faites une requête?

Ceci peut être atténué dans une certaine mesure en utilisant les indices sur latitude et longitude donc il suffit de calculer la distance pour une « boîte » de points contenant le cercle que nous voulons réellement:

select * from business
where (latitude>96 and latitude<116) and 
      (longitude>-5 and longitude<15) and 
      (Some formula to compute distance here) < 2000

Si 96, 116, etc. sont choisis pour correspondre à l'unité de la valeur « 2000 » et le point sur le globe vous de calculer les distances.

Comment précisément cette utilisation des index dépend de votre SGBDR et les choix de son planificateur de marques.

En termes généraux, c'est une façon primitive d'optimiser une sorte de recherche du plus proche voisin . Si vos supports SGBDR GiST , comme postgres alors vous devriez envisager de les utiliser à la place.

Answer 2

(Divulgation:. Je suis un gars de Microsoft SQL Server, de sorte que mes réponses sont influencées par cela)

Pour faire vraiment efficace, il y a deux choses que vous voulez: la mise en cache et le support de données spatiales natif. données spatiales prennent en charge vous permet de stocker des données de la géographie et la géométrie directement dans la base de données sans faire des calculs intensifs / coûteux à la volée, et vous permet de créer des index très rapidement trouver le point le plus proche de votre position actuelle (ou la plus efficace itinéraire ou autre).

est important si Caching vous voulez à l'échelle, période. La requête la plus rapide est celui que vous ne faites jamais. Chaque fois qu'un utilisateur demande les choses les plus proches de lui, vous stockez son emplacement et le jeu de résultats dans un cache comme Redis ou memcached pendant une période d'heures. Places d'affaires ne vont pas changer pour 4 heures -. Eh bien, ils pourraient si quelqu'un édite une entreprise, mais vous n'avez pas nécessairement besoin que d'être immédiatement mis à jour dans tous les jeux de résultats

Answer 3

Yelp utilisations probables SIG

PostgreSQL a la mise en œuvre de référence pour les SIG avec PostGIS . Yelp peuvent utiliser MySQL qui est inférieur dans tous les sens . Dans le cas de quelque chose comme Yelp, ils gardent presque certainement les coordonnées pour,

• L'utilisateur
• Les destinations possibles

Ces coordonnées sont presque certainement WGS84, et stocké en tant que type Géographie. Dans PostgreSQL et PostGIS il ressemblerait à quelque chose comme ça,

CREATE TABLE businesses (
  id   int               GENERATED BY DEFAULT AS IDENTITY PRIMARY KEY,
  name text,
  geog geography(point)
);
CREATE INDEX ON businesses USING gist(geog);
.... fill table
ANALYZE businesses;

Ils rempliraient cette table. Ensuite, ils saisissent les coordonnées WGS84 de votre téléphone et de générer une requête, comme celui-ci avec SQL Alchemy (dans le cas de Yelp),

SELECT *
FROM businesses AS b
WHERE ST_DWithin( b.geog, ST_MakePoint(userLong,userLat) );

Pour plus d'informations, consultez notre spatiale , et consultez systèmes d'information géographique @ StackExchange