動的に変わる集合に対する類似検索のスケッチを利用した高速化

使用动态变化集的草图加速相似性搜索

• 批准号: 21K11901
• 负责人: 古賀 久志
• 金额: $ 2.25万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21K11901/
• 关键词: 集合間類似検索; スライディングウィンドウ; スケッチによる要約; 転置インデクス; 株価予測; データストリーム; スケッチ; Min Hash; 類似検索; ストリームデータ; 近似解法; データのスケッチ

昨年度に提案した動的に変化する集合を対象とするスケッチ更新アルゴリズムの空間計算量の削減に取り組んだ。本アルゴリズムでは、Min-Hashというハッシュ関数を利用してスケッチを作成する。ハッシュ値算出には(1)ハッシュ値割り当て表と(2)集合のヒストグラムが必要になるが、前者については表サイズを小さくする既存手法を採り入れて空間計算量の大幅な削減に成功した。一方で、後者についてはヒストグラムの空間計算量を大幅に減らすと集合からどの要素がいつ離脱するかという情報を保持できないため、スケッチの精度が下がるという問題が発生した。このため、後者については空間計算量を30パーセント程度削減するに留まった。動的に変化する集合に対して、省メモリで精度の高いヒストグラムを生成する手法が必要になっており、2023年度はこの条件を満たすヒストグラム生成法についても研究を進める。一方、応用研究としては動的に変化するテキスト集合をクエリとする範囲類似検索 (Range Search)についても研究した。ここで動的に変化するテキスト集合とは、具体的には特定ユーザによるSNSへの投稿を指しており、類似検索により投稿内容が似た類似ユーザを探すことを目指している。本問題に対して転置インデクスを用いた高速解法を考案した。とくに提案手法では転置インデクスをクエリに対してのみ持たせることで、転置インデクスの管理オーバーヘッドを増やさずに高速処理を実現した。この他に、株価時系列を終値の集合と見なして類似検索ベースの株価予測にも取り組んだ。ここでは過去の類似時系列を検索して、過去の事例から株価の上昇/下落を予測する。そして、予測対象銘柄以外の他社データも過去の事例に加えた方が、予測精度が向上するという興味深い結果を得た。

我们努力减少去年提出的草图更新算法的空间计算量，以动态变化的集合。在此算法中，使用称为Min-Hash的哈希功能创建草图。哈希值计算需要（1）哈希值分配表和（2）设置的直方图，但是对于以前的现有方法，采用了减少表尺寸的现有方法，并且空间计算的量大大减少了。另一方面，对于后者，如果直方图的空间计算量大大减少，则有关哪些元素将与集合分开的信息，而何时未保留元素，从而导致了降低草图的准确性的问题。因此，后者的空间计算量减少了约30％。需要一种用于使用减少内存动态变化集的高度精确直方图的方法，在2023年，我们还将对满足这种情况的直方图生成方法进行研究。另一方面，作为一项应用研究，我们还研究了范围相似性搜索（范围搜索），该搜索使用动态更改文本集作为查询。在这里，动态更改的文本集是指社交媒体上特定用户的帖子，旨在通过搜索类似的用户来搜索具有相似内容的类似用户。设计了使用转置索引解决此问题的快速解决方案。特别是，所提出的方法允许转置索引仅用于查询，从而实现高速处理，而无需增加转移索引的管理开销。此外，考虑到股票价格序列是一组收盘价，我们还研究了类似的基于搜索的股票价格预测。在这里，我们搜索了过去的类似时间序列，以预测股票价格上涨/降低了过去的情况。此外，我们获得了一个有趣的结果，即如果添加了过去的案例，则添加预测到预测股票以外的其他公司的数据将提高预测准确性。

项目成果

文字位置に着目した Min-Hash ベースの文字列類似検索

基于最小哈希的关注字符位置的字符串相似度搜索

• 发表时间: 2023
• 期刊: 人工知能学会研究資料
• 作者: 古賀久志，別府直輝;笠井龍一
• 通讯作者: 笠井龍一

画像の追加を許容するDeep Hashingに基づく類似画像検索

基于深度哈希的相似图像搜索，允许添加图像

• 发表时间: 2022
• 作者: 友田涼太;古賀久志;Y. Maeda and N. Suzuki;Ye Chenyang，古賀久志
• 通讯作者: Ye Chenyang，古賀久志

区間Min-Hashを用いた時系列データに対する近似最近傍探索

使用区间 Min-Hash 近似最近邻搜索时间序列数据

• 发表时间: 2023
• 作者: 友田涼太;古賀久志
• 通讯作者: 古賀久志

Exact Algorithm to Solve Continuous Similarity Search for Evolving Queries and Its Variant

解决演化查询的连续相似性搜索及其变体的精确算法

• DOI: 10.1587/transinf.2021dap0003
• 发表时间: 2022
• 期刊: IEICE Transactions on Information and Systems
• 影响因子: 0.7
• 作者: 古賀久志，別府直輝;笠井龍一;中尾 友紀，古賀久志;T. Yamazaki and H. Koga
• 通讯作者: T. Yamazaki and H. Koga

Stock Price Prediction for Individual Brands with Indexing DTW

使用索引 DTW 预测单个品牌的股价

• DOI: 10.20729/00220096
• 发表时间: 2022
• 期刊: 情報処理学会論文誌
• 作者: 古賀久志，別府直輝;笠井龍一;中尾 友紀，古賀久志
• 通讯作者: 中尾 友紀，古賀久志