Indexing the Earth Mover’s Distance Using Normal Distributions

Summary: Accelerates EMD-based k-NN over uncertain data with a projection lower bound, approximating distributions as normals plus error. Embeds normals via a Hough transform and exploits stochastic dominance for scalable indexing, including heterogeneous datasets. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h5712faee4069fc58
Venue: VLDB
Year: 2012
Pagerank: 5.7249454e-05
Overall Rank: 6,641 | 55.36%
DOI: 10.14778/2078331.2078336

Incoming Non-self Citations Over Time

Authors

1. Brian E. Ruttenberg (University of California Santa Barbara)
2. Ambuj K. Singh (University of California Santa Barbara)

BibTeX Citation

@article{ruttenberg_vldb12,
        title = {{Indexing the Earth Mover’s Distance Using Normal Distributions}},
        author = {Ruttenberg, Brian E. and Singh, Ambuj K.},
        journal = {PVLDB},
        series = {{VLDB} '12},
        volume = {5},
        number = {3},
        pages = {205--216},
        doi = {10.14778/2078331.2078336},
        url = {https://doi.org/10.14778/2078331.2078336},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,533	Earth Mover’s Distance based Similarity Search at Scale	2014	VLDB	6.0923371e-05
11,885	Fast Dataset Search with Earth Mover's Distance	2022	VLDB	4.9793485e-05
12,397	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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.0010679641
193	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00025648171
478	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017631293
3,413	Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction	2008	SIGMOD	7.3250313e-05
4,196	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.7421052e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,882	Indexing Uncertain Data	2009	PODS
2	7,165	Nearest Neighbor Searching Under Uncertainty II	2013	PODS
3	11,885	Fast Dataset Search with Earth Mover's Distance	2022	VLDB
4	2,104	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB
5	5,533	Earth Mover’s Distance based Similarity Search at Scale	2014	VLDB
6	1,518	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB
7	7,584	Effectively Indexing Uncertain Moving Objects for Predictive Queries	2009	VLDB
8	1,635	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
9	4,835	Nearest-Neighbor Searching Under Uncertainty	2012	PODS
10	4,196	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB