Поиск ближайших пользователей без перебора многих записей

Question

Когда пользователи входят в мое приложение, я хочу, чтобы они могли видеть количество пользователей в пределах выбранного радиуса.Я планировал начать сохранять координаты в моей базе данных и проходить по каждой записи (~ 50 000), запустив userCoordinates.distance (from: databaseCoordinateValue).Однако во время тестирования я обнаружил, что этот процесс занимает много времени и не является масштабируемым решением.Есть ли у вас какие-либо советы о том, как быстро запрашивать элементы базы данных в пределах определенного радиуса?

Я использую:

• Swift 4
• Firebase (бета-версия Firestore)
• Xcode 10

Пример структуры базы данных и способа хранения данных

 database.collection("users").document((Auth.auth().currentUser?.uid)!).setData([
                "available_tags" : ["milk", "honey"]]) { err in
                if let err = err {
                    print("Error adding document: \(err)")
                }
             }

Answer 1

Взгляните на геометрию s2 - http://s2geometry.io/. Основная концепция заключается в том, что вы кодируете каждое местоположение на Земле как 64-битное #, причем местоположения, близкие друг к другу, являются близкими #.Затем вы можете искать местоположения на расстоянии х, находя что-нибудь +/- определенного # от местоположения.Теперь фактическая реализация немного сложнее, поэтому вам в конечном итоге потребуется создать несколько «ячеек», т.е.мин и макс # на диапазон.Затем вы делаете поиск для каждой ячейки.(Более подробную информацию можно получить по адресу http://s2geometry.io/devguide/examples/coverings.)

. Вот пример этого в файле node.js / javascript. Я использую это в бэкэнде, а внешний интерфейс просто проходит в регионе / области.

    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 есть много способов найти закрывающие ячейки (то есть, для какой области вы хотите искать значения), поэтому определенно стоит взглянуть на API и найти правильное соответствие для вашего варианта использования.