Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
DynamicでScalableな空間分割データ構造Bkd-Tree
Search
Takatomo Torigoe
November 27, 2020
Programming
0
940
DynamicでScalableな空間分割データ構造Bkd-Tree
社内勉強会資料です。
Takatomo Torigoe
November 27, 2020
Tweet
Share
More Decks by Takatomo Torigoe
See All by Takatomo Torigoe
型付きアクターモデルがもたらす分散シミュレーションの未来
piyo7
0
830
AI動画生成ガチャ紹介
piyo7
1
130
AIイラスト生成・編集テクニック紹介
piyo7
2
380
PandasAIにおけるLLMを用いた自然言語クエリの仕組み
piyo7
0
470
HdrHistogram紹介:ストリーミングで統計値を算出するための 高速・省メモリなライブラリ
piyo7
0
350
AI画像生成の紹介スライドをAI画像とAIチャットで作ってみた
piyo7
0
330
将棋AI「dlshogi」紹介
piyo7
1
730
軌跡検索エンジンT-Torch論文紹介
piyo7
0
240
アドテクと機械学習
piyo7
0
340
Other Decks in Programming
See All in Programming
Python型ヒント完全ガイド 初心者でも分かる、現代的で実践的な使い方
mickey_kubo
1
120
設計やレビューに悩んでいるPHPerに贈る、クリーンなオブジェクト設計の指針たち
panda_program
6
2.1k
High-Level Programming Languages in AI Era -Human Thought and Mind-
hayat01sh1da
PRO
0
780
テストから始めるAgentic Coding 〜Claude Codeと共に行うTDD〜 / Agentic Coding starts with testing
rkaga
12
4.5k
Is Xcode slowly dying out in 2025?
uetyo
1
270
「Cursor/Devin全社導入の理想と現実」のその後
saitoryc
0
820
スタートアップの急成長を支えるプラットフォームエンジニアリングと組織戦略
sutochin26
1
5.8k
AIと”コードの評価関数”を共有する / Share the "code evaluation function" with AI
euglena1215
1
170
たった 1 枚の PHP ファイルで実装する MCP サーバ / MCP Server with Vanilla PHP
okashoi
1
260
AI時代のソフトウェア開発を考える(2025/07版) / Agentic Software Engineering Findy 2025-07 Edition
twada
PRO
87
29k
初学者でも今すぐできる、Claude Codeの生産性を10倍上げるTips
s4yuba
16
11k
PHP 8.4の新機能「プロパティフック」から学ぶオブジェクト指向設計とリスコフの置換原則
kentaroutakeda
2
910
Featured
See All Featured
GraphQLの誤解/rethinking-graphql
sonatard
71
11k
Six Lessons from altMBA
skipperchong
28
3.9k
Principles of Awesome APIs and How to Build Them.
keavy
126
17k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
53
2.9k
The Cost Of JavaScript in 2023
addyosmani
51
8.5k
Stop Working from a Prison Cell
hatefulcrawdad
271
21k
A Tale of Four Properties
chriscoyier
160
23k
Git: the NoSQL Database
bkeepers
PRO
430
65k
Why You Should Never Use an ORM
jnunemaker
PRO
58
9.4k
実際に使うSQLの書き方 徹底解説 / pgcon21j-tutorial
soudai
PRO
181
54k
Side Projects
sachag
455
42k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
35
2.4k
Transcript
Dynamic で Scalable な 空間分割データ構造 Bkd-Tree 鳥越貴智 2020/11/27 データサイエンス共有会 #meetup_ds
Bkd-Tree? 全文検索エンジンElasticsearchで、地理インデックスとして使われている。 BKD-backed geo_shapes in Elasticsearch: precision + efficiency +
speed Geospatial Advancements in Elasticsearch Elasticsearchのコアである Apache Luceneで実装されている。 org.apache.lucene.util.bkd
Bkd-Tree? kd-Treeの亜種。ざっくり言うとforest of balanced binary kd-trees。 kd-Treeについては「k-d treeによる最近傍探索」が分かりやすい。 K-D-B-Treeよりもディスク使用率が高く追加コストを安くした、という触れ込み のためK-D-B-Treeから紹介します。
ちなみにK-D-B-TreeはWikipediaに英文記事があるものの、Bkd-Treeの解説記事 はほぼ無く「The Bkd Tree: A Dynamic Disk Optimized BSP Tree」くらい。
K-D-B-Tree The K-D-B-Tree : a search structure for large multidimensional
dynamic indexes (1981)
range query を想定 [K-D-B-Tree] Data Structure Region Pages Point Pages
平衡多分木 1 Nodeを 1 Pageに メモリ配置
[K-D-B-Tree] Insertions 1. 木を辿って、Pointの位置を含むPoint Pageを探し、Pointを追加する。 2. Pointが増えてPoint Pageが溢れたら、Regionを分割する。 3. Regionが増えてRegion
Pageが溢れたら、さらに親のRegionを分割する。 親Regionの分割は、 子Regionの分割を引き起こすため、 コストが高い。
[K-D-B-Tree] Splitting Patterns ] Pointの分布特性を知っているならば、 Cyclic以外の分割パターンの方がいい場合もある。
[K-D-B-Tree] Deletions and Reorganization 1. Pointが属するPoint Pageから、Pointを削除する。 2. ストレージ使用率が減ってきたらリバランス。 (リバランス例)
Region Page A, B, Cの使用率が半分を切ったため、 どれか二つを合体させたいが、 長方形にするためには三つ合体させないといけない。 しかし三つ合体すると溢れるため、 二つの長方形に再分割を行う必要がある。
[K-D-B-Tree] Utilization 空のK-D-B Treeに 一様乱数で発生させた100,000Points をCyclicに分割してInsertした実験
Bkd-Tree Bkd-Tree: A Dynamic Scalable kd-Tree (2003)
[Bkd-Tree] Main Idea • K-D-B-Treeは追加削除時にリバランスすることでクエリ性能を保つ代わり、 ストレージ使用率が低下する。(その後に提案されたhB-Treeも同じ) • Bkd-Treeはリバランスせず、後述の「Bulk Load」「Logarithmic Method」
という手法によって、ストレージをほぼ100%で使いきる。 // Bkd-Treeの論文はPageではなくBlockで使用率を考えている。K-D-B-Treeも 1 Node 1 Pageに拘らなければ、キャッシュヒット落とさず使用率上げる 実装はできる気がするものの、これは現代の感覚か(?) // 使用率は置いておいても、枝の数がまちまちだとクエリ性能落ちるので、 できるだけ木をコンパクトにするのは重要なはず。
[Bkd-Tree] Bulk Load • Bkd-Treeは2分木 ◦ 葉は一定数のPointを保持する。 ◦ 葉のインデックスのシフト演算で、子 ノードのポインタを置き換えられる。
• 空の木に1点ずつ追加するのではなく、ま とめて木を構築する。 (not Dynamic) • 1階層ごとにソートして分割位置を決める のではなく、グリッド行列で一気に掘る。
[Bkd-Tree] Logarithmic Method • サイズが指数的に膨らんでいく木の列をなす。ただし列は欠けてもよい。 • クエリは並列的に投げる。 • Point追加は、メモリ上のバッファ木 に対して行う。 ◦
これはリバランスせず、Leafを大きくしたり深くしたりするはず。 • バッファ木が溢れたら、ストレージ上の木とBulk Loadによってマージ。 ◦ 下図の場合 をマージして、 size 4Mの を作り出し、 を空にする。
[Bkd-Tree] Insertion Performance • Bkd-Treeは、追加コストがK-B-D-Treeより2桁安い。 ◦ 木のマージ自体はコスト高いが、その間もクエリは投げられる。