不确定数据流查询处理算法的研究

《不确定数据流查询处理算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号⋯⋯⋯⋯⋯⋯⋯UDC⋯⋯⋯⋯⋯⋯⋯密级⋯公⋯无⋯⋯暑哦≯声哮硕士研究生学位论文不确定数据流查询处理算法的研究申请人：学号：培养单位：学科专业：研究方向：指导教师：完成日期：李红2121368计算机科学技术学院计算机应用技术不确定数据库朱敬华副教授2015年3月万方数据随着科技的发展及人们对查询处理方法认知的加深，不确定数据受到普遍重视，不确定数据的查询处理方法也在很多领域普遍运用。对不确定数据流的查询研究逐步成为数据库领域的热门研究问题之一。本文研究了三种不确定数据流的查询处理算法，分别是分布式不确定数据流的top—k聚集查询算法、不确定

2、数据流的概率skyline查询算法和不确定数据流的聚类算法。Top—k查询技术常用于传感器网络。如今的查询技术大多采取集中式的查询处理形式，时间开销与通信开销较大。针对这一问题，本文研究在分布式环境下不确定数据流的top—k聚集查询算法。首先根据元组数量提出三种聚集算法，然后根据这三个算法提出了一个混合的解决方案，基于混合的解决方案给出top—k聚集算法DAT的框架。实验结果表明DAT算法既能在满足精确度需要的同时降低时间开销，又能在通信开销上好于集中式查询。作为多标准决策等问题的解决方式，skyline查询处理常用于市场分析、目标决策等实际应用。根据

3、现有skyline查询算法的优势和局限性，对于枚举计算方法的低效问题提出一个高效的概率skyline查询算法PSUDS。该方法用自底向上算法得出初步的结果集，然后用插入算法和删除算法对结果集进行更新和维护。不同参数值对p-skyline大小和运行时间的影响结果显示，PSUDS具有良好的扩展性。与Baseline算法进行比较可以看出PSUDS具有较高的效率。聚类方法在数据流上广泛应用，但大部分针对确定数据流。虽然有一些是在不确定数据流上的算法，但算法中大多没有考虑数据的分布。针对这一问题，本文引入KL距离(相对熵)的概念，提出高效的不确定数据流聚类算法K

4、L．Micro。实验结果表明KL—Micro算法充分考虑了不确定数据分布情况，提高了聚类结果质量，具有较高的准确性及效率。通过实验及分析可以得出，以上不确定数据流的查询处理算法精确度较高且具万方数据黑龙江大学硕士学位论文有高效性，具有实际应用价值。关键词：不确定数据流；Top—k；Skyline聚类万方数据AbstractWiththedevelopmentofscienceandtechnologyandthedeepeningofpeople’Scognitiononqueryprocessingmethod，uncertaindatahasatt

5、ractedextensiveaUention，anduncertaindataqueryprocessingmethodbecomeswidelyusedinmanyfieldsResearchonuncertaindatastreamsquerygraduallybecomesoneofthehotresearchtopicsinthefieldofdatabase．Thispaperstudiesthreekindsofuncertaindatastreamsqueryprocessingalgorithms，whicharedistribute

6、dtop—kaggregationqueryalgorithmonuncertaindatastreams，probabilisticskylinequeryalgorithmonuncertaindatastreamsandaclusteringalgorithmonuncertaindatastreams．Top-kquerytechnologyiscommonlyusedinsensornetwork．Theexistingquerytechnologiesmostlyusecentralizedmodeofqueryprocessing，whi

7、chhavealargetimeoverheadandcommunicationoverhead．Inordertosolvethisproblem，thispaperstudiesthetop—kaggregationqueryalgorithmonuncertaindatastreamsindistributedenvironment．Tostartwith，threeaggregationalgorithmsareproposedbasedonnumbersoftuples．Thenahybridsolutioncomesoutwiththese

8、threealgorithms．Theframeworkoftop-kaggregationa