Approximate String Matching with SIMD

Fiori, Fernando J; Pakalén, Waltteri; Tarhio, Jorma

doi:10.1093/comjnl/bxaa193

Skip to Main Content

Article Navigation

Journal Article

Approximate String Matching with SIMD

Get access

Abstract

We consider the |$k$| mismatches version of approximate string matching for a single pattern and multiple patterns. For these problems, we present new algorithms utilizing the single instruction multiple data (SIMD) instruction set extensions for patterns of up to 32 characters. We apply SIMD computation in three ways: in counting of mismatches, in comparison of substrings and in calculation of fingerprints. We show the competitiveness of the new algorithms by practical experiments.

This article is published and distributed under the terms of the Oxford University Press, Standard Journals Publication Model (https://academic.oup.com/journals/pages/open_access/funder_policies/chorus/standard_publication_model)

Editor:

You do not currently have access to this article.

Download all slides

Sign in with email/username & password
Get email alerts
Save searches
Purchase content
Activate your purchase/trial code

Get help with access

Institutional access

Access to content on Oxford Academic is often provided through institutional subscriptions and purchases. If you are a member of an institution with an active account, you may be able to access content in one of the following ways:

IP based access

Typically, access is provided across an institutional network to a range of IP addresses. This authentication occurs automatically, and it is not possible to sign out of an IP authenticated account.

Sign in through your institution

Choose this option to get remote access when outside your institution. Shibboleth/Open Athens technology is used to provide single sign-on between your institutionâ€™s website and Oxford Academic.

Click Sign in through your institution.
Select your institution from the list provided, which will take you to your institution's website to sign in.
When on the institution site, please use the credentials provided by your institution. Do not use an Oxford Academic personal account.
Following successful sign in, you will be returned to Oxford Academic.

If your institution is not listed or you cannot sign in to your institutionâ€™s website, please contact your librarian or administrator.

Sign in with a library card

Enter your library card number to sign in. If you cannot sign in, please contact your librarian.

Society Members

Society member access to a journal is achieved in one of the following ways:

Sign in through society site

Many societies offer single sign-on between the society website and Oxford Academic. If you see â€˜Sign in through society siteâ€™ in the sign in pane within a journal:

Click Sign in through society site.
When on the society site, please use the credentials provided by that society. Do not use an Oxford Academic personal account.
Following successful sign in, you will be returned to Oxford Academic.

If you do not have a society account or have forgotten your username or password, please contact your society.

Sign in using a personal account

Some societies use Oxford Academic personal accounts to provide access to their members. See below.

Personal account

A personal account can be used to get email alerts, save searches, purchase content, and activate subscriptions.

Some societies use Oxford Academic personal accounts to provide access to their members.

Viewing your signed in accounts

Click the account icon in the top right to:

View your signed in personal account and access account management features.
View the institutional accounts that are providing access.

Signed in but can't access content

Oxford Academic is home to a wide variety of products. The institutional subscription may not cover the content that you are trying to access. If you believe you should have access to that content, please contact your librarian.

Institutional account management

For librarians and administrators, your personal account also provides access to institutional account management. Here you will find options to view and activate subscriptions, manage institutional settings and access options, access usage statistics, and more.

Purchase

Subscription prices and ordering for this journal

Purchasing options for books and journals across Oxford Academic

Short-term Access

To purchase short-term access, please sign in to your personal account above.

Don't already have a personal account? Register

Approximate String Matching with SIMD - 24 Hours access

EUR €15.00

GBP £13.00

USD $16.00

Rental

This article is also available for rental through DeepDyve.

Views

216

Altmetric

Total Views 216

131 Pageviews

85 PDF Downloads

Since 2/1/2021

Month:	Total Views:
February 2021	28
March 2021	25
April 2021	1
May 2021	4
June 2021	1
July 2021	2
August 2021	26
September 2021	6
October 2021	2
January 2022	2
March 2022	4
April 2022	4
May 2022	2
June 2022	19
July 2022	13
August 2022	8
September 2022	1
October 2022	7
November 2022	6
December 2022	6
February 2023	5
March 2023	6
April 2023	1
June 2023	3
July 2023	1
August 2023	2
September 2023	8
October 2023	6
November 2023	5
January 2024	2
February 2024	6
March 2024	4

Approximate String Matching with SIMD

Abstract

Citations

Views

Altmetric

Email alerts

Citing articles via

Latest

Most Read

Most Cited

Approximate String Matching with SIMD

Abstract

Sign in

Personal account

Institutional access

Institutional account management

Get help with access

Institutional access

IP based access

Sign in through your institution

Sign in with a library card

Society Members

Sign in through society site

Sign in using a personal account

Personal account

Viewing your signed in accounts

Signed in but can't access content

Institutional account management

Purchase

Short-term Access

Rental

Citations

Views

Altmetric

Email alerts

Citing articles via

Latest

Most Read

Most Cited

This Feature Is Available To Subscribers Only