{"entities":{"Q1108806":{"pageid":1119555,"ns":120,"title":"Item:Q1108806","lastrevid":66735018,"modified":"2026-04-12T12:31:00Z","type":"item","id":"Q1108806","labels":{"en":{"language":"en","value":"A tradeoff between search and update time for the implicit dictionary problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4068308"}},"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":"Q1108806$DC7A9C52-28C1-4CF1-B51B-998D8040BEE2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bab9e3d86317acb8cc4c4f2bb57d8b730bde91d9","datavalue":{"value":{"text":"A tradeoff between search and update time for the implicit dictionary problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1108806$404FECA0-40C0-40BF-89DB-37DFC87D7D4A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"48756c843448357f777cf583ad5fa29956f019be","datavalue":{"value":"0654.68078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108806$761DCA1D-F19C-41F2-8B49-5B1D04D8BDCB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8e847978bd465db295b3005b9f371dce4a8dd121","datavalue":{"value":"10.1016/0304-3975(88)90018-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108806$B1487C9C-787A-46E4-8EBA-DDF7F64A3B7C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bafe71e5b991a8bf89ef6acecffbc39fc3714598","datavalue":{"value":{"entity-type":"item","numeric-id":430835,"id":"Q430835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$5ADE6480-BD4F-4323-BD7F-9FAFE3BF5109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5832eb8522cc074d0d11f3d15788f1238c174fec","datavalue":{"value":{"entity-type":"item","numeric-id":760214,"id":"Q760214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$D201B088-129E-4B92-A528-DF598D704C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9f67cb0cf32cbf6fbdaa6fa8e53737df0b645b88","datavalue":{"value":{"entity-type":"item","numeric-id":287049,"id":"Q287049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$C38D152A-A0DF-485E-AF9A-80C11B991316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb601144f50446ab918878975754b8b11688e0e2","datavalue":{"value":{"entity-type":"item","numeric-id":477097,"id":"Q477097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$71B5B574-F470-4CF4-B933-C0A41F8FCA69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a028a6348dcfc7b43c17e257a75b67ed9a2b7db","datavalue":{"value":{"entity-type":"item","numeric-id":178716,"id":"Q178716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$7D0AB89E-7CF3-46DE-B54E-0E1591CAC07D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$7A92B10F-77D9-4344-8761-06E694124538","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1108806$87751009-3AC2-4C33-AE9C-A4A11A37D3AF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f5ba526456cd66219c228e414edf78ca08b09fc","datavalue":{"value":"An implicit dictionary can be viewed as a set of allowable permutations together with an associated search algorithm and an associated update algorithm (a comparison-based model, with elements drawn from a totally ordered universe, is used in this paper). The authors study lower bounds for the search time, given a constant-time update algorithm. It is proved that if update is easy (constant-time), then situations in which search is difficult (super-logarithmic time) occur. The first and the final paragraphs constitute a very good exposition of related results, ideas and open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108806$7F39AE4C-F4DA-45B9-93F7-B098183975D7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108806$30E431CD-AE67-4F27-A32E-3256719E07CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108806$3403BA9E-954C-4368-8241-7F244CB82B0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108806$66EAA8D4-7D6A-4DA1-A34A-157463C70144","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9054c8985edd9b32eac167a405b785d5e8a70571","datavalue":{"value":"4068308","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108806$48F11E71-FA3B-4B55-B374-951AC304532D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc3b2c9670df3aacf6e2a0965a75323a753cc7c","datavalue":{"value":"implicit dictionary","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108806$621BA71A-E1E2-45E4-A167-4D2F04585A37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c61da4d0f953ae6ac684ebed199df1260b610dc","datavalue":{"value":"update","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108806$F110E98B-C257-48E3-8EE1-4E11442F3984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e26a91fa3877ce4ff4e1cbc4fd7a7c11ebbd1370","datavalue":{"value":"search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1108806$0FC2BBEA-92F4-42F8-A74F-B70D36012E8D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73ebd5021b1f9cabffa6534aa25947283831467f","datavalue":{"value":{"entity-type":"item","numeric-id":790617,"id":"Q790617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$D1B25C47-A797-43D3-B7F7-691C41FBF8F5","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":"Q1108806$FA9A7E24-E1E1-4E5C-8D6B-1C9F131C08A4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6391579303006132d99b2a799af9d2cbbe5b0fd6","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90018-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1108806$6130E2D7-2CD1-4002-B988-EFF5B36E8403","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"67f3cebf474b1443aa2e64a3288dfb2c128cb6a6","datavalue":{"value":"W2069907263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1108806$0706A854-764D-45AD-BDBB-9B05E6D11C4B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7498d642043c715a459f4d497293669889cce883","datavalue":{"value":{"entity-type":"item","numeric-id":3700848,"id":"Q3700848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$E57E9DAA-ECE8-4A5D-ACB3-FE0A5B0EF710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"502e01abb5832bb4467d07bb35e696fe038ea90a","datavalue":{"value":{"entity-type":"item","numeric-id":800083,"id":"Q800083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$30C53CEA-17D0-42C8-B5BD-BC24CABF98D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55318b5f52efbae39ee0db1fca6ade07e04b8071","datavalue":{"value":{"entity-type":"item","numeric-id":1151264,"id":"Q1151264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$27E9F920-30CA-4725-9F8D-39AF8601B540","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0c8a659f7245b4a85efedb83f71c0a5e053efe1","datavalue":{"value":{"entity-type":"item","numeric-id":3962473,"id":"Q3962473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$83C9A03B-5802-4BFB-A30E-0E85629DDD9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c4b432264b1d95c77c217a25bbd889f27e5418d","datavalue":{"value":{"entity-type":"item","numeric-id":1146004,"id":"Q1146004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$881C8007-6408-4CDE-B087-839B1D1EB75A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1c5883e6a323dea257e285e0caa569b30daff64","datavalue":{"value":{"entity-type":"item","numeric-id":3912073,"id":"Q3912073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1108806$7CA94DF5-5DB6-4081-B0F2-BFA05113B479","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7b2dfcbd17a55b6ad412258937905a908ca1a18","datavalue":{"value":{"entity-type":"item","numeric-id":4028917,"id":"Q4028917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61457c307e0e80ba7fe918a92373e16a452df5e2","datavalue":{"value":{"amount":"+0.9190781712532043","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":"Q1108806$F02CCD67-ECA3-4F79-B5CC-B6E7E01BBB54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a20a982f3b567ce273da249f19d2d0a1d018690","datavalue":{"value":{"entity-type":"item","numeric-id":5900747,"id":"Q5900747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"780850055115d3d29e5b954fd00a464e85a122d6","datavalue":{"value":{"amount":"+0.9190778732299804","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":"Q1108806$31E2BEC3-693D-467A-9105-5C734955CF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5c22fced6985426dc3728ba8ca58cc9a80b6fa4","datavalue":{"value":{"entity-type":"item","numeric-id":1607123,"id":"Q1607123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0853e5bf12eb6ad1b53c4c5249ce0f71e1d95fb9","datavalue":{"value":{"amount":"+0.9185641407966614","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":"Q1108806$6CA8EBE7-49E3-4F06-9C86-61C23A586642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e39b1a107f37e91ea4d441b51c396f1f2d520a0a","datavalue":{"value":{"entity-type":"item","numeric-id":4449185,"id":"Q4449185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b239cfc95f91d3df0d4208f0a5fcc606d32304a9","datavalue":{"value":{"amount":"+0.9177650213241576","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":"Q1108806$6ED540BF-15A1-4AD9-8941-0B769416802E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebec14e0505c2d64c5c08bf7b968c0cb1413c3aa","datavalue":{"value":{"entity-type":"item","numeric-id":3725558,"id":"Q3725558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eef54baf564dc84c6b130ec3f82e92a1e04fd27e","datavalue":{"value":{"amount":"+0.9077783823013306","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":"Q1108806$2FB20D92-FB87-4291-8F91-7242FEC4D1AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A tradeoff between search and update time for the implicit dictionary problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_tradeoff_between_search_and_update_time_for_the_implicit_dictionary_problem"}}}}}