不确定数据世系管理和相似性查询

《不确定数据世系管理和相似性查询》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要不确定性数据在很多应用中广泛出现，例如经济、军事、物流、金融、电信等，其表现形式多种多样，包括关系型数据、半结构化数据、图数据、流数据、移动对象数据以及无结构化的Web数据等。目前，根据应用的特点与数据形式的多样性，已经出现了多种不确定数据模型，这些模型的核心思想都源自可能世界模型。该模型从一个不确定的数据源演化出诸多确定性的可能世界实例，所有实例的概率之和等于1。尽管可以针对各个实例单独进行查询处理，合并中间结果并获取最终结果，但是可能世界实例的数量远大于不确定数据库的规模，从而导致可能世界模型在实践应用中并不可行。因此必须采用排序、剪枝等启发式技术进行优化处理以

2、提高查询处理效率。针对不确定数据管理的挑战，本文主要考察不确定数据查询处理的优化。主要工作分为两部分：不确定数据世系管理和相似性查询。具体的，针对数据的不确定性，研究如何通过不确定数据的世系追踪数据不确定性的来源和大小，以及对不确定性集合数据进行相似度评价，最后提出了不确定数据流上ER-topk查询的精确算法。本文的主要贡献如下：·首先研究了如何利用数据世系追踪数据不确定性的来源和大小。基于P胛一tree数据结构，近似描述不确定数据的How世系，避免了追踪数据演化的中间结果，同时也避免了运用可能世界模型对不确定性数据进行建模；基于P胛一tree，可以追踪目标数据的不确定

3、性来源，以及对目标数据的不确定性大小进行评价。·针对不确定集合，定义了不确定性集合的期望相似度算子，提出了不确定集合期望相似度的精确和近似算法。具体的，运用动态规划方法在多项式时间内给出不确定集合期望相似度的精确算法，而不必扩展可能世界实例；考虑到精确算法需要耗费大量的时间和空间，为克服可扩展性差的缺点，我们运用Monte-Carlo方法在线性时间内近似计算不确定集合的期望相似度。·考虑到不确定集合相似度的多样性，又评价了不确定性集合的概率阈值相似度。给出了不确定集合的概率阈值相似度算子的定义，以及精确和近似算法。运用动态规划方法在多项式时间内给出不确定集合概率阂值相似

4、度的精确计算过程；同时考虑到概率阈值相似度的计算结果是一个概率值，当用户给定VIII表目录相似度的阈值，利用尾概率不等式提出了一个线性时间内的剪枝规则，大大加快了精确解的计算过程；考虑到没有被剪枝的不确定集合的精确算法需要耗费大量的时间和空间，我们运用Monte—Carlo方法近似计算不确定集合的概率阈值相似度。·基于界标模型提出了不确定数据流响应ER-topk查询的精确算法，该方案将所有不断到来的元组分成两组，一组包含ER-topk查询的候选结果，剩下的元组包含在另外一组中，我们分别用数据结构domGraph和probTree来维护这两类元组；基于期望的线性性，我们避

5、免了扩展所有可能世界实例，在次线性时间内给出查询的结果。本文研究了不确定数据的查询处理，主要工作包括不确定数据世系管理和不确定数据的相似性查询，通过大量的实验验证了提出算法的效率和可扩展性等。关键词：不确定数据；数据世系；相似性查询；期望相似度：概率阈值相似度；数据流；top-k查询；相似度连接查询；分类号：TP311IXAbstractAppearingwidelyinvariousfields，inclusiveofeconomy，military，logistic，fi—nanceandtelecommunication，eta1．，uncertaindataha

6、smanydifferentstyles，such38relationaldata，semi—structuredata，streamingdata，andmovingobjects．accord—ingtoscenariosanddatacharacteristics，tensofdatamodelshavebeendeveloped，stemmingfromthecorepossibleworldmodelthatcontmnsahugenumberofthepossibleworldinstanceswiththesumofprobabilitiesequalto

7、1．However，thenUN—berofthepossibleworldinstancesisfargreaterthanthevolumeoftheuncertaindatabase，makingitinfeasibletocombineintermediateresultsgeneratedfiomallofpossibleworldinstancesforthefinalqueryresults．Thusjsomeheuristictechniques，suchasordering，pruning，mustbeusedtored