2 次元のポイントにインデックスを付けるためのストレージを探しています。より具体的には、ウェイ (またはエッジ) のジオメトリを OpenStreetMap に保存して、検索できるようにしたいと考えています。ストレージへのクエリは、ウェイの 2 つのエンドポイントに基づいてジオメトリを検索します。このクエリは、Dijkstra と同様のアルゴリズムによって検出されたパスのジオメトリを再構築するために実行されるため、ジオメトリ ルックアップの速度が重要になります。
私の場合、ノードは符号なしの整数であり、ジオメトリは文字列またはポイントのベクトルとしてエンコードできます。どちらの方法でも機能します。
ノードの数は約 10 億になるため、すべてをメモリに保持することはできません。そのため、外部ストレージまたはディスク ベースのストレージを見つけるとよいでしょう。
私はすでに Stxxl を試しましたが、文字列やベクトルなどの非 POD 型を値としてサポートしていないようです。
事前にご提案いただきありがとうございます
2 つの個別のベクトルを維持することで、マップのような動作をシミュレートできます。2 つの<key, value>ペア<0, "hello">があるとし<1, "world">ます。最初のものvector (of char)には、
h, e, l, l, o, \0, w, o, r, l, d, \0
2 番目には、このようにそれぞれのandがvector (of pair of two 'size_type's)含まれています。begin positionone past end positionstring
<0, 6>, <6, 12>
ご覧のとおり、 の"world"後に が来る必要はありません"hello"。このように、新しい <key, value>ペアについては、2 番目のベクトルの開始位置と終了位置を更新するだけで ( indexed access )、最初のベクトルの末尾に値を配置します(シフトは不要です)。
編集: の代わりに、私が推測するより良い解決策を補うものをvector (of pair of two 'size_type's)使用することもできます。map< int, pair<size_type, size_type> >好きなのを選びな。