一种物化Web视图的在线选择算法

建立了一个考虑更新代价的Web视图置换测度模型,并以此为基础,提出一种物化Web视图在线选择算法DCR.该算法在简单的缓存算法基础上引入了选择置换机制, 通过监测提交的用户查询, 决定是否将其结果予以保存, 必要时依据置换测度值的大小进行置换, 实现Web视图物化总量的控制, 防止视图过分物化, 以降低动态缓存管理、索引和检索的开销.同时可结合适当的维护方式, 提高更新效率, 避免频繁的更新对查询性能产生太大的影响, 使整个算法更具适用性. 实验表明, 在查询集较大、数据源更新比较频繁的场合, DCR算法可以降低视图检索开销, 并可通过机会更新有效减少了失效视图的数量,使算法在用户查询响应性能方面显示出较大的优势.     

基于迭代事务集与交集剪枝的最大频繁项集挖掘算法

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,如果采用Apriori类的候选项目集生成一检验方法,则候选项目集生成的代价通常很高.为寻求避免生成大量候选项集或生成频繁模式树的挖掘算法,提出一种从事务项集交集求最大频繁项集的迭代算法DIIP(Datasets Iteration and Intersection Pruning Algorithm),通过不断缩减事务集数据量和尽可能早地对项目集进行修剪实现最大频繁项集的挖掘,该算法有别于已有的最大频繁项集经典算法,实验表明该算法有效可行.     

基于不确定数据的分布式Top-k查询算法

目前基于不确定数据的Top-k查询算法仅考虑了集中式的环境,为了解决分布式系统中节省系统带宽的问题,在此基础上,提出了在分布式环境中基于不确定数据的Top-k查询算法UDTopk.该算法定义了一个候选集(candidate set),仅使用候选集中的数据,而不用访问数据集中所有数据,就可以得到正确的Top-k查询答案.算法通过动态维护候选集、仅传输少量数据,达到减少网络中数据传输的目的.实验结果表明,该算法可以有效地节省网络带宽.     

一种找出较优重写查询的启发式算法

提出了一种实用的启发式算法．该算法使用了一种简单的代价模型来比较查询之间的相对代价,并利用多项式时间从实化视图得到的多个重写查询中找出一个执行代价较节省的重写查询,不需要查询优化器的支持,减少了优化器的负担．实验结果表明该算法找出的较优重写查询的执行时间比穷尽搜索算法的略有增加,而搜索时间和空间显著减少．利用该算法可快速地响应查询,能显著改进数据仓库的查询性能．     

一种高效的实视图选择算法

数据往往被存储在分布式的数据源中,当需要对数据做查询操作时,就无法像查询单数据源那样有效率.联机分析处理(OLAP)被提出,并用来克服这个问题.在这个过程中,为了提高OLAP的查询效率,采用了将视图实体化的技术,即将综合性的复杂的查询结果放入实视图中,再将OLAP查询与实视图相互关联起来.但是,实视图需要占据大量的物理存储空间,而当数据源一旦更新时,为了与底层数据源保持一致,必须对实视图进行相应的更新维护,从而产生实视图的维护代价,因此实视图选择必须在提高查询响应速度和资源限制二者之间做出一定的权衡.文章提出了一种算法,可以在对维护代价一定条件约束下,使得查询代价达到最小的算法.经过实验,该算法不仅计算复杂度较小,而且维护成本较低.     

数据仓库中实体化视图的一种维护算法

实现实体化视图是提高系统响应时间的一个关键技术和有效的解决方案,在具体的实现过程中面临着实体化视图的维护问题. 由于源数据的不稳定性,其数据的变化必须及时传播到实体化视图中,以保持实体化视图与源数据的变化一致性,否则会降低实体化视图中数据的新鲜度,并影响联机分析处理(OLAP)查询结果的真实性和有效性. 针对视图的维护问题,提出了实体化视图的一种维护算法,它将使视图重计算代价最小化.     

基于粗集约简的索引枚举选择方法

依据可索引列构造原子配置及其候选空间,针对候选配置提出了一种基于粗集约简的分层估算方法.首先通过对关系型联机分析的查询执行语法分析,生成索引集的原子配置,使得其中的索引列均被高代价算子访问.然后利用约简迭代构造彼此不可替代的索引集,以有效缩减待考察空间.最后基于索引的数量约束,使用枚举代价估算消除了当前层中代价最大的索引.利用约简的特性,该方法在保证索引有效性的前提下,有效降低了代价估算的复杂度.实验验证在付出中等规模的估算代价后,约简分层的枚举方法显著提高了枚举估算的效率.     

一种改进的最小代价网络编码算法

分析了网络编码内在特性,指出网络编码区别于传统多播并提升多播传输性能的根本原因在于网络中存在被不同传输路径所重用的关键链路.通过在构建网络编码多播的传输路径时形成较少的关键链路,提出了一种基于关键链路的最小代价网络编码算法.该算法是在最大流算法的基础上加以改进的,并结合了网络增广链和最小截集的性质,是一种有效的最小代价网络编码算法.基于随机网络的仿真实验证明,在实现多播理论容量的前提下,该算法能有效降低网络编码的代价.     

一种基于时空因素的实化视图选择算法的研究与设计

分析了几种经典视图选择算法存在的不足,提出了一种新的基于时空因素的价值模型,在此基础上设计了一个新的视图选择算法——PBPUS(preprocessing benefit perunit space)算法。该算法与原有算法相比,降低了视图搜索的时间,减少了实化视图更新维护的代价,有效提高了实化视图的查询效率。     

P2P环境下面向不确定数据的kNN查询方法

由于仪器的不精确和网络延时等原因,在传感器网络和P2P系统中数据都存在不确定性.为解决此问题,基于现有的集中式的不确定数据的kNN查询方法,提出了一种在P2P环境中对不确定数据的kNN查询方法.该方法在super-peer的网络拓扑结构的基础上,以一种扩展的R树(P2PR-tree)作为此查询算法的空间索引结构,解决P2P环境中对多维数据的索引.并且结合两种剪枝策略减小了候选集的范围和减少了查询在P2P网络中的网络代价.实验结果表明,该方法在减少网络代价方面具有较高的性能.