Abstract
The Hausdorff distance is commonly used as a similarity measure between two point sets. Using this measure, a set X is considered similar to Y iff every point in X is close to at least one point in Y. Formally, the Hausdorff distance HausDist(X, Y) can be computed as the Max-Min distance from X to Y, i.e., find the maximum of the distance from an element in X to its nearest neighbor (NN) in Y. Although this is similar to the closest pair and farthest pair problems, computing the Hausdorff distance is a more challenging problem since its Max-Min nature involves both maximization and minimization rather than just one or the other. A traditional approach to computing HausDist(X, Y) performs a linear scan over X and utilizes an index to help compute the NN in Y for each x in X. We present a pair of basic solutions that avoid scanning X by applying the concept of aggregate NN search to searching for the element in X that yields the Hausdorff distance. In addition, we propose a novel method which incrementally explores the indexes of the two sets X and Y simultaneously. As an example application of our techniques, we use the Hausdorff distance as a measure of similarity between two trajectories (represented as point sets). We also use this example application to compare the performance of our proposed method with the traditional approach and the basic solutions. Experimental results show that our proposed method outperforms all competitors by one order of magnitude in terms of the tree traversal cost and total response time.
- P. K. Agarwal, S. Har-Peled, M. Sharir, and Y. Wang. Hausdorff distance under translation for points and balls. In SCG, pages 282--291, 2003. Google ScholarDigital Library
- H. Alt, O. Aichholzer, and G. Rote. Matching shapes with a reference point. In SCG, pages 85--92, 1994. Google ScholarDigital Library
- H. Alt, B. Behrends, and J. Blömer. Approximate matching of polygonal shapes (extended abstract). In SCG, pages 186--193, 1991. Google ScholarDigital Library
- C. Andújar, P. Brunet, and D. Ayala. Topology-reducing surface simplification using a discrete solid representation. ACM Trans. Graph., 21(2):88--105, 2002. Google ScholarDigital Library
- W. G. Aref and I. F. Ilyas. An extensible index for spatial databases. In SSDBM, pages 49--58, 2001. Google ScholarDigital Library
- F. Aurenhammer. Voronoi diagrams - a survey of a fundamental geometric data structure. ACM Comput. Surv., 23(3):345--405, 1991. Google ScholarDigital Library
- N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In SIGMOD, pages 322--331, 1990. Google ScholarDigital Library
- N. Beckmann and B. Seeger. A revised R*-tree in comparison with related index structures. In SIGMOD, pages 799--812, 2009. Google ScholarDigital Library
- D. Berndt and J. Clifford. Using dynamic time warping to find patterns in time series. AAAI Workshop on Knowledge Discovery in Databases, pages 229--248, 1994.Google Scholar
- L. Chen and R. Ng. On the marriage of lp-norms and edit distance. VLDB, pages 792--803, 2004. Google ScholarDigital Library
- L. Chen, M. T. Özsu, and V. Oria. Robust and fast similarity search for moving object trajectories. SIGMOD, pages 491--502, 2005. Google ScholarDigital Library
- A. Corral, Y. Manolopoulos, Y. Theodoridis, and M. Vassilakopoulos. Closest pair queries in spatial databases. In SIGMOD, pages 189--200, 2000. Google ScholarDigital Library
- A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD, pages 47--57, 1984. Google ScholarDigital Library
- J. Hershberger and J. Snoeyink. Speeding up the douglas-peucker line-simplification algorithm. In Intl. Symp. on Spatial Data Handling, pages 134--143, 1992.Google Scholar
- G. R. Hjaltason and H. Samet. Incremental distance join algorithms for spatial databases. In SIGMOD, pages 237--248, 1998. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. ACM Trans. Database Syst., 24(2):265--318, 1999. Google ScholarDigital Library
- D. P. Huttenlocher, K. Kedem, and J. M. Kleinberg. On dynamic voronoi diagrams and the minimum hausdorff distance for point sets under euclidean motion in the plane. In SCG, pages 110--119, 1992. Google ScholarDigital Library
- D. P. Huttenlocher, G. A. Klanderman, and W. Rucklidge. Comparing images using the hausdorff distance. IEEE Trans. Pattern Anal. Mach. Intell., 15(9):850--863, 1993. Google ScholarDigital Library
- P. Indyk and S. Venkatasubramanian. Approximate congruence in nearly linear time. In SODA, pages 354--360, 2000. Google ScholarDigital Library
- E. J. Keogh and C. Ratanamahatana. Exact indexing of dynamic time warping. Knowl. Inf. Syst., 7(3):358--386, 2005. Google ScholarDigital Library
- P.-F. Marteau. Time warp edit distance with stiffness adjustment for time series matching. IEEE Trans. Pattern Anal. Mach. Intell., 31(2):306--318, 2009. Google ScholarDigital Library
- D. Papadias, Y. Tao, K. Mouratidis, and C. K. Hui. Aggregate nearest neighbor queries in spatial databases. ACM Trans. Database Syst., 30(2):529--576, 2005. Google ScholarDigital Library
- N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In SIGMOD, pages 71--79, 1995. Google ScholarDigital Library
- H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan-Kaufmann, San Francisco, 2006. Google ScholarDigital Library
- H. Shin, B. Moon, and S. Lee. Adaptive multi-stage distance join processing. In SIGMOD, pages 343--354, 2000. Google ScholarDigital Library
- M. Vlachos, D. Gunopulos, and G. Kollios. Discovering similar multidimensional trajectories. In ICDE, pages 673--684, 2002. Google ScholarDigital Library
- C. Xia, H. Lu, B. C. Ooi, and J. Hu. Gorder: An efficient method for KNN join processing. In VLDB, pages 756--767, 2004. Google ScholarDigital Library
- Y. Zheng, Q. Li, Y. Chen, X. Xie, and W.-Y. Ma. Understanding mobility based on gps data. In UbiComp, pages 312--321, 2008. Google ScholarDigital Library
- Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations and travel sequences from gps trajectories. In WWW, pages 791--800, 2009. Google ScholarDigital Library
Index Terms
- An incremental Hausdorff distance calculation algorithm
Recommendations
Hausdorff distance under translation for points and balls
We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the article, we consider two sets A,B of balls in Rd, d=2,3, and wish to find a translation t that minimizes the Hausdorff distance between A+t, the ...
Hausdorff distance under translation for points and balls
SCG '03: Proceedings of the nineteenth annual symposium on Computational geometryWe study the shape matching problem under the Hausdorff distance and its variants. Specifically, we consider two sets A,B of balls in Rd, d=2,3, and wish to find a translation t that minimizes the Hausdorff distance between A+t, the set of all balls in ...
Extended Hausdorff distance for spatial objects in GIS
Distance is a fundamental concept in spatial sciences. Spatial distance is a very important parameter to measure the relative positions between spatial objects and to indicate the degree of similarity between neighbouring objects. Indeed, spatial ...
Comments