论文部分内容阅读
随着Web在线数据库(Web DataBase, WDB)的激增，Web正在迅速地“深化”。通过WDB对外提供的唯一入口(表单/查询接口)有效地集成与挖掘蕴藏在深网WDB中海量丰富的信息十分必要和迫切。由于WDB查询接口嵌入在浩瀚的Web页面中，具有规模巨大、动态变化、异质和分布稀疏的“大数据”4V特征，因此，深网数据集成与挖掘的若干关键问题：如特定领域WDB入口的自动发现与识别、查询接口模式匹配和查询接口集成等一直是亟待解决的挑战性难题。本文针对已有算法对问题缺乏抽象建模，大多采用启发式或尝试与纠错的低效算法而无法有效求解问题的缺陷，采用抽象和形式化描述与问题求解方法，对上述关键问题的有效建模方法及可行高效算法进行了系统研究，所做工作及取得的主要研究成果如下：1)针对特定领域的WDB入口的自动发现与识别问题，作者首先将问题抽象为多目标优化问题，建立了多目标优化模型。之后，采用“分而治之”的思想，基于所提出的新的两步页面分类算法、链接打分机制、爬虫爬行停止条件和断点保护等一系列优化策略/算法，设计并实现了一种特定领域的高效的WDB聚焦表单爬虫E-FFC。理论分析与实验结果表明： E-FFC中所采取的各种优化策略/算法正确有效，其性能优于现有公开文献的特定领域的WDB聚焦表单爬虫。之后，为了进一步改进E-FFC的性能，作者给出了基于智能代理的可进行并行爬行的特定领域WDB聚焦表单爬虫框架iCrawler；2)针对特定领域查询接口集成中的模式匹配问题，作者基于所提出的查询接口属性负相关度量公式、语义相似度度量公式，有效地选择了三个模式匹配器，采用所构建的领域本体树及修正的证据理论组合规则，提出并实现了一种高效可行的特定领域的WDB查询接口复杂模式匹配算法；3)针对特定领域的WDB查询接口集成问题，作者首先将查询接口建模成一棵其对应属性的层次化有序树(简称为模式树)，识别出了属性在其模式树应满足的三种约束：层次约束、组约束和顺序约束，提出了量化这三类属性约束的度量方法：属性约束矩阵。发现并证明了查询接口模式树与其对应的属性约束矩阵所存在的唯一对应关系。在此基础上，将查询接口集成问题转化为多目标优化问题，给出了问题模型，提出了一种基于模型的可行高效的问题求解算法；4)针对在深网数据集成与挖掘系统中所面临的信息公共模式抽取问题：MLCS问题，作者采用所提出的有效的数据划分、快速非支配分层排序及前向比较操作、并发线程调度等策略，提出并实现了一种改进的基于支配点的高效MLCS并行算法，该算法有效地解决了基于支配点的MLCS算法的性能瓶颈问题，是对已有的基于支配点的MLCS算法的较大改进。之后，作者对MLCS问题进行了更进一步深入的研究分析，揭示并理论证明了现有基于支配点的MLCS算法框架所存在的时间性能瓶颈和缺陷。针对此性能瓶颈和缺陷，提出了求解问题的无冗余公共子序列有向无环图(ICSG)，并基于反链、并行集合、并行集合链(PCC)等概念，建立了问题模型ICSG+PCC。提出了分别通过一次正向和反向拓扑排序优化ICSG图(删除了其中所有的非关键点)的方法，创新性地提出了一种基于ICSG+PCC模型的新型高效的MLCS并行算法，理论分析与实验结果表明：所提出的MLCS并行算法的时间复杂度达到了线性级别，以压倒的优势优于现有最好的基于支配点的MLCS并行算法。