超高速データストリームのためのオンライン型半構造情報変換システムの開発

超高速数据流在线半结构化信息转换系统开发

• 批准号: 16650021
• 负责人: 坂本 比呂志
• 金额: $ 1.6万
• 依托单位: Kyushu Institute of Technology (2005)Hokkaido University (2004)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16650021/
• 关键词: データストリーム; 半構造データ; オンラインアルゴリズム; 情報抽出; パターン発見; XML; XPath; 情報検索; ストリーム; 文法圧縮; 圧縮索引; SAX

本研究では,半構造データに対する高速なXPath処理法を提案した.これまでに,データを効率的に圧縮する手法として知られている算術符号化を半構造データの検索に応用した,逆算術符号化が提案されている.これは,木構造データ上のパスの依存関係を,データを圧縮したまま復号化することなく検査できる手法であり,この関係性を利用することで,パスによる問い合わせを高速に処理できる.しかしながら,この問い合わせで利用可能なパスの形式は限定されているため,一般のXPathの問い合わせは処理が困難である.そこで本研究では,このような逆算術符号化にノード間の先祖子孫関係を判定可能な範囲ラベルを導入することにより,より複雑な問い合わせ処理を高速に実現するための手法を提案する.評価実験の結果,300MB程度のXMLデータに対してテキストを直接処理する既存の手法と比較し,数十から百倍の高速化を達成した.また,本研究では,畳み込みカーネルのアイディアに基づいた,ラベル付き順序木に対するこれまでにない新しいカーネル関数を提案した.まず,畳み込みカーネルの枠組みにおいてラベル付き順序木に対して任意の部分グラフを部分構造として用いた場合の,効率の良いカーネル計算のアルゴリズムを提案し,曖昧なラベルや構造を取り込むような拡張を行った.さらに,より一般的な木構造として,順序のないラベル付き根付き木に対するカーネルを考えた場合には,カーネルの計算が#P-完全問題であることを示した.

在这项研究中，我们提出了一种用于半结构数据的高速XPATH处理方法。已经提出了一种用于有效压缩数据的方法的逆算术编码，该方法应用了算术编码，以搜索半结构化数据。这是一种允许路径对树结构化数据的依赖性，而无需在压缩时解码数据，并且通过使用这种关系，可以高速处理路径的查询。但是，由于此查询可用的路径的格式有限，因此很难处理一般的Xpath查询。因此，在这项研究中，通过引入可以确定这种反算术编码中节点之间祖先关系的范围标签，可以高速进行更复杂的查询。我们提出了一种使之成为可能的方法。作为评估实验的结果，我们的速度比直接处理300MB XML数据的文本的现有方法快几十至百倍。此外，在这项研究中，我们根据卷积核的概念提出了一个前所未有的新内核功能，用于标记的订单树。首先，当将任意子图用作卷积内核框架中标记的订单树的部分结构时，我们提出了有效的内核计算算法，并已扩展以结合模棱两可的标签和结构。此外，我们表明，当考虑标记的生根树作为更通用的树结构的内核时，内核计算是一个＃P-Complete问题。

项目成果

WWWからの情報抽出-ウェブラッパーの自動構築-

从 WWW 中提取信息 - 自动构建 Web 包装器 -

• 发表时间: 2004
• 期刊: 人工知能学会誌 19・3
• 作者: 有村博紀;坂本比呂志他2名
• 通讯作者: 坂本比呂志他2名

A Space-Saving Linear-Time Algorithm for Grammar-Based Compression

一种基于语法的压缩的节省空间的线性时间算法

• 发表时间: 2004
• 期刊: Proc.11th International Symposium on String Processing and Information Retrieval LNCS3246
• 作者: H.Sakarnoto;T.Kida;S.Shimozono
• 通讯作者: S.Shimozono

Efficient Substructure Discovery from Large Semi-Structured Data

• DOI: 10.1137/1.9781611972726.10
• 发表时间: 2001-10
• 期刊: IEICE Trans. Inf. Syst.
• 作者: Tatsuya Asai;K. Abe;Shinji Kawasoe;H. Sakamoto;Hiroki Arimura;S. Arikawa

A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression

基于语法的压缩的完全线性时间近似算法

• 发表时间: 2005
• 期刊: Journal of Discrete Algorithms 3(2-4)
• 作者: 鹿島 久嗣;他2名;Shunsuke Inenaga 他1名;Takuya Kida;石野 明(他1名);大谷 壽一(他3名);Hiroshi Sakamoto
• 通讯作者: Hiroshi Sakamoto

算術符号化を利用したXMLデータへの高速な問い合わせ処理の改良

使用算术编码改进 XML 数据的高速查询处理

• 发表时间: 2006
• 期刊: 第17回データ工学ワークショップ(DEWS〜2006)講演論文集
• 作者: 舞田哲哉;他1名
• 通讯作者: 他1名