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

选取EMD(earth mover’s distance)作为度量概率数据相似性的标准.EMD具有抗噪性好,对概率分布间的微小偏移不敏感等优良特性,但却具有三次方的复杂度.针对此问题,提出EMD-kJoin算法,在相似性搜索方面,基于线性规划的对偶理论为概率数据构建索引,避免不必要的EMD求精计算;在处理流程方面,以复杂度较低的范围查询为主要操作,并逐步缩小搜索阈值.通过使用真实数据集对EMD-k Join进行测试,证明EMD-k Join极大提高了基于EMD的概率数据top-k相似性连接操作的执行效率.

Top-k similarity joins on probabilistic data based on earth mover's distance

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.