ユーザーの地理座標を指定して、2 人のユーザーがまったく同じ場所にいるかどうかをリアルタイムで検出できるサービスを実装したいと考えています。
これをリアルタイムでスケーリングするには、Redis のような分散インメモリ データストアを使用する必要があるようです。ジオハッシュを使用して調査しましたが、問題は、互いに近いポイントが常に同じハッシュプレフィックスを共有するとは限らないことです。また、2 人のユーザーが隣り合って立っている場所が十分に近いかどうかを調べることに関心があるため、ジオハッシュはやり過ぎかもしれません。
もちろん、簡単な解決策は、地理座標のペアが互いにわずかな距離内にあるかどうかをテストすることです。しかし、AFAIK、Redis、およびその他のメモリ内データストアには、そのような検索をサポートするための地理空間インデックスがありません。
これを実装するための最良の方法は何ですか?
この機能はRedis 3.2+に組み込まれています。
しかし、古いバージョンの場合、問題は依然として存在します。私は Yin Qiwen の回答を参考にして Node 用のモジュールを作成しました。コードを調べると、それがどのように Redis を使用しているかがわかります。彼の指示は完璧で、素晴らしい結果を得るために従うことができました. https://github.com/arjunmehta/node-georedis
基本的に、ネイティブ コマンドに使用されるのと同じアルゴリズムです。
これは非常に高速で、あらゆる種類の交差/haversine タイプの操作を回避します。Yin Qiwen の方法の最もクールな点 (私が思うに) は、アルゴリズムの最も計算量の多い部分をクライアントに分散できることです (すべてを DB またはサーバーで行うのではなく)。
100% 正確ではなく、事前に構成された距離ステップを使用しますが、ほとんどのアプリケーションでは、私が想像する正確な精度は必要ありません。
また、 GIS stack exchangeでの Yin Qiwen の記事を言い換えました。
いろいろ絡んですみません。:P
一般に、これは GeoHash と Redis のソート済みセットによって実行できます。redis で空間インデックス サービスを実装する方法について説明する前に、私が書いた設計があります。
これがあなたの質問に答えていないことは理解しています...しかし、それが正しいツールだとは思いません。
PostgreSQL + PostGIS は非常にうまく機能します。PostgreSQL は、メモリに収まる限り多くのデータベースを実行するように構成できます。
PostGIS は (私が思うに) rtree インデックスを使用するため、興味のある種類のルックアップを実行するのは非常に高速です。
Websocket リクエストを起動するバックエンドを使用すると、ほぼリアルタイムで実行できます。バックエンドが人の GPS 座標を受信するときはいつでも。空間ルックアップを実行します。WebSocket を介して該当するクライアントに通知します。
このスレッドの他の回答で言及されている Redis 地理版は、バージョン 3.2 以降、 Redis に統合されています (この以前のコメントも参照してください)。
ここで新しいコマンドを見つけることができます (今のところベータ版):
Tarantool データベースは、データをメモリに保持し、それらをトランザクション ログとしてディスクにプッシュし、RTree タイプの空間インデックス (2 次元だけでなく) と、そのようなインデックスに対する多数の適切な操作 (包含、オーバーラップ、距離) を備えています。
私は商用プロジェクトで、3D 空間でオブジェクトを記述するレコードを保存およびクエリするために使用しています。
http://tarantool.org/doc/book/box/box_index.html
https://github.com/tarantool/tarantool/wiki/R-tree-index-quick-start-and-usage
標準のクライアントと例は Lua にありますが、データベース作成者によって開発された他のクライアントがいくつかあります。私は Scala アプリケーションで Java クライアントを使用して成功しています。
データベースも非常に高速です。他のデータベースとの科学的な比較を次に示します (空間データベースであるという側面は別として): http://airccse.org/journal/ijdms/papers/6314ijdms01.pdf