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

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

• 批准号: 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-完全問題であることを示した.

In this paper, we propose a semi-structured XPath processing method. This is the first time that we've had a problem with this problem. The dependency relationship between the structure and the structure is discussed in detail below. This is a very difficult problem to deal with. In this study, we propose a method for determining the possible range of ancestor and descendant relations between the two groups by inverse arithmetic symbolization. As a result of the evaluation, the XML file of 300MB level is processed directly by the existing method, and the speed of tens of times is achieved. In this study, we propose a number of new ways to improve the quality of life in the community. In this case, the efficiency of the system is good, and the calculation of the system is very simple. In addition, when considering the general wooden structure and the order of the wooden structure, the calculation of the wooden structure is a #P-complete problem.

项目成果

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

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

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

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

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