Our technology can perform millions of nearest road distance neighbor queries on a road network. People often counter our claim by telling us that “Google Maps already does this!”. The short answer, is: No, Google does not do it! In this post, we dissect what Google Maps can and cannot do when it comes to finding the nearest object to a query point. You may be surprised to learn that Google Maps uses crow-flying distance (i.e., it assumes that you can fly over buildings and lakes). What is even worse is that Google Maps quietly buries this rather obvious deficiency in their service.
Why is this a big deal? Imagine that you are driving and want to look for gas stations. Don’t you want to know which is the closest one? The fundamental operation in location-based services involves proximity determination. And, when you are using Google Maps on your phone, correct ordering of query results is very important. If you still don’t believe me, take out your phone and start a Google Maps App. Search for “Gas Station”. Do you see an option to sort by distance on your Google Maps App? We are using Google Maps 9.12.1 and we do not find that option!
If you are wonderiing why Google would miss providing a capability as fundamental as proximity search, the only answer that we think of is that it is because it is HARD! Computing nearest neighbors in a road network at scale is very challenging without a technology like ours. Here is our take down of local search with Google Maps. The screenshot below represents the result of a simple query to find the Moroccan restaurants near Broadway and Grand Streets in Bayonne, NJ circa 2010
Google Maps (Circa 2010. As an aside, W Grant St no longer exists in Bayonne, NJ in Google Maps). The red boxes are the distance labels provided by Google Maps for each of the restaurants that it retrieved which is clearly the crow-flying distance. The white boxes are the actual road network distances that we computed for each of the resultin restaurants. The green boxes correspond to the actual order of the restaurants when we sorted them by the road network distance. As you can easily see, the order is off.
Until recently. Google Maps used to look like the above screenshot. One could search for the nearest restaurants near an address. In this case, we searched for “Moroccan restaurants” from an address in Bayonne, NJ which is a small city that lies across the Hudson river, a stone throw distance away from NYC. The Google Maps search would provide a result where its constituent objects are ordered by the crow-flying distance from the query location. The earlier version of Google Maps was explicit (using the direction labels NE, E, SE etc.) in admitting that the restaurants were sorted by the crow-flying distance. The red boxes are the distance values as displayed by Google (which we zoomed in and enlarged so that one can read them clearly) . It is not surprising that ordering the restaurants by the crow-flying l distance provides an incorrect ordering when we found their actual network distances and reordered them. In the screenshot above, we annotate each restaurant by its real position in the ordering in terms its actual road network distance using the white boxes, and its position in this ordering using the green boxes. We can see that the discrepancy between using the different distances is really high. For example, (A is the closest using a crow-flying distance ordering while it is 5th in the road network ordering.
Recently, Google maps became a bit “sneaky” about how they order the restaurants. We say sneaky because they go to great lengths to hide the fact that they do not (cannot do) real road distance ordering. You might ask why? Of course, it is expensive to calculate so many distance values. First they dropped the sort-by-distance feature from the user interface (UI). Presently, you can order the restaurants by their rating as well as by which ones are still open. As of June 8th, 2016, the UI looks as like this.You should also try this query on the Google Maps App that runs on your smartphone.
While the option to sort restaurants by distance disappeared from the UI, the Google Place API still has this option. We found it rather strange that distance is a less important measure than price, rating, and hours open. Here is the relevant section corresponding to sorting results by distance. https://developers.google.com/places/web-service/search#PlaceSearchRequests . Note that the description is vague in terms of what kind of distance is.used. Is it crow-flying or or is it actual road network distance?
rankby— Specifies the order in which results are listed. Possible values are:
prominence(default). This option sorts results based on their importance. Ranking will favor prominent places within the specified area. Prominence can be affected by a place’s ranking in Google’s index, global popularity, and other factors.distance. This option biases search results in ascending order by their distance from the specifiedlocation. Whendistanceis specified, one or more ofkeyword,name, ortypeis required.
We thought that maybe if we looked at the API result, it would shed more light on this matter. Hence we used the API function to obtain the nearest neighbor using the following command:
wget ‘https://maps.googleapis.com/maps/api/place/nearbysearch/json?location=40.745554,-74.024788&type=restaurant&name=Moroccan&rankby=distance&key=API_KEY‘ -O – > moroccan.txt
The result of this query is a JSON object and and the attributes of the first result are given below. One item worhty of noting here is that the distance field is conveniently missing so there is no way to really tell how the restaurants are ordered! In other words, Google gives the result as an ordered set of restaurants but they dol not tell us what is the distance to the restaurant. How strange and WHY?
{
"geometry" : {
"location" : {
"lat" : 40.7382731,
"lng" : -74.0094302
}
},
"icon" : "https://maps.gstatic.com/mapfiles/place_api/icons/restaurant-71.png",
"id" : "2101251f9292829b759665d48357b41f929daabb",
"name" : "Cafe Gitane",
"opening_hours" : {
"open_now" : true,
"weekday_text" : []
},
"photos" : [
{
"height" : 3024,
"html_attributions" : [
"\u003ca href=\"https://maps.google.com/maps/contrib/108258590706343440244/photos\"\u003eEnrico Zanardo\u003c/a\u003e"
],
"photo_reference" : "CoQBdwAAABnNJSzjdBdNz5MLXV3gszFAmRr5f1LckNgtPkl5vjO8vL5E0hbvnNXrAexdecYmfjkYboawO-m4fv9tp9LWrbkKT8_RBKFp8cnosLM1A1EB-Zghpi5E8Tcf1qSKoV20bWQPbnQTI13UXvi5WrAenMWzE5_Mx3fShT0WcHwnQdoREhDTXOvArQC2uUoH1BrFuA8GGhRKfpGuPJJ1D8F7bACVfIFvcy2dXw",
"width" : 4032
}
],
"place_id" : "ChIJ7eAGYupZwokRzdxbaFHhXJM",
"price_level" : 2,
"rating" : 4.2,
"reference" : "CmRfAAAAyrYukNSqOB98TSfaRxrKGsdLht8horRYBUJrn7_BORQ-PoN9LXidlWGRqj3Eid4CqlNkX-vFUrzj3Xf8zgwAaEjWgkPsXhsEKQjPUYE8HEi_NVMvRvtHCVUpHcmLVkuEEhBkSnbEJeG2rnba9nJVY_G1GhTQveenlP24MwmVtPMQTAjeSyjHxA",
"scope" : "GOOGLE",
"types" : [ "cafe", "restaurant", "food", "point_of_interest", "establishment" ],
"vicinity" : "113 Jane Street, New York"
},
We are now in a real dilemma. Looking at the output we have no idea what ordering Google used since they don’t provide a distance field. How can we prove or disprove anything now by simply looking at the output? To give you an idea, can we look at the result and deduce what ordering they use? We started with two candidates sort orders that we could think of, actual road network distance (as computed by Google) and crow-flying distance (computed with a standard closed form equation using the query point and the restaurant location). To examine what ordering Google used, we deployed the following methodology.
- Make a query for Moroccan restaurants from a random query point near and around Jersey City, NJ
- Obtain the nearest restaurants using the Google API, using the rankby distance feature
- For each neighbor obtain the actual network distance from Google Maps and compute the crow-flying distance
- Check if the result is a monotonically increasing ordering of the restaurants by their road network distances
- Or check if the result is an ordering of the restaurants by their crow-flying distances.
We made 100 random queries around Jersey City, NJ. Here are some results.
- All 100 results were found to be sorted by the crow-flying distance. We are now confident that Google Maps indeed uses crow-flying distance.
- Only 12 of these 100 were sorted by the actual road network distance, while 88 of the results did not conform to the road network distance. In other words, there was a result i and i+1 such the road network distance of i+1 was less than that of i. The 12 queries that provided correct road network distance ordering simply corresponded to the cases where the crow-flying distance ordering was the same as the road network distance ordering.
Our analysis has shown without any doubt that Google Maps search does not use actual road network distance. Instead it simply provides a crow-flying distance ordering. However, there are now more unanswered questions than answers.
- Why is Google not able to provide the actual road network distance result but resorts to crow-flying distance? A company with Google’s resources should be able to provide road network distance or trip time. Are you not surprised by that? One would expect that they would even take current traffic into account.
- Why does this feel like Google Maps is silently pushing this whole deficiency under the rug here? Why not be more forthright about what sort ordering they use?
So there you have it. Google does not give you restaurants sorted by road network distance.
The code for running the test is here
#! /usr/bin/perl
use Geo::Distance::Google;
use JSON::XS;
use Data::Dumper qw/Dumper/;
my $geo = Geo::Distance::Google->new;
# Start somewhere in Jersey City, NJ
my $lat = 40.745554;
my $lon = -74.024788;
my $num_tests = 100;
my $key = "YOUR_API_KEY_GOES_HERE";
my $tot_roads = 0;
my $tot_spatial = 0;
my $pi = atan2(1,1) * 4;
# Do a num_tests rounds and check if the crow-flying or road distance ordering holds?
for (my $i = 0; $i < $num_tests; ++$i) {
my $road_failed = 0;
my $spatial_failed = 0;
# Jiggle the point a bit and try the query
my $sign_lat = 1;
$sign_lat = -1 if (rand() < 0.5);
my $sign_lon = 1;
$sign_lon = -1 if (rand() < 0.5); $lat += $sign_lat * rand() / 30; $lon += $sign_lon * rand() / 30; # Easier than using a API.. my $text = `wget "https://maps.googleapis.com/maps/api/place/nearbysearch/json?location=$lat,$lon&type=restaurant&name=Moroccan&rankby=distance&key=$key" -O -`; my $json = JSON::XS->new->decode($text) or die $!;
# print Dumper($json);
my $count = 0;
my $road_dist = undef;
my $spatial_dist = undef;
my $oroad_dist;
my $ospatial_dist;
# Process the JSON output
foreach my $result (@{$json->{results}}) {
$count++;
my $rest_lat = $result->{geometry}->{location}->{lat};
my $rest_lon = $result->{geometry}->{location}->{lng};
my $distance = $geo->distance(
origins => "$lat, $lon",
destinations => "$rest_lat, $rest_lon",
);
my $road_dist = $distance->[0]->{destinations}->[0]->{distance}->{text};
my $spatial_dist = distance($lat, $lon, $rest_lat, $rest_lon, "K");
# See if the result follows a monotically increasing order of network distance
if ($count > 1 && $oroad_dist > $road_dist) {
$road_failed = 1;
}
# See if the result follows a monotically increasing order of crow-flying distance
if ($count > 1 && $ospatial_dist > $spatial_dist) {
$spatial_failed = 1;
}
$oroad_dist = $road_dist;
$ospatial_dist = $spatial_dist;
# Print out all the details of the restaurants and the two distances
print $count, " ", $rest_lat, " ", $rest_lon, " ", $road_dist, " ", $spatial_dist."KM", "\n";
}
print "Did Road Ordering Fail? ", $road_failed, "\n";
print "Did Crow-flying ordering Fail?", $spatial_failed, "\n";
$tot_roads += $road_failed;
$tot_spatial += $spatial_failed;
}
print "Total Tests = ", $num_tests, "\n";
print "Total Roads failed = ", $tot_roads, "\n";
print "Total Spatial failed = ", $tot_spatial, "\n";
# Here is a bit of code borrowed from the following website to compute
# crow-flying distance.
#:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
#::: :::
#::: This routine calculates the distance between two points (given the :::
#::: latitude/longitude of those points). It is being used to calculate :::
#::: the distance between two locations using GeoDataSource(TM) products :::
#::: :::
#::: Definitions: :::
#::: South latitudes are negative, east longitudes are positive :::
#::: :::
#::: Passed to function: :::
#::: lat1, lon1 = Latitude and Longitude of point 1 (in decimal degrees) :::
#::: lat2, lon2 = Latitude and Longitude of point 2 (in decimal degrees) :::
#::: unit = the unit you desire for results :::
#::: where: 'M' is statute miles (default) :::
#::: 'K' is kilometers :::
#::: 'N' is nautical miles :::
#::: :::
#::: Worldwide cities and other features databases with latitude longitude :::
#::: are available at http://www.geodatasource.com :::
#::: :::
#::: For enquiries, please contact sales@geodatasource.com :::
#::: :::
#::: Official Web site: http://www.geodatasource.com :::
#::: :::
#::: GeoDataSource.com (C) All Rights Reserved 2015 :::
#::: :::
#:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
sub distance {
my ($lat1, $lon1, $lat2, $lon2, $unit) = @_;
my $theta = $lon1 - $lon2;
my $dist = sin(deg2rad($lat1)) * sin(deg2rad($lat2)) + cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * cos(deg2rad($theta));
$dist = acos($dist);
$dist = rad2deg($dist);
$dist = $dist * 60 * 1.1515;
if ($unit eq "K") {
$dist = $dist * 1.609344;
} elsif ($unit eq "N") {
$dist = $dist * 0.8684;
}
return ($dist);
}
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
#::: This function get the arccos function using arctan function :::
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
sub acos {
my ($rad) = @_;
my $ret = atan2(sqrt(1 - $rad**2), $rad);
return $ret;
}
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
#::: This function converts decimal degrees to radians :::
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
sub deg2rad {
my ($deg) = @_;
return ($deg * $pi / 180);
}
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
#::: This function converts radians to decimal degrees :::
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
sub rad2deg {
my ($rad) = @_;
return ($rad * 180 / $pi);
}
Roads Inside Any Database 