面向大数据库正则表达式查询的有效算法
张晓煜1
林晓2
王志杰2
1.郑州航空工业管理学院计算机科学与应用系,河南郑州,4500152.上海交通大学 计算机科学与工程系,上海,200240
摘要：针对大数据库中正则表达式查询,提出了一种基于索引的有效算法.首先,构造索引.该索引结构在前缀树基础上加以改进,为每个节点创建二维数组存放该节点所辖子树各层的首次关键节点,并对每个节点附加关键节点指针以指向同层的下一关键节点.然后,通过所提出的索引结构进行查询.最后,分析了所提出算法的时间和空间复杂度,并进行了实验.实验结果证明:随着数据集的增加,其查询时间和输入/输出(I/0)时间增长速度较缓慢,说明其可扩展性较好,适合于大数据库中正则表达式查询.并且,随着查询字串的增加,查询时间与I/O时间均呈递减趋势,证明了该算法的效率和有效性.
关键词：正则表达式查询处理大数据库索引
分类号：TP3(计算技术、计算机技术)
资助基金：国家自然科学基金(U1304616)河南省科技攻关计划(122102210480)
论文发表日期：2015-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：6( 56-61 )
英文信息