問題タブ [geohashing]

私のアプリケーションでは、すべてのユーザーのジオハッシュをテーブルに保存しており、それらのジオハッシュを使用してユーザーの隣人を見つけたいと考えています。

WikiでGeohashについて収集した情報によると：

データベースで使用する場合、geohashed データの構造には 2 つの利点があります。まず、geohash によってインデックス付けされたデータには、連続したスライス内の特定の長方形領域のすべてのポイントが含まれます (スライスの数は、必要な精度と geohash の「断層線」の存在によって異なります)。これは、単一インデックスに対するクエリが複数インデックス クエリよりもはるかに簡単または高速なデータベース システムで特に役立ちます。第 2 に、このインデックス構造は、迅速で汚れた近接検索に使用できます。最も近いポイントは、多くの場合、最も近いジオハッシュの中にあります。

たとえば、「sj8101b085」の隣人を見つけるために、次のようにしてハッシュを検索することを計画していました。

次に、ハッシュ長を 1 つずつ減らして同じクエリを実行します。つまり、「sj8101b08%」、「sj8101b0%」など、必要な数のネイバーが得られるまで続けます。これだけでいいのだという印象を受けました。

しかし、同じ記事の最後で参照されているこの C ライブラリlibgeohashを見つけました。ライブラリには、GEOHASH_get_adjacent指定されたハッシュの隣接ハッシュを提供するという関数があります。geohash 文字列は、地球上の長方形の領域を表します。この関数は、隣接する長方形を表すジオハッシュを返します。これは、必要な数のネイバーを取得するまで、この関数を再帰的に実行する必要があることを意味します (ネイバー、次にネイバーのネイバーなど)。

検索アルゴリズムをどのように記述すればよいのでしょうか。最初のアプローチを使用するか、2番目のアプローチを使用しますか?

ロケーションベースの「チャット」アプリケーションを構築しており、Amazon の DynamoDB を使用して高スループットと自動スケーリングを利用しています。

アプリケーションは、データベース内のユーザーの場所を頻繁に更新します (私は PHP geohash ライブラリを使用しています)。また、特定の地理的半径内のユーザーも検索します。

私は NoSQL を初めて使用します (MySQL の経験が豊富です)。「Users」テーブルのモデリングについて意見を求めています。2 つの懸念事項:

1) ユーザーのジオハッシュ/経度/緯度属性が頻繁に更新される場合、DynamoDB で問題 (テーブル ロック?) が発生しますか? MySQL では、Users テーブル全体がロックされないように、これらの値だけを格納する別のテーブルを作成します。DynamoDB でそれについて心配する必要はありますか?

2) 地理的な半径でユーザーを検索していますか? これは、geohash 属性にグローバル セカンダリ インデックスを設定し、それに対してクエリを実行しているだけですか? シャーディングはこれに問題を引き起こしますか?

私は現在、GeoJSON ポリゴンに正常に変換されたジオポイント + 半径の組み合わせを使用しています (精度が少し失われています)。私が今必要としているのは、所定の精度でその領域と交差するすべての Geohash のリストへの変換です。

私が望んでいることを正確に行うgeohash-polyを見つけましたが、それは ruby​​ ではなく javascript/node-js にあります。

そこにルビーに相当するものはありますか? ありがとう

2 つのテーブルがt1あり、t2(t1のサイズは の 1/10 ですt2)。各テーブルには<Lat, Long>、いくつかのポイントの緯度と経度を含む 2 つの列があります。の各行について、それに最も近いt1行を見つけたいと思います。t2これを行うための最も効率的なクエリは何ですか? Hive には地理空間検索用のライブラリがありますか?

geo_point タイプのフィールドが入力された約 3300 のドキュメントがあります。ドキュメントをタイル マップで視覚化しようとすると、kibana で「結果が見つかりません」と表示されます。

私はすでに座標を次のように配置しようとしました：-文字列のジオハッシュ-[lon、lat]配列-「lat」および「lon」プロパティを持つオブジェクト-文字列「lat、lon」

geo_point を設定するこれらすべての方法は、ES docsに従って許可されています。Kibana はこのフィールドを geo_point (フィールド名の近くに地球のアイコンがあります) として検出しますが、タイル マップには何も表示されません。

私がどうかしましたか、まずいことでもありましたか？

Kibana 4.2、elasticsearch 2.0.0 を使用しています

約50万ポリゴンの交差するジオハッシュ（精度の長さ6まで）を見つけようとしています。すべてのポリゴンについて、そのポリゴン内のすべてのジオハッシュ (精度の長さ 6 まで) を見つけてインデックスを作成する必要があります。postgis st_geohash と st_intersect を使用してから redis に保存しようとしましたが、私のユースケースでは非常に遅いです。50 万ポリゴンのジオハッシュを 10 分でインデックス化する必要があります。

luceneを使用してそれが可能であることを読みました。「ポリゴンの地理空間インデックス」を検索してみましたが、適切なリンクが見つかりませんでした。私は弾性検索と lucene の初心者です。

親切に、それを行う方法を教えてください。または、正しい方向に向けてください。

よろしく、

問題に関して私が抱えている問題の解決策を見つけるために、誰かが私を正しい方向に導いてくれれば幸いです.

精度 4 で地球の可能なすべてのジオ ハッシュを生成する必要があります。これは、位置データベースのデータを分割するルックアップ テーブルを作成できるようにするためです。

geo ハッシュの最初の 4 つのプレフィックスに基づいてデータベースをシャーディングする予定です。Redis には、geo ハッシュ プレフィックスとそれぞれのシャード IP を持つキー ストアがあります。

ハッシュを生成して隣人を見つけるライブラリがありますが、PHP で特定の精度のすべての可能なハッシュのリストを生成するにはどうすればよいですか?

geo ハッシュ ライブラリを使用してすべての隣人を再帰し、リストを生成する方法はありますか? 私はその論理を理解することができません。

前もって感謝します。

UPDATE 07-​​11-0215: これは私がこれまでに持っているものです...

geohash.php は次のとおりです。Chris Veness によって js コードから PHP に移植されました。

問題は、30504 要素の配列を生成することですが、geohash の精度が 3 の場合、合計で 256 (水平方向のハッシュ) * 128 (垂直方向のハッシュ) = 32768 ハッシュになるはずです。

どこが間違っているのかわかりませんか？

ある種の位置情報ベースの機能を提供するモバイル アプリケーションに使用する Node.js を利用した RESTful Web サービスを作成する予定です。最も基本的な使用例は次のようになります。

• ユーザーは、リソースの名前とユーザーの現在の場所 (緯度と経度) を含む要求を Web サービスに送信することで、リソースを作成できます。
• Web サービスは、このリソースに関するメタデータをある種のコレクションに内部的に保存します。
• ユーザーは、現在の場所から 5 km 以内にあるリソースのリストを Web サービスに照会できます。

私の頭に浮かんだ最初の問題の 1 つは、スケーラビリティでした。将来のある時点で、サーバーが 100 万個のリソースのメタデータを保持するとします。ユーザーが近くの結果を照会する場合、距離を計算するために 100 万のエントリをループすると、永遠に時間がかかります。

世の中には同じ流れのサービスがたくさんあるので、このようなものを実装するのにそれほど時間はかからないと思いました。私は間違っていたかもしれません。

私は現在、実証済みの方法とアルゴリズムの研究に 2 日間取り組んでいます。今では、QuadTrees、Geohases、空間インデックスをサポートするデータベース、数式などについて手に入れることができるすべてのものを読んでいます。ただし、すべてがどのように機能するかの全体像はまだ把握できていません。

似たようなことに取り組んだことがある人が、このユースケースと私が使用する予定のテクノロジーを考慮して、どのアプローチが最も適しているかについての洞察を共有できることを望んでいました. また、それを実装する方法の簡単な説明は、私を大いに助けてくれます!

36,742 ポイントの入力があります。これは、距離行列の下三角を (ビンセンティ近似を使用して) 計算したい場合、36,742*36,741*0.5 = 1,349,974,563 距離を生成する必要があることを意味します。

50km以内のペアの組み合わせをキープしたいです。私の現在のセットアップは次のとおりです

これには明らかに何時間もかかります。私が考えていたいくつかの可能性：

• numpy を使用して、ループするのではなく、これらの計算をベクトル化します
• ある種のハッシングを使用して簡単な大まかなカットオフ (100 km 以内のすべての店舗) を取得し、それらの店舗間の正確な距離のみを計算します。
• ポイントをリストに保存する代わりに、四分木のようなものを使用しますが、実際の距離ではなく、近いポイントのランキングにのみ役立つと思います->だから、ある種のジオデータベースを推測します
• 私は明らかにハバーシンまたはプロジェクトを試してユークリッド距離を使用できますが、可能な限り最も正確な測定値を使用することに興味があります
• 並列処理を利用します（ただし、関連するすべてのペアを取得するためにリストを切り取る方法を考え出すのに少し苦労しました）。

編集：ここではジオハッシュが間違いなく必要だと思います-例：

ただし、geo-hash によって返された店舗の距離計算を (ループするのではなく) ベクトル化したいと考えています。

Edit2: Pouria Hadjibagheri - ラムダとマップを使ってみました:

そして、それらはすべて約61 秒でした (店舗数を 32,000 から 2000 に制限しました)。地図の使い方が間違っていたのでしょうか。

私は2つのポリゴンを持っています。"Polygon 1:" は (緯度、経度) 度で表されます。もう 1 つの "Polygon 2:" は、ジオハッシュでエンコードされたセル ID を使用して表現されます。私の特定のケースでは、精度 = 5 と仮定しています。ポリゴン 1 とポリゴン 2 が交差するかどうかを知りたいですか?

たとえば、緯度と経度 (度単位) のポリゴン (ポリゴン 1) が次の場合:(77.164230,33.187725|77.164188,33.188013|77.164066,33.188336|77.164457,33.188676|77.164685,33.188861|77.165012,33.189296|77.165467,33.188591|77.165490,33.188213|77.165085,33.188057|77.164811,33.187902|77.164230,33.187725)

ここで、77.164230 度は緯度、33.188013 度は経度です。次に、ジオハッシュでエンコードされたポリゴン「utxwg」(ポリゴン 2) がポリゴン 1 と交差するかどうかを調べたいですか? 交差点が存在するかどうかを調べるために使用できるアルゴリズムはありますか?