{"entities":{"Q2363989":{"pageid":2374732,"ns":120,"title":"Item:Q2363989","lastrevid":52857773,"modified":"2026-01-23T16:02:37Z","type":"item","id":"Q2363989","labels":{"en":{"language":"en","value":"Engineering a lightweight external memory suffix array construction algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6747590"}},"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":"Q2363989$4CD25E55-43AA-4055-AD21-456435CD8E48","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"78aa8f4a70eed13617c3815345a8ac66ca5e4276","datavalue":{"value":{"text":"Engineering a lightweight external memory suffix array construction algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2363989$B23D3846-B737-4C80-8801-1DEEAB999303","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b9144f6d50e37c48ac4d71c1a776b05df60ebf91","datavalue":{"value":"1377.68328","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363989$F2CB0B32-942B-49B8-9B31-5EAD37E69960","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"acc8b8e8ab120016a45498ce1a0f5e55eeb44f96","datavalue":{"value":{"entity-type":"item","numeric-id":323034,"id":"Q323034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$7E18A117-633B-4FD2-8869-0B449BFD0EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8400774f10ffee572cfb28061d17918f659dafb5","datavalue":{"value":{"entity-type":"item","numeric-id":405572,"id":"Q405572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$C25D7D04-7D15-43A7-B671-67AA738103A9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e5cf57799e8c41ecba181c21bc95047b71cb3443","datavalue":{"value":{"entity-type":"item","numeric-id":294368,"id":"Q294368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$98B6EF74-CF8D-4585-84C1-42C77D56E00D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"45c15162b94cadee206f6a79d1b59255a2edbef7","datavalue":{"value":{"time":"+2017-07-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2363989$8F1A4531-33F6-4AF3-B13A-936A34CE7BA4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a0f110a2051bfa4c2d08d58016ec7d186fd6055f","datavalue":{"value":"In this article, the authors show how to use delayed merging to reduce from \\(O (n^2 / (M B))\\) blocks to \\(O (n^2 / (M B \\log_\\sigma n) + n / B)\\) blocks the I/O complexity of Ferragina et al.'s scan-based external-memory suffix-array construction, where \\(n\\) is the length of the text, \\(M\\) is the size of RAM in words, \\(B\\) is the size of a block in words and \\(\\sigma\\) is the alphabet size. They also show how to apply techniques developed since the publication of Ferragina et al.'s algorithm, to reduce the running time from \\(O((n^2 / M) \\log \\sigma)\\) to \\(O ((n^2 / M) \\log (\\log (\\sigma) / \\log \\log n)\\).  Finally, they show experimentally that their algorithm is competitive with what was the state of the art when this article was submitted. While it was in press, however, several new algorithms were developed, and the authors et al.'s paper [``Engineering external memory induced suffix sorting'', in: Proceedings of the 19th workshop on algorithm engineering and experiments, Alenex'17. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 98--108 (2017; \\url{doi:10.1137/1.9781611974768.8})] is probably now a better reference for most purposes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363989$CBE52A9D-005E-4D85-B426-75CC0A5402AC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"190982f8ef5a79efe62543507a2f94a300470907","datavalue":{"value":{"entity-type":"item","numeric-id":390357,"id":"Q390357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$4A17427D-24F4-476F-968E-A05C2DA0CEEB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363989$00FFFC1A-8114-42E6-A841-DE2F4BDF97E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3543429e8d344d11b000c174b2dc0984c342f966","datavalue":{"value":"6747590","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363989$E85691A7-AAB9-47CE-BBD7-530AED7C932F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b2b8c69c915ad45b42bcb328aeaa3c5604db3a52","datavalue":{"value":"suffix array construction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363989$F5DBD627-E1AB-49D9-9E04-A114BBA3F831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f48dd990e8197df9a28faf499e324d5ffeb32a9","datavalue":{"value":"external memory algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363989$68BFE1D1-8198-4569-A83F-E9A95031EDC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3318a8a5564cdcdf8771603173452660fa04ccac","datavalue":{"value":"algorithm engineering","type":"string"},"datatype":"string"},"type":"statement","id":"Q2363989$2E6E02ED-E07E-4FEF-B675-A35A99AA8C1F","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"2870a49bdb58342723679d5caca66d0a62273e26","datavalue":{"value":{"entity-type":"item","numeric-id":54565,"id":"Q54565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$E9CAFF64-5CB6-47DA-AD82-D41297336F83","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":"Q2363989$F9D92B4C-D8A6-48BA-B955-2FD817D88D2E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cdd5fcecee723376b2c7a78e4fb096775f31bf07","datavalue":{"value":"https://doi.org/10.1007/s11786-016-0281-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q2363989$44FE1373-C5F3-4D41-8E51-5950C9824851","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f8dfaa3d4c1a635339599fbf000bdef38fd92c0e","datavalue":{"value":"W2402980768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363989$E9CF0839-4D32-4A0E-805D-780471B15BB9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4b4505ecee57edec84bced67e5a0d2a405bf689","datavalue":{"value":{"entity-type":"item","numeric-id":876707,"id":"Q876707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$EB284AB9-117E-4FE5-B3F0-E06ABCB41217","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afd2aafbb6692eb6476c0e4d0607d51a26bb1058","datavalue":{"value":{"entity-type":"item","numeric-id":3060784,"id":"Q3060784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$F05594C3-5577-4D7F-A5C1-E91E3DE8DD0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a8471b906a33bfae3324c74cb4ae249dc56541c","datavalue":{"value":{"entity-type":"item","numeric-id":2912840,"id":"Q2912840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$B3632567-1318-43CB-A8AD-9F69A1B59ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d867ed5c4c3d58a135801c19b0eae205474b55d","datavalue":{"value":{"entity-type":"item","numeric-id":5266606,"id":"Q5266606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$77280CBC-347E-44FB-9C89-EBA0E99AB05F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05c7209d0813d4fef81b9a5bc9028cfff986421a","datavalue":{"value":{"entity-type":"item","numeric-id":5956830,"id":"Q5956830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$547A2875-1004-45FC-BB53-EB2EE4D27CCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d94bf235754aea381a086b3086a4f966c468169d","datavalue":{"value":{"entity-type":"item","numeric-id":1190451,"id":"Q1190451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$B054C7B7-12D5-4ECF-B91D-96DB4C65F96D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19fbb909753d818fd159cc36b598ffc8e380b559","datavalue":{"value":{"entity-type":"item","numeric-id":4928573,"id":"Q4928573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$DC2D6276-BFC8-4F33-AF6D-60F8EE2004FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"134660c56210441d0b0db00a83332a8974a6c04c","datavalue":{"value":{"entity-type":"item","numeric-id":5269285,"id":"Q5269285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$0B5627EA-F70C-4F08-9BD4-0B659CDB9F9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a24ae0a1d1e586373bb307e659c4ed8903393ce4","datavalue":{"value":{"entity-type":"item","numeric-id":2429367,"id":"Q2429367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$8EFA8380-AD0B-4AD6-8B89-7357C640E8D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38f1ef0c6008067a98e6eb681185db01b14f722a","datavalue":{"value":{"entity-type":"item","numeric-id":3546296,"id":"Q3546296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$C1267217-12F6-42CF-AE9D-57403D6ABE63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"252834c90591b854166063cf3762097adfc6377c","datavalue":{"value":{"entity-type":"item","numeric-id":2465056,"id":"Q2465056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$F7C59A86-DEB4-4024-B58C-E2824BD9A0D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb48265c4e2c7a10b8bf40b138f5d1f99b268431","datavalue":{"value":{"entity-type":"item","numeric-id":5266615,"id":"Q5266615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$76A9B853-9680-4649-87B6-8FD72F66AE9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef3759ca5323bb46971441f738d150a0020816a6","datavalue":{"value":{"entity-type":"item","numeric-id":5165609,"id":"Q5165609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$6C888CA4-1178-474B-B0FB-1484DF5C8DDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f5fa024f3ceba85e016cdee70373544af599545","datavalue":{"value":{"entity-type":"item","numeric-id":3455222,"id":"Q3455222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$4C5F11BE-BE10-4F84-9CC2-2F8BD8D66F0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cac7f741f9b1e3426d597355d63b43bdf762c36a","datavalue":{"value":{"entity-type":"item","numeric-id":4148937,"id":"Q4148937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$35ECB965-0055-4590-BB9F-A5F5D3EF6691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"765e1a7b0cd5402f72cc273dc87f1f94470d841f","datavalue":{"value":{"entity-type":"item","numeric-id":3142586,"id":"Q3142586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$82DD032C-3279-4FDD-A6E8-876F971959C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9c0f6c12d8ae5a3a9d115b1a1d9acbb6131623f","datavalue":{"value":{"entity-type":"item","numeric-id":2944557,"id":"Q2944557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$FF91D8E0-B8A4-4246-AD51-33BDC5614D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec848a3172f695ba51d2e61c54636efa90e7a1eb","datavalue":{"value":{"entity-type":"item","numeric-id":5397902,"id":"Q5397902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$83B4D5F8-32DD-4B3B-A9A2-54B517E323E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c279c7c320a90ec1b772168afa2ec092a906e1e","datavalue":{"value":{"entity-type":"item","numeric-id":2903190,"id":"Q2903190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2363989$46401A2A-0470-4C39-A850-CF7A891036D5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"313c8f9a1ce680687f8a0f47f949914588d29ab6","datavalue":{"value":"10.1007/S11786-016-0281-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2363989$35D95230-1D9F-4603-8CA7-CB1096EA249B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4855cbd2c1c3699cb60c292aeb71532dee2da8e","datavalue":{"value":{"entity-type":"item","numeric-id":5956830,"id":"Q5956830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea7ae8f5ee02d102e030c64ce82ca8db82c4bc5e","datavalue":{"value":{"amount":"+0.8849083781242371","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":"Q2363989$5972A353-E347-4119-80AE-AA9E1203CF9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b11e274d69d5045adedad9e92bc9d79cee6923f","datavalue":{"value":{"entity-type":"item","numeric-id":1882475,"id":"Q1882475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea7ae8f5ee02d102e030c64ce82ca8db82c4bc5e","datavalue":{"value":{"amount":"+0.8849083781242371","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":"Q2363989$68D6E976-309D-4387-B348-DEBA62EE6C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0022b4efa6639360546f5a0a65b6f7a6e307568","datavalue":{"value":{"entity-type":"item","numeric-id":5269285,"id":"Q5269285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2892432a09468ffccbbd9f91328559656af8e6b7","datavalue":{"value":{"amount":"+0.8836497068405151","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":"Q2363989$031E9D5F-AE15-4E8D-8F0C-D0A8A2FDB927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e5bc2b85f185958acb36c4aa1ed5102ab23b3ad","datavalue":{"value":{"entity-type":"item","numeric-id":4629538,"id":"Q4629538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcba626ed454f44c5851b88d4fc3bc085807f21b","datavalue":{"value":{"amount":"+0.8684871792793274","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":"Q2363989$36293042-18EE-46A1-98EE-8A851F67900F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3814e1d575c6c6aec8367f304e9b1601056bc271","datavalue":{"value":{"entity-type":"item","numeric-id":5266606,"id":"Q5266606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9a862b738ba2f4e7c71e8efb09c2b4c083040fb","datavalue":{"value":{"amount":"+0.867460310459137","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":"Q2363989$3EC848B1-F011-4E39-8C74-65C8BEC404FC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2363989","badges":[]}}}}}