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.7033967e-05
Overall Rank: 6,657 | 55.38%
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,558	Earth Mover’s Distance based Similarity Search at Scale	2014	VLDB	6.0703095e-05
11,935	Fast Dataset Search with Earth Mover's Distance	2022	VLDB	4.9605343e-05
12,446	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	4.9605343e-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.0010688884
198	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00025558119
481	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017567157
3,424	Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction	2008	SIGMOD	7.2974683e-05
4,216	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.717297e-05

Semantically Similar Papers

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