Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Slice Distance: An Insert-Only Levenshtein Distance with a Focus on Security Applications
Karlstad University, Faculty of Health, Science and Technology (starting 2013), Department of Mathematics and Computer Science (from 2013). (PRISEC)ORCID iD: 0000-0001-9886-6651
Karlstad University, Faculty of Health, Science and Technology (starting 2013), Department of Mathematics and Computer Science (from 2013). (DISCO)ORCID iD: 0000-0003-3461-7079
Karlstad University, Faculty of Health, Science and Technology (starting 2013), Department of Mathematics and Computer Science (from 2013). (PRISEC)ORCID iD: 0000-0003-0778-4736
Karlstad University, Faculty of Health, Science and Technology (starting 2013), Department of Mathematics and Computer Science (from 2013). (DISCO)ORCID iD: 0000-0001-7311-9334
2018 (English)In: Proceedings of NTMS 2018 Conference and Workshop, New York: IEEE, 2018, p. 1-5Conference paper, Published paper (Refereed)
Abstract [en]

Levenshtein distance is well known for its use in comparing two strings for similarity. However, the set of considered edit operations used when comparing can be reduced in a number of situations. In such cases, the application of the generic Levenshtein distance can result in degraded detection and computational performance. Other metrics in the literature enable limiting the considered edit operations to a smaller subset. However, the possibility where a difference can only result from deleted bytes is not yet explored. To this end, we propose an insert-only variation of the Levenshtein distance to enable comparison of two strings for the case in which differences occur only because of missing bytes. The proposed distance metric is named slice distance and is formally presented and its computational complexity is discussed. We also provide a discussion of the potential security applications of the slice distance.

Place, publisher, year, edition, pages
New York: IEEE, 2018. p. 1-5
Keywords [en]
Measurement, Pattern matching, Time complexity, Transforms, Security, DNA
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kau:diva-67012DOI: 10.1109/NTMS.2018.8328718ISI: 000448864200049ISBN: 978-1-5386-3662-6 (electronic)ISBN: 978-1-5386-3663-3 (print)OAI: oai:DiVA.org:kau-67012DiVA, id: diva2:1198286
Conference
9th IFIP International Conference on New Technologies, Mobility and Security, 26-28 February 2018, Paris, France
Funder
Knowledge Foundation, 4707Available from: 2018-04-17 Created: 2018-04-17 Last updated: 2018-11-23Bibliographically approved

Open Access in DiVA

fulltext(389 kB)71 downloads
File information
File name FULLTEXT03.pdfFile size 389 kBChecksum SHA-512
f85c680928d2ecd87fc1c79aa6cc00376814bf01a2e20169c75f9960e62d35a2ecc7a9931453ba006c13022f7145acc1603dd45b0d9b52f4d18c04ea78152696
Type fulltextMimetype application/pdf

Other links

Publisher's full texthttps://ieeexplore.ieee.org/document/8328718/

Authority records BETA

Afzal, ZeeshanGarcia, JohanLindskog, StefanBrunström, Anna

Search in DiVA

By author/editor
Afzal, ZeeshanGarcia, JohanLindskog, StefanBrunström, Anna
By organisation
Department of Mathematics and Computer Science (from 2013)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 72 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 241 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf