日本語 / English
XICS: 内容および構造検索のためのXML索引
XMLの普及に伴って,XML文書に対する問合せを高速に処理する技術は非常に重要になってきています. XML問合せ処理に関する過去の研究では主にXML文書の構造に焦点をあてた検索を取り扱っていますが,本研究では索引を生成し利用することによって構造検索(//title 等)と全文検索(//section[contains(.,'XML')] 等)の両方を高速化することを目的としています.XML全文検索に関しては,W3Cよりワーキングドラフト [1]が発表されるなど注目され始めています.実用性の観点から,提案する索引は広く普及しているB+木を用いることを設計指針とし,索引はPostgreSQL等でも使用されているGiST (Generalized Search Tree) [2]を用いて実装しています.
XML文書の構造を保持し,問合せを効率的に処理するために, XML文書中の各ノードには根ノードからの経路情報の符号を含む識別子を付与します.経路情報と兄弟番号の情報を組み合わせてノード識別子とし,ノード識別子を探索キーとするB+木(STB-tree)と,テキストと識別子の組合せを探索キーとするB+木(COB-tree)を構築することで内容と構造の両方を扱います.
STB-treeでは逆経路情報に基づいて探索キーを順序づけすることにより //title などのはじめに // を含む問合せにも高速に対処することができます.また,COB-treeではテキスト片の保持に工夫を行い,隣り合う探索キー同士の差分情報を利用して索引中のテキストの圧縮を行うことも考えています.

図1. XICS概観.
この索引を利用することで,先行研究 [3]に比べて最大数百倍の問合せ処理高速化を実現しました.探索キー中の経路情報を利用することで絞り込みを行っています.

図2. 先行研究との問合せ処理時間の比較.
  • Toshiyuki Shimizu and Masatoshi Yoshikawa, ``Full-Text and Structural Indexing of XML Documents on B+ Tree,'' IEICE Transactions on Information and Systems, Vol. E89-D, No. 1, pp. 237-247, January 2006.
  • Toshiyuki Shimizu and Masatoshi Yoshikawa, ``Full-Text and Structural XML Indexing on B+ Tree,'' 16th International Conference on Database and Expert Systems Applications (DEXA 2005), Lecture Notes in Computer Science (LNCS), Springer-Verlag, Vol. 3588, pp. 451-460, Copenhagen, Denmark, August 22-26, 2005. (92/390 = 24%) [paper] [slides]
  • 清水 敏之, 吉川 正俊, ``XML文書の内容および構造検索のためのB+木索引,'' 電子情報通信学会第16回データ工学ワークショップ 第3回日本データベース学会年次大会 (DEWS2005). 優秀論文賞受賞 [paper]
[1] W3C. "XQuery 1.0 and XPath 2.0 Full-Text 1.0," May 2007. http://www.w3.org/TR/xquery-full-text/.
[2] J. M. Hellerstein, J. F. Naughton, and A. Pfeffer, "Generalized search trees for database systems," Proc. of 21st International Conference on Very Large Data Bases, pp.562-573, Zurich, Switzerland, Sept. 1995.
[3] R. Kaushik, R. Krishnamurthy, J. F. Naughton, and R. Ramakrishnan,"On the integration of structure indexes and inverted lists," Proc. of the 2004 ACM SIGMOD international conference on Management of data, pp.779-790, Paris, France, June 2004.