SMARTString Matching Algorithms Research Tool

by Simone Faro - www.dmi.unict.it/~faro/smart/ - email: faro@dmi.unict.it

Report of Experimental Results

Test Code EXP1790259501

Date 2026-09-24 17:19:53

Text midimusic (alphabet : 128 - size : 1048576 bytes)

248163264128256512102420484096
TVSBS
0.01
1.06
0.96 - 1.40
0.01
0.79
0.72 - 1.07
0.01
0.59
0.52 - 0.87
0.01
0.43
0.38 - 0.64
0.01
0.35
0.31 - 0.52
0.01
0.30
0.26 - 0.51
0.01
0.26
0.23 - 0.44
0.01
0.25
0.21 - 0.47
0.01
0.24
0.22 - 0.35
0.01
0.22
0.20 - 0.32
0.01
0.21
0.18 - 0.43
0.00
 -
0.00 - 0.00
SBNDMQ2
0.00
0.65
0.59 - 1.00
0.00
0.36
0.33 - 0.55
0.00
0.30
0.25 - 0.46
0.00
0.24
0.22 - 0.35
0.00
0.23
0.20 - 0.36
0.00
0.23
0.20 - 0.32
0.00
0.23
0.20 - 0.37
0.00
0.23
0.18 - 0.49
0.00
0.23
0.20 - 0.35
0.00
0.23
0.20 - 0.36
0.00
0.23
0.19 - 0.61
0.00
0.22
0.18 - 0.62
BXS2
0.00
0.84
0.80 - 1.15
0.00
0.36
0.32 - 0.52
0.00
0.29
0.24 - 0.49
0.00
0.24
0.21 - 0.40
0.00
0.23
0.20 - 0.37
0.00
0.23
0.20 - 0.38
0.00
0.24
0.20 - 0.34
0.00
0.22
0.18 - 0.55
0.00
0.23
0.20 - 0.37
0.00
0.23
0.20 - 0.32
0.00
0.22
0.19 - 0.54
0.00
0.22
0.19 - 0.56
FS-W8
0.00
 -
40.38 - 489451.54
0.00
 -
0.31 - 1375.90
4.81
5.25
0.27 - 259.63
0.24
0.60
0.23 - 17.46
0.19
0.49
0.23 - 13.04
0.06
0.34
0.21 - 13.95
0.03
0.31
0.22 - 7.68
0.09
0.32
0.19 - 16.53
0.04
0.27
0.20 - 11.49
0.02
0.23
0.19 - 0.87
0.02
0.22
0.18 - 0.58
0.03
0.22
0.20 - 0.48
FSBNDM-W6
0.00
 -
41.27 - 478917.05
0.00
 -
0.31 - 1358.86
4.84
5.28
0.27 - 253.73
0.24
0.60
0.23 - 16.20
0.19
0.50
0.23 - 12.87
0.07
0.34
0.21 - 14.57
0.03
0.31
0.21 - 6.26
0.08
0.30
0.19 - 14.84
0.04
0.27
0.20 - 11.62
0.02
0.23
0.20 - 0.45
0.02
0.22
0.19 - 0.60
0.03
0.22
0.20 - 0.62
FSBNDMQ20
0.00
0.64
0.59 - 0.83
0.00
0.36
0.32 - 0.51
0.00
0.30
0.25 - 0.50
0.00
0.24
0.21 - 0.36
0.00
0.23
0.20 - 0.38
0.00
0.23
0.19 - 0.34
0.00
0.26
0.21 - 0.36
0.00
0.22
0.19 - 0.48
0.00
0.23
0.20 - 0.36
0.00
0.23
0.18 - 0.60
0.00
0.23
0.19 - 0.65
0.00
0.22
0.19 - 0.47
FSBNDMQ41
0.00
0.84
0.80 - 1.16
0.00
0.58
0.54 - 0.85
0.00
0.33
0.31 - 0.47
0.00
0.25
0.23 - 0.36
0.00
0.23
0.21 - 0.34
0.00
0.23
0.21 - 0.33
0.00
0.25
0.21 - 0.35
0.00
0.22
0.20 - 0.41
0.00
0.23
0.21 - 0.34
0.00
0.22
0.19 - 0.47
0.00
0.23
0.21 - 0.32
0.00
0.23
0.21 - 0.34
LWFR4
0.00
0.84
0.81 - 1.19
0.01
0.85
0.80 - 1.48
0.01
0.35
0.32 - 0.51
0.01
0.26
0.24 - 0.37
0.01
0.23
0.21 - 0.35
0.01
0.22
0.20 - 0.33
0.01
0.23
0.20 - 0.33
0.01
0.20
0.17 - 0.42
0.01
0.21
0.19 - 0.32
0.01
0.21
0.17 - 0.57
0.02
0.23
0.20 - 0.91
0.03
0.32
0.21 - 2.96
QF34
0.00
0.84
0.81 - 1.16
0.00
0.53
0.49 - 0.81
0.00
0.32
0.29 - 0.49
0.00
0.26
0.23 - 0.40
0.00
0.23
0.20 - 0.34
0.00
0.22
0.19 - 0.38
0.00
0.24
0.19 - 0.34
0.00
0.21
0.18 - 0.44
0.00
0.21
0.18 - 0.75
0.00
0.20
0.17 - 0.65
0.00
0.24
0.18 - 1.17
0.01
0.26
0.19 - 1.77
QF43
0.00
0.84
0.80 - 1.21
0.00
0.85
0.81 - 1.23
0.00
0.34
0.31 - 0.50
0.00
0.25
0.23 - 0.35
0.00
0.22
0.21 - 0.37
0.00
0.21
0.20 - 0.31
0.00
0.23
0.19 - 0.31
0.00
0.20
0.19 - 0.32
0.00
0.20
0.18 - 0.30
0.00
0.19
0.17 - 0.40
0.00
0.20
0.18 - 0.38
0.01
0.22
0.18 - 0.66
TSA
0.00
0.74
0.68 - 1.39
0.00
0.49
0.45 - 0.69
0.00
0.35
0.32 - 0.52
0.00
0.28
0.25 - 0.42
0.00
0.24
0.21 - 0.37
0.00
0.22
0.20 - 0.32
0.03
0.31
0.22 - 7.71
0.11
0.34
0.20 - 27.47
0.05
0.27
0.20 - 13.21
0.02
0.23
0.19 - 0.50
0.02
0.23
0.20 - 0.37
0.03
0.23
0.21 - 0.36
WFRQ3
0.00
0.81
0.76 - 1.22
0.01
0.89
0.83 - 1.20
0.01
0.38
0.35 - 0.67
0.01
0.27
0.24 - 0.37
0.01
0.24
0.21 - 0.34
0.01
0.22
0.20 - 0.31
0.01
0.24
0.20 - 0.33
0.01
0.21
0.19 - 0.32
0.01
0.21
0.19 - 0.46
0.01
0.21
0.17 - 0.52
0.01
0.27
0.19 - 1.64
0.01
0.47
0.19 - 5.42
TWFR3
0.00
0.81
0.77 - 1.03
0.00
0.78
0.72 - 1.05
0.00
0.36
0.33 - 0.47
0.01
0.26
0.24 - 0.37
0.01
0.23
0.21 - 0.34
0.01
0.22
0.20 - 0.33
0.01
0.24
0.20 - 0.40
0.01
0.21
0.19 - 0.34
0.01
0.21
0.19 - 0.62
0.01
0.22
0.18 - 0.60
0.02
0.28
0.19 - 1.96
0.03
0.49
0.21 - 5.36
TWFRQ4
0.00
0.82
0.76 - 1.25
0.01
0.84
0.81 - 1.07
0.01
0.34
0.32 - 0.48
0.01
0.26
0.24 - 0.39
0.01
0.23
0.21 - 0.35
0.01
0.22
0.20 - 0.32
0.01
0.23
0.20 - 0.32
0.01
0.21
0.19 - 0.36
0.01
0.21
0.19 - 0.45
0.01
0.22
0.19 - 0.39
0.02
0.22
0.19 - 0.47
0.03
0.23
0.21 - 0.41
MUSL1
0.00
0.60
0.35 - 0.91
0.00
0.61
0.39 - 0.83
0.00
0.42
0.26 - 0.77
0.00
0.36
0.23 - 0.62
0.00
0.31
0.21 - 0.61
0.00
0.28
0.20 - 0.51
0.00
0.28
0.20 - 0.45
0.00
0.24
0.19 - 0.43
0.00
0.23
0.19 - 0.32
0.01
0.21
0.17 - 0.46
0.01
0.21
0.17 - 0.46
0.01
0.21
0.19 - 0.33
SIMDKR
0.00
0.24
0.20 - 0.43
0.00
0.25
0.20 - 0.48
0.00
0.23
0.20 - 0.41
0.00
0.24
0.20 - 0.48
0.00
0.23
0.20 - 0.41
0.00
0.24
0.20 - 0.50
0.00
0.22
0.18 - 0.64
0.00
0.23
0.20 - 0.40
0.00
0.23
0.20 - 0.33
0.00
0.22
0.18 - 0.57
0.00
0.22
0.18 - 0.62
0.00
0.23
0.20 - 0.44
KRSIMD
0.00
0.64
0.51 - 0.99
0.00
0.60
0.49 - 0.74
0.00
0.58
0.49 - 0.70
0.00
0.61
0.53 - 0.78
0.00
0.59
0.52 - 0.75
0.00
0.58
0.52 - 0.73
0.00
0.54
0.47 - 1.33
0.00
0.59
0.52 - 0.78
0.00
0.58
0.52 - 0.74
0.00
0.56
0.51 - 1.03
0.00
0.57
0.53 - 1.12
0.00
1.00
0.95 - 1.29
EPSM
0.00
0.25
0.23 - 0.36
0.00
0.27
0.25 - 0.40
0.00
0.29
0.27 - 0.36
0.00
0.26
0.24 - 0.37
0.00
0.23
0.21 - 0.32
0.00
0.22
0.20 - 0.31
0.01
0.21
0.18 - 0.46
0.01
0.21
0.19 - 0.27
0.01
0.22
0.20 - 0.31
0.02
0.23
0.20 - 0.40
0.05
0.27
0.22 - 0.69
0.12
0.35
0.32 - 0.53
HC4
0.00
 -
0.00 - 0.00
0.00
0.85
0.80 - 1.12
0.00
0.34
0.31 - 0.48
0.00
0.26
0.24 - 0.36
0.00
0.23
0.21 - 0.33
0.00
0.22
0.20 - 0.31
0.00
0.20
0.18 - 0.45
0.00
0.20
0.19 - 0.30
0.00
0.20
0.18 - 0.36
0.00
0.21
0.17 - 0.41
0.00
0.22
0.17 - 0.98
0.01
0.36
0.19 - 3.01
LHC3
0.00
 -
0.00 - 0.00
0.00
0.51
0.48 - 0.76
0.00
0.31
0.29 - 0.48
0.00
0.26
0.23 - 0.38
0.00
0.23
0.21 - 0.34
0.00
0.22
0.20 - 0.33
0.00
0.21
0.17 - 0.46
0.00
0.20
0.19 - 0.30
0.00
0.20
0.18 - 0.31
0.01
0.20
0.17 - 0.46
0.01
0.20
0.17 - 0.52
0.01
0.21
0.19 - 0.31
LHC7
0.00
 -
0.00 - 0.00
0.00
 -
0.00 - 0.00
0.00
0.72
0.69 - 0.94
0.00
0.31
0.29 - 0.43
0.00
0.24
0.23 - 0.35
0.00
0.22
0.20 - 0.32
0.00
0.21
0.18 - 0.50
0.00
0.21
0.19 - 0.31
0.00
0.20
0.19 - 0.32
0.01
0.20
0.17 - 0.47
0.01
0.20
0.18 - 0.42
0.01
0.21
0.19 - 0.28
FHC3
0.00
 -
0.00 - 0.00
0.00
0.43
0.40 - 0.64
0.00
0.28
0.26 - 0.40
0.00
0.24
0.22 - 0.33
0.00
0.22
0.21 - 0.32
0.00
0.21
0.18 - 0.56
0.00
0.20
0.18 - 0.39
0.00
0.20
0.19 - 0.30
0.01
0.21
0.18 - 0.40
0.01
0.21
0.17 - 0.74
0.01
0.23
0.17 - 1.60
0.01
0.40
0.19 - 4.10
Table 1. Running times of experimental tests n.EXP1790259501. Each time value is the mean of 500 runs. Running times are in milliseconds.

Average Running Times
[No canvas support]
TVSBS
SBNDMQ2
BXS2
FS-W8
FSBNDM-W6
FSBNDMQ20
FSBNDMQ41
LWFR4
QF34
QF43
TSA
WFRQ3
TWFR3
TWFRQ4
MUSL1
SIMDKR
KRSIMD
EPSM
HC4
LHC3
LHC7
FHC3


Chart 1. Plot of the running times of experimental tests n.EXP1790259501. The x axes reports the length of the pattern (in a log scale) while the y axes reports the running time in milliseconds.
Worst Running Times
[No canvas support]
Best Running Times
[No canvas support]
TVSBS - Thathoo-Virmani-Sai-Balakrishnan-Sekar
[No canvas support]
Detailed plot of the running times relative to the TVSBS algorithm. The plot reports the mean and the distribution of the running times.
SBNDMQ2 - simplified bndm with q-grams
[No canvas support]
Detailed plot of the running times relative to the SBNDMQ2 algorithm. The plot reports the mean and the distribution of the running times.
BXS2 - BXS with q-grams limit
[No canvas support]
Detailed plot of the running times relative to the BXS2 algorithm. The plot reports the mean and the distribution of the running times.
FS-W8 - Multiple Sliding Windows
[No canvas support]
Detailed plot of the running times relative to the FS-W8 algorithm. The plot reports the mean and the distribution of the running times.
FSBNDM-W6 - fsbndm with multiple sliding windows
[No canvas support]
Detailed plot of the running times relative to the FSBNDM-W6 algorithm. The plot reports the mean and the distribution of the running times.
FSBNDMQ20 - fsbndm with q-grams and lookahead
[No canvas support]
Detailed plot of the running times relative to the FSBNDMQ20 algorithm. The plot reports the mean and the distribution of the running times.
FSBNDMQ41 - fsbndm with q-grams and lookahead
[No canvas support]
Detailed plot of the running times relative to the FSBNDMQ41 algorithm. The plot reports the mean and the distribution of the running times.
LWFR4 - Weak Factor Recognizer, Linear Version
[No canvas support]
Detailed plot of the running times relative to the LWFR4 algorithm. The plot reports the mean and the distribution of the running times.
QF34 - Q-gram Filtering q=3 s=4
[No canvas support]
Detailed plot of the running times relative to the QF34 algorithm. The plot reports the mean and the distribution of the running times.
QF43 - Q-gram Filtering q=4 s=3
[No canvas support]
Detailed plot of the running times relative to the QF43 algorithm. The plot reports the mean and the distribution of the running times.
TSA - word-wise popcount
[No canvas support]
Detailed plot of the running times relative to the TSA algorithm. The plot reports the mean and the distribution of the running times.
WFRQ3 - Weak Factor Recognizer with q-grams
[No canvas support]
Detailed plot of the running times relative to the WFRQ3 algorithm. The plot reports the mean and the distribution of the running times.
TWFR3 - Tuned Weak Factor Recognizer
[No canvas support]
Detailed plot of the running times relative to the TWFR3 algorithm. The plot reports the mean and the distribution of the running times.
TWFRQ4 - Tuned Weak Factor Recognizer with q-grams
[No canvas support]
Detailed plot of the running times relative to the TWFRQ4 algorithm. The plot reports the mean and the distribution of the running times.
MUSL1 - musl memmem Two-way string-matching
[No canvas support]
Detailed plot of the running times relative to the MUSL1 algorithm. The plot reports the mean and the distribution of the running times.
SIMDKR - SIMD generic Rabin-Karp variants
[No canvas support]
Detailed plot of the running times relative to the SIMDKR algorithm. The plot reports the mean and the distribution of the running times.
KRSIMD - Polynomial SIMD Rabin-Karp (AVX2)
[No canvas support]
Detailed plot of the running times relative to the KRSIMD algorithm. The plot reports the mean and the distribution of the running times.
EPSM - SSE4 Exact Packed String Matching
[No canvas support]
Detailed plot of the running times relative to the EPSM algorithm. The plot reports the mean and the distribution of the running times.
HC4 - HashChain q=4
[No canvas support]
Detailed plot of the running times relative to the HC4 algorithm. The plot reports the mean and the distribution of the running times.
LHC3 - Linear HashChain q=3
[No canvas support]
Detailed plot of the running times relative to the LHC3 algorithm. The plot reports the mean and the distribution of the running times.
LHC7 - Linear HashChain q=7
[No canvas support]
Detailed plot of the running times relative to the LHC7 algorithm. The plot reports the mean and the distribution of the running times.
FHC3 - Fast HashChain q=3
[No canvas support]
Detailed plot of the running times relative to the FHC3 algorithm. The plot reports the mean and the distribution of the running times.