试论互关联后继树索引改进研究与应用

《试论互关联后继树索引改进研究与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复旦大学硕士学位论文互关联后继树索引改进研究与应用姓名：李卓尔申请学位级别：硕士专业：计算机软件与理论指导教师：胡运发20080504摘要全文索引的显著特点就是提供对非结构化海量数据的管理和快速查询。全文索引创建的空间效率和索引建好后的查询速度是全文索引研究领域的两大热点。本文讨论并比较了现有的几种流行的全文索引模型，介绍了一种新型的全文数据库的数据模型——互关联后继树(文中简称为IRST)，并且在此基础上介绍了近期研究的一些新进展。首先在索引的查询速度上有所提高。文章先介绍了一种双排序互关联后继树(DIRST)，它是在在互关联后继树模型上的改进而成。然后通过比较最新研究

2、的双排序互关联后继树逆向区间二分查询法与已有的双排序互关联后继树正向区间二分查询法的性能，证实了双排序互关联后继树逆向区间二分查询法是目前基于互关联后继树的最快的查询方法。另外，文章还介绍了互关联后继树在频繁模式挖掘上的应用情况。通过一种互关联后继图的模型，成功的将后继树应用于频繁模式挖掘。通过与经典的FP—Growth算法比较，互关联后继树频繁模式挖掘算法在测试情况下普遍大大优于FP—Growth算法。从而证明了互关联后继树在频繁模式挖掘上也有很好的应用前景。关键字：全文检索，互关联后继树，双排序互关联后继树，频繁模式挖掘中图法分类号TP31lAbstractOneno

3、tablefeatureoffulltextindexistheprovisionofmanagementandrapidquerytomassiveunstructureddata．Thespaceefficiencyofcreatingindexandthequeryspeedafterthecompletionofbuildingindexaretwomajorhotspotsinthefieldofresearch．Inthispaper，wecomparesomeexistingmodelsoffulltextindex．WealSOintroduceanewd

4、atamodeloffull-textdatabase—InterReleventSuccessiveTree(inthetextreferredasIRST)，andsomeprogressonrecentresearch．First，thequeryspeedintheindexhasincreased．ThepaperfirstintroducesaDoubleSortedInterReleventSuccessiveTree(DIRST)，whichwasimprovedfromtheIRSTmodel．Andbycomparingtheperformanceof

5、latestresearchedBackwardsSearchAlgorithmofDIRSTandexistingForwardsSearchAlgorithmofDIRST，provethatBackwardsSearchAlgorithmofDIRSTisthemostrapidquerymethodonIRST．Inaddition，thearticlealsointroducedtheapplicationofIRSTinfrequentpatternmining．ThroughamodelofInterReleventSuccessiveGraph，theIR

6、STmodelhasbeensuccessfullyusedinfrequentpatternmining．ComparingwiththeclassicFP—Growthalgorithm，IRSTfrequentpatternminingalgorithmisgenerallymuchbetterthanFP-Growthalgorithminmosttestcases，whichprovedthattheIRSTalsohasaverygoodprospectinfrequentpatternmining．Keyword：Full—TextRetrieval，Int

7、erReleventSuccessiveTree(IRST)，DoubleSortedInterReleventSuccessiveTree(DIRST)，FrequentPatternMining41．1研究背景第一章绪论随着计算机产业的发展，以计算机存储设备为载体的电子信息愈来愈多，这些信息大致可分为两类：结构化数据和非结构化数据，结构化数据指的是诸如企业财务帐目和生产数据、学生的分数数据等等，非结构化数据的则是一些文本数据、图象声音等多媒体数据等等。据统计，非结构化数据占有整个信息量的80％以上。对于结构化数据，用RDB