kd-tree Visualization(2) - agwの日記
先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。 繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成したkd木を可視化したものは以下のようなものでした。 同じく、木構造として可視化したものは以下のようなものでした。 さて、では何故均衡の取れない木が構築されてしまうのでしょう? 座標群の初めの点、1番の点を挿入した直後の状態を可視してみましょう。 この可視と先ほどの木構造としての可視を比較すると不均衡な木が構築される理由がより明らかとなります。木構造の可視にて1番の左側にぶら下がっている2番以下の座標群は、この可視では1番によって空間分割された領域の下側、つまり、y座標値がより小さい側に分布しています。 同様に、木構造にて1番の右側にぶら下がってい
kd-tree Visualization(1) - agwの日記
前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索はてなに以下のような問題が提示されていたのがきっかけでした。 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索するアルゴリズムを考えています 高速、低負荷で検索するにはどうしたらいいでしょうか？ 条件は次の通りです １．集合Pはあらかじめ、任意の順番でソートしておける ２．点ｐの近似点にする条件は、margin範囲内で一番近いものとするが、margin値はそのときどきで変わる ターゲットの言語はjavascriptで、200msぐらいの間隔で検索を続けるつもりです 集合P の個数が 1000 ~ 10000 点くらいだったらどうしますか？ 二次元の値(x, y)をもつ集合P から任意の点p の近似点を検索する… - 人力検索
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
