Research on fundamental compression technology to promote the utilization of compressed data

基础压缩技术研究促进压缩数据利用

• 批准号: 21K11758
• 负责人: 喜田 拓也
• 金额: $ 2.66万
• 依托单位: Hokkai-Gakuen University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K11758/
• 关键词: 大規模データ; データストリーム; パターン頻度計測; フィルタリング技術; 透過的データ圧縮法; 文法圧縮; 高階圧縮; 圧縮パターン照合; 圧縮データ利活用

本研究の目的は，圧縮されたデータに対して統計および知識処理を効率よく行う圧縮処理体系の基盤を築くことである．ここで「効率よい」とは，次の三つの観点において優れていることである．第一には，データをどれだけコンパクトに表現できるかという圧縮率の観点である．第二には，処理時間とメモリ消費量をどれだけ抑えられるかという計算量の観点である．第三には，圧縮後のデータ自体が，後の情報検索やデータ解析の際にどのくらい利用しやすいかというデータ活用の観点である．これまで，データ活用の観点から，非定型の文字列データに対する圧縮データ上でのキーワード検索や部分系列の頻度計測などは議論されてきた．一方で，表データやログデータのように数値データを多く含み構造化されたデータに対して，データ圧縮を積極的に用いたデータ活用方法についてほとんど議論されていない．申請者らはこれまでに，データストリームに対する頻出アイテム系列発見のための省メモリアルゴリズムについて開発を行い，第177回アルゴリズム研究会にて発表を行っている．この技術は，絶えず流れ込むデータ（データストリーム）中に頻出する部分系列を発見するためのものである．センサーログなどの数値データはデータストリーム型であり，これに対して頻出するパターンを任意の長さで検出することができる．本年度は，これまで得られた知見を基に，数値データの圧縮表現に関する調査を開始した．

本研究的目的是建立一个压缩处理系统的基础，该系统可以对压缩数据进行有效的统计和知识处理。这里，“高效”是指在以下三个方面表现优异。第一个是压缩率，即数据表达的紧凑程度。第二个考虑因素是可以完成的计算量，以减少处理时间和内存消耗。第三个考虑因素是压缩数据本身用于后续信息检索和数据分析的容易程度。到目前为止，从数据利用的角度，已经讨论了非标准字符串数据的压缩数据的关键字搜索和部分序列的频率测量。另一方面，对于包含大量数值数据（例如表数据和日志数据）的结构化数据主动使用数据压缩的数据利用方法却很少讨论。申请人目前已经开发出一种节省内存的算法，用于发现数据流中的频繁项序列，并在第 177 算法研究组上进行了展示。该技术用于发现不断流动的数据（数据流）中频繁出现的子序列。传感器日志等数值数据采用数据流的形式，可以检测任意长度的频繁出现的模式。今年，我们根据迄今为止获得的知识开始了数值数据压缩表示的研究。