問題タブ [hilbert-curve]

自然言語文字列の膨大な (ただし有限の) セットがあります。

各文字列を数値に変換する方法が必要です。どの文字列でも、値は毎回同じでなければなりません。

指定された 2 つの文字列が「異なる」ほど、対応する 2 つの値も異なるはずです。それらが「似ている」ほど、値の違いは少なくなります。

必要な文字列間の違いの正確な定義はまだわかりません。とにかく自然言語の解析はありません。おそらく、Levenstein のようなものである必要があります (ただし、Levenstein は相対的であり、絶対メトリックが必要です)。簡単なことから始めましょう。

寸法の更新

単一の数値ではなく、多次元 (3 次元が最適) のベクトルで解決できれば幸いです。

期待される結果の正確さに関する更新

こことここで正しく指摘されているように、ある文字列から別の文字列までの距離はMAX(firstStringLength, secondStringLength)次元を持つベクトルです。一般に、情報の損失なしに次元数を減らすことはできません。

ただし、絶対的な解決策は必要ありません。N 次元の文字列空間から 3D 空間への「十分な」変換で解決します。

また、有限の長さの有限数の文字列があることにも注意してください。(ただし、文字列の数はかなり多く、約 8000 万 (10 GB) であるため、シングルパスのステートレス アルゴリズムを選択することをお勧めします。)

参考文献をスキャンしたところ、ヒルベルトの空間充填曲線がここで役立つ可能性があるという印象を受けました。Hilbert Space-Filling Curve 記事のクラスタリング プロパティの分析のように見えますが、私の問題に近いものについて説明しています...

ヒルベルト曲線アプローチの更新

1. 各文字列を N 次元空間のポイントにマップします。ここで、N はセット内の文字列の最大長です。ところで、文字列の i 番目の文字コードを i 番目の座標値として使用できますか?
2. その N 次元空間を通るヒルベルト曲線をプロットします。
3. 文字列ごとに、文字列の座標に最も近い曲線上のポイントを取得します。その点のヒルベルト値 (曲線の始点からの長さ) が、私が求める 1 次元の値です。
4. 3D 値が必要な場合は、ヒルベルト曲線を 3D でプロットし、上で計算したヒルベルト値に一致する点を選択します。

これは正しく見えますか？ここでの計算費用はいくらになるでしょうか。

N次元のポイントの膨大なセットがあります（数千万、Nは100に近い）。

空間的な局所性を維持しながら、これらの点を 1 つの次元にマッピングする必要があります。ヒルベルトの空間充填曲線を使用してそれを行いたいです。

各点について、曲線上の最も近い点を選びたいと思います。点のヒルベルト値 (曲線の始点から選択した点までの曲線の長さ) は、私が求める単一次元の値です。

計算は即時である必要はありませんが、まともな最新の家庭用 PC ハードウェアでは数時間以内で済むと思います。

実装に関する提案はありますか？私を助けるライブラリはありますか？（言語はあまり関係ありません。）

一連のヒルベルト値 (ヒルベルト曲線の開始点から指定された点までの長さ) があります。

これらの値を 3D ポイントに変換する最良の方法は何ですか? 元のヒルベルト曲線は 3D ではなかったので、必要なヒルベルト曲線ランクを自分で選択する必要があると思います。ただし、カーブの全長 (つまり、セット内の最大値) はあります。

おそらく既存の実装がありますか？ヒルベルト曲線/値を操作できるライブラリはありますか? 言語はあまり関係ありません。

XKCDコミック195では、ヒルベルト曲線を使用してインターネットアドレス空間のマップのデザインが提案されているため、同様のIPアドレスのアイテムがクラスター化されます。

IPアドレスが与えられた場合、そのようなマップ上でその2D座標（0から1の範囲）をどのように計算しますか？

MySQLにax、y、z 3Dポイントが保存されています。リージョン、スライス、またはポイントネイバーに質問したいと思います。Peano-Hilbert曲線を使用してポイントにインデックスを付け、クエリを高速化する方法はありますか？または、MySQLに3Dデータを保存するためのより効率的な方法はありますか？

アーマンに感謝します。

おそらくヒルベルト曲線を使用して、ジオハッシュのようなインデックスを使用して地理空間情報を保存することを検討しています。私の質問は、そのようなインデックスでエリア クエリを分割する最善の方法に関するものです。

たとえば、この記事では、エリア クエリを複数のクエリに分割して、地域性の低い範囲をクエリすることを回避する方法を示しています (この画像を参照)。通常のジオハッシュのように Z 曲線を使用して 1 回のクエリで円形領域を検索する場合は、関心のある領域のほんの一部しかない左下象限全体をクエリする必要があります。

この場合、検索をいくつかのクエリに分割することをお勧めしますが、これを行う最善の方法に関する情報を見つけることができませんでした. このような範囲クエリを、元​​の領域をカバーする小さな範囲に分割するアルゴリズムはありますか?

スパース ジオメトリの非立方バウンディング ボックスを含む 3D 配列があります。

配列 geometry[x][y][z] には、(x,y,z) が計算領域の一部である場合は値 0 が含まれ、そうでない場合は 1 が含まれます。

計算を並べ替えるために、ヒルベルト曲線を使用してこの空間をトラバースしたいと考えています。

コンテキストは、メモリにバインドされた GPU プログラムでグローバル メモリ アクセスを最適化しています。

どうすればこれを実装できますか?

更新:要素の19個の隣接ノードを追跡する隣接リストと一緒に(配列に)格納するだけなので、空でないセルをトラバースしたいだけです。

計算は、2 つの配列間でコピーするだけです。

これは疎格子ボルツマン法の伝播段階であり、物理的な解釈は隣接するサイトから「流体粒子」をストリーミングしています。

adjacency_map の値が連続的であるほど、次のようになります。より合体したメモリアクセスが得られることを願っています。

OpenCL カーネル:

PHP の GD ライブラリを使用して、ピクセル単位でヒルベルト曲線に読み込めるようにしたい大量のデータがあります。

目的は、アドレスをピクセル グリッド上のポイントにマッピングする任意のサイズのルックアップ テーブルを作成することです。例えば。

この例の 8 番目の連続アドレスは 2,2 です。最終結果のルックアップ テーブルは、参照可能なポイントだけで構成されます。

これを生成する効果的な方法が確実にあることはわかっていますが、まだ考えていません。

空間インデックスを一括読み込みするために、ヒルベルト次数で d 次元のデータ ベクトルを並べ替えようとしています。

ただし、各点のヒルベルト値を明示的に計算したくはありません。特に、特定の精度を設定する必要があります。高次元データでは、これには32*dビットなどの精度が含まれ、効率的に行うには非常に面倒です。データが不均一に分布している場合、これらの計算の一部は不要であり、データ セットの一部に特別な精度が必要になります。

代わりに、パーティショニング アプローチを実行しようとしています。2次元の一次ヒルベルト曲線を見ると

まず x 軸に沿ってデータを分割し、最初の部分 (必ずしもオブジェクトの半分を含むとは限りません!) が 1 と 2 (まだソートされていない) で構成され、2 番目の部分が 3 と 4 のオブジェクトを持つようにします。それだけ。次に、Y 軸で各半分をもう一度分割しますが、順序を 3-4 に逆にします。

したがって、基本的には、分割統治戦略 (QuickSort と密接に関連しています。均等に分散されたデータでは、これは最適であるはずです!) を実行し、必要に応じてヒルベルト インデックスの必要な「ビット」のみを計算します。したがって、「1」に単一のオブジェクトがあると仮定すると、その完全な表現を計算する必要はありません。オブジェクトが均等に分散されている場合、パーティションのサイズはすぐに減少します。

私は、長いグレーコーディングの次元インターリーブに変換する通常の教科書的なアプローチを知っています。これは私が探しているものではありません (利用可能な例はたくさんあります)。私は明示的に遅延分割統治ソートのみを望んでいます。さらに、2D 以上が必要です。

このように機能する記事またはヒルベルトソートアルゴリズムを知っている人はいますか? または、「回転」を正しく行う方法、どの表現を選択するかという重要なアイデアはありますか? 特に高次元では... 2Dでは些細なことです。1 は +y、+x の回転、4 は -y、-x (回転と反転) です。しかし、より高い次元では、これはよりトリッキーになると思います。

(もちろん、結果は、オブジェクトをヒルベルト次数で十分に大きな精度でソートした場合と同じになるはずです。必要のないときに完全な表現を計算し、それを管理する時間を節約しようとしているだけです。多くの人々は、かなり高価な「ヒルベルト数へのオブジェクト」ハッシュマップを保持しています。)

Peano 曲線と Z 曲線についても同様のアプローチが可能であり、おそらく実装が少し簡単です...おそらく最初にこれらを試す必要があります (Z 曲線は既に機能しています。仮想ピボットとしての適切な平均/グリッド値と各反復の次元の循環)。

編集：Zおよびpeano曲線でどのように解決したかについては、以下を参照してください。また、すでに 2D ヒルベルト曲線に対しても機能しています。しかし、ヒルベルト曲線の回転と反転はまだ正しくありません。

次の 3 つのタイプ INT(4)、つまり Short 、または INT(8) または varchar(512) のキーを持つことができる多次元ポイントがあります。

このため、通常のヒルベルト曲線変換は使用できません。コンパクトなヒルベルト インデックスを計算するための非常に優れたリソースを見つけました。ここにリンクがあります。

http://web.cs.dal.ca/~chamilto/hilbert/index.html

彼の論文のポイントと動機は理解できますが、コードを解読することはできません。コンパクト ヒルベルト インデックスとその逆関数を計算するために呼び出す関数がわかりません。