{"entities":{"Q4933374":{"pageid":6962956,"ns":120,"title":"Item:Q4933374","lastrevid":58362729,"modified":"2026-04-04T21:38:10Z","type":"item","id":"Q4933374","labels":{"en":{"language":"en","value":"Polylogarithmic approximation for edit distance and the asymmetric query complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5799063"}},"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":"Q4933374$B20CABE7-66E1-4AC2-A7A8-C3BECFBDAB72","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5ee60e80bc6b29680c6b954e42182936a7cb7c3","datavalue":{"value":{"text":"Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4933374$300DBD1A-28B8-46D1-9C8C-57437D39E6C6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ebc564f0d7b4831a635ec66773fc87d60216057b","datavalue":{"value":"1309.68228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4933374$A0D17322-F119-4B8C-9D0E-B8A8A18202D6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ebc1725e35109144dee167262476bc9739dd2715","datavalue":{"value":"10.1007/978-3-642-16367-8_16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4933374$F3324EA1-0CD1-4D21-87D9-BEDD4131BA47","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eae9a31d6f758a27f2fb0dd99a7d1baabffdd3ef","datavalue":{"value":{"entity-type":"item","numeric-id":713204,"id":"Q713204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$86A42C56-2318-4EB6-9C7A-4425E4F1DE05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4ab31fa932ebec99543358ca6fa8f0045c7548e","datavalue":{"value":{"entity-type":"item","numeric-id":249078,"id":"Q249078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$3C765F5A-224E-4E65-B2C5-2B151B2526C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"43912d6de9de9a18670bd6c5f7fa4a46eeab49c0","datavalue":{"value":{"entity-type":"item","numeric-id":343846,"id":"Q343846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$B0A654A7-FC9C-4BDB-98E4-22A2B25E5545","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"5dcfb82b5a4f71d8b3d00fe7f0f86b3d86674e54","datavalue":{"value":{"entity-type":"item","numeric-id":4933358,"id":"Q4933358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$323EC551-3770-464A-B22B-C1E3963A5ADA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8268186a71ffa78cd296b9bac558860fe9e35f3f","datavalue":{"value":{"time":"+2010-10-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4933374$4E930701-84D0-459D-A447-E31A8F35031A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d5ed93c3c1baed368605dc2b5f37ba2f19a4701a","datavalue":{"value":"https://arxiv.org/abs/1005.4033","type":"string"},"datatype":"url"},"type":"statement","id":"Q4933374$DB6F1510-171E-49F8-BF9D-10189F9ECD46","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4933374$F8CA9454-83B1-4787-9731-3CEC15978669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4933374$2B7D4805-8BC1-44DB-86F8-A49E1DF48830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4933374$2DD30ACC-8964-475E-932C-9C5277A4D439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4933374$B652AD74-EF12-4B84-8C41-8C0D8DD3189E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"81af830397078409b7ebc77d009c93a4ec93c76f","datavalue":{"value":"5799063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4933374$B1AF1914-4C67-4B95-9B20-F3690D509B2A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91c92c699214b9d1be7a56f31bd929aa164bb428","datavalue":{"value":"edit distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q4933374$8D20F27D-AC36-438E-8543-45C071603856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b75d02aa96eefe42964c24b2e52964b9dd69149a","datavalue":{"value":"sampling","type":"string"},"datatype":"string"},"type":"statement","id":"Q4933374$C7D6AC65-4C21-4E29-B230-D15BC78BA5CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8745712302d28813999fe70c270cd7743c07054b","datavalue":{"value":"query complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4933374$DDB40625-3E59-414C-AEFB-9AE87136085D","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":"Q4933374$42759E44-A5F9-45F8-8849-9B673E7783C7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4ff607e3d45a536968e75be70b7012c0de034f88","datavalue":{"value":"W2949329905","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4933374$C5C789A8-4262-4AC4-BEF9-87B18CFC3EAB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"138d808c1a0d7bbfa300ea1020e86219b9fb4bf4","datavalue":{"value":{"entity-type":"item","numeric-id":4229812,"id":"Q4229812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$F65ACB58-CD0C-4802-8936-BFE463FD0AF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6f12679e730f186e807cbb39398fa0f8075753","datavalue":{"value":{"entity-type":"item","numeric-id":4404425,"id":"Q4404425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$B7031BE4-3F63-4C49-BACC-BE4C5C9F435E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$44185B7A-1F3A-4EDF-871A-DED1584216FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc28553cbd079f414114c265d86a94b6ad484595","datavalue":{"value":{"entity-type":"item","numeric-id":1140994,"id":"Q1140994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$DE61EEED-E982-4B9C-BE11-2D1DD62C8FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68b0f454f3281122c373d744b02f4808cc572d85","datavalue":{"value":{"entity-type":"item","numeric-id":2378530,"id":"Q2378530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$8E5B2FA4-5883-46F8-AB2F-F7321609AB11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b29c6873abbc02300c1cb0f658b3c10af08da0d8","datavalue":{"value":{"entity-type":"item","numeric-id":4388886,"id":"Q4388886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$831B1A26-C036-4082-ABA4-1682A4793E01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27329418648ed5811311868e6639c7ec3f856bdc","datavalue":{"value":{"entity-type":"item","numeric-id":3581511,"id":"Q3581511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$D032A62B-B205-4365-A7A9-C89C3017C112","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b2840b356506435518d4c57b03598b0d3706b52","datavalue":{"value":{"entity-type":"item","numeric-id":5172713,"id":"Q5172713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$64CFC03C-EDE4-4576-B706-8EC0488BA315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849c33b86f8e61f28145f77ac7d3bfa3a56d1d17","datavalue":{"value":{"entity-type":"item","numeric-id":5901101,"id":"Q5901101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$BCA4DBB5-E647-421C-843D-9DF721B10BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b10ec616fa6562d3491dfa0d6a5fe81118b28a9f","datavalue":{"value":{"entity-type":"item","numeric-id":3581249,"id":"Q3581249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$6DF2C60E-9D5B-4C9C-80A5-13C2EC772A2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2dcadb8e195ee2b38e9a1eef2b06860d5848540","datavalue":{"value":{"entity-type":"item","numeric-id":4952617,"id":"Q4952617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$AE4CC5C6-0000-4369-A5DD-1CCC35E93E68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25378c5ba54c710be77387bca23e11ce01b8c09d","datavalue":{"value":{"entity-type":"item","numeric-id":3192009,"id":"Q3192009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$2B1C3DE2-AFDB-476C-8C7F-00BF8D196F8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4d660c59b37881d4c5782fa6012563c9a5299de","datavalue":{"value":{"entity-type":"item","numeric-id":4828999,"id":"Q4828999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$89BD6BEA-9D64-454D-8249-310B63A2F6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"255f2abbf01959438a9ff43f29dd6ddb4cbae804","datavalue":{"value":{"entity-type":"item","numeric-id":2491108,"id":"Q2491108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$882D5C3D-D723-41CC-877E-E1557A4BE3C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c86695286d07f923493469fe0b6d3073f595923c","datavalue":{"value":{"entity-type":"item","numeric-id":3583421,"id":"Q3583421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$7CEC18B9-CC94-418B-A614-B22D6389ED5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb93f3f40d4f7fa05ba4b0493d46d818141218c7","datavalue":{"value":{"entity-type":"item","numeric-id":3068638,"id":"Q3068638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$CAE7E793-D62F-4316-BBCC-55C89F245A1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b5e3ccad20789149437796ad16100c362b7387a","datavalue":{"value":{"entity-type":"item","numeric-id":5417617,"id":"Q5417617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$439C2FE5-6810-4044-8121-A4F9371EA578","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d5515aff75268154bcc49a278d62a52fa663088","datavalue":{"value":{"entity-type":"item","numeric-id":5417608,"id":"Q5417608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$3B7ED992-8457-449E-8D5F-4514C69E7615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1819e4e39996edd82f19faa4a71f0ec40bf9e47","datavalue":{"value":{"entity-type":"item","numeric-id":3579208,"id":"Q3579208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$B0DCBBAC-B29F-4BBB-AB3B-7EDDF984003B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0e3b672d7742cf14899d7e0164d781c95536ede","datavalue":{"value":{"entity-type":"item","numeric-id":5433267,"id":"Q5433267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$631205B7-638C-49C8-8C7C-3B473AF746A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ab61ce3d863a44242c09ccd335a8a05f0ff7118","datavalue":{"value":{"entity-type":"item","numeric-id":1577018,"id":"Q1577018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$07E391FC-2675-4786-B2FF-11194FAF804E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6161e7cb734082ba8b3b446ab2553d952dc4d51d","datavalue":{"value":{"entity-type":"item","numeric-id":4507359,"id":"Q4507359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$8968ECDE-DEB7-44CD-95DD-6359D0389AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"758b3b06f484118518b51cebee562ff96b080c1e","datavalue":{"value":{"entity-type":"item","numeric-id":3581423,"id":"Q3581423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4933374$214B4957-6225-46A8-86A7-B55E9A2AC6A1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"977f40b0ff6ba05d045f3ac21de33c5ca8169574","datavalue":{"value":{"entity-type":"item","numeric-id":5172713,"id":"Q5172713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce00d5c53f6229f50f8f066eade69bb214e108d5","datavalue":{"value":{"amount":"+0.8628825545310974","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4933374$B5ABA794-7946-4C3F-9E33-97145CF05166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c139153c3053980e8e0a6d476fa66ef309d1afe1","datavalue":{"value":{"entity-type":"item","numeric-id":4910578,"id":"Q4910578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2addac5c04f96a367591392a98759ca735bf8587","datavalue":{"value":{"amount":"+0.8627060651779175","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4933374$5ABF2262-C499-48A8-AF60-2A38E5AD1956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94182b0139fad5832be5818b27dbf1c225116dae","datavalue":{"value":{"entity-type":"item","numeric-id":5417608,"id":"Q5417608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5866138fe6b185edc819785857628b5ab2894ac","datavalue":{"value":{"amount":"+0.8287907838821411","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4933374$34BD8FFA-94C8-4E5A-A4D9-C482B21B1934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7513c844a4dc1c0d53b49357a70abf67bdbbd9c","datavalue":{"value":{"entity-type":"item","numeric-id":5056449,"id":"Q5056449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df58afe4ce2d8bdaeb78732313b82e84e7c401de","datavalue":{"value":{"amount":"+0.8239254951477051","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4933374$5E028B37-BEEC-41EF-A8C3-8FF271312760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1267e63db932a9b4f49fd9f5d13a345b516b5666","datavalue":{"value":{"entity-type":"item","numeric-id":3581249,"id":"Q3581249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"917690f3502ef6f46a53b203aba47454d5fc1ec2","datavalue":{"value":{"amount":"+0.8211959004402161","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4933374$34CDEC21-B9C3-454C-8ED3-8C9942578076","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4933374","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4933374"}}}}}