More Web Proxy on the site http://driver.im/

Article

Testing metric properties

Authors:

Dana RonAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 276 - 285

https://doi.org/10.1145/380752.380811

Published: 06 July 2001 Publication History

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 ε far from having the property. In ε far we mean that more than an ε-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 ε 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]

R. Agarwala, V. Bafna, M. Farach, M. Paterson, and M. Thorup. On the approximability ofnumerical taxonomy (fitting distances by tree metrics). SIAM Journal on Computing, 28(3):1073-1085, 1999.]]

Digital Library

[2]

N.Alon, S.Dar, M. Parnas, and D. Ron. Testing of clustering. In Proceedings of the 41st FOCS, pages 240-250, 2000.]]

Digital Library

[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]

N. Alon, M. Krivelevich, I. Newman, and M Szegedy. Regular languages are testable with a constant number of queries. In Proceedings of the 40th FOCS, pages 656-666, 1999.]]

Digital Library

[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. Culberson and P. Rudnicki. A fast algorithm for constructing trees from distance matrices. Information Processing Letters, pages 215-220, 1989.]]

Digital Library

[8]

A. Czumaj, C. Sohler, and M. Ziegler. Property testing in computational geometry. InProceedings of the 8th ESA, pages 155-166, 2000. Lecture Notes in Computer Science edited by M.Paterson, Springer-Verlag, Berlin.]]

Digital Library

[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]

F. Ergun, S. Kannan, S. R. Kumar, R. Rubinfeld, and M. Viswanathan. Spot-checkers. In Proceedings of the 32nd STOC, pages 259-268, 1998.]]

Digital Library

[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]

O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, 45(4):653-750, 1998.]]

Digital Library

[15]

O. Goldreich and D. Ron. Property testing in bounded degree graphs. In Proceedings of the 31st STOC, pages 406-415, 1997. To appear in Algorithmica.]]

Digital Library

[16]

S. Kannan, E. Lawler, and T. Warnow. Determining the evolutionary tree. Journal of Algorithms, 21(1):26-50, 1996.]]

Digital Library

[17]

M. Krivanek. The complexity of ultrametric partitions on graphs. Information Processing Letters, 27:265-270, 1988.]]

Digital Library

[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]

R. Rubinfeld and M. Sudan. Robust characterization of polynomials with applications to program testing. SIAM Journal on Computing, 25(2):252-271, 1996.]]

Digital Library

[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.]]

Cited By

Fan CLi P(2022)Metric Nearness with Minimum Distortion: Optimal and Approximation2022 IEEE Information Theory Workshop (ITW)10.1109/ITW54588.2022.9965888(434-439)Online publication date: 1-Nov-2022
https://doi.org/10.1109/ITW54588.2022.9965888
Fichtenberger HRohde D(2018)A theory-based evaluation of nearest neighbor models put into practiceProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327757.3327780(6743-6754)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327757.3327780
Sidiropoulos AWang DWang YKlein P(2017)Metric embeddings with outliersProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039729(670-689)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039729
Show More Cited By

Index Terms

Testing metric properties
1. Mathematics of computing

Recommendations

Testing metric properties

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 ...
Properties of several metric spaces of fuzzy sets
Abstract
This paper discusses the properties of the spaces of fuzzy sets in a metric space equipped with the endograph metric and the sendograph metric, respectively. We first give some relations among the endograph metric, the sendograph metric and the Γ-...
Toward a Software Testing and Reliability Early Warning Metric Suite
ICSE '04: Proceedings of the 26th International Conference on Software Engineering

The field reliability is measured too late for affordablyguiding corrective action to improve the quality of thesoftware. Software developers can benefit from an earlywarning of their reliability while they can still affordablyreact. This early warning ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
42
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fan CLi P(2022)Metric Nearness with Minimum Distortion: Optimal and Approximation2022 IEEE Information Theory Workshop (ITW)10.1109/ITW54588.2022.9965888(434-439)Online publication date: 1-Nov-2022
https://doi.org/10.1109/ITW54588.2022.9965888
Fichtenberger HRohde D(2018)A theory-based evaluation of nearest neighbor models put into practiceProceedings of the 32nd International Conference on Neural Information Processing Systems10.5555/3327757.3327780(6743-6754)Online publication date: 3-Dec-2018
https://dl.acm.org/doi/10.5555/3327757.3327780
Sidiropoulos AWang DWang YKlein P(2017)Metric embeddings with outliersProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039729(670-689)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039729
Li YWang ZWoodruff DMacskassy SPerlich CLeskovec JWang WGhani R(2014)Improved testing of low rank matricesProceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining10.1145/2623330.2623736(691-700)Online publication date: 24-Aug-2014
https://dl.acm.org/doi/10.1145/2623330.2623736
Czumaj ASohler C(2005)Testing hypergraph colorabilityTheoretical Computer Science10.1016/j.tcs.2004.09.031331:1(37-52)Online publication date: 15-Feb-2005
https://dl.acm.org/doi/10.1016/j.tcs.2004.09.031
Krauthgamer RSasson O(2003)Property testing of data dimensionalityProceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/644108.644112(18-27)Online publication date: 12-Jan-2003
https://dl.acm.org/doi/10.5555/644108.644112
Parnas MRon D(2003)Testing metric propertiesInformation and Computation10.1016/S0890-5401(03)00160-3187:2(155-195)Online publication date: 15-Dec-2003
https://dl.acm.org/doi/10.1016/S0890-5401%2803%2900160-3
Bollig BWegener I(2003)Functions that have read-once branching programs of quadratic size are not necessarily testableInformation Processing Letters10.1016/S0020-0190(03)00230-887:1(25-29)Online publication date: 16-Jul-2003
https://dl.acm.org/doi/10.1016/S0020-0190%2803%2900230-8
Halevy SKushilevitz E(2003)Distribution-Free Property TestingApproximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques10.1007/978-3-540-45198-3_26(302-317)Online publication date: 2003
https://doi.org/10.1007/978-3-540-45198-3_26
Czumaj ASohler C(2001)Testing Hypergraph ColoringAutomata, Languages and Programming10.1007/3-540-48224-5_41(493-505)Online publication date: 4-Jul-2001
https://doi.org/10.1007/3-540-48224-5_41

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten