{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T05:13:31Z","timestamp":1784265211826,"version":"3.55.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:p>Querying uncertain data sets (represented as probability distributions) presents many challenges due to the large amount of data involved and the difficulties comparing uncertainty between distributions. The Earth Mover's Distance (EMD) has increasingly been employed to compare uncertain data due to its ability to effectively capture the differences between two distributions. Computing the EMD entails finding a solution to the transportation problem, which is computationally intensive. In this paper, we propose a new lower bound to the EMD and an index structure to significantly improve the performance of EMD based K-- nearest neighbor (K--NN) queries on uncertain databases.<\/jats:p><jats:p>We propose a new lower bound to the EMD that approximates the EMD on a projection vector. Each distribution is projected onto a vector and approximated by a normal distribution, as well as an accompanying error term. We then represent each normal as a point in a Hough transformed space. We then use the concept of stochastic dominance to implement an efficient index structure in the transformed space. We show that our method significantly decreases K--NN query time on uncertain databases. The index structure also scales well with database cardinality. It is well suited for heterogeneous data sets, helping to keep EMD based queries tractable as uncertain data sets become larger and more complex.<\/jats:p>","DOI":"10.14778\/2078331.2078336","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"205-216","source":"Crossref","is-referenced-by-count":29,"title":["Indexing the earth mover's distance using normal distributions"],"prefix":"10.14778","volume":"5","author":[{"given":"Brian E.","family":"Ruttenberg","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ambuj K.","family":"Singh","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.25"},{"key":"e_1_2_1_2_1","first-page":"307","volume-title":"ICDE","author":"Assent I.","year":"2008"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089026"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"S. D. Cohen and L. J. Guibas. The earth mover's distance: Lower bounds and invariance under translation. Technical report 1997. S. D. Cohen and L. J. Guibas. The earth mover's distance: Lower bounds and invariance under translation. Technical report 1997.","DOI":"10.21236\/ADA358270"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_6_1","first-page":"220","article-title":"Fast contour matching using approximate earth mover's distance","volume":"1","author":"Grauman K.","year":"2004","journal-title":"IEEE CVPR"},{"key":"e_1_2_1_7_1","volume-title":"McGraw-Hill","author":"Hillier F. S.","year":"1990"},{"key":"e_1_2_1_8_1","unstructured":"P. Hough. Method and means for recognizing complex patterns Dec. 18 1962. US Patent 3 069 654. P. Hough. Method and means for recognizing complex patterns Dec. 18 1962. US Patent 3 069 654."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/375663.375680","volume-title":"ACM SIGMOD","author":"Keogh E.","year":"2001"},{"key":"e_1_2_1_10_1","first-page":"555","volume-title":"Management Science","author":"Levy H.","year":"1992"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_51"},{"key":"e_1_2_1_12_1","first-page":"946","volume-title":"ICDE","author":"Ljosa V.","year":"2007"},{"key":"e_1_2_1_13_1","volume-title":"Prentice Hall","author":"Oppenheim A.","year":"1999"},{"key":"e_1_2_1_14_1","unstructured":"S. Rachev and L. Ruschendorf . Mass Transportation Problems: Theory . Springer series in statistics: Probability and its applications . Springer 1998 . S. Rachev and L. Ruschendorf. Mass Transportation Problems: Theory . Springer series in statistics: Probability and its applications. Springer 1998."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_2_1_16_1","volume-title":"Morgan Kaufmann","author":"Samet H.","year":"2006"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.882482"},{"key":"e_1_2_1_18_1","first-page":"1227","volume-title":"IEEE International Conference on Multimedia and Expo","volume":"2","author":"Srinivasan S.","year":"2004"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.imavis.2009.01.002"},{"key":"e_1_2_1_20_1","first-page":"199","volume-title":"ACM SIGMOD","author":"Wichterich M.","year":"2008"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the VLDB Endowment, 3(1--2):758--769","author":"Xu J.","year":"2010"},{"key":"e_1_2_1_22_1","first-page":"385","volume-title":"VLDB","author":"Yi B.","year":"2000"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1145\/1102351.1102481","volume-title":"ICML","author":"Zhou D.","year":"2005"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2078331.2078336","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,27]],"date-time":"2024-05-27T23:59:27Z","timestamp":1716854367000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2078331.2078336"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["10.14778\/2078331.2078336"],"URL":"https:\/\/doi.org\/10.14778\/2078331.2078336","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,11]]}}}