kd-tree Visualization(2) - agwの日記
先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。 繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成したkd木を可視化したものは以下のようなものでした。 同じく、木構造として可視化したものは以下のようなものでした。 さて、では何故均衡の取れない木が構築されてしまうのでしょう? 座標群の初めの点、1番の点を挿入した直後の状態を可視してみましょう。 この可視と先ほどの木構造としての可視を比較すると不均衡な木が構築される理由がより明らかとなります。木構造の可視にて1番の左側にぶら下がっている2番以下の座標群は、この可視では1番によって空間分割された領域の下側、つまり、y座標値がより小さい側に分布しています。 同様に、木構造にて1番の右側にぶら下がってい
計算幾何学
計算幾何学とは 計算幾何学とは、「コンピュテーショナル・ジオメトリー」(Computational Geometry) の日本語訳である。 コンピュータで扱う幾何学というのが、その性格をよく表している。 最近専門家の間では、英語のまま呼ぶ人が多い。というのも、 訳の読み「けいさんきかがく」が「計算機科学」と間違われやすい、 という理由によるものだという。 私は「計算幾何学」という、 生硬でどこか不器用な面持ちが漂う邦訳の字面が好きである。 だから、「けいさん きかがく」というように読み方に注意して、 邦訳を使ってほしい。 なお、切れる場所での注意が肝心という話は、 エスペラントの読み方という記事を参照のこと。 さて、計算幾何学とは何だろうか。私の理解する範囲では、 「数学で扱う形（図形）を、 数学上の知識とコンピュータのアルゴリズム・データ構造を駆使して、 効率良く処理する学問体系」となる
kd-tree Visualization(1) - agwの日記
前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索はてなに以下のような問題が提示されていたのがきっかけでした。 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです １．集合Pはあらかじめ、任意の順番でソートしておける ２．点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです 集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか？ 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索する… - 人力検索
空間インデックス - ma38su.sourceforge.jp
Cell method データ領域を包含するセルのサイズを事前に決定する必要があるため、動的なデータベースには不利のようです。 各セルは、そのセル領域と重なる領域の識別子を持ちます。セルを細かく区切れば検索精度は向上しますが、使用するデータ領域が増加します。 Digital MapはCell methodにより読み込む領域を検索していますが、すべてオンメモリでデータ構造を構築しているため、セルのサイズを大きくせざるを得ず、検索精度があまりよくありません。それに加えて数値地図25000には領域の外接長方形のデータしかないのでcell methodの恩恵をあまり受けることができず、地図データの読み込みが遅く、また表示領域以外の領域が読み込まれることが多々あります。 Quad Trees 領域を4分割（2次元）することで木構造を構築します．ディスク上に構築する際には、2分割するよりも高速です．ペ
Moving Object Database (MoDB) / Trajectory Database
移動オブジェクトデータベース (MoDB: Moving Object Database) 2009/1/28 更新 移動オブジェクトデータベースとは 移動オブジェクト (Moving Object: mob)(注1)とは，「1) 時間経過に従って位置が変わる物体」のことで，特に「2) 移動先の単純予測が難しい」物体のことを指します．具体的には，歩行者や移動する車，野生の動物，台風やハリケーンなどがそれに当たります．天体や砲弾のように，物理法則を用いればかなりの精度で移動先が予測できる物体は，MoDB の研究の中では対象としません．画像処理技術などでは Moving Object という用語は「画像の中にある動いている物体全般」の意味で使われますが，MoDB の扱う mob はこれとは異なります． MoDB は GPS などの測位システムで取得された mob の位置データを扱うデータベース
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
