基于EMD的概率数据top-k相似性连接  

Top-k Similarity Joins on Probabilistic Data Based on Earth Mover's Distance

作　　者：许嘉[1] 于戈[1] 谷峪[1] 白秋石[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819

出　　处：《东北大学学报（自然科学版）》2011年第5期634-637,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(6100305860933001);中央高校基本科研业务费青年教师科研启动基金资助项目(N100704001)

摘　　要：选取EMD(earth mover’s distance)作为度量概率数据相似性的标准.EMD具有抗噪性好,对概率分布间的微小偏移不敏感等优良特性,但却具有三次方的复杂度.针对此问题,提出EMD-kJoin算法,在相似性搜索方面,基于线性规划的对偶理论为概率数据构建索引,避免不必要的EMD求精计算;在处理流程方面,以复杂度较低的范围查询为主要操作,并逐步缩小搜索阈值.通过使用真实数据集对EMD-k Join进行测试,证明EMD-k Join极大提高了基于EMD的概率数据top-k相似性连接操作的执行效率.Use the EMD（earth mover＇s distance） to measure the similarity between two probabilistic records.EMD is robust to outliers and minute probability shifting,but has a cubic time complexity.An algorithm,EMD-k Join,is proposed that speeds up the EMD-based similarity search by constructing an index for probabilistic data using the primal-dual theory in linear programming and thus eliminates unnecessary EMD calculations.Meanwhile, it improves performance of the join process by adopting range query as the main operation and gradually shrinking the search range.Experimental results on real data sets show that EMD-k Join dramatically improves efficiency of EMD-based top-k joins on probabilistic data.

关 键 词：Top-k相似性连接 概率数据管理 EMD 对偶理论 B+树索引 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]