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: 10470
Venue: VLDB
Year: 2011
Pagerank: 5.7844585e-05
Overall Rank: 6,749 | 53.70%
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,112	Fast Large-Scale Trajectory Clustering	2020	VLDB	6.3596697e-05
7,155	VRE: A Versatile, Robust, and Economical Trajectory Data System	2022	VLDB	5.6869288e-05
11,577	Fast Dataset Search with Earth Mover's Distance	2022	VLDB	5.093636e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
28	Nearest Neighbor Queries	1995	SIGMOD	0.00052102434
221	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.00024224879
303	On The Marriage of Lp-norms and Edit Distance	2004	VLDB	0.00021956234
1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010493702
1,685	Closest Pair Queries in Spatial Databases	2000	SIGMOD	0.00010017073
2,974	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.9083221e-05
5,405	GORDER: An Efficient Method for KNN Join Processing	2004	VLDB	6.2291247e-05
6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD	5.8809448e-05

Semantically Similar Papers

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