{"entities":{"Q760797":{"pageid":762646,"ns":120,"title":"Item:Q760797","lastrevid":48773575,"modified":"2026-01-05T20:09:58Z","type":"item","id":"Q760797","labels":{"en":{"language":"en","value":"A probabilistic analysis of the height of tries and of the complexity of triesort"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3885325"}},"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":"Q760797$F11DFD62-6695-4B7D-BD39-A2868D87541E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac42e483e81900a1935f4314724eb694985c85c6","datavalue":{"value":{"text":"A probabilistic analysis of the height of tries and of the complexity of triesort","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q760797$66801856-28C9-4C0E-95E3-730B9410EEA1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"290d9cb3cbd2ac083029e650adedac35ad78822d","datavalue":{"value":"0555.68037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760797$C7496B65-C298-4A23-8012-1BDDED4B2647","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aad0bd0a05904cf6d656e640e2e1f75798a40e0a","datavalue":{"value":"10.1007/BF00264248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760797$F6BBEDAD-31B2-4D0A-8313-6E03968A5C34","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760797$544598A8-B363-4D06-B1DE-4F7392A11369","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q760797$E64C3071-B131-4838-A9C7-006D83DD6291","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3342d81527790245ec80b66c04a7a7cea5a7e872","datavalue":{"value":"We consider binary tries formed by using the binary fractional expansions of \\(X_ 1,...,X_ n\\), a sequence of independent random variables with common density f on [0,1]. For \\(H_ n\\), the height of the trie, we show that either \\(E(H_ n)\\sim 2 \\log_ 2 n\\) or \\(E(H_ n)=\\infty\\) for all \\(n\\geq 2\\) according to whether \\(\\int f^ 2(x)dx\\) is finite or infinite. Thus, the average height is asymptotically twice the average depth (which is \\(\\sim \\log_ 2 n\\) when \\(\\int f^ 2(x)dx<\\infty)\\). The asymptotic distribution of \\(H_ n\\) is derived as well. If f is square integrable, then the average number of bit comparisons in triesort is n log\\({}_ 2n+O(n)\\), and the average number of nodes in the trie is O(n).","type":"string"},"datatype":"string"},"type":"statement","id":"Q760797$048E3688-5BFC-4E7A-AD5E-3E6BF464CC68","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760797$6F260968-87FD-4122-938C-A1F5D6A075BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5a0a7c2e828ddff20f80f3a8411b2dc11a195016","datavalue":{"value":"3885325","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q760797$CAB13B55-B9F1-446B-97A1-596D216AF004","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f056c95f0e5f16f946f5c6be0a0ed028640d91e9","datavalue":{"value":"binary tries","type":"string"},"datatype":"string"},"type":"statement","id":"Q760797$93F0B46F-962A-44DD-8C54-D437AF2CF9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6319110217e1bed71af8c1e582d83ee5f4fcd30c","datavalue":{"value":"average height","type":"string"},"datatype":"string"},"type":"statement","id":"Q760797$CC531016-05EC-42D2-9CAD-433CAE5F0F1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc4f4db3c99d1c0752a4c6f699f7f88236024cf1","datavalue":{"value":"triesort","type":"string"},"datatype":"string"},"type":"statement","id":"Q760797$65856B7F-433A-4268-B44D-1D276D76E415","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"68ee3d60719c97b3f7244d7f2c477985e89e7464","datavalue":{"value":{"entity-type":"item","numeric-id":1242411,"id":"Q1242411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760797$60DD830A-AAF7-445A-B3AF-153FA2B34E37","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":"Q760797$D7578ECF-EA4B-4275-BD16-638131462F8F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"491114bf078fcb4fbdf112a6c375b2016fcc2e7c","datavalue":{"value":{"entity-type":"item","numeric-id":1154740,"id":"Q1154740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760797$BBF855E1-4259-4175-91A3-CE8C31D6EA1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e6de655229b95d58d17d9092f79dad5c4230ab3","datavalue":{"value":{"entity-type":"item","numeric-id":1160188,"id":"Q1160188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760797$7780B159-57E1-47DA-B5E8-DBC5CFD7B289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"627afac7f7cfd0cf9939d1a6650cf76e495deee8","datavalue":{"value":{"entity-type":"item","numeric-id":3940858,"id":"Q3940858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760797$D3C12A1C-5231-4F25-8C7A-7B26027946D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a466c6b7a5fc934441da93e12d108bda396d0ebd","datavalue":{"value":{"entity-type":"item","numeric-id":5615180,"id":"Q5615180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760797$CD7719C9-6568-420D-915E-3A320464F0D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd966e82a7ce19fa6b2fe0239f5c9f1a3971b9a2","datavalue":{"value":{"entity-type":"item","numeric-id":1157926,"id":"Q1157926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760797$E762FD08-AEF1-46C9-82C6-015387B9A077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9686893a2fd7dd1a4293474524bad24cee6a0051","datavalue":{"value":{"entity-type":"item","numeric-id":1146528,"id":"Q1146528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760797$A09CF375-0A31-4D4E-82FE-D3BB79F8FB8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7253f0bdfa37ccd027ced7993617837dd322b000","datavalue":{"value":{"entity-type":"item","numeric-id":4135799,"id":"Q4135799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q760797$4D0E3953-4FBF-4919-A973-B1F37F86B951","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfcf3e279676d08df4d316b77f00fd66bae87277","datavalue":{"value":{"entity-type":"item","numeric-id":3512599,"id":"Q3512599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2b7415e6617907b091daa8b84075c6eb9c244a9","datavalue":{"value":{"amount":"+0.8630914688110352","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":"Q760797$948D97F4-67F1-49F6-82E1-2906DF04BABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9adfda606a0a24efad8b4fd40e1d75daa355d089","datavalue":{"value":{"entity-type":"item","numeric-id":3642866,"id":"Q3642866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2044cb733b197cd51edeef71543f4e0f236bc11","datavalue":{"value":{"amount":"+0.8573727011680603","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":"Q760797$4D72F62E-EF96-4C85-A14F-D5A074564961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edac795f572ba75b51bd5a8b8740a33685bd4cc6","datavalue":{"value":{"entity-type":"item","numeric-id":2921651,"id":"Q2921651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b95be0f334f3fa1c5eda89dd9a4148fe8f39c3ee","datavalue":{"value":{"amount":"+0.8538225293159485","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":"Q760797$0564B1F5-358C-40CF-9AC1-56A9FE7EFDD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85e3709f591ae7ade858b8c07edeaffb4061d3c0","datavalue":{"value":{"entity-type":"item","numeric-id":4508387,"id":"Q4508387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2a9434bd0ddc868db08f1ccbb417dc660fa5603","datavalue":{"value":{"amount":"+0.8458643555641174","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":"Q760797$2C4E6130-9797-4AA4-84C7-C3AD5C0A234E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e456cc617f4b1e0e70a39823082a37fdc683b8fc","datavalue":{"value":{"entity-type":"item","numeric-id":1277381,"id":"Q1277381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4dbd4154a7ccef283396548182bc33e946f9047c","datavalue":{"value":{"amount":"+0.8426094055175781","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":"Q760797$00AFE954-365B-4DCB-8B2D-9BA5F998F178","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:760797","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:760797"}}}}}