{"entities":{"Q1112590":{"pageid":1123339,"ns":120,"title":"Item:Q1112590","lastrevid":69672201,"modified":"2026-04-13T08:36:52Z","type":"item","id":"Q1112590","labels":{"en":{"language":"en","value":"A lower bound for finding predecessors in Yao's cell probe model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4078773"}},"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":"Q1112590$E89971DB-A6DE-40E7-A63F-067F95A59DD2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bd28527f35cca55c676af7f9f0aef8fcafd6973e","datavalue":{"value":{"text":"A lower bound for finding predecessors in Yao's cell probe model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1112590$E30C35F2-0412-43EF-95AE-F1D52A3E66FC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3ee8412ae7c8ba8c148ff38bb054003a55ef2497","datavalue":{"value":"0659.68030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112590$805A8D0B-D6C6-4BA5-9620-8953957BFDDF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"947446c2efe45223bdeb2484903d27504ffa422d","datavalue":{"value":"10.1007/BF02126797","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112590$F5872550-12A9-414C-AEA3-3AB5F155EC3F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112590$A8EFC386-B461-48E0-AB45-C6CA501A5598","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":"Q1112590$E80ABA9A-B38A-467F-8EFE-5B7E72E77C3F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7496547883ac7b246c7f80458202d5cccf1972b6","datavalue":{"value":"Let L be the set consisting of the first q positive integers. We prove that there does not exist a data structure for representing an arbitrary subset A of L which uses poly(\\(| A|)\\) cells of memory (where each cell holds c log q bits of information) and which the predecessor in A of an arbitrary \\(x\\leq q\\) can determine by probing only a constant (independent of q) number of cells. Actually our proof gives more: the theorem remains valid if this number is less than \\(\\epsilon\\) log log q, that is \\textit{D. E. Willard}'s algorithm [Inf. Process. Lett. 17, 81-84 (1983; Zbl 0509.68106)] for finding the predecessor in O(log log q) time is optimal up to a constant factor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112590$1888E68A-32D1-4960-9AFD-E25B5E4EDFB4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112590$5D78B812-C86A-4F26-8F6D-8C16D67BFCA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112590$7BBF016D-D81B-4691-9E68-22E0F9579486","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5887b7ad1ec5efed1d2ab791a957a2a47057b06c","datavalue":{"value":"4078773","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112590$C20B42BC-A94F-425C-82BE-9CC641F3C3C4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7915dd5598b9ee2f1ffd00b77c8c69025466654c","datavalue":{"value":"cell probe model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112590$1E95D8CB-909E-465A-87F3-BE38F18B810C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c25bc710e4a99b4ad5c06b7d722ebbdb9259ca1e","datavalue":{"value":"data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1112590$B7CA10E4-DAFC-47D3-A452-4BDEDDC22A49","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0148865fab0c03358d2bdbf45e3f52d46a798048","datavalue":{"value":{"entity-type":"item","numeric-id":684397,"id":"Q684397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112590$533A17EA-79FA-4DA4-A79E-9E72D2A59C48","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":"Q1112590$CB8D3558-18D8-473F-B109-0FA2A213AE30","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a1d3c6724ea17117a18d7e30b6082abf4a4f53a","datavalue":{"value":{"entity-type":"item","numeric-id":3719870,"id":"Q3719870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112590$EB680E15-67D5-43AE-A932-8113B0914747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6581c334339263ed58f5f1667f37cda420ce29f5","datavalue":{"value":{"entity-type":"item","numeric-id":1838333,"id":"Q1838333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1112590$41841A58-57C8-4290-BD46-D7AB43FDAE7A","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":"Q1112590$A4353321-A938-43E4-8F7A-F463EC4464CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8f500214fd6c13e76959641c6fcdf621ca13e4aa","datavalue":{"value":"https://doi.org/10.1007/bf02126797","type":"string"},"datatype":"url"},"type":"statement","id":"Q1112590$C6BA7889-F16A-4C27-999B-8B5E00744B97","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d19c642496f46d6a946e4aa45373551386669899","datavalue":{"value":"W1985177045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1112590$A3B5E7B0-0BF6-4E53-8336-D5616A7D4179","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68730c9bdd3467a36b824d92987f1385049d3a58","datavalue":{"value":{"entity-type":"item","numeric-id":2819557,"id":"Q2819557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1ba0a6ce5b53ab37e69e35093fa30296c19c8af","datavalue":{"value":{"amount":"+0.8697361350059509","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":"Q1112590$2739A315-ACB3-4C7C-855D-B1A099A42FD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"328910ff9627152408f7c0050017eda48182c475","datavalue":{"value":{"entity-type":"item","numeric-id":2931388,"id":"Q2931388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"344a6e6ad802bf16582c2e14ed262d3ac0b26f2a","datavalue":{"value":{"amount":"+0.8675729632377625","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":"Q1112590$071A0ABB-24C1-4701-B411-98BA43DD485C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95023238d8b43461a17dd236c72f78bebeebd5a2","datavalue":{"value":{"entity-type":"item","numeric-id":1869935,"id":"Q1869935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d097467af72f058f4ca0490fdded06f1c76e5d64","datavalue":{"value":{"amount":"+0.8631759881973267","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":"Q1112590$FB95C140-8E59-455B-ACA7-B94877ABDF1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1640c0c92b5e2966a53e856e7ed3c6c28f166ec0","datavalue":{"value":{"entity-type":"item","numeric-id":5060139,"id":"Q5060139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"180295b1fd2007c90de4f1635fcc50f37f4f0fa8","datavalue":{"value":{"amount":"+0.842728853225708","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":"Q1112590$8E7E9D92-68BB-43D6-8A5C-F04AD411DB29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"091341b86904f7821cbcb5329402f2388ff9cb58","datavalue":{"value":{"entity-type":"item","numeric-id":2475409,"id":"Q2475409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ae5a28f73eafcda102f7a21098213b953996157","datavalue":{"value":{"amount":"+0.8424453735351562","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":"Q1112590$3426C94A-20AA-4EA9-8335-B16FEA141BCC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A lower bound for finding predecessors in Yao's cell probe model","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_lower_bound_for_finding_predecessors_in_Yao%27s_cell_probe_model"}}}}}