Testing metric properties

ABSTRACT

Finite metric spaces, and in particular tree metrics play an important role in various disciplines such as evolutionary biology and statistics. A natural family of problems concerning metrics is deciding, given a matrix M, whether or not it is a distance metric of a certain predetermined type. Here we consider the following relaxed version of such decision problems: For any given matrix M and parameter \eps, we are interested in determining, by probing M, whether M has a particular metric property P, or whether it is &egr; far from having the property. In &egr; far we mean that more than an &egr;-fraction of the entries of M must be modified so that it obtains the property. The algorithm may query the matrix on entries M[i,j] of its choice, and is allowed a constant probability of error.We describe algorithms for testing Euclidean metrics, tree metrics and ultrametrics. Furthermore, we present an algorithm that tests whether a matrix M is an approximate ultrametric. In all cases the query complexity and running time are polynomial in 1 &egr and independent of the size of the matrix. Finally, our algorithms can be used to solve relaxed versions of the corresponding search problems in time that is sub-linear in the size of the matrix.

REFERENCES

• 1: Richa Agarwala , Vineet Bafna , Martin Farach , Mike Paterson , Mikkel Thorup, On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics), SIAM Journal on Computing, v.28 n.3, p.1073-1085, Feb. 1999 [doi>10.1137/S0097539795296334]
• 2: N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
• 3: N. Alon, E. Fischer, M. Krivelevich, and M Szegedy. Efficient testing of large graphs. In Proceedings of the 40th FOCS, pages 645-655, 1999.
• 4: Noga Alon , Michael Krivelevich , Ilan Newman , Mario Szegedy, Regular Languages are Testable with a Constant Number of Queries, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.645, October 17-18, 1999
• 5: J-P Barthelemy and A. Guenoche. Trees and Proximity Representations. Wiley, New York, 1991.
• 6: L. Cavalli-Sforza and A. Edwards. Phylogenetic analysis models and estimation procedures. American Journal of Human Genetics, 19:233-257, 1967.
• 7: J. C. Culberson , P. Rudnicki, A fast algorithm for constructing trees from distance matrices, Information Processing Letters, v.30 n.4, p.215-220, February 1989 [doi>10.1016/0020-0190(89)90216-0]
• 8: Artur Czumaj , Christian Sohler , Martin Ziegler, Property Testing in Computational Geometry, Proceedings of the 8th Annual European Symposium on Algorithms, p.155-166, September 05-08, 2000
• 9: W. H. E. Day. Computational complexity of inferring phylogenies from dissimilarity matrices. Bulletin of Mathematical Biology, 49(4):461-467, 1987.
• 10: A. Dress and V. von Haessler (Eds.). Trees and Hierarchical Structures. Springer Verlag, 1987. Lecture Notes in Bio-Mathematics.
• 11: Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.259-268, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276757]
• 12: M. Farach, S. Kannan, and T. Warnow. A robust model for finding optimal evolutionary trees. Algorithmica, 13(1/2):155-179, 1995.
• 13: J. Felsenstein. Numerical methods for inferring evolutionary trees. Quarterly Review on Biology, 57(4):379-404, 1982.
• 14: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 15: Oded Goldreich , Dana Ron, Property testing in bounded degree graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.406-415, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258627]
• 16: Sampath K. Kannan , Eugene L. Lawler , Tandy J. Warnow, Determining the evolutionary tree using experiments, Journal of Algorithms, v.21 n.1, p.26-50, July 1996 [doi>10.1006/jagm.1996.0035]
• 17: Mirko Křvánek, The complexity of ultrametric partitions on graphs, Information Processing Letters, v.27 n.5, p.265-270, April 28, 1988 [doi>10.1016/0020-0190(88)90090-7]
• 18: M. Parnas and D. Ron. Testing metric properties. Available from: http://www.eng.tau.ac.il/~danar, 2000.
• 19: D. Ron. Property testing. To appear in the Handbook on Randomization. Currently available from: http://www.eng.tau.ac.il/~danar, 2000.
• 20: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
• 21: P. H. A. Sneath and R. R. Sokal. Numerical Taxonomy. W.H.Freeman, 1973.
• 22: P. Turan. On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok, 48:436-452, 1941.
• 23: M. S. Waterman, T. F. Smith, M Singh, and W. A. Beyer. Additive evolutionary trees. Journal of Theoretical Biology, 64:199-213, 1977.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Measurement, Performance, Reliability, Theory, Verification