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: 10659
Venue: VLDB
Year: 2012
Pagerank: 5.8560106e-05
Overall Rank: 6,513 | 55.32%
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,407	Earth Mover’s Distance based Similarity Search at Scale	2014	VLDB	6.2281449e-05
11,577	Fast Dataset Search with Earth Mover's Distance	2022	VLDB	5.093636e-05
12,104	Supporting Data Uncertainty in Array Databases	2015	SIGMOD	5.093636e-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.0010828372
190	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00026105472
468	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017986163
3,353	Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction	2008	SIGMOD	7.492706e-05
4,112	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.8944534e-05

Semantically Similar Papers

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