{"entities":{"Q1422397":{"pageid":1433137,"ns":120,"title":"Item:Q1422397","lastrevid":71871477,"modified":"2026-04-14T01:05:46Z","type":"item","id":"Q1422397","labels":{"en":{"language":"en","value":"Low dimensional embeddings of ultrametrics."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2041880"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$0F7DD2A4-D283-4DAF-8C12-D1F67B9F29E4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bcfd3684e58ee1b832be5a220f9b60791a67ebf4","datavalue":{"value":{"text":"Low dimensional embeddings of ultrametrics.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1422397$18B203EC-CEC8-43A6-B46E-6D5DEF73AE9A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af1b7d59d5a011ac3bcd0e76410bec3a1069c965","datavalue":{"value":"1042.54020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422397$CDC40BD2-9B1D-4CC9-AC59-2C6C5D7E2693","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6441b04c78f0db4705bdccbf7117dee8afcd822d","datavalue":{"value":{"entity-type":"item","numeric-id":388454,"id":"Q388454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$03E129C5-B8F4-40E3-BE29-E7EA62FF2591","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2129463e4fb202d617a918e802d846c3730ad87","datavalue":{"value":{"entity-type":"item","numeric-id":610753,"id":"Q610753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$F5025952-CEC8-43A0-93BF-CA31F2D091D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e15064a955e2b0fc1477893d6cd3b38b1f1b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":185634,"id":"Q185634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$FBF5939D-1C60-4A34-85BE-2B4A0DE85B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c81ab3c92f44f395b025a7c9836ac25b0a0d1756","datavalue":{"value":{"entity-type":"item","numeric-id":178480,"id":"Q178480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$8B873677-14DB-4DF2-ADC9-5B0FD6B4E55E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$CAD4333F-6749-4274-A527-DD8CDC3DB288","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1aee94454bbb3bb990b95de2d91d20cd9c9645ff","datavalue":{"value":{"time":"+2004-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1422397$94B286CD-09CB-4EA2-ABCE-E7080B30D583","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3d0eea54894f2b69bc1a794d007fc9a4d7e6f6ac","datavalue":{"value":"In the recent years, low-distortion embeddings of finite metric spaces into normed linear spaces became recognized as a very powerful toolkit for designing efficient algorithms. See \\textit{J.~Matousek} [Chapter 15 in: Lectures on discrete geometry, Spinger, New York (2002; Zbl 0999.52006)] for an introduction to the area.  An \\textit{ultrametric} is a metric space satisfying the condition  \\[ d(x,z)\\leq\\max\\{d(x,y),~d(y,z)\\}~\\forall x,y,z. \\]  It is well known that a finite ultrametric is isometric to a subset of \\(\\ell_2\\) and, hence, to a subset of \\(\\ell_p\\).  The main result of the paper is an estimate for \\(m\\) such that there exist low-distortion embeddings of \\(n\\)-element ultrametrics into \\(\\ell_p^m\\). It is shown that \\(m=O(\\log n)\\). The result is stated and proved in a more general context of hierarchically well-separated trees, introduced by \\textit{Y.~Bartal} [Probabilistic approximation of metric spaces and its algorithmic applications, 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), 184--193, IEEE Comput. Soc. Press, Los Alamitos, CA (1996)].  The result is applied to metric Ramsey-type problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422397$27978B86-0D35-4042-8898-E3A4CDD0ACE1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9934057d10323980704e6b94db4ebac54a6fd5ff","datavalue":{"value":"54E35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422397$C2044F34-83F7-4ACD-9ECA-0561007E7D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422397$BAAFE5AF-2A2D-4B55-A906-37ACC1BA16AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79f8d64a9a918483c4e5229e22c3ea6d9711b362","datavalue":{"value":"46B07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422397$9E8823FB-C1C4-4F51-A85B-43CD426A78D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b1973cb8aec01fefec7c06d3ac452f505442dd21","datavalue":{"value":"54C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422397$561A8150-BB70-4630-8DD1-8A56FBA3B517","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"30b139e5b15fcbfc350f871ab1e96b59f06bfac6","datavalue":{"value":"2041880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422397$E1DE37F4-A198-4E46-B609-2705717C6586","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bf21e1e0c5ad39c665faf75d5865d902c465148","datavalue":{"value":"ultrametric","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422397$468D5B0B-0718-4C39-A312-C6B68849F060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"428585b73b190c77bb2f2924b393d0ce5b07c115","datavalue":{"value":"distortion of an embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422397$6394308B-6B83-4BFB-881A-F4EED38DC5D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79868fa7d2ed2a6553b37c589c14ecdcfeb2d4ec","datavalue":{"value":"Banach space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422397$B6973367-7585-4FA0-9180-00324996389D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"baf33faeaf4a0c3be1451bbec76caca339373d3e","datavalue":{"value":"metric Ramsey theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422397$5691E881-6FC6-4916-83A2-80B7BAA890E8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"14ba19fd9284d2cf0d8decec72dc0f5317181977","datavalue":{"value":{"entity-type":"item","numeric-id":394136,"id":"Q394136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$0E17C407-3E01-4C49-B253-7B74D9FC33A2","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$77C01D65-3CCE-4D21-9B93-A559E96F7E81","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"00490022f02a4ffb35b089d6d3d206fc2afecf19","datavalue":{"value":"https://doi.org/10.1016/j.ejc.2003.08.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q1422397$7E38B6AB-C341-404D-80E1-99BACA7A881B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"62c5d4e374349b71acbc015535218b8c75cd098f","datavalue":{"value":"W2016332796","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422397$360843BE-5044-40C9-BAFA-FC7BB36F2221","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c9d868e83d6afc00e6cf62466ea7476106e9dfc","datavalue":{"value":{"entity-type":"item","numeric-id":4725539,"id":"Q4725539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$80D42D5B-BDE2-4BA9-8E5C-E5D6F877C215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad82fd8c87f038994d369493a830aa027d225a7d","datavalue":{"value":{"entity-type":"item","numeric-id":4542533,"id":"Q4542533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$FFE121DA-2110-45F1-B751-367F8210CDBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95672c743a77218c6d02ab7cc752b972964f1d8a","datavalue":{"value":{"entity-type":"item","numeric-id":5901089,"id":"Q5901089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$E51B7224-603B-4F3A-95CB-28FBAC487870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3bad3c5b5846738240b5cf22734a1596c4299f3","datavalue":{"value":{"entity-type":"item","numeric-id":2751735,"id":"Q2751735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$D2881FB1-871A-4561-9154-215C7E1C5945","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90b6fe1e6ca9f0f96e89b69032dd74b5fee6b7a3","datavalue":{"value":{"entity-type":"item","numeric-id":3326256,"id":"Q3326256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$F0900667-8FB4-4AE7-805D-76CD726144AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c9025f7a5272d444a4e4ca842ab7414d63870f9","datavalue":{"value":{"entity-type":"item","numeric-id":1246147,"id":"Q1246147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422397$3B5176C8-4544-40B0-969B-79214317CD58","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"11413c2234aa8b044af6512c7eb1d70a1f0e2da3","datavalue":{"value":"10.1016/J.EJC.2003.08.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422397$51AAD169-298D-482E-B133-401C347C8974","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4fd66e7143b50910c0e5fba57bff27cf1da772fe","datavalue":{"value":{"entity-type":"item","numeric-id":2382346,"id":"Q2382346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23bc95ce7bec481430dd61b5054248547ac294e9","datavalue":{"value":{"amount":"+0.8400272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422397$0CB0BC65-9568-424C-90A0-8B5D5EA2440A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bde1dda0004b2a1e50390cb91602796f09403588","datavalue":{"value":{"entity-type":"item","numeric-id":4651533,"id":"Q4651533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b8940e1bc504198e92a570f07e5061104b20924","datavalue":{"value":{"amount":"+0.78874385","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422397$BF190017-46F9-41AD-AA4D-C164D3F9A1D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27a0930dca702c8280059eb591708ad186425607","datavalue":{"value":{"entity-type":"item","numeric-id":2968104,"id":"Q2968104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40e6192ea5eb5bb90b76d7b4f84cbf7c7587bc01","datavalue":{"value":{"amount":"+0.788063","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422397$980367C0-8AAA-4600-B3D0-04FC6E64651E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ae435a37cab822a4b0bc2db169b6f1bd50a15f4","datavalue":{"value":{"entity-type":"item","numeric-id":4542534,"id":"Q4542534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e37a6c6bd6e47b17b6a8a9d60f6f9daad42dc5d6","datavalue":{"value":{"amount":"+0.7864653","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422397$B3AB7D20-9224-4B51-9154-7A9388888324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc56f00ae6a69e0f5da5b446e2902dc49fd8f0a1","datavalue":{"value":{"entity-type":"item","numeric-id":2819599,"id":"Q2819599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99c0046819987c2610b3b891afadc7ca7deba7be","datavalue":{"value":{"amount":"+0.7846406","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422397$ED2BAA9F-1991-4682-BE22-889520BDA656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc8cba36787fdcbfd4c6c587eb5f32ce2fd7329d","datavalue":{"value":{"entity-type":"item","numeric-id":2934632,"id":"Q2934632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c55aeb9db876f3980593786f270af195d15afeea","datavalue":{"value":{"amount":"+0.77270705","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422397$A1BEF558-4942-4577-AA2A-310554D694AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"355bf39c8af0fc401575351938f8ed5cd6a4e35c","datavalue":{"value":{"entity-type":"item","numeric-id":5501324,"id":"Q5501324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41a29e9abf6f7ed63edcaf6cab2221c87000dbbc","datavalue":{"value":{"amount":"+0.76904625","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422397$06E30709-1457-41EA-9795-C7D52D313435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bbdce4eeafe2dbd4b2bbf11e25e9b0c373e6570","datavalue":{"value":{"entity-type":"item","numeric-id":4633900,"id":"Q4633900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"372c96096d5615be713e2263b6927b366bb31262","datavalue":{"value":{"amount":"+0.76492107","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422397$A67D8685-9F2B-4FD3-A0B7-EBA39EBC6BBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"658d24e9afae689c1f4639a8cba72446afad302a","datavalue":{"value":{"entity-type":"item","numeric-id":5252661,"id":"Q5252661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8899868f96c4705264c223faecf7ef20ef98e9e9","datavalue":{"value":{"amount":"+0.764463","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1422397$6657673C-8DC3-49EC-8E80-D066585CD993","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Low dimensional embeddings of ultrametrics.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Low_dimensional_embeddings_of_ultrametrics."}}}}}