Solution of skip distance constraint on sub-linear time string-matching architecture

Nai Lun Huang; Tsern-Huei Lee; Kuo Kun Tseng

doi:10.1109/TENCON.2013.6718990

Solution of skip distance constraint on sub-linear time string-matching architecture

Nai Lun Huang, Tsern-Huei Lee, Kuo Kun Tseng

Department of Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

Pre-filters are well-known techniques used to speed up string-matching process. The skip-based pre-filters make it possible to achieve sub-linear time complexity. However, they have a common constraint that their skip distances are bounded by the shortest keyword length. If the shortest keyword length is small, then this constraint will be a bottleneck problem in string-matching throughput. This paper provides a solution that the skip distance can be longer than the shortest keyword length. Also, a matching strategy based on the solution is proposed. This strategy can not only solve the bottleneck problem, but also reduce the operations in the sub-linear time string-matching procedure.

Original language	English
Title of host publication	2013 IEEE International Conference of IEEE Region 10, IEEE TENCON 2013 - Conference Proceedings
DOIs	https://doi.org/10.1109/TENCON.2013.6718990
State	Published - 1 Dec 2013
Event	2013 IEEE International Conference of IEEE Region 10, IEEE TENCON 2013 - Xi'an, Shaanxi, China Duration: 22 Oct 2013 → 25 Oct 2013

Publication series

Name	IEEE Region 10 Annual International Conference, Proceedings/TENCON
ISSN (Print)	2159-3442
ISSN (Electronic)	2159-3450

Conference

Conference	2013 IEEE International Conference of IEEE Region 10, IEEE TENCON 2013
Country	China
City	Xi'an, Shaanxi
Period	22/10/13 → 25/10/13

Keywords

pre-filter
skip distance
string matching
sub-linear time
verification

Access to Document

10.1109/TENCON.2013.6718990

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Solution of skip distance constraint on sub-linear time string-matching architecture'. Together they form a unique fingerprint.

Cite this

Huang, N. L., Lee, T-H., & Tseng, K. K. (2013). Solution of skip distance constraint on sub-linear time string-matching architecture. In 2013 IEEE International Conference of IEEE Region 10, IEEE TENCON 2013 - Conference Proceedings [6718990] (IEEE Region 10 Annual International Conference, Proceedings/TENCON). https://doi.org/10.1109/TENCON.2013.6718990

@inproceedings{8bb932f3c50e40f68eb707c722969607,

title = "Solution of skip distance constraint on sub-linear time string-matching architecture",

abstract = "Pre-filters are well-known techniques used to speed up string-matching process. The skip-based pre-filters make it possible to achieve sub-linear time complexity. However, they have a common constraint that their skip distances are bounded by the shortest keyword length. If the shortest keyword length is small, then this constraint will be a bottleneck problem in string-matching throughput. This paper provides a solution that the skip distance can be longer than the shortest keyword length. Also, a matching strategy based on the solution is proposed. This strategy can not only solve the bottleneck problem, but also reduce the operations in the sub-linear time string-matching procedure.",

keywords = "pre-filter, skip distance, string matching, sub-linear time, verification",

author = "Huang, {Nai Lun} and Tsern-Huei Lee and Tseng, {Kuo Kun}",

year = "2013",

month = dec,

day = "1",

doi = "10.1109/TENCON.2013.6718990",

language = "English",

isbn = "9781479928262",

series = "IEEE Region 10 Annual International Conference, Proceedings/TENCON",

booktitle = "2013 IEEE International Conference of IEEE Region 10, IEEE TENCON 2013 - Conference Proceedings",

note = "null ; Conference date: 22-10-2013 Through 25-10-2013",

}

Huang, NL, Lee, T-H & Tseng, KK 2013, Solution of skip distance constraint on sub-linear time string-matching architecture. in 2013 IEEE International Conference of IEEE Region 10, IEEE TENCON 2013 - Conference Proceedings., 6718990, IEEE Region 10 Annual International Conference, Proceedings/TENCON, 2013 IEEE International Conference of IEEE Region 10, IEEE TENCON 2013, Xi'an, Shaanxi, China, 22/10/13. https://doi.org/10.1109/TENCON.2013.6718990

Solution of skip distance constraint on sub-linear time string-matching architecture. / Huang, Nai Lun; Lee, Tsern-Huei; Tseng, Kuo Kun.

2013 IEEE International Conference of IEEE Region 10, IEEE TENCON 2013 - Conference Proceedings. 2013. 6718990 (IEEE Region 10 Annual International Conference, Proceedings/TENCON).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Solution of skip distance constraint on sub-linear time string-matching architecture

AU - Huang, Nai Lun

AU - Lee, Tsern-Huei

AU - Tseng, Kuo Kun

PY - 2013/12/1

Y1 - 2013/12/1

N2 - Pre-filters are well-known techniques used to speed up string-matching process. The skip-based pre-filters make it possible to achieve sub-linear time complexity. However, they have a common constraint that their skip distances are bounded by the shortest keyword length. If the shortest keyword length is small, then this constraint will be a bottleneck problem in string-matching throughput. This paper provides a solution that the skip distance can be longer than the shortest keyword length. Also, a matching strategy based on the solution is proposed. This strategy can not only solve the bottleneck problem, but also reduce the operations in the sub-linear time string-matching procedure.

AB - Pre-filters are well-known techniques used to speed up string-matching process. The skip-based pre-filters make it possible to achieve sub-linear time complexity. However, they have a common constraint that their skip distances are bounded by the shortest keyword length. If the shortest keyword length is small, then this constraint will be a bottleneck problem in string-matching throughput. This paper provides a solution that the skip distance can be longer than the shortest keyword length. Also, a matching strategy based on the solution is proposed. This strategy can not only solve the bottleneck problem, but also reduce the operations in the sub-linear time string-matching procedure.

KW - pre-filter

KW - skip distance

KW - string matching

KW - sub-linear time

KW - verification

UR - http://www.scopus.com/inward/record.url?scp=84894368247&partnerID=8YFLogxK

U2 - 10.1109/TENCON.2013.6718990

DO - 10.1109/TENCON.2013.6718990

M3 - Conference contribution

AN - SCOPUS:84894368247

SN - 9781479928262

T3 - IEEE Region 10 Annual International Conference, Proceedings/TENCON

BT - 2013 IEEE International Conference of IEEE Region 10, IEEE TENCON 2013 - Conference Proceedings

Y2 - 22 October 2013 through 25 October 2013

ER -