您所在的位置: 成果库 压缩索引理论、技术及其应用

压缩索引理论、技术及其应用

发布时间: 2021-09-13

来源: 科技服务团

基本信息

合作方式: 创业融资
成果类型: 新技术
行业领域:
新一代信息技术产业,信息传输、软件和信息技术服务业
成果介绍

建立了并开发了熵压缩的文本自索引理论与技术,同时支持在压缩索引上的快速检 索。理论空间占用为 nHk + 2nlog(Hk+2) + n + o(n) 位。定位给定模式 P 在输入文本 T 中 的所有出现时间复杂度为 O(m log n + occ log n(loglog n)2)。字串提取时间复杂度为 O(len  (log σ + loglog n) + log n(loglog n)2) , 其中 n 是文本 T 的输入规模, σ 是 T 的字符表大小, Hk 是 T 的高阶经验熵, occ 是模式 P 在文本 T 中的出现次数。

提出并开发了首个图数据库相似性搜索的简明索引, 支持图的快速相似性搜索。理 论空间占用逼近图数据库大小的线性对数函数。在实现上,该索引是首个能在内存中在 2 千 500 万个化学分子结构图数据库中进行快速图的相似性搜索的简明索引。已有索引都是 传统索引,据我们所知,只能在少于 500 万个图数据库上进行搜索。

已完成算法理论和技术的软件开发。针对各种输入数据分布的优化一直在进行中。

主要技术指标:

普通文本数据上自索引空间占用为输入文本大小的 30%,高度重复数据上自索引空 间占用为输入文本大小的 5%。在压缩索引上进行模式搜索,包括定位和提取查询平均时 间在毫秒或微秒级。图数据库简明索引空间占用为输入大小的 5%-15%, 图的相似性查询 在秒级。

成果亮点
团队介绍
成果资料