Studies on Advanced Pattern Matching over Continuous Data Streams

连续数据流上的高级模式匹配研究

• 批准号: 20700001
• 负责人: KIDA Takuya
• 金额: $ 2.75万
• 依托单位: Hokkaido University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20700001/
• 关键词: アルゴリズム理論; データストリーム; パターン照合; 情報検索; 文字列処理; データ圧縮; 接尾辞木; VF符号

I have studied high speed and advanced pattern matching over continuous data streams and also about compression technique for realizing that. For the former, I have proposed a pattern matching algorithm, named BPS, which is based on bit-parallel techniques and allows complex queries for multi-dimension data streams. By the algorithm, we can search over data streams for queries that highly combined with numerical data and categorical data as well as text data. For the latter, I have developed a novel data compression method, named STVF coding, which is based on VF coding and suitable for pattern matching. The method has a good feature of allowing doing keyword search in simple and quick manners, as it gains high compression ratios as well as existent well-known compression methods.

研究了连续数据流上的高速、高级模式匹配以及实现这种匹配的压缩技术。对于前者，本文提出了一种基于位并行技术的模式匹配算法BPS，该算法支持多维数据流的复杂查询。通过该算法，我们可以在数据流中搜索与数值型数据和分类型数据以及文本数据高度结合的查询。针对后者，本文在VF编码的基础上，提出了一种适合于模式匹配的数据压缩方法STVF编码。该方法与现有的压缩方法相比，具有压缩比高、检索简单、快速的特点。

项目成果

An Efficient Algorithm for Almost Instantaneous VF Code Using Multip lexed Parse Tree

一种使用复用解析树的几乎瞬时 VF 代码的高效算法

• 发表时间: 2010
• 期刊: Proc.of Data Compression Conference 2010 IEEE DCC.2010
• 作者: Satoshi Yoshida;Takuya Kida
• 通讯作者: Takuya Kida

A Combination of Variable-length-to-Fixed-length Coding with Arithmetic Coding for Efficient Compression and Pattern Matching

变长到定长编码与算术编码的结合实现高效压缩和模式匹配

• 发表时间: 2010
• 作者: Satoshi Yoshida;Takuya Kida
• 通讯作者: Takuya Kida

Unsupervised Spam Detection by Document Probability Estimation with Maximal Overlap Method

基于最大重叠法的文档概率估计的无监督垃圾邮件检测

• 发表时间: 2010
• 期刊: Transactions of the Japanese Society for Artificial Intelligence
• 作者: T. Uemura;D. Ikeda;T. Kida;H. Arimura
• 通讯作者: H. Arimura

分節木と共用文字列で表現される符号上での効率良い圧縮照合アルゴリズム

线段树和共享字符串表示的代码的高效压缩匹配算法

• 发表时间: 2010
• 期刊: 電子情報通信学会和文論文誌
• 作者: Tangtisanon Pikulkaew;Hiroaki Kikuchi;喜田拓也
• 通讯作者: 喜田拓也

ウェブ閲覧における効率的なキーワード抽出とその利用

高效的关键词提取并在网页浏览中使用

• 发表时间: 2007
• 作者: 上村卓史;他2名
• 通讯作者: 他2名