0

When users log in to my app, I want them to be able to see the number of users within a selected radius. I was planning to start storing coordinates in my database and looping through each record (~50,000), running userCoordinates.distance(from: databaseCoordinateValue). However, during testing, I've found that this process takes a long time and is not a scalable solution. Do you have any advice on how to quickly query database items within a defined radius?

I am using:

  • Swift 4
  • Firebase (Firestore beta)
  • Xcode 10

Example of database structure and how data gets stored

 database.collection("users").document((Auth.auth().currentUser?.uid)!).setData([
                "available_tags" : ["milk", "honey"]]) { err in
                if let err = err {
                    print("Error adding document: \(err)")
                }
             }
  • Are you familiar with [Geofire](https://github.com/firebase/geofire-objc)? More info in [this other SO answer](https://stackoverflow.com/a/43358909/1032372). – shim Oct 11 '18 at 14:24

1 Answers1

7

Take a look at s2 geometry - http://s2geometry.io/. The basic concept is you encode each location on earth as a 64 bit # with locations close to each other being close #'s. Then, you can look up locations within x distance by finding anything that is +/- a certain # from the location. Now, the actual implementation is a bit more complicated, so you end up needing to creating multiple 'cells' ie. a min and max # on the range. Then, you do lookups for each cell. (More info at http://s2geometry.io/devguide/examples/coverings.)

Here's an example of doing this in node.js / javascript. I use this in the backend and have the frontend just pass in the region/area.

    const S2 = require("node-s2");

    static async getUsersInRegion(region) {
    // create a region
    const s2RegionRect = new S2.S2LatLngRect(
      new S2.S2LatLng(region.NECorner.latitude, region.NECorner.longitude),
      new S2.S2LatLng(region.SWCorner.latitude, region.SWCorner.longitude),
    );

    // find the cell that will cover the requested region
    const coveringCells = S2.getCoverSync(s2RegionRect, { max_cells: 4 });

    // query all the users in each covering region/range simultaneously/in parallel
    const coveringCellQueriesPromies = coveringCells.map(coveringCell => {
      const cellMaxID = coveringCell
        .id()
        .rangeMax()
        .id();
      const cellMinID = coveringCell
        .id()
        .rangeMin()
        .id();

      return firestore
        .collection("User")
        .where("geoHash", "<=", cellMaxID)
        .where("geoHash", ">=", cellMinID).
        get();
    });

    // wait for all the queries to return
    const userQueriesResult = await Promise.all(coveringCellQueriesPromies);

    // create a set of users in the region
    const users = [];

    // iterate through each cell and each user in it to find those in the range
    userQueriesResult.forEach(userInCoveringCellQueryResult => {
      userInCoveringCellQueryResult.forEach(userResult => {
        // create a cell id from the has
        const user = userResult.data();
        const s2CellId = new S2.S2CellId(user.geoHash.toString());
        // validate that the user is in the view region
        // since cells will have areas outside of the input region
        if (s2RegionRect.contains(s2CellId.toLatLng())) {
          user.id = userResult.id;
          users.push(user);
        }
      });
    });

    return users;
  }

S2 geometry has a lot of ways to find the covering cells (i.e. what area you want to look up values for), so it's definitely worth looking at the API and finding the right match for your use case.

R. Wright
  • 960
  • 5
  • 9