{"entities":{"Q685702":{"pageid":687551,"ns":120,"title":"Item:Q685702","lastrevid":63462393,"modified":"2026-04-11T13:20:01Z","type":"item","id":"Q685702","labels":{"en":{"language":"en","value":"Parallel searching of multidimensional cubes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 423590"}},"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":"Q685702$D4CBB595-C08D-4EA6-8B39-837C8B95715E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"13c6ffd98e2780b981a7584f67ddeea1f5b0fd42","datavalue":{"value":{"text":"Parallel searching of multidimensional cubes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685702$F10679B5-3483-49B9-A7ED-1C56AF48EB2E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a2b145238b06c65fbfba2b0ac9da099f72e89d2c","datavalue":{"value":"0802.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685702$662AC587-8F29-4CFE-B1A9-8C9B31B1E3B2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7e4ef0e30755f449648b86d30960c25eb311f6b2","datavalue":{"value":"10.1016/0012-365X(93)90381-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685702$8D6AD9F4-99C1-4B82-BBEF-60C804F5C2E7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"195a11023b9fa51026b0ae4c10238ff0a353371b","datavalue":{"value":{"entity-type":"item","numeric-id":407593,"id":"Q407593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685702$C9643750-7C72-46FD-986C-B404A171FC9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f12495924f470ae3671be11cd0c05f786ec14d07","datavalue":{"value":{"entity-type":"item","numeric-id":593776,"id":"Q593776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685702$B39279AD-3DD2-4BF1-85C6-85A0C53A1732","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685702$FA031039-6E2E-4A2B-8298-3D9B2AC9AF4C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1a4582cf37b19337c7eae16fd67b6e107844c9e6","datavalue":{"value":{"time":"+1993-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685702$BCF92649-71F9-4FBB-AC0D-14C229E689E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"65e74f03adda33ce074e711cea425f699fa9e434","datavalue":{"value":"Let \\((P,\\leq)\\) be a finite partially ordered set and let \\(f:P \\to R\\) be an order-preserving, injective, real-valued function. The search problem associated with \\(P\\) is: Given a real number \\(x\\), determine if there exists \\(p \\in P\\) such that \\(f(p) = x\\), and find such a \\(p\\) if it exists. An elementary step is the evaluation of \\(f\\) at some \\(p \\in P\\). The complexity \\(c(P)\\) of the search problem is the minimum, over all algorithms for the problem, of the maximum number of steps taken by the algorithm. When \\(k\\) processors are used, the complexity is denoted by \\(c_ k (P)\\).   In this paper the authors consider the search problem when \\(P\\) is a product of several chains of the same length. \\(Q_{nd}\\) denotes the \\(d\\)- dimensional cube of side length \\(n\\), and we write \\(W(n,d,k)\\) for \\(c_ k (Q_{nd})\\).   The authors prove that \\(W(n,d,n^{d-1}) = \\Theta (\\log \\log n)\\) and that, moreover, any randomized algorithm using \\(n^{d-1}\\) processors for searching \\(Q_{nd}\\) takes time \\(\\Omega (\\log \\log n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q685702$F492AA40-A8A3-4BA4-8CB6-DF20982E6965","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685702$98018102-FC3B-4F7F-8B66-3C4FE4981DC0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685702$A3136155-DF4C-4F2A-A1C1-026E48075C45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685702$6FEE2995-68AD-4C39-BC0E-0D11CC02F803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685702$75D91030-316D-48B1-95D7-8D06BDCF74B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b78f7864a137fe5235a0c5ccf705b4656ab0ed62","datavalue":{"value":"423590","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685702$167685E5-71F4-473C-91A0-28B2B3211146","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e0c7481e3c5c308fc47ea6e648bd33e7ea295f7","datavalue":{"value":"searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q685702$60F4F4E5-7C25-4FF5-B7BC-4FDF55B29DFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af9e99e8256de9f0f20ed06fe953e61d6498e535","datavalue":{"value":"multidimensional cube","type":"string"},"datatype":"string"},"type":"statement","id":"Q685702$C35B51BB-162E-46A1-810A-29C18ACBA98C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q685702$1DE7109D-DE71-40D1-ACA2-CB36183AD73C","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":"Q685702$4FB5F21F-E574-47BE-B5BC-E93C5C014A59","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2bd35d34c8cb4660ca6ae9b0c6b460814b14576","datavalue":{"value":{"entity-type":"item","numeric-id":1082818,"id":"Q1082818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685702$A2940D5E-714D-400A-A78B-F57D4538AAD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6505b854a2165a46817abfb719244cbda75f9063","datavalue":{"value":{"entity-type":"item","numeric-id":3700849,"id":"Q3700849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685702$82404BD6-D2C8-4DA2-BEAD-A3E4FD714651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"105a42b9d963cd1fb6e3de311b73c6eb9ace9be3","datavalue":{"value":{"entity-type":"item","numeric-id":4069777,"id":"Q4069777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685702$761C2596-4C7A-4391-9C5E-42507CD64941","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5caf050c2d4733b825749f7b0d2149d8bd0d2399","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)90381-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q685702$223ED98D-FF3A-4595-9A92-961F160F4D4E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2e7569fe8ad56dbd5ae979c1daf9a40059aab4bd","datavalue":{"value":"W2049177452","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685702$28BA7E5D-C68D-44E4-8FEB-20737BE39DB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d2954025a92c49d7af4ebf52226b8544db107bb","datavalue":{"value":{"entity-type":"item","numeric-id":1903637,"id":"Q1903637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45dea13a7c17e7c267028dc9e2b839e3f4370c99","datavalue":{"value":{"amount":"+0.9037707","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685702$971AF022-9C8F-42F5-AA9F-81AE08C05B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c2b5c98aa74dbd47a5ed1c12b31b5ad585147cd","datavalue":{"value":{"entity-type":"item","numeric-id":3746899,"id":"Q3746899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d4a8b0a4ab312d400e2a468a35afa774024a924","datavalue":{"value":{"amount":"+0.90314716","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685702$0E4F5310-0698-4969-8A29-D3212157DBAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b899885d776460cc306a4c326d78e15f88cd38d","datavalue":{"value":{"entity-type":"item","numeric-id":1386363,"id":"Q1386363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a4c59ad707aa3189e38e5ffc0865dfa2c9a1e7a","datavalue":{"value":{"amount":"+0.9014251","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685702$88D6AC27-C8E5-40BE-B476-417D89126019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c77f46ed8a35a24a4adad2b572d86edf9a658baa","datavalue":{"value":{"entity-type":"item","numeric-id":5943313,"id":"Q5943313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44c2547743c83c350dcaf3cd700c6a7dc54c8146","datavalue":{"value":{"amount":"+0.8941159","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685702$76CDA076-086F-4B2A-AD69-803C00B56EB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47f0a0b37076bd2158eeed4c12e62d8ad1b7f016","datavalue":{"value":{"entity-type":"item","numeric-id":750158,"id":"Q750158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aefa8b4de9d050d9f553ef5c324537df84c1926","datavalue":{"value":{"amount":"+0.891307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685702$A5E021BD-1AB6-4D98-BF3E-BF7EA9477420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e97a2ceda4e2ca77c30a5a206752df9604f60433","datavalue":{"value":{"entity-type":"item","numeric-id":1106664,"id":"Q1106664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c57f4be0fbe1ccc5f124bf1fa5dabf1bb596bf9","datavalue":{"value":{"amount":"+0.89079374","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685702$E847AC8D-F37E-4BC2-AD8D-99A981BC1DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ca814004ae7466d8fe797966facaba3268c4539","datavalue":{"value":{"entity-type":"item","numeric-id":3809283,"id":"Q3809283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d15d665547cee54660d8dc852418e953e624454c","datavalue":{"value":{"amount":"+0.8869959","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685702$C2C12E8F-9359-431C-93F8-661347670518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d092b35725488d21520afc6699a5d340368545c","datavalue":{"value":{"entity-type":"item","numeric-id":2699998,"id":"Q2699998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa453195de35d61f25daf746d559dd4a128cb61f","datavalue":{"value":{"amount":"+0.88598204","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685702$BC7274A9-7339-47F0-97D3-426B202D9242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"595eeb03dcd148ac4c3e1499b3369b4b446fa439","datavalue":{"value":{"entity-type":"item","numeric-id":5286337,"id":"Q5286337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7597ba1f7e400e47120541a247a171d6045bcf0","datavalue":{"value":{"amount":"+0.8856391","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685702$861DB5D8-B5FD-47B5-9425-E93FFE2E4865","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel searching of multidimensional cubes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parallel_searching_of_multidimensional_cubes"}}}}}