{"entities":{"Q1736784":{"pageid":1747525,"ns":120,"title":"Item:Q1736784","lastrevid":57516324,"modified":"2026-03-31T05:59:30Z","type":"item","id":"Q1736784","labels":{"en":{"language":"en","value":"siEDM: an efficient string index and search algorithm for edit distance with moves"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042335"}},"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":"Q1736784$7F475BEC-839F-4377-8126-3DA1CCF90EE2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"62b38068edffd1983518228d25855d83c8f17123","datavalue":{"value":{"text":"siEDM: an efficient string index and search algorithm for edit distance with moves","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736784$7E4231F3-5039-43A9-875A-FEF367B4260D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"408ddc78017038046128614af90305e6625a95e7","datavalue":{"value":"1461.68272","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736784$18D12F40-58A7-4FC1-83B8-B62477F16CF3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4b9f43d69b7398a6127c32814940db1333acec2","datavalue":{"value":{"entity-type":"item","numeric-id":776838,"id":"Q776838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$9B3859AC-B367-407A-83A9-7701554C79D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0316e0fa2cb8cc541d1fc8e9108efd0f1935ecb5","datavalue":{"value":{"entity-type":"item","numeric-id":1736783,"id":"Q1736783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$4AC5FC2E-8282-40D5-853C-905C71037A40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"37966e12fb8f99674155b703308bb1d61ae07bcd","datavalue":{"value":{"entity-type":"item","numeric-id":1017662,"id":"Q1017662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$A572555E-C3E9-4C7F-87C9-CF1CAF77736F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e50afd505300858526fe479bff5feeb216b4efae","datavalue":{"value":{"entity-type":"item","numeric-id":776839,"id":"Q776839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$C7D8067C-E044-475A-AC25-87969145CFB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7ecba06da1291beb2f77aecfa4b3f126c91ea535","datavalue":{"value":{"entity-type":"item","numeric-id":782201,"id":"Q782201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$461E1D95-469C-4F17-B82D-5EC5F48FA623","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$27E7703D-84A6-40AE-845D-40F6BA2BA13A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736784$876B08C7-CEF7-49E7-80A8-0186F5A7ABC1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e4a5a5d414e9820bdbed3806999eec5343b48589","datavalue":{"value":"https://arxiv.org/abs/1602.06688","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736784$B43E0298-E14F-47F4-BE05-022178C52711","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a4acdbe35eb1e5fd8553f4faebe422f7d96e50b","datavalue":{"value":"Summary: Although several self-indexes for highly repetitive text collections exist, developing an index and search algorithm with editing operations remains a challenge. \\textit{Edit distance with moves (EDM)} is a string-to-string distance measure that includes substring moves in addition to ordinal editing operations to turn one string into another. Although the problem of computing EDM is intractable, it has a wide range of potential applications, especially in approximate string retrieval. Despite the importance of computing EDM, there has been no efficient method for indexing and searching large text collections based on the EDM measure. We propose the first algorithm, named \\textit{string index for edit distance with moves (siEDM)}, for indexing and searching strings with EDM. The siEDM algorithm builds an index structure by leveraging the idea behind the \\textit{edit sensitive parsing (ESP)}, an efficient algorithm enabling approximately computing EDM with guarantees of upper and lower bounds for the exact EDM. siEDM efficiently prunes the space for searching query strings by the proposed method, which enables fast query searches with the same guarantee as ESP. We experimentally tested the ability of siEDM to index and search strings on benchmark datasets, and we showed siEDM's efficiency.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736784$6B63BFF8-455C-47D3-841D-56B1F15A4269","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736784$B6EB5B92-6F25-4962-9922-BFAD6A329E38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736784$9225EA45-FF6C-4949-9372-165CE3E3B515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a762d1a2468ec8882180d0d1124f12b94f8eb1b0","datavalue":{"value":"68P20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736784$3F0F1698-88A7-485B-990D-7CA44D36DFBB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7bde79435a36776fa5b15735afe5a8797f62095e","datavalue":{"value":"7042335","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736784$51F4BC0F-2611-4434-AABE-16117F746679","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7f5162bd0558012745512aba5ec916dfc72f9c1","datavalue":{"value":"edit distance with moves","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736784$066AA721-8A18-4E67-AE2D-2FF84B76905F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d240af8860199b9b86a9204a1be6bfdac8c45cec","datavalue":{"value":"self-index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736784$863A8CA3-B63D-41D5-9249-2F1002BC1892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8930d0a1037d53f3c78903d3756d340b5651c47","datavalue":{"value":"grammar-based self-index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736784$7A7A8801-A926-4D88-B3BB-1949A30B591C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18594d8ae35ef52dc782357490c88280928ea56b","datavalue":{"value":"string index for edit-distance with moves","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736784$14CCF56C-D7EB-479B-B546-FD980D16D804","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":"Q1736784$0E0FC73D-E379-44EB-9721-58535659EE57","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3d2127b8f7e4a65153276e6e2b7cb8f2b9b74f01","datavalue":{"value":"W2281094450","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736784$085FF00F-E2FA-4524-953B-C787F02F848A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"58c177c7bb7d72b185da483d7140f6ab10755431","datavalue":{"value":{"entity-type":"item","numeric-id":3225703,"id":"Q3225703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$BE7ED30C-994A-4DDE-8956-4A22582E460A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1952346e7ecf1075c8bea9f0142fb644e640b13","datavalue":{"value":{"entity-type":"item","numeric-id":5405087,"id":"Q5405087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$55B490C3-D021-486E-B4EA-1A658C6554D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76c7daef6bcfec4a523dde8517efb22e2b20b172","datavalue":{"value":{"entity-type":"item","numeric-id":4223050,"id":"Q4223050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$5B24F4BA-20A6-4A5F-AF5B-F9785EE25F9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c52a170c3dbb1f9eb0465602c0af46c0d05280b","datavalue":{"value":{"entity-type":"item","numeric-id":4849531,"id":"Q4849531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$14C1C3E5-C326-478F-A44D-6BD3522E5BDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78be78fc52b183c8c9dbc9f30b84bf9a1498583c","datavalue":{"value":{"entity-type":"item","numeric-id":5528329,"id":"Q5528329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$B08E1CD3-007B-430A-B26E-364BBFEADD0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c830392b42198068dee3836469bacb6b1c47d02a","datavalue":{"value":{"entity-type":"item","numeric-id":2944538,"id":"Q2944538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$713A2DBA-36EB-4013-BF6C-F01E63B53D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25ae762c1dfbede321af085a0342cdf93b03c954","datavalue":{"value":{"entity-type":"item","numeric-id":2457310,"id":"Q2457310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$9475A1DB-4DC8-4550-9ADF-4DA2EFF681DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a02501ba1784f9fa9b249e87d73a76228bb631d1","datavalue":{"value":{"entity-type":"item","numeric-id":1736509,"id":"Q1736509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$6F4396A9-507C-4ED2-B65C-3960F62B348B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15262a72c7028e36466966050ffb0fe71f831ce0","datavalue":{"value":{"entity-type":"item","numeric-id":2376813,"id":"Q2376813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$FE92DEBF-3CB9-4469-8D47-54F96E883978","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"560a7675947e1b63eb5fc9b3f950334044c3e731","datavalue":{"value":{"entity-type":"item","numeric-id":4928576,"id":"Q4928576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$8306AD4D-BB51-4A0D-8D57-97562B3EB297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5be4288db1580f5486fedd45c0ec394688fe6541","datavalue":{"value":{"entity-type":"item","numeric-id":4347161,"id":"Q4347161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$E96572F9-42DF-4F07-A884-5047A1C8D956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5fe996f9daf33eb9c55d542920748702f080673","datavalue":{"value":{"entity-type":"item","numeric-id":4828937,"id":"Q4828937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$1E56A760-6EB8-41A7-8ED4-B78AC8E5CA02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24e9bb1e0c34ee877369c0387049ae36917638aa","datavalue":{"value":{"entity-type":"item","numeric-id":3581537,"id":"Q3581537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$7E48CACC-D529-4F2C-ABCB-501F2C6464BF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f924e09d1ccd4e638602e51a7515cf586c301b3d","datavalue":{"value":"10.3390/A9020026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736784$19615BE3-A780-492F-86A2-C9E95D3F0EA6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd5f8c7a47258fbc27c1df60e05b1d18fbac014d","datavalue":{"value":{"entity-type":"item","numeric-id":4828999,"id":"Q4828999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f71ab635d9a40a4038b33a3c97edc937b2e6074","datavalue":{"value":{"amount":"+0.786504864692688","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":"Q1736784$F1007ABE-1C10-429C-B5F5-B01948F5547A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed5a5a4102ed40fecdda865ae52b1b7b49a31904","datavalue":{"value":{"entity-type":"item","numeric-id":2944538,"id":"Q2944538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0595f5a705f66d05fb1025e61467bfc7f817564e","datavalue":{"value":{"amount":"+0.7865046262741089","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":"Q1736784$58D23450-4D4F-46C6-A4E2-0ACD8EEEA98B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1540de24c74631e8bba542491bf92df69892c911","datavalue":{"value":{"entity-type":"item","numeric-id":2287426,"id":"Q2287426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbca2e6ffcf91bc6cfd619c4ce88f74492dbe021","datavalue":{"value":{"amount":"+0.7284426689147949","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":"Q1736784$43646B1B-932F-46A2-9C46-299CEFF7DC0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53c8f5f31069d4f1ad890162428c222fd1ce765d","datavalue":{"value":{"entity-type":"item","numeric-id":3637110,"id":"Q3637110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78d6bb6cc0aff5f5149408846727d9251b33659c","datavalue":{"value":{"amount":"+0.7232927680015564","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":"Q1736784$AC6E8A1E-4144-404F-AE6F-2149BE789F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93d6494741f7b5acbdd541852efc7de0882444bc","datavalue":{"value":{"entity-type":"item","numeric-id":818138,"id":"Q818138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3aa32741bc5b519b11ee7f11d01833a2340ea80","datavalue":{"value":{"amount":"+0.7221136093139648","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":"Q1736784$DA14F8F3-D93E-47A4-A110-2943A828C642","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736784$B6A22932-57BF-4543-B4AA-F5FF1D579D0B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736784","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736784"}}}}}