{"entities":{"Q1111382":{"pageid":1122131,"ns":120,"title":"Item:Q1111382","lastrevid":42887063,"modified":"2025-07-15T17:51:12Z","type":"item","id":"Q1111382","labels":{"en":{"language":"en","value":"On O(\\(\\sqrt{n})\\) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076618"}},"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":"Q1111382$30F91B2E-F4DA-447E-95EF-B9A9F4388F19","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eb3728a3911f8a8832b28583e996972bf3a6b6f0","datavalue":{"value":{"text":"On O(\\(\\sqrt{n})\\) time algorithm for the ECDF searching problem for arbitrary dimensions on a mesh-of-processors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111382$03EE5B0D-C969-4FA6-B71A-E8B03BEFCBDA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c0dfedce31feff07706a2928ed6186ed7fa61fc5","datavalue":{"value":"0658.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111382$9E695477-1184-4145-A000-3B8E17C3FABE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"025d4ee04bf7fe94ff0db0b55cdc8c48f56e7f6c","datavalue":{"value":"10.1016/0020-0190(88)90165-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111382$13987C15-83FF-4A61-8C9E-B475AD3952C4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc845237dc55a4f97425333484ce2e32547c4a9d","datavalue":{"value":{"entity-type":"item","numeric-id":287249,"id":"Q287249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$C3ADD478-AFDA-44D0-B0AF-44C396F61BA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"51149425cfd0041766e9190a28dd4f1dfa2163a2","datavalue":{"value":{"entity-type":"item","numeric-id":223042,"id":"Q223042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$D1106364-DFD8-4AD8-944F-789F3E81706B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$FA8B86FF-434F-438B-ABEA-6F804FB4397B","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":"Q1111382$A5D880D3-9C6C-4191-B4A7-02764D1D0C74","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6525f291d80599ad985e466138377c075d8c96ea","datavalue":{"value":"The first author [ibid. 22, 303-306 (1986)] presented an optimal O(\\(\\sqrt{n})\\) time parallel algorithm for solving the ECDF searching problem for a set of n points in two- and three-dimensional space on a mesh-of-processors of size n. However, it remained an open problem whether such an optimal solution exists for the d-dimensional ECDF searching problem for \\(d\\geq 4.\\)    We solve this problem by presenting an optimal O(\\(\\sqrt{n})\\) time parallel solution to the d-dimensional ECDF searching problem for arbitrary dimension \\(d=O(1)\\) on a mesh-of-processors of size n. The algorithm has several interesting implications. Among others, the following problems can now be solved on a mesh-of-processors in (asymptotically optimal) time O(\\(\\sqrt{n})\\) for arbitrary dimension \\(d=O(1):\\) the d-dimensional maximal element determination problem, the d- dimensional hypercube containment counting problem, and the d-dimensional hypercube intersection counting problem. The latter two problems can be mapped to the 2d-dimensional ECDF searching problem but require an efficient solution to this problem for at least \\(d\\geq 4\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111382$17C41EFF-8B71-4CAD-9482-BC9C5FFFC836","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111382$3F4F5ECC-24A8-4D6F-934C-A11A907C549F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111382$1C2EF89B-8477-4192-943E-27AAEA596BAE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"df34dbcf7195206de670df197ab466b29d5fe8b7","datavalue":{"value":"4076618","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111382$FC2FB89B-5FD5-4BBD-9B8A-358B1B08D8FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111382$10830A69-B3B5-4902-A581-8023F3548032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111382$E26CDA9E-2639-4D74-A181-14F8E461FA40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c640cc3051a1abbdf173accf51cb348a4501e688","datavalue":{"value":"mesh-of-processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111382$DA5E03F6-77F4-4B61-8BFD-1F243418AAC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2896838d8c1925248e92be383b2b572b65a97ba0","datavalue":{"value":"ECDF searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111382$8C150230-492A-439A-9590-4DCF5ABA1665","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":"Q1111382$B63D7F4F-63A0-4AA6-90AD-C704C50F8000","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8b7a7d3a13f33aef15d49c14bd2cec6f5e67139","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90165-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111382$EF8A8CC5-F095-4A50-9BD1-771471D1CD9C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c6e386bf8684cb5c15c8346f0aa971a9f2825c0d","datavalue":{"value":"W2035232924","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111382$D2F64121-839F-45CD-AB05-D937550A13C9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dc7eb8caf969204b8972e6206e244f9c8f10485","datavalue":{"value":{"entity-type":"item","numeric-id":148390,"id":"Q148390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$FDAC0E1C-C86C-4940-8DB1-9E5188B1417C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07b2848158f553a071983f95df9364fd4736c3f2","datavalue":{"value":{"entity-type":"item","numeric-id":1165008,"id":"Q1165008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$D4C83C60-E920-45F7-9A6E-1ADA29BC6386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2034f32ee69a3f9f5b46504a02acb33a9c9b33","datavalue":{"value":{"entity-type":"item","numeric-id":5375460,"id":"Q5375460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$18FDA1CD-9960-40EA-B79D-5BEF2E147740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a715219fd6274692c890d4aa82ed20d1406419","datavalue":{"value":{"entity-type":"item","numeric-id":1158972,"id":"Q1158972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$28B84901-8BCA-447A-897D-33CA86D0074E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"694910451200ab7067ebbccacf142af3ac2a2369","datavalue":{"value":{"entity-type":"item","numeric-id":3992847,"id":"Q3992847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$3926F193-4AFE-4CE4-99B0-53F5A0C2604C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8f18ea1af35e16f8b078e128f38839dcba5c2a1","datavalue":{"value":{"entity-type":"item","numeric-id":4120129,"id":"Q4120129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$C97ED931-703C-4459-8F7E-63500EEF679C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d1d1cb66d27d2e53aba37392ad47b61e11f859","datavalue":{"value":{"entity-type":"item","numeric-id":3326832,"id":"Q3326832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111382$1DAC04A2-29EA-4232-A1AF-ADE969E14AD9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc37c4287fad1462a9e735477b35d27f33c0b9e5","datavalue":{"value":{"entity-type":"item","numeric-id":915448,"id":"Q915448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0a321135aecf45e43a1d317d331b7b3366ac7e6","datavalue":{"value":{"amount":"+0.854442","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":"Q1111382$61678917-991A-4528-8BF2-BBFCAD74D09C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e603757b5a8e5ddd7495152ea71cc4646d3caf5","datavalue":{"value":{"entity-type":"item","numeric-id":1125801,"id":"Q1125801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fc68aaddd53ba3db9c40ded89a02fa02da6222b","datavalue":{"value":{"amount":"+0.8414941","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":"Q1111382$7F61958A-62F9-44F7-B68B-AD82EF70798F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1db546a84fb7daabe9ed67ba2de150225d343c34","datavalue":{"value":{"entity-type":"item","numeric-id":1350305,"id":"Q1350305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2daa1e8e279bd1d282773576a4911923988dd975","datavalue":{"value":{"amount":"+0.83558774","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":"Q1111382$6279B6D0-0966-477F-852B-1CA716C7143C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1698e1d6268df8fdaddeb160e5dc28c20bc1f43","datavalue":{"value":{"entity-type":"item","numeric-id":1112618,"id":"Q1112618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"335f0f0105a75c06ed0d140788e10aded39ea7c9","datavalue":{"value":{"amount":"+0.8353814","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":"Q1111382$D989BE1F-6218-4675-8D31-568147DC084A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecf07df8ee8f20204fc2496e72a8e6ef76dbf218","datavalue":{"value":{"entity-type":"item","numeric-id":3774969,"id":"Q3774969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10402e294dece47e4fb326cc8ec9bec841c13b0d","datavalue":{"value":{"amount":"+0.83419985","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":"Q1111382$8A77BF65-6CA0-4EE2-BB67-BF4E7D5E9EDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7a7bb8a676d4b94771ae42a1e399fdcab6c72c6","datavalue":{"value":{"entity-type":"item","numeric-id":751246,"id":"Q751246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee4f669e94defc1d68a90f1b5b55bebc7586d0f1","datavalue":{"value":{"amount":"+0.8337468","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":"Q1111382$ED619C64-D7DA-4FEE-AAB7-85F76FA0EE0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a544f5fe3391b268484e4ba4b3ab7b3c90db0899","datavalue":{"value":{"entity-type":"item","numeric-id":4763398,"id":"Q4763398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"703240bbfd378b3a36241f5d7b000626a9b15c2a","datavalue":{"value":{"amount":"+0.82857066","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":"Q1111382$F4BA06E7-364F-474E-96BD-37685965086B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc149d3278c735c4c76ce09ec65bcde52245d500","datavalue":{"value":{"entity-type":"item","numeric-id":1192947,"id":"Q1192947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e9d1f85b0ed0d327ff492bd200eb0fc06c81974","datavalue":{"value":{"amount":"+0.8258225","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":"Q1111382$EC3FA498-FB50-47D6-B5F8-C18DBEF732C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dac3b257ef1296ccd46867ef6d64ec4695fc043c","datavalue":{"value":{"entity-type":"item","numeric-id":1328103,"id":"Q1328103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c7d1240485740fc8e754ab83f37ef1a07f41784","datavalue":{"value":{"amount":"+0.8256966","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":"Q1111382$7AAA6770-A047-4FEA-8BBE-5B9C825C47D2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1111382","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1111382"}}}}}