{"entities":{"Q1183573":{"pageid":1194322,"ns":120,"title":"Item:Q1183573","lastrevid":70204815,"modified":"2026-04-13T13:09:09Z","type":"item","id":"Q1183573","labels":{"en":{"language":"en","value":"A characterization of digital search trees from the successful search viewpoint"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33392"}},"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":"Q1183573$252BB352-4540-4435-988F-B1A442022960","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3e7fe689ff37b32aa7480b6214f77df23ecb7a41","datavalue":{"value":{"text":"A characterization of digital search trees from the successful search viewpoint","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183573$D076E9FE-AC5D-4EB9-BAB9-4F0E8A6C40AC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78894b1905e4fb51edfa92022c070b980eb3a052","datavalue":{"value":"0746.68027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183573$AD68A9FA-2DBA-42B8-880C-D4CFEFB5DDC9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ce63b8466cc078c58c455fa00f29f099bdcb0db6","datavalue":{"value":"10.1016/0304-3975(91)90050-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183573$67A50BB3-D759-432E-96D0-617D4D80EA0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a0536f9243d280433a98a65ec05603a2c2dc486","datavalue":{"value":{"entity-type":"item","numeric-id":205208,"id":"Q205208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$D1BEDAFA-F862-4F50-80E6-ED7892FD6141","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":"Q1183573$5E75173D-A3DD-4C66-A568-308997648FF8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183573$B6C62144-5845-440C-9F6B-066349EBEBF5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"200415b09802f86cb8186a07e4d15d43189b6e9e","datavalue":{"value":"The author is interested in studying the average complexity of the successful search in digital trees. He assumes that a sequence of elements is an independent sequence of Bernoulli trials and that the \\(i\\)- th digit in a key occurs independently of the other digits. In previous papers, the author has investigated radix search trees and Patricia tries from this point of view. He uses the method of generating functions and establishes a relationship between the derivatives of a generating function, defined by a rather sophisticated recurrence equation, and the moments of a successful search. It is well-known that the number of digits examined during a random successful search is \\(c_ 1\\log n+O(1)\\). By solving the recurrence asymptotically, the author gets a more precise characterization of the form \\(c_ 1\\log n+c_ 2+O(\\log n/n)\\). Finally, he compares the three types of digital trees: The best constant in the mean value is achieved for the digital search tree, whereas the best variance is for Patricia tries. Unfortunately, the paper is not self- contained and, therefore, difficult to read.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183573$A0297F3A-5035-44E1-B82F-DC4C9FAF84EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183573$1F2CABF5-EA22-483B-A2BF-3F77087675DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183573$295B598A-8191-4167-B7E1-9F6F6652F15C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1af092f79674f59e56f8c77169a5f407e7616ee3","datavalue":{"value":"33392","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183573$E67E1956-AF67-48CB-8C45-D744B1BFCE10","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"acdc2342f5e05119dfbadf183d9251deee6f8bd8","datavalue":{"value":"digital search trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183573$2A24B679-1E6F-4754-BE96-76249683E6EC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"022fe16d37aa700fea70e7a830c42e0ea8776f70","datavalue":{"value":{"entity-type":"item","numeric-id":685457,"id":"Q685457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$7C5C1C4B-BDEF-4CA7-A86F-A5A7A329B0C2","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":"Q1183573$93EA9684-A82C-4488-8AC4-DC12AA70F138","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"690d2e2fa3c40e1612ad82748583fec22cea8345","datavalue":{"value":{"entity-type":"item","numeric-id":5558293,"id":"Q5558293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$B03E9117-7FA0-4F4F-864C-537A00B50AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b59b9a95c5ede48fa66f5efb685b30e863d99e05","datavalue":{"value":{"entity-type":"item","numeric-id":3948568,"id":"Q3948568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$AE20FB89-5062-4930-B21F-850A4D6D5E19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22edc8364f1eb7339169dcf02ec2f0f92b9e8e3e","datavalue":{"value":{"entity-type":"item","numeric-id":3216553,"id":"Q3216553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$B9DA888C-EDF7-46BD-8287-10DE8E172C09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c59cd30bf57624ba7d4c5f385e23562e9b8b1de","datavalue":{"value":{"entity-type":"item","numeric-id":1052098,"id":"Q1052098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$D6F4191B-8392-414C-B5AE-D78AC5B446BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"456401424d85fae521849688533ab4f9f42c26d8","datavalue":{"value":{"entity-type":"item","numeric-id":3751029,"id":"Q3751029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$F712D374-4DA5-454B-B03A-8F18631B2C9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6d2de0d5448ae6743a6615321c894340d9b9b0b","datavalue":{"value":{"entity-type":"item","numeric-id":5216437,"id":"Q5216437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$9D560C50-3D04-4379-BB53-7DF40BA14750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf642f27a5e151d87048789170324d5bd920c44e","datavalue":{"value":{"entity-type":"item","numeric-id":5820721,"id":"Q5820721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$67655FA4-9068-4228-863B-91F43E8B6DA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35d51f618786ffe15b4cd1284eebc21b52c6ebf4","datavalue":{"value":{"entity-type":"item","numeric-id":3816955,"id":"Q3816955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$F359B947-3ED8-4FEE-87DE-F8018C01A412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45c6d80a82219366ad87fbe22a361ba3fb8da61d","datavalue":{"value":{"entity-type":"item","numeric-id":4156973,"id":"Q4156973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$D5A72D98-21EF-4EA4-AFD5-6DF3FDE178E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0385821e9133246541ff3ce14a9391e54d89a805","datavalue":{"value":{"entity-type":"item","numeric-id":3742733,"id":"Q3742733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$55351190-740A-4795-A46D-4A6EB627AC28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d2ec417b9925e205343e97045503da2641d9919","datavalue":{"value":{"entity-type":"item","numeric-id":3730026,"id":"Q3730026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$36CD4739-8A4D-4BFE-A5BF-A0D9B00F8D4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2a17d055c8e8800e81a807a66b474ce10107017","datavalue":{"value":{"entity-type":"item","numeric-id":1262137,"id":"Q1262137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$44A68781-8BB7-4B27-9FCB-CE04A48CD637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$A7010476-0BBA-45CE-B7EE-0251B16FF6DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"210f94c182b582e961447efb9e04c73fa8bfbb16","datavalue":{"value":{"entity-type":"item","numeric-id":3715948,"id":"Q3715948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$1330402D-E7EE-4E62-9E16-557752A68E84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fccdca0dcf800c2f7e1b5c4fd22731aa66bda250","datavalue":{"value":{"entity-type":"item","numeric-id":5589310,"id":"Q5589310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$146B00A8-9053-4E5D-A05D-BC853CD89490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad88eac4ac88e2fbef6717213f6791e4118fa174","datavalue":{"value":{"entity-type":"item","numeric-id":3495658,"id":"Q3495658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$AEFD3652-09FE-469E-A6CC-2BADFDA95C72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"423e0b3bfd3fa63866dbcce00eb4cd950a418635","datavalue":{"value":{"entity-type":"item","numeric-id":1111028,"id":"Q1111028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$E5A2B625-4D5C-4C1E-97CD-F0433E142E46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ba83f7c53aa3abf8eeeaa3002f73e3759e6fc1e","datavalue":{"value":{"entity-type":"item","numeric-id":3777471,"id":"Q3777471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183573$F3F4034C-D7EF-4F3E-BA98-1333C6774481","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57bce111fabc0158a50ce7cb90ec777436cfc2df","datavalue":{"value":{"entity-type":"item","numeric-id":3751029,"id":"Q3751029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a116ab74ce8a02caf1dbc9dc47075084ee0c370","datavalue":{"value":{"amount":"+0.8698500394821167","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":"Q1183573$DC532752-A1E4-4005-ADAE-6D7D9BE63AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bfc1cf3893d4ff242263c626538e0b39d1c68c7","datavalue":{"value":{"entity-type":"item","numeric-id":3730026,"id":"Q3730026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8db625f7e2adc4fa75ffb8c7007d872102b8fa22","datavalue":{"value":{"amount":"+0.8351051211357117","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":"Q1183573$7B5128BA-5F31-4356-9F70-FE620F6E637F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21f7d085cbf0e940999740c36182e3c5083ba6d9","datavalue":{"value":{"entity-type":"item","numeric-id":4867323,"id":"Q4867323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac0ea90656e95f84b2fb2c6da4f0f17c95a26b23","datavalue":{"value":{"amount":"+0.8095636963844299","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":"Q1183573$B4D2EF12-7199-4D2A-B3A0-5A71B61F45C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b3cfe926811fc58b7403853f75b6012a0b18dc2","datavalue":{"value":{"entity-type":"item","numeric-id":4288883,"id":"Q4288883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a9242aef1077df97e75cb24e2d32d9253cb0c9c","datavalue":{"value":{"amount":"+0.8067622780799866","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":"Q1183573$DB384821-C044-4873-8512-16921B5CD8EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"780098d9260feffe1f8ef3df4a17bc8047ef4eeb","datavalue":{"value":{"entity-type":"item","numeric-id":3495658,"id":"Q3495658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee71483ea71cee163de21ac1049e3a5fa78b1d44","datavalue":{"value":{"amount":"+0.8031333088874817","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":"Q1183573$A1CA73F7-C849-4043-B51B-3FE0CAAE83FA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A characterization of digital search trees from the successful search viewpoint","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_characterization_of_digital_search_trees_from_the_successful_search_viewpoint"}}}}}