階層Tree構造のRDBでの表現について。
計算済のItem間距離のデータを元に、Itemから近傍Itemを返すことをしたいわけですが。 実務的な制約もありRDB構造で表現できる方法はないかとちょっと検討。
階層型クラスタリングを行い、その近傍を返す仕組みをRDBで表現できないものかと思ってみたり。(こんな時のためのGraphDBかもしれませんが。)
先人の知恵
みんな同じような課題に直面するよね。
Tree表現の整理*1
- (1)Hierarchical/Recursive SQL extensions
- (2)Tree encodings
- (2-1)Materialized Path
- (2-2)Nested Sets
(1) Hierarchical/Recursive SQL extensions
ノードのリンク構造をそのまま表現し、探索をする方法。素直ながら効率は悪い。
実際の用途ではItemから検索をしていくので、下層のNodeから、そのNodeが所属する上位Nodeに所属するNodeを参照するLookup tableを予め用意しておけば、実行時の計算を軽減できるかもしれないけれど、やっぱり効率は悪そう。
(2-1) Materialized Path
Path文字列表現にてTree構造を表現する方法。
PostgreSQLあたりなら、こういうのとか使えるかも。Path表現を行いLtreeで探索。
(2-2) Nested Sets
概要としては、こういうのとか。
入れ子集合モデル(Nested Sets MODEL)という、木構造を集合として扱う方法。
なんとスマートな。しかし驚きなのが、この木構造を集合として扱うこの方法自体は、元々はThe Art of Computer Programmingで紹介されているとのこと(!)。 Knuth先生、パナい。*2
Nested Setsの問題点
- ノードの追加に弱い
- あるノードを含むintervalをみつけるのが難しい
"Nested Intervals Tree Encoding in SQL"
- Tropashko, V. 2005. Nested intervals tree encoding in SQL. 34, 2 (Jun. 2005), 47–52.(http://sigmod.acm.org/publications/sigmod-record/0506/p47-article-tropashko.pdf)
上記を解決する方法。有理数で表現。
時間が取れたら読む。
