不确定数据集上top-k查询与优化算法的-研究

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

1、万方数据东北大学硕士学位论文摘要APT4U—Topk算法应用到分布式环境中，提出了DAPT4UTop—k算法。DAPT4U．Topk算法避免了节点端发送全部本地元组，有效地减少分布式系统中的通信开销。但是，在某些数据集情况下，节点依然需要上传大部分数据，DAPT4U．Topk算法的通信代价和时间复杂度依然较高。针对在某些数据集上U．Topk查询需要展开全部可能世界模型，查询优化算法失效的情况，论文在最后～个部分提出了MPUTop．k查询优化算法。MPUTop．k的语义是返回概率最大的可能世界模型实例的Top．k向

2、量。因为MPUTop．k不需要计算全部可能世界模型概率，因此更具有实际应用价值。进一步，我们将MPUTop．k查询优化算法应用到分布式环境中，提出了DMPUTop．k算法。由于全局MPUTop—k算法和各个结点局部MPUTop．k算法的返回的结果相同，因此DMPUTop．k算法可应用于多跳地分布式环境中。特别地，文中证明了如果可能世界模型空间中某个实例的概率不小于0．5时，从查询结果的角度来看，MPUTop—k和U-Topk查询是等价的。这个结论为U—Topk查询处理提供了一种近似计算的方法。文中对上述工作进行了

3、详细的过程说明和算法描述，包括必要的理论证明用以说明算法的正确性，同时还使用来自于生产实际的真实数据集和部分模拟数据集对所提算法的性能进行了实验验证。关键字：不确定性数据；集中式；分布式；Top—k查询；U．Topk查询III万方数据东北大学硕士学位论文AbstractResearchonTop-·kQueriesOptimizingAlgorithmonUncertainDatasetAbstractTop·kquerytechnologyisusedwidely,whichistofindoutthehigh

4、estkresultaccordingtotheuser-definedscoringfunction．Inthetraditionaldeterministicdatabase，Top-kqueryhasitsclearsemantics，andresearchershaveproposedvariouskindofoptimizedprocessingalgorithm．However,withthedevelopmentofdataacquisitionanddataprocessingtechnology

5、,inmoreandmoreapplicationfielduncertaindataisdiscovered，suchasWirelessSensorNetworks(WSN)，RFIDsystem，mobilecomputing，etc．Uncertaindataisgettingmoreandmoreattentionfromtheacademicandbecomeahotresearchissue．Intraditionaldatabase，Top—kqueryprocessingonlyconsider

6、stheorderofscoringfunctionvalue．However,Top—kqueryonuncertaindatashouldconsiderboththescoringfunctionvalueandtheuncertainty．So，Top-kquerytechnologyondeterministicdatabaseCan’tbestraightlyimmigratedtotheuncertaindatabase．Inpreviouswork，researchershaveproposeds

7、everalTOp—kquerysemanticsonuncertaindata．However,mostofthemdoesn’tconsiderqueryoptimizaitonprobleminsomespecificsemantics．Inaddition，thecurrentuncertaindatamanagementandTOp—kqueryprocessingmethodarealwaysbasedoncentralizeddatabaseordataflow．Inpractice，moreunc

8、ertaindataisderivedfromdistributedsystems．IfcentralizedmthodforTop—kqueryprocessingisadoptedtodistributeduncertaindataset，Itmeanseachnodemustreportallitsdatatothesinknode，whichwillbringgr