有质量保证的清洗不确定数据

有质量保证的清洗不确定数据内容摘要不确定或不精确的数据在应用中普遍存在，像基于位置的服务，传感器监控及数据的采集和整合。对于这些应用，概率数据库可以被用来存储不确定的数据，提供的查询设施用于产生统计置信度。假设一个有限的资源可用来“清洗”数据库（例如，通过探测一些传感器数据值来获得他们最新的值），我们要解决清洗不确定对象集的选择问题，为了在查询答案时达到最好的质量改善。为此，我们提出PWS-quality指标，这是一个普遍的措施，是在可能世界的语义下量化查询答案的模糊性。我们研究PWS-quality指标如何被有效的评价，主要有两个等级：（1）审查元组与其他元组之间相互独立的可满足性的查询（例如，范围查询）;（2）需要的一系列相关联的元组知识的查询（如最大查询）。然后，我们提出了一个多项式时间的解决方案，以达到在PWS-quality指标中最优的改善。也将提出其他快速启发式算法。在实验中，表现出实际和综合的数据集，表明该PWS-quality标准的评估可以很快，而且我们的清洗算法提供了一个高效率的最佳解决方案。据我们所知，为概率数据库开发质量标准是第一个工作，然后探讨这个标准如何用于数据清洗。关键词：不确定数据；数据库；PWS-quality指标；质量改善；清洗算法1导言传统上，数据库假定数据存储的值是准确或精确的。但是，在许多新兴的应用程序中，数据库本身存在不确定性。考虑一个栖息地监测系统，其中的数据，如温度，湿度和风速是从传感器获得的。由于传感器性质的不完善，所获得的数据通常含有噪声污染。再举一个例子,在全球定位系统(GPS)中，定位值的收集有一些测量误差。在生物特征数据库，存储的特征向量的属性值是不准确的。综合与记录联动工具也会使置信度的值与根据匹配质量输出的元组联系在一起。为了应付处理不确定性日益增长的需要，研究人员最近提出将其不确定性看作一个“一等公民”，通过一个“不确定数据库”管理数据。在这些数据库中，查询可以进行评估，以产生有概率保证的不精确的答案。查询答案的模糊性构成了查询质量的概念，它描述了查询答案是“多么好”。在本论文中，我们就如何通过减少模糊数据库的方法来提高查询质量的问题进行分析。不精确的数据可以以不同的方式得到缓解。例如，在传感器监测中的应用，数据库系统是用来存储在一个地理区域部署的成千上万个传感器的当前值。由于资源有限，系统可能无法捕捉到在每一个时间点的传感器信息；相反，它使用存储的值来估计当前传感器的读数。为了减少估计的误差，系统可以“探测”传感器，这是对系统最新估值的响应。再举一个例子，考虑一个电影评级的数据库，是一个基于把IMDB电影信息和从Netflix挑战中得到的用户评级相融合的数据库。该数据库包含了每部电影的用户评级，可描绘出一个概率分布表。澄清这些等级的不确定性可以通过联系各自的用户来“消毒”。由此产生的数据库，不确定性比以前少，而且可以提供更高质量的服务。理想的情况下，整个数据库都应该被清洗。事实上,这可能是不可行的,因为清洗数据是很昂贵的。例如，一个传感器监测系统，可能只探测传感器的一小部分，部分原因是由于无线网络带宽有限，部分是由于传感装置稀缺的电池电源。至于电影评级数据库，困难的可能是验证电影评级中涉及的所有的用户评级。一般来说，清洗操作是受限制的，例如，通过一个固定的“预算”，它描述了可用于投资清洗数据的最大努力量。对于一个传感器监测系统的清洗预算，可以是传感器探测使用的最大带宽量。对于电影评级数据库，这样的预算可以是考虑验证电影评级需要工时的最大数值。在本论文中，我们要解决在有限的预算下，为达到更好的查询或服务质量目标，清洗不确定数据的问题。尽管不确定数据库的清洗具有重要性，但相对较少的工作已经完成。我们的主要想法是利用查询的信息来决定要被清洗的数据项的设置。通过对这些数据的操作，返回给用户的答案质量可以达到最高改善。我们在概率数据库的基础上开发我们的解决方案，这是一种被广泛研究的不确定性数据的模型。，我们面对的主要挑战包括：（1）通过查询结果定义一个健全的综合的质量标准；（2）制定有效的方法来计算这个指标；（3）制定有效的和最佳的清洗算法。为了说明这一点，图1显示了一个概率数据库报价关系，其中通过使用从网页收集而来的某一匹配的自动模式方法，存储了四个产品的价目（带有ID的a，b，c和d）。所谓的存在概率（缩写为Prob）的属性是用来注明每个元组存在的置信度。一个元组也与一个“x-元组”相联系，这个“x-元组”表示一个分配方案的替代选择。例如，产品a有0.7的机会提供一个120美元的价格，并且有一个0.3的机会提供80美元的报价。现在考虑一个最大查询：“返回元组的最高价格。”由于数据不准确，这个查询可以产生不准确的答案。表2显示了查询的结果，它包含了元组ID和作为正确答案的非零概率（或条件概率）。产生的有统计保证答案的这些查询，一般被称为概率查询。表1不确定的数据库实例表2在表1中进行最大查询的结果在概率结果的基础上，为捕捉一个查询结果的模糊程度，可以定义一个“质量分数”的实数值。例如，在最大查询的查询结果（见表2）分数为-1.73（根据我们的质量指标）。假设表1是部分清洗（例如，通过咨询公司的有关产品的实际价格）。表3显示了一种可能的情形，其中不确定性与x-元组相关的a和c都被删除。在此表中，每一个a和c只有一个元组存在，这个元组的存在概论等于1。最大查询的新结果显示在表4，具有较低的模糊性，或得出了一个改进的质量分数-0.97。在极端情况下，如果所有的x-元组被清洗过，质量分数最高（我们的质量标准值为0）。表3对表1部分清洁的实例表4对表3进行最大查询的结果这样的查询质量标准应该如何定义？尽管之前提出一些质量措施，但他们要么提供特定的查询，要么没有为概率数据库的使用做设计。为了解决这些问题，我们提出了PWS-quality指标。这个度量标准提供了一个查询概率数据库的查询质量（即可以被任何查询使用）的通用方法。它实际上是一种熵函数，它很方便地返回一个实数值分数，表示在查询答案中不精确的数量。PWS-quality标准也是使数据高效清洗的解决方案，我们也将在本论文中显示。PWS-quality标准的另一个显著特点是，它假设了可能世界语义学（或简称PWS）。PWS提供了对一个正式的概率数据模型的诠释，在这个模型中一个数据库被看作是一种确定性数据库实例集(称为可能世界），每个实例都包含了从每个x-元组中提取的元组集。表1的一个可能世界例子包含了元组{a1，b2，c3，d1}。概率数据库查询评价算法应遵循PWS的概念，即产生的结果应该是与在所有可能世界上的查询评价相一致的。类似地，PWS-quality指标分数是从所有可能世界获得的查询结果中计算得来的。一个关于PWS-quality指标明显的问题是，它的计算效率很低。这是因为评估这一措施要求检查所有的可能世界，数量可以以指数增大。有趣的是，我们观察到，不是经常需要检查所有的数据库实例；事实上PWS-quality指标的计算是通过使用返回给用户的查询答案。这是作为一个以实体为基础的查询而广泛熟知的一类查询。这种类型的查询满足了返回给用户包含元组ID的最后答案，以及其条件概率（例如，表2）。我们研究两个实体查询的代表性的例子，即范围查询和最大查询。两种查询都在许多应用中被使用。例如，在一个传感器监测中的应用，可以查询的范围是：“返回温度值在[10℃，20℃]的传感器的ID”。在电影数据库中，最大查询可以是：“返回观众评价最高的电影ID”。我们发现，这两个查询的PWS-quality标准，可通过查询答案信息快速计算出来。我们的方法是有效的，因为一个查询答案可以通过现有的查询评估和索引算法有效地被保证，而且我们的技术复杂性是与查询答案的大小成线性关系的。PWS-quality指标也可作为数据清洗问题的有用工具。给定要清洗的x-元组集，我们证明PWS-quality指标的预期值总是单调递增的。这有助于我们制订数据清洗问题，如：选择x-元组的子集X，使得（1）在X中清洗x-元组的预期质量改进是最高的；及（2）清洗X的总成本不超过给定的预算。这个问题是有挑战性的，因为计算X的预期质量改善需要在X中的所有元组的组合。此外，找到最佳X集要求对数据库中x-元组的不同组合测试，呈现一个指数时间复杂度。为了解决这些问题，我们把PWS-quality表达转换到一个“x-形式”中——x-元组概率信息的一种线性函数。x-形式使我们非常容易地计算出清洗x-元组集的预期质量改进。除此之外，范围查询和最大查询有相同的格式（具有不同的参数），所以支持两种查询只需要有一个唯一的解决方案。要找到没有从整个数据库测试的所有x-元组组合的最佳解决方案，我们发现，选择x-元组是唯一必须的，即出现在查询答案中的元组。然后，我们模拟作为优化问题的清洗工作，并开发一个基本动态编程算法，以推算出多项式时间中x-元组的最优集。我们也建议用其他近似的启发式(如贪心算法)。我们的算法，同时服务范围查询和最大查询。他们也支持数据库包含相同属性值的元组。我们已进行详细评估，以检验我们的实验方法。结果表明对于既真实又综合的数据集，PWS-quality可以有效计算。此外，x-元组可以迅速选择实现预期质量的最优改善。其中启发式贪心算法，提供了一个具有最高效率近乎最佳的操作。图1说明了采用了我们的解决方案的系统设计。，自接到用户的请求，查询引擎产生一个概率查询答案。此信息传递到质量经理。在这个模块里，质量评估计算PWS-quality分数。然后它会给数据清洗算法发送必要的信息，该算法可以在可用的预算范围内推导出要清洗（或“清洗集”）的x-元组的最优解集。清洗经理负责执行消毒活动（例如，索取选定的来源报告给其更新后的值）。当再次执行时，查询将在预期查询中有所改善，值得注意的是，质量经理是与查询引擎脱钩的，因为它只需要查询答案元组的概率信息。另一个问题是，PWS-quality分数也发送给用户。这种实值评级为用户提供一种直观的方式去了解答案的模糊程度，无需解释出现在查询答案中众多可能的概率值。在本论文中，我们注重质量评估员的设计和数据清洗算法。图1我们解决办法的框架本文其余部分的组织如下。在第2节，我们提出了相关工作。第3节讨论了数据和查询模式。在第4节我们介绍了PWS-quality的正式概念，以及有效的评估方法。第5节描述了以质量为基础的清洗方法和其他启发式。在第6节给出我们的实验结果。论文是在第7节结束。附录A中，我们详述为PmaxQ找到x-形式的证明。附录B介绍了针对清洗问题的动态规划算法。附录C中，我们还讨论了在一个被清洗的数据库中，查询如何可以有效地进行评估。2相关工作查询不确定数据库。由于其简单和明确的语义，概率数据库模型已受到大量的关注。特别是对x-元组的概念，已作为代表元组不确定性的正式模型被普遍采用。Dalvietal表明，使用PWS概念的评估查询是低效的，因为一个可能世界的指数增长需要研究。因此，研究人员提出修改查询语义。举一个例子，不同变体的top-k查询有效解决方案的研究。另一个研究数据模型是“属性的不确定性”，其中属性值具有范围查询和概率分布函数的特点。对于这个数据模型，有效评估和索引算法已经被提出，包括范围查询，最近查询，最小/最大查询，轮廓查询和反向轮廓查询。数据不确定性有效查询算法的分类进行了研究。最近，一个基于PWS属性不确定性的正式模型已经被提出。在ULDB中，提出了一种结合了概率数据库和血统数据库的属性模型。虽然我们的工作是以概率数据库为基础的，这个想法可能会被扩展，以支持其他数据模型。不确定性数据的质量指标。大量的质量措施也进行了研究。在文献[10,14]中,如果结果的条件概率高于用户自定义的阈值，那么查询结果将被认为是令人满意的。在文献[29]中，一个top-k查询的质量被包含在查询结果中的实际top-k值所赋予。在文献[9]中，为范围查询，最近查询，AVG和SUM查询定义了不同的指标。在这些工作中，质量指标是专为特定的查询类型定义的。另一方