DBScholar

Back to papers

Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance

Summary: Similarity search on probabilistic data via Earth Mover’s Distance (EMD); range and kNN queries on probabilistic histograms. Primal–dual LP theory with B+ tree indexing enables effective candidate pruning, yielding dramatic scalability gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
10314
Venue
VLDB
Year
2010
Pagerank
6.8944534e-05
Overall Rank
4,112 | 71.79%
DOI
10.14778/1920841.1920939

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{xu_vldb10,
        title = {{Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance}},
        author = {Xu, Jia and Zhang, Zhenjie and Tung, Anthony K.H. and Yu, Ge},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {758--769},
        doi = {10.14778/1920841.1920939},
        url = {https://doi.org/10.14778/1920841.1920939},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank Citing Paper Year Venue Pagerank
3,193 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.649474e-05
5,407 Earth Mover’s Distance based Similarity Search at Scale 2014 VLDB 6.2281449e-05
5,726 Pigeonring: A Principle for Faster Thresholded Similarity Search 2019 VLDB 6.1079184e-05
6,513 Indexing the Earth Mover’s Distance Using Normal Distributions 2012 VLDB 5.8560106e-05
9,355 Optimal Spatial Dominance: An Effective Search of Nearest Neighbor Candidates 2015 SIGMOD 5.282937e-05
11,577 Fast Dataset Search with Earth Mover's Distance 2022 VLDB 5.093636e-05
11,732 MP-RW-LSH: An Efficient Multi-Probe LSH Solution to ANNS-L1 2021 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010828372
50 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00043596705
78 ULDBs: Databases with Uncertainty and Lineage 2006 VLDB 0.00036571789
331 Trio: A System for Data, Uncertainty, and Lineage 2006 VLDB 0.00020936658
574 Management of Probabilistic Data: Foundations and Challenges 2007 PODS 0.00016278855
796 Optimal Multi-Step k-Nearest Neighbor Search 1998 SIGMOD 0.00013932561
1,327 A Unified Approach to Ranking in Probabilistic Databases 2009 VLDB 0.00011141552
1,363 Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach 2008 SIGMOD 0.00011025316
1,638 U-DBMS: A Database System for Managing Constantly-Evolving Data 2005 VLDB 0.00010155338
3,353 Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction 2008 SIGMOD 7.492706e-05
5,764 Indexing Uncertain Data 2009 PODS 6.0955299e-05
7,708 Similarity Search on Bregman Divergence: Towards Non-Metric Indexing 2009 VLDB 5.5628618e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,776 Efficient User-Adaptable Similarity Search in Large Multimedia Databases 1997 VLDB
2 690 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD
3 6,513 Indexing the Earth Mover’s Distance Using Normal Distributions 2012 VLDB
4 50 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB
5 6,561 Efficient Probabilistic Reverse Nearest Neighbor Query Processing on Uncertain Data 2011 VLDB
6 3,548 Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases 2012 VLDB
7 11,577 Fast Dataset Search with Earth Mover's Distance 2022 VLDB
8 3,353 Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction 2008 SIGMOD
9 1,605 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB
10 5,407 Earth Mover’s Distance based Similarity Search at Scale 2014 VLDB