{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T17:13:40Z","timestamp":1743009220511,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_42","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"515-526","source":"Crossref","is-referenced-by-count":2,"title":["Testing Properties of Sets of Points in Metric Spaces"],"prefix":"10.1007","author":[{"given":"Krzysztof","family":"Onak","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"42_CR1","series-title":"Comtemporary Mathematics","first-page":"189","volume-title":"Conference in Modern Analysis and Probability, New Haven, 1982","author":"W.B. Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conference in Modern Analysis and Probability, New Haven, 1982. Comtemporary Mathematics, vol.\u00a026, pp. 189\u2013206. American Mathematical Society, Providence (1984)"},{"key":"42_CR2","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 10\u201333 (2001)","DOI":"10.1109\/SFCS.2001.959878"},{"issue":"2","key":"42_CR3","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0890-5401(03)00160-3","volume":"187","author":"M. Parnas","year":"2003","unstructured":"Parnas, M., Ron, D.: Testing metric properties. Information and Computation\u00a0187(2), 155\u2013195 (2003)","journal-title":"Information and Computation"},{"key":"42_CR4","unstructured":"Krauthgamer, R., Sasson, O.: Property testing of data dimensionality. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 18\u201327 (2003)"},{"issue":"2","key":"42_CR5","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing\u00a025(2), 252\u2013271 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"42_CR6","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM\u00a045(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Chan, H.T.H., Dhamdhere, K., Gupta, A., Kleinberg, J.M., Neiman, O., Slivkins, A.: Metric embeddings with relaxed guarantees. In: FOCS, pp. 83\u2013100 (2005)","DOI":"10.1109\/SFCS.2005.51"},{"issue":"2","key":"42_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S. Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci.\u00a01(2), 117\u2013236 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"1","key":"42_CR9","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s00453-002-0959-4","volume":"34","author":"J. Feigenbaum","year":"2002","unstructured":"Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.: Testing and spot-checking of data streams. Algorithmica\u00a034(1), 67\u201380 (2002)","journal-title":"Algorithmica"},{"issue":"1","key":"42_CR10","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/BF02716581","volume":"15","author":"H.J. Bandelt","year":"1996","unstructured":"Bandelt, H.J., Chepoi, V.: Embedding metric spaces in the rectilinear plane: a six-point criterion. Discrete & Computational Geometry\u00a015(1), 107\u2013117 (1996)","journal-title":"Discrete & Computational Geometry"},{"key":"42_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF01448840","volume":"100","author":"K. Menger","year":"1928","unstructured":"Menger, K.: Untersuchungen uber allgemeine Metrik. Mathematische Annalen\u00a0100, 75\u2013163 (1928)","journal-title":"Mathematische Annalen"},{"key":"42_CR12","unstructured":"Edmonds, J.: Embedding into $\\ell_\\infty^2$ is easy, embedding into $\\ell_\\infty^3$ is NP-complete. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 522\u2013531 (2007)"},{"key":"42_CR13","first-page":"55","volume":"13","author":"F. Hadlock","year":"1978","unstructured":"Hadlock, F., Hoffman, F.: Manhattan trees. Utilitas Mathematica\u00a013, 55\u201367 (1978)","journal-title":"Utilitas Mathematica"},{"issue":"4","key":"42_CR14","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math.\u00a05(4), 545\u2013557 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. In: ICALP, pp. 249\u2013253 (1990)","DOI":"10.1007\/BFb0032036"},{"key":"42_CR16","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0022-5193(77)90351-4","volume":"64","author":"M.S. Waterman","year":"1977","unstructured":"Waterman, M.S., Smith, T.F., Singh, M., Beyer, W.A.: Additive evolutionary trees. Journal of Theoretical Biology\u00a064, 199\u2013213 (1977)","journal-title":"Journal of Theoretical Biology"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Sampling algorithms: lower bounds and applications. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, pp. 266\u2013275 (2001)","DOI":"10.1145\/380752.380810"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:13:06Z","timestamp":1738325586000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}