An Incremental Hausdorff Distance Calculation Algorithm

Summary: Introduces an incremental Hausdorff-distance algorithm that simultaneously traverses indexes on both point sets, avoiding linear scans and exploiting MAX-MIN structure. For trajectory similarity, it reduces tree-traversal cost and response time by an order of magnitude. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h4d4ebaf8444addc1
Venue: VLDB
Year: 2011
Pagerank: 5.6812765e-05
Overall Rank: 6,790 | 54.35%
DOI: 10.14778/2002974.2002978

Incoming Non-self Citations Over Time

Authors

1. Sarana Nutanong (University of Maryland)
2. Edwin H. Jacox (University of Maryland)
3. Hanan Samet (University of Maryland)

BibTeX Citation

@article{nutanong_vldb11,
        title = {{An Incremental Hausdorff Distance Calculation Algorithm}},
        author = {Nutanong, Sarana and Jacox, Edwin H. and Samet, Hanan},
        journal = {PVLDB},
        series = {{VLDB} '11},
        volume = {4},
        number = {8},
        pages = {506--517},
        doi = {10.14778/2002974.2002978},
        url = {https://doi.org/10.14778/2002974.2002978},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,011	Fast Large-Scale Trajectory Clustering	2020	VLDB	6.3148258e-05
5,743	VRE: A Versatile, Robust, and Economical Trajectory Data System	2022	VLDB	6.0099017e-05
11,885	Fast Dataset Search with Earth Mover's Distance	2022	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
227	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.0002393284
306	On The Marriage of Lp-norms and Edit Distance	2004	VLDB	0.00021575844
1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010275036
1,719	Closest Pair Queries in Spatial Databases	2000	SIGMOD	9.7976056e-05
3,034	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.7330662e-05
5,532	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.0932822e-05
6,540	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.7523628e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,540	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD
2	1,157	A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space	1997	PODS
3	12,840	The Power of Two Min-Hashes for Similarity Search among Hierarchical Data Objects	2008	PODS
4	5,796	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
5	11,982	Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering*	2021	SIGMOD
6	6,704	Distance-Sensitive Hashing	2018	PODS
7	1,304	Continuous Nearest Neighbor Search	2002	VLDB
8	2,021	Distributed Trajectory Similarity Search	2017	VLDB
9	10,326	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
10	20	Similarity Search in High Dimensions via Hashing	1999	VLDB