论文部分内容阅读
Top-k查询作为一种有效的数据分析手段,在数据库领域有着越来越重要的研究地位。已有的Top-k查询研究中,主要侧重于提高查询效率以快速响应用户需求,存在更新效率以及查询结果质量较低的问题。此外,在查询过程中,没有融入情境感知功能,因此无法适应因情境变化引起的移动对象属性动态变化。基于传统Top-k查询中存在的问题,本文研究了支持情境感知的Top-k查询技术,提出了融合情境感知的Top-k查询架构,支持用户动态情境的Top-k查询算法和在多用户偏好趋同情境下的分组Top-k算法,主要的研究工作如下:(1)将情境感知功能融入Top-k查询,研究分析了现有Top-k模型,在其基础上提出了CIMT查询模型。在CIMT查询模型中,提出了一种数据拆分的情境预过滤算法,以及两种拆分准则。算法利用情境因子将一个原始目标对象替换为对应的分裂目标对象,分裂目标对象为原始目标对象在特定情境下的表现。并且在对数据划分网格的基础上提出了TTI索引(Trunk Tree Index),在TTI索引上提出了SRG(Search Record in Grid)快速定位算法,用于支持拆分过程中大量的目标对象的增、删、改、查操作,该索引结构可满足查询架构建立的高效性。通过实验验证了SRG算法对查询结果质量及情境预过滤算法效率的提高。(2)在TTI网格索引的基础上,提出了一种支持裁剪以及目标对象属性动态变化的GID-Top-k算法(Grid Index based Dynamic Top-k Computation Algorithm)。GID-Top-k算法以网格的支配关系为基础,根据网格在索引中的位置和网格的概要信息对数据进行裁剪,通过判断网格是否具有“k支配能力”以及确定索引中的“剪枝单元”来划分自由区和影响区,提高了剪枝效率。算法的计算模块负责将网格分区并计算初始Top-k结果,当数据变化发生在自由区时,不影响Top-k查询的结果集;当数据变化发生在影响区时,重新划分区域及计算。通过实验将GID-Top-k算法与已有的Top-k算法在多种条件下进行对比和分析,验证了算法正确性和高效性。(3)对于偏好重复度很大的用户群来说,单独为每个用户计算影响区中Top-k结果的性价比较低。基于以上考虑,提出了一种基于用户权重的分组算法来合并权重及偏好相似的用户,为他们查找相同的k个结果,以减少计算代价。同时设计了两种分组算法,EIG(Equal Interval Group)算法和SG(Similar Group)算法,并提出了综合评分函数来计算组内的目标对象得分。以不分组算法为基础,设计实验比较EIG算法和SG算法花费的代价以及提高的查询效率和组内用户满意程度。