xml文档检索的索引结构研究

《xml文档检索的索引结构研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京交通大学硕士学位论文XML文档检索的索引结构研究姓名：郝雪峰申请学位级别：硕士专业：计算机应用技术指导教师：须德20050301摘要提出一种对XML文档建立索引的新方法。浚方法支持分支查询和带有通配符的查询。同时设计了一种通过一次遍历xML文档就可以建立索引的算法。按照我们设计的线模型，XML文档被看作一条线，文档中各个元素被看作这条线的线段。查询xML文档就相当于指定相应的线段。使用一种基于区间的动态树标记模式，每个线段都被给予一个区间。然后把XML文档中所有的路径插入到一个trie结构中，并使用B+树管理这些区间。定义了三种运算，这些运算使不同B+树上的区间集合

2、可以相互运算。三种运算对应算法的最差情况时间复杂度是0(m+n)。分支查询最后的结果可以通过这些运算直接得到。这种索引方法的创新处体现在如下几个方面：提出了用于查询XML文档的线模型；定义了三种运算，并给出了相应的算法：在线模型和三种运算的基础上，我们使这种索引方法支持分支查询：最可能匹配的点在索引结构里有聚集效果，这种特性大大减少了磁盘I／O，并同时使磁盘优化成为可能：提出一种动态的树标记算法，使我们的索引结构支持数据插入和删除；并给出了通过一次扫描建立索引结构的算法。通过实验，我们把该索引方法和时下流行的技术进行比较。实验证明该方法的查询处理开销和磁盘I／O与查询表

3、达式的复杂度和查询结果集的大小线性相关。实验结果表明了我们索引方法的显著性能优势。根据本文主要研究成果撰写的论文，LMIX：ADynamicXMLIndexMethodUsingLineModel，已经被LectureNotesinComputerScience收录出版发行，并被SCI检索。关键词：XML索引，NativeXML数据库，数据管理，数据检索AbsttactAbstractAnewwayofindexingXMLdocumentiSproposed．whichsupportstwigqueriesandquerieswi出wildcards．Anonce-o

4、verindexconstructionalgorithmiSalSOgiven．AccordingtotheLineModelwedesign，veeCOnsiderXMLdocumentasaline，andeveryelementsofthedocumentastheline’Ssegments．ToqueryanXMLdocumentiStoidentifythecorrespondingsegments．Usingarange—baseddynamictreelabelingscheme，eachsegmentofthelineisgivenarange．We

5、putallthepathsofXMLdocumentintoatde，andorganizetherangesetswithB+-treesgroupingbythenodesonthetrie．Threeoperationsaledefined，whichenabletherangesetsontheB+-treescorrespondingtodifferentnodesinthetrietooperatewitheachother．n心worst—casetimecomplexityofthealgorithmwedesignedfortheoperations

6、is0(m+n)．Thefinalresultsoftwigqueriescanbegotthroughtheseoperationsdirectlyataspeedsimilartothesimplepathquery．Throughextensiveexperiments，wecompareourmethodwi血otherpopulartechniques．Inparticular,weshowthattheprocessingcostanddiskI，Oofourindexmethodislinearlyproportionaltothecomplexityof

7、queryandthesizeofqueryresults．ExperimentalresulIsdemostratethegreatperformancebenefitsofourproposedteclmiqlies．PaperLMIX．'ADynamicXMLIndexMe伪odUsingLineModel，whichiswroteaccordingtothemainresearchmsultsofthisthesis，hasbeenacceptedbyLectureNotesinComputerScienceandindexedb