Abstract: 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.