{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T21:13:25Z","timestamp":1760044405415},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>\n            Probabilistic data is coming as a new deluge along with the technical advances on geographical tracking, multimedia processing, sensor network and RFID. While similarity search is an important functionality supporting the manipulation of probabilistic data, it raises new challenges to traditional relational database. The problem stems from the limited effectiveness of the distance metric supported by the existing database system. On the other hand, some complicated distance operators have proven their values for better distinguishing ability in the probabilistic domain. In this paper, we discuss the similarity search problem with the\n            <jats:italic>Earth Mover's Distance<\/jats:italic>\n            , which is the most successful distance metric on probabilistic histograms and an expensive operator with cubic complexity. We present a new database approach to answer range queries and k-nearest neighbor queries on probabilistic data, on the basis of Earth Mover's Distance. Our solution utilizes the primal-dual theory in linear programming and deploys\n            <jats:italic>B<\/jats:italic>\n            <jats:sup>+<\/jats:sup>\n            tree index structures for effective candidate pruning. Extensive experiments show that our proposal dramatically improves the scalability of probabilistic databases.\n          <\/jats:p>","DOI":"10.14778\/1920841.1920938","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"758-769","source":"Crossref","is-referenced-by-count":27,"title":["Efficient and effective similarity search over probabilistic data based on earth mover's distance"],"prefix":"10.14778","volume":"3","author":[{"given":"Jia","family":"Xu","sequence":"first","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony K. H.","family":"Tung","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ge","family":"Yu","sequence":"additional","affiliation":[{"name":"Northeastern University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"T. lehmann et al. irma project site. http:\/\/ganymed.imib.rwth-aachen.de\/irma\/.  T. lehmann et al. irma project site. http:\/\/ganymed.imib.rwth-aachen.de\/irma\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559816"},{"key":"e_1_2_1_3_1","first-page":"1151","volume-title":"VLDB","author":"Agrawal P.","year":"2006","unstructured":"P. Agrawal , O. Benjelloun , A. D. Sarma , C. Hayworth , S. U. Nabar , T. Sugihara , and J. Widom . Trio: A system for data, uncertainty, and lineage . In VLDB , pages 1151 -- 1154 , 2006 . P. Agrawal, O. Benjelloun, A. D. Sarma, C. Hayworth, S. U. Nabar, T. Sugihara, and J. Widom. Trio: A system for data, uncertainty, and lineage. In VLDB, pages 1151--1154, 2006."},{"key":"e_1_2_1_4_1","first-page":"343","volume-title":"SODA","author":"Andoni A.","year":"2008","unstructured":"A. Andoni , P. Indyk , and R. Krauthgamer . Earth mover distance over high-dimensional spaces . In SODA , pages 343 -- 352 , 2008 . A. Andoni, P. Indyk, and R. Krauthgamer. Earth mover distance over high-dimensional spaces. In SODA, pages 343--352, 2008."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.25"},{"key":"e_1_2_1_6_1","first-page":"953","volume-title":"VLDB","author":"Benjelloun O.","year":"2006","unstructured":"O. Benjelloun , A. D. Sarma , A. Y. Halevy , and J. Widom . Uldbs: Databases with uncertainty and lineage . In VLDB , pages 953 -- 964 , 2006 . O. Benjelloun, A. D. Sarma, A. Y. Halevy, and J. Widom. Uldbs: Databases with uncertainty and lineage. In VLDB, pages 953--964, 2006."},{"key":"e_1_2_1_7_1","first-page":"1271","volume-title":"VLDB","author":"Cheng R.","year":"2005","unstructured":"R. Cheng , S. Singh , and S. Prabhakar . U-dbms: A database system for managing constantly-evolving data . In VLDB , pages 1271 -- 1274 , 2005 . R. Cheng, S. Singh, and S. Prabhakar. U-dbms: A database system for managing constantly-evolving data. In VLDB, pages 1271--1274, 2005."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.75"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316764"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265531"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0159-3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2004.1315035"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376685"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497596"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/261124.261131"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687685"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1058"},{"key":"e_1_2_1_19_1","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1998","unstructured":"C. H. Papadimitriou and K. Steiglitz . Combinatorial Optimization: Algorithms and Complexity . Dover Publications , 1998 . C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367934"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/938978.939133"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2009.5206834"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276319"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587662"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386119"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272745"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016028.1016030"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376639"},{"key":"e_1_2_1_30_1","volume-title":"Tra5-10: Efficient and effective similarity search over probabilistic data based on earth mover's distance, national university of singapore","author":"Xu J.","year":"2010","unstructured":"J. Xu , Z. Zhang , A. K. Tung , and G. Yu . Tra5-10: Efficient and effective similarity search over probabilistic data based on earth mover's distance, national university of singapore , 2010 . J. Xu, Z. Zhang, A. K. Tung, and G. Yu. Tra5-10: Efficient and effective similarity search over probabilistic data based on earth mover's distance, national university of singapore, 2010."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687630"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920938","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:35:25Z","timestamp":1672227325000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920938"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920938"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920938","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}