从偏好数据库中挖掘Ceteris Paribus偏好

针对传统的推荐系统需要用户给出明确的偏好矩阵（U-I矩阵）,进而使用自动化技术来获取用户偏好的问题,提出了一种从偏好数据库中挖掘出Agent的偏好信息的方法。从知识发现的角度,通过Ceteris Paribus规则（CP规则）,提出了k阶偏好挖掘算法（kPreM）。在算法中,利用k阶CP规则对偏好数据库中的信息进行剪枝处理,减少了数据库扫描次数,从而提高了偏好信息的挖掘效率。随后以一种通用的图模型——条件偏好网（CP-nets）为工具,揭示了用户的偏好可近似表达为CP-nets的定性条件偏好网。实验结果表明,用户的偏好都是带有条件的偏好。另外,通过挖掘得出的CP-nets偏好模型,为设计个性化的推荐系统提供了理论基础。     

CP-nets 的完备性及一致性研究

CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点.然而,任意二值CP-nets上的强占优算法还没有给出,CP-nets可表示的偏好的完备性还无人研究,CP-nets所能表示的偏好是否一致也还未彻底解决.基于CP-nets上的强占优运算研究CP-nets的完备性和一致性.首先,通过构造CP-nets导出图及其性质的研究,得出强占优的本质是求取翻转关系的传递闭包,从而利用Warshall算法求出可判断任意CP-nets的强占优;其次,通过求取3种不同结构(可分离的、链表结构和树形结构)的CP-nets的偏好个数,给出了CP-nets可表达的偏好的不完备性定理,并给出了可分离的CP-nets中偏好的计数公式;最后,研究CP-nets的一致性,给出了CP-nets的一致性判定定理及其算法.所做工作不仅解决了Boutilier和Goldsmith提出的一些难题,还深化了CP-nets的基础理论研究.     

CP-nets的可满足性序列求解算法研究

CP-nets是一种简单、直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点.然而对于CP-nets的基础性质——可满足性序列的研究却较少.通过构造CP-nets导出图,利用改进的图的深度优先遍历算法实现二值网的强占优测试,对强占优测试得到的可达矩阵进行分析,得出任意结构CP-nets的可满足性序列个数关系;给出了生成全部可满足性序列的算法;强化和扩充了CP-nets的基本概念,深化了CP-nets的基础理论研究.     

面向任意区间树结构的差分隐私直方图发布算法*

当前一种有效的差分隐私直方图发布是先将直方图映射成满m叉区间树,后利用查询一致性约束提高查询精度.然而,并非所有直方图都能映射成满m叉区间树.针对此问题,文中首先提出可实现任意直方图向树结构映射的k-区间树;然后从理论上分析对于任意区间树结构下的差分隐私直方图发布,仍可在一致性约束下利用最优线性无偏估计进一步降低区间计数查询的误差;最后提出面向任意区间树结构基于局部最优线性无偏估计的差分隐私直方图发布算法(LBLUE).实验对比分析同类算法和LBLUE所发布数据的区间计数查询精度及算法效率,表明LBLUE有效可行.     

CP-nets学习的复杂度

CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题。不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题。首先,建立命题公式的可满足性和CP-nets表示的偏好公式之间的联系,将CP-nets的学习问题转化为命题的推理问题。随后,给出两类具有特殊结构的CP-nets的学习问题的计算复杂度,其中最复杂的无环CP-nets上的学习问题是NP-complete,而最简单的集合结构CP-nets上的学习问题是P。这些结论给出了CP-nets(如链结构、有界树宽)学习问题复杂度的上下界。     

CP-nets及其表达能力研究

偏好处理是人工智能中的一个重要研究内容, 它的4个研究热点是偏好的表示、 提取、 聚合和推理. 条件偏好网(Conditional preference networks, CP-nets)是一种简单直观的偏好表示的图形工具, 但很少有工作研究CP-nets的表达能力. 本文研究CP-nets的表达能力, 详细研究了CP-nets表达偏好的完备性, 其上构造的运算复杂度以及适用的场合. 首先给出了CP-nets模型上的几个运算, 利用改进的Warshall算法求出了二值网的强占优测试在最坏情况下的复杂度为O(4n). 其次通过构造CP-nets导出图及其性质的研究, 得出CP-nets特别适合不完全信息下的多属性定性偏好决策. 当需要处理更完全信息时, 可借助于与Agent的交互来完成. 虽然我们给出了CP-nets的强占优测试的理论解, 但其理论上可解, 实际上不可解. 为了解决强占优测试的指数级复杂度问题, 本文最后给出了一种带有软约束的满足问题(Soft constraint satisfaction problem, SCSP)的求解方法. 它把CP-nets中的定性运算转为约束半环中的定量运算, 从而将指数级的复杂度转化为多项式的复杂度, 间接提高了部分CP-nets的表达能力. 本文所做的工作是对Boutilier和Bistarelli工作的改进和提高.     

基于前缀编码的先根遍历树生成算法的研究与应用

在管理信息系统的层次分类树中,为了快速查询分类信息并高效地生成层次分类子树,提出了一种基于前缀编码的先根遍历树生成算法。该算法中的节点采用前缀编码的数据结构,便于快速检索出子树节点集合;在构造子树时预先对其进行先根遍历,产生有序遍历表,同时记录最近各层节点的信息,使得建立子树的效率得到大幅提高。最后通过实例验证了所提算法的有效性,为管理信息系统中层次分类树的建立提供了可行的解决途径。     

基于贪婪策略的紧密k核子图查询

k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询（CRKSQ）问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8%以内。     

基于多索引树的阴影光线遍历算法

阴影光线求交计算是光线跟踪的重要计算瓶颈。然而,构造一棵能有效剔除阴影 光线冗余求交计算的标准树结构仍然十分困难。为区分遮挡和非遮挡的阴影光线,提出一种基 于多索引树的遍历方法,在节点中增加提升遍历速度的索引。首先,针对遮挡光线为尽快与图 元相交的遍历特征,选择性的将位于叶节点上、对光线遮挡概率高的图元索引到中间节点,促 使光线提前在树中层停止搜索。其次,针对非遮挡光线为尽快搜索最邻近节点的遍历特征,为 底层节点建立邻接索引,减少节点搜索空间。利用帧间相关性预测遮挡类型,采用相应遍历方 法进行针对性的加速。相比专有树结构的遍历算法,该算法将遍历时效率提升 20%以上,具有 更好的遍历性能,且预计算时间更少。     

对双亲／孩子结构连接算法的研究与改进

结合区间编码和结点模型映射方法提出一种用于关系数据库的扩展存储模式.通过按广度优先遍历XML树实现对双亲/孩子关系结构连接算法的改进.改进后的算法降低了内存空间的开销,缩小了列表的扫描范围,明显提高了查找匹配速度,达到了查询优化的目的.     

LCA关系序对导引小枝查询

让关系数据库支持XML数据存储和查询,是XML领域重要的研究分支.DM XML系统以关系数据库为平台,融合结构映射和模型映射,根据路径统计实现了路径分区的编码方案.提出了DM XML查询模式集的解析、验证和生成方法.集合中的模式对应唯一的约束节点LCA关系序对,该序对并能严格地转化为等价的SQL查询.从实验数据分析,表明了DM XML编码方案的合理性和路径查询的高效性.     

一种高效基于模式图的数据库关键字查询方法

针对基于模式图的数据库关键字查询方法中普遍存在的查询效率较低的问题,提出了合并网络查询方法(CCNE)。CCNE中设计了一种合并网络结构,可以有效地避免传统方法中因候选网络之间的重复结构造成的冗余操作。同时,给出一种改进的候选网络生成策略,可以避免产生冗余候选网络并缩小遍历范围,从而提高效率。最后,在合并网络的基础上,设计一种合并网络执行算法,在很大程度上减少了传统方法所需执行的大量复杂数据库查询操作,进一步提高查询效率。多组基于真实数据集的实验结果表明CCNE可以在保证查询结果无缺失的情况下有效提高查询效率。     

多编码树GPU并行轴心子图匹配

子图同构问题是非确定多项式(NP)完全问题,而轴心子图同构是一种特殊的子图同构问题.针对现在已经有许多高效的子图同构算法,然而对于轴心子图同构问题目前并没有基于GPU的搜索算法,且通过改造已有的子图同构算法来解决轴心子图匹配问题会产生大量不必要的中间结果这一问题,提出了一种基于GPU的轴心子图同构算法.首先,通过一种新...     

对左兄弟／右兄弟结构连接算法的研究与改进

结合区间编码和结点模型映射方法提出一种用于关系数据库的扩展存储模式。通过按结点编码中的广度遍历序号建立聚集索引，实现左兄弟／右兄弟关系结构连接算法的改进。改进后的算法降低了内存空间的开销，缩小了列表的扫描范围，明显提高了查找匹配速度，达到了查询优化的目的。     

采用图遍历算法的服务端请求伪造漏洞检测

针对基于PHP语言开发的Web应用系统,提出了一种基于图遍历算法的服务端请求伪造漏洞检测和利用方法。通过构建抽象语法树,获取每个文件的数据流信息,进而利用数据流中的传递依赖关系构造全局的代码属性图,使用图遍历算法对生成的代码属性图进行污点分析,得到污点变量的代码传递依赖路径图,最后使用约束求解的方法对路径图中的经过函数信息进行漏洞检测并生成可利用的攻击向量。实验结果表明,这种检测方式相较于传统的静态审计方法能够很好地发现服务端请求伪造漏洞,并能够自动化生成可绕过的攻击向量。     

图的树分解算法及其应用

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。     

一种基于图结构分解的图近似查询方法研究

图近似查询能够得到与查询图近似的结果集,相比较精确查询具有更广泛的应用范围。为提高近似查询的查准率和查全率,提出一种基于图结构分解的查询算法。该算法通过对查询图和目标图进行图结构分解,对其建立图分解索引,利用查询图的最小生成树集得到满足阈值的生成树集,通过图标准编码在索引中快速定位,查找出所有可能的近似结果。实验结果表明,该算法能有效得到近似结果,提高查询速度。     

Allocating tree structured programs in a distributed system withuniform communication costs

Studies the complexity of the problem of allocating m modules to n processors in a distributed system to minimize total communication and execution costs. When the communication graph is a tree, Bokhari has shown that the optimum allocation can be determined in O(mn²) time. Recently, this result has been generalized by Fernandez-Baca, who has proposed an allocation algorithm in O(mn^k+1) when the communication graph is a partial k-tree. The author shows that in the case where communication costs are uniform, the module allocation problem can be solved in O(mn) time if the communication graph is a tree. This algorithm is asymptotically optimum     

基于CURE聚类算法的静态R树构建方法

R树索引结构在空间对象查询和复杂空间关系查询方面具有重要作用。传统空间索引结构R树是动态生成的,树的结构是根据连续插入算法实现的,通过分裂子节点直至生成R树的根节点。动态生成算法会导致R树节点最小外包矩形之间的大量重叠,影响空间查询效率,且空间利用率不高。为了弥补动态生成R树的不足,提出了基于CURE算法的静态R树生成方法,给出CU_RHbuilt建树算法,该算法不仅能有效地处理海量数据,识别任何形状的簇,减少矩形重叠度,而且采用划分技术可较大程度地减小计算代价,空间利用率较高。进一步提出了基于CURE算法的R树节点分裂方法。理论研究与实验表明,所提方法具有较高的查询效率。