Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Query for nearby locations

I am using Firebase to store users with their last scanned latitude and longitude.

An entry looks like this:

"Bdhwu37Jdmd28DmenHahd221" : {
  "country_code" : "at",
  "firstname" : "John",
  "gender" : "m",
  "lat" : 11.2549387,
  "lon" : 17.3419559
}

Whenever a user presses a specific "search" button, I want my Firebase function to fetch the people nearest to the person who sent the request.

Since Firebase only allows for querying after one field, I decided to add the country_code, to kind of have some range-restrictions and query for that field. But it is still super slow when I load every user of a specific country and then check for the smallest distance between a given user and all the other users in the same country.

Already with 5 users, the function takes like 40 seconds to achieve the results.

I have also read about compound Indexes, but I would need to somehow combine the latitude and the longitude and query for both fields.

Is there any way to either get a second and third query involved here (e.g. search for the same country_code, and then for a similar longitude and latitude) or do I have to solve this inside my server code ?

like image 303
Thomas Avatar asked Apr 11 '17 23:04

Thomas


1 Answers

The Firebase Database can only query by a single property. So the way to filter on latitude and longitude values is to combine them into a single property. That combined property must retain the filtering traits you want for numeric values, such as the ability to filter for a range.

While this at first may seem impossible, it actually has been done in the form of Geohashes. A few of its traits:

  1. It is a hierarchical spatial data structure which subdivides space into buckets of grid shape

So: Geohashes divide space into a grid of buckets, each bucket identified by a string.

  1. Geohashes offer properties like arbitrary precision and the possibility of gradually removing characters from the end of the code to reduce its size (and gradually lose precision).

The longer the string, the larger the area that the bucket covers

  1. As a consequence of the gradual precision degradation, nearby places will often (but not always) present similar prefixes. The longer a shared prefix is, the closer the two places are.

Strings starting with the same characters are close to each other.

Combining these traits and you can see why these Geohashes are so appealing for use with the Firebase Database: they combine the latitude and longitude of a location into a single string, where strings that are lexicographically close to each other point to locations that are physically close to each other. Magic!

Firebase provides a library called Geofire, which uses Geohashes to implement a Geolocation system on top of its Realtime Database. The library is available for JavaScript, Java and Objective-C/Swift.

To learn more about Geofire, check out:

  • this blog post introducing Geofire 2
  • the demo app that used to show local busses moving on a map app showing SF busses.
    The app doesn't work anymore (the data isn't being updated), but the code is still available.
  • this video and documentation on how to implement geoqueries on Cloud Firestore.
like image 64
Frank van Puffelen Avatar answered Nov 10 '22 23:11

Frank van Puffelen