{"entities":{"Q1114453":{"pageid":1125202,"ns":120,"title":"Item:Q1114453","lastrevid":66157857,"modified":"2026-04-12T07:56:26Z","type":"item","id":"Q1114453","labels":{"en":{"language":"en","value":"An average-case analysis of MAT and inverted file"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4083043"}},"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":"Q1114453$B57F968B-B2DA-4E55-9E1F-1D981709E3E7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"094ecaa345a97a24bb355cc3b41c64b4b1bf0027","datavalue":{"value":{"text":"An average-case analysis of MAT and inverted file","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1114453$8468A789-FDE3-4D2B-98D6-574445822728","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f283279fb936dc0ab40eae0b4e336fa6fe77708f","datavalue":{"value":"0662.68115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114453$5799A2EC-1ABD-4933-A7E6-233684858A73","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3afe31af6d51d435a6d246433970cf3a46d03515","datavalue":{"value":"10.1016/0304-3975(88)90069-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114453$0DC0E5A9-1901-4F24-8855-A5783401F051","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aedf720352fcca932fab3523c4bbcafd7c4c7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1104176,"id":"Q1104176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$0DE9A35E-026F-4DFE-8723-F51E4B734C1C","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":"Q1114453$41243093-302C-4862-901F-6B106398ACE9","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":"Q1114453$1BAD3D09-30EB-46CD-8EDF-A5F5DA4BDE29","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ca7636765bc72310ae233913ae12cef2f94322db","datavalue":{"value":"It is shown in the literature that the multiple attribute tree outperforms inverted files in terms of worst-case complexities for partial-match queries. In this paper, we estimate the expected values for the complexities of both complete match query and range query on multiple attribute tree and inverted files. We use a uniform probabilistic model for the input data space. We show that the multiple attribute tree is more efficient than the inverted file in terms of these expected value measures.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114453$54782C5B-2D15-4336-A32A-8D7309C17EB6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114453$8237494A-D66A-4741-95C5-9504A615D8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114453$6A63E1C1-68AD-4C56-A409-2DDB52996287","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a9b9ad3c98bec7b34c5b84f4e1b4ece1af842cce","datavalue":{"value":"4083043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114453$D9E5ADDD-467D-4505-B2E9-21CC098CB000","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb7d6f5aeb60ca76c3f6ac7217858201ef4f3aed","datavalue":{"value":"multiple attribute tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114453$40292359-457B-4243-82CD-5B8447DA64BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06703de941b16a31be2750fedfbfd54329a13b27","datavalue":{"value":"inverted files","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114453$A09FC043-F749-4C8E-920C-5C8430B7E6F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"973c45ed827f482c485ec4ada7322f4ea4ee73b4","datavalue":{"value":"complete match query","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114453$1FAEB7EB-8A4B-4E3B-8546-54C2DE3D011D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4407d37c9c9dd591e8d5153fce9b63f9c3e4251","datavalue":{"value":"range query","type":"string"},"datatype":"string"},"type":"statement","id":"Q1114453$66C95168-4677-4B0B-AE09-D550219EBCB0","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":"Q1114453$2B5BD86E-A84C-4D04-BBE6-2057BD3B3AA6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a58209be14f64fa8d52d8430706cfe2c31a6de3e","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90069-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1114453$38BE9AE7-9455-4EB4-B7C2-F9B99DCF728D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4d990a086f2861cd4d133e4f054307879eb281bd","datavalue":{"value":"W2012262792","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1114453$62645B6E-A765-44FA-B954-D280EEE7AE3A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2174f93d8f054d363698d664314501d8811c3760","datavalue":{"value":{"entity-type":"item","numeric-id":4055179,"id":"Q4055179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$C6FD9C7F-C114-42CC-BC84-09F306170321","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f360ddac80f0d8b14526d7ab36d7dfb31094767a","datavalue":{"value":{"entity-type":"item","numeric-id":1223149,"id":"Q1223149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$7336E605-0D63-4C41-9EBE-D5A0CF3ABFBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af3e91ac1ea223f3938943b5a35b38e93b068fc9","datavalue":{"value":{"entity-type":"item","numeric-id":3862478,"id":"Q3862478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$16489FA3-BD72-47D0-93BA-D25523342FA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"271119935a5a2abd0cde86ace30f3f960bd17a5e","datavalue":{"value":{"entity-type":"item","numeric-id":3907087,"id":"Q3907087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$C787E6D0-3069-4D51-8926-73B46E7AA984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"172bdb286ae92efe59a6c7b82053444baf1ba0dc","datavalue":{"value":{"entity-type":"item","numeric-id":4134953,"id":"Q4134953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$DD11F15B-40FF-4351-BDA3-A36E95DBBA00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff1d9e07f14e7c6fa554b66a72aec06069c7134","datavalue":{"value":{"entity-type":"item","numeric-id":3315040,"id":"Q3315040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$A1E8C750-48A3-4CF3-8D09-DD7FB3795942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"037faaabe85635ba4adce3490b4774c88457094b","datavalue":{"value":{"entity-type":"item","numeric-id":1157907,"id":"Q1157907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$22FF9401-F485-4857-A6D1-915B068829CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a2d7f66eae34bce09c14e9d162a2ab247e4ed16","datavalue":{"value":{"entity-type":"item","numeric-id":3674091,"id":"Q3674091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$E4EBB126-9932-425C-A41D-03D2DEC960A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13a3a7280de730af3d9db633159c55d6af15a679","datavalue":{"value":{"entity-type":"item","numeric-id":798014,"id":"Q798014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1114453$30DA98B4-DDAF-4FEE-B47B-FB7BBC27B6A6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3ffaf41381068f86d39be091b34839ce26c95d1","datavalue":{"value":{"entity-type":"item","numeric-id":3026380,"id":"Q3026380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b39753d564272bf72566cdf3e89f8f359015172","datavalue":{"value":{"amount":"+0.7772505283355713","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":"Q1114453$3E72B602-EA57-4F0C-9916-F64B50077605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2fc48a9e7c9e915c41e4593c3ae8ab8a2a404c7","datavalue":{"value":{"entity-type":"item","numeric-id":3804179,"id":"Q3804179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eae0eb03658b13720be343825ac5e0b0cdd35d2f","datavalue":{"value":{"amount":"+0.7755114436149597","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":"Q1114453$2821FF36-9FCF-4458-89D6-AE76F774D1CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ed0b40a1f75fddb67f889eb41269f9fa95832bf","datavalue":{"value":{"entity-type":"item","numeric-id":911252,"id":"Q911252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4187a21cbe9b14b2f3c84940047b897d0cfe333e","datavalue":{"value":{"amount":"+0.774280309677124","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":"Q1114453$52C0B5D8-7D2C-48A3-AD07-161B69102DC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59fb5644c1f627b8b88761e1efbe73ba498f8969","datavalue":{"value":{"entity-type":"item","numeric-id":911259,"id":"Q911259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18f5af641e666b45e4c1cc8f97fbe77745227b0b","datavalue":{"value":{"amount":"+0.7503223419189453","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":"Q1114453$B53361C4-F42A-4F9C-825C-1585F631FAC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b5e06db8a57b3c23f8875fceb915361ebe0cf8d","datavalue":{"value":{"entity-type":"item","numeric-id":798014,"id":"Q798014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9d918a75ee92e5ee5fd216ddee10f95a101e26b","datavalue":{"value":{"amount":"+0.7473565936088562","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":"Q1114453$06C64B08-2D4F-4CD9-B5CF-DC5586DAD4EC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An average-case analysis of MAT and inverted file","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_average-case_analysis_of_MAT_and_inverted_file"}}}}}