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 16:18:21

Text rand2 (alphabet : 2 - size : 1048576 bytes)

248163264128256512102420484096
TVSBS
0.01
2.81
2.20 - 3.68
0.01
2.70
1.98 - 3.76
0.01
2.60
1.44 - 4.23
0.01
2.79
0.94 - 4.22
0.01
2.83
0.93 - 4.83
0.01
2.87
0.89 - 4.91
0.01
2.78
0.71 - 4.37
0.01
2.65
0.84 - 4.94
0.01
2.83
1.03 - 4.40
0.01
2.84
0.79 - 4.83
0.01
2.91
0.80 - 5.18
0.00
 -
3.33 - 3.33
SBNDMQ2
0.00
2.39
2.26 - 2.71
0.00
2.36
1.38 - 4.87
0.00
1.47
0.68 - 3.23
0.00
0.85
0.74 - 1.71
0.00
0.52
0.46 - 0.74
0.00
0.49
0.43 - 1.26
0.00
0.49
0.43 - 1.18
0.00
0.50
0.44 - 1.03
0.00
0.50
0.45 - 0.66
0.00
0.50
0.47 - 0.73
0.00
0.49
0.45 - 1.27
0.00
0.56
0.47 - 0.73
BXS2
0.00
0.83
0.80 - 1.32
0.00
2.68
1.55 - 6.37
0.00
1.76
0.73 - 3.37
0.00
0.96
0.82 - 2.61
0.00
0.60
0.53 - 0.88
0.00
0.60
0.51 - 1.68
0.00
0.59
0.52 - 1.64
0.00
0.61
0.51 - 1.64
0.00
0.60
0.54 - 0.80
0.00
0.60
0.55 - 0.85
0.00
0.58
0.52 - 1.75
0.00
0.63
0.51 - 1.70
FS-W8
0.00
 -
999.00 - 7357365.72
0.00
 -
999.00 - 483802.15
0.00
 -
999.00 - 1891.07
0.10
2.91
1.12 - 7.75
0.01
3.19
1.06 - 4.94
0.01
3.27
0.89 - 6.32
0.01
3.49
0.85 - 6.61
0.01
3.35
0.95 - 6.28
0.02
3.55
0.81 - 4.82
0.02
3.56
0.62 - 4.44
0.04
3.62
0.86 - 6.84
0.07
3.52
1.18 - 6.92
FSBNDM-W6
0.00
 -
999.00 - 7339991.74
0.00
 -
999.00 - 498214.47
0.00
 -
999.00 - 1918.59
0.10
2.86
1.12 - 4.98
0.01
3.18
1.02 - 4.72
0.01
3.25
0.87 - 7.13
0.01
3.44
0.78 - 6.11
0.01
3.39
0.95 - 6.65
0.02
3.54
0.80 - 5.16
0.02
3.57
0.62 - 5.18
0.04
3.62
0.83 - 8.75
0.07
3.55
1.18 - 7.81
FSBNDMQ20
0.00
2.43
2.28 - 2.84
0.00
2.28
1.43 - 2.61
0.00
1.49
0.69 - 2.80
0.00
0.82
0.69 - 1.84
0.00
0.52
0.48 - 0.67
0.00
0.51
0.44 - 1.28
0.00
0.50
0.45 - 1.20
0.00
0.50
0.45 - 1.16
0.00
0.52
0.46 - 0.75
0.00
0.52
0.48 - 0.77
0.00
0.51
0.45 - 1.18
0.00
0.51
0.44 - 1.27
FSBNDMQ41
0.00
0.85
0.81 - 1.22
0.00
1.61
1.29 - 1.85
0.00
1.20
0.60 - 2.37
0.00
0.78
0.52 - 1.64
0.00
0.50
0.45 - 0.66
0.00
0.50
0.44 - 1.05
0.00
0.49
0.43 - 1.13
0.00
0.48
0.43 - 1.16
0.00
0.50
0.41 - 0.67
0.00
0.50
0.46 - 0.74
0.00
0.49
0.40 - 1.22
0.00
0.51
0.43 - 1.10
LWFR4
0.00
0.85
0.81 - 1.19
0.01
1.41
1.32 - 1.83
0.00
1.24
0.52 - 2.54
0.01
0.77
0.48 - 1.46
0.01
0.48
0.38 - 0.70
0.01
0.37
0.29 - 0.89
0.01
0.29
0.26 - 0.77
0.01
0.26
0.23 - 0.64
0.01
0.28
0.24 - 0.61
0.01
20.30
0.24 - 103.66
0.02
181.10
0.30 - 201.01
0.00
 -
358.77 - 358.77
QF34
0.00
0.84
0.81 - 1.21
0.00
2.50
1.60 - 3.21
0.00
1.72
0.49 - 3.03
0.00
1.23
0.60 - 3.05
0.00
1.59
0.48 - 3.91
0.00
4.33
0.44 - 7.31
0.00
8.62
8.15 - 11.26
0.00
17.03
16.22 - 20.72
0.00
32.91
31.59 - 34.22
0.00
62.08
58.04 - 63.34
0.00
110.82
107.57 - 122.92
0.01
215.71
211.64 - 240.31
QF43
0.00
0.84
0.81 - 1.16
0.00
0.84
0.80 - 1.13
0.00
1.40
0.54 - 2.85
0.00
0.72
0.48 - 1.85
0.00
0.58
0.39 - 0.77
0.00
0.45
0.32 - 1.44
0.00
2.04
0.30 - 7.31
0.00
9.43
0.48 - 10.28
0.00
19.29
18.60 - 22.94
0.00
32.94
31.29 - 37.58
0.00
66.24
59.71 - 68.55
0.01
117.87
115.18 - 131.59
TSA
0.00
2.10
2.05 - 3.09
0.00
1.88
1.55 - 2.31
0.00
1.23
0.98 - 2.38
0.00
0.75
0.61 - 1.48
0.00
0.52
0.45 - 0.64
0.00
0.34
0.29 - 1.15
0.01
3.50
0.79 - 6.98
0.01
3.55
1.06 - 4.61
0.02
3.61
0.81 - 4.95
0.02
3.45
0.62 - 6.03
0.04
3.67
0.89 - 5.06
0.07
3.61
1.27 - 6.01
WFRQ3
0.00
0.84
0.81 - 1.17
0.00
2.37
2.00 - 2.79
0.00
2.09
0.88 - 5.49
0.00
0.74
0.58 - 1.69
0.01
0.49
0.41 - 0.91
0.01
0.36
0.30 - 0.81
0.01
0.28
0.25 - 0.65
0.01
0.26
0.24 - 0.36
0.01
0.25
0.22 - 0.35
0.01
9.97
0.21 - 241.91
0.00
 -
501.97 - 501.97
0.00
 -
922.86 - 922.86
TWFR3
0.00
0.84
0.81 - 1.07
0.00
1.94
1.53 - 4.25
0.00
1.99
0.76 - 5.28
0.00
0.90
0.61 - 2.32
0.01
0.56
0.43 - 1.21
0.01
0.40
0.33 - 1.02
0.01
0.30
0.27 - 0.63
0.01
0.27
0.24 - 0.36
0.01
0.28
0.24 - 0.76
0.01
45.92
0.23 - 256.15
0.00
 -
501.67 - 501.67
0.00
 -
919.48 - 919.48
TWFRQ4
0.00
0.84
0.81 - 1.09
0.00
1.35
1.25 - 2.81
0.00
1.19
0.52 - 2.79
0.00
0.64
0.46 - 1.07
0.00
0.36
0.29 - 1.02
0.00
0.28
0.24 - 0.69
0.01
0.26
0.23 - 0.59
0.01
0.25
0.23 - 0.36
0.01
0.24
0.22 - 0.33
0.02
3.42
0.62 - 6.58
0.04
3.67
0.89 - 5.21
0.07
3.59
1.21 - 6.41
MUSL1
0.00
2.76
2.56 - 3.27
0.00
1.15
1.02 - 2.53
0.00
2.97
1.44 - 5.34
0.00
3.04
1.08 - 6.41
0.00
3.31
1.03 - 6.44
0.00
3.69
0.97 - 6.83
0.00
3.69
0.77 - 7.29
0.00
3.74
1.12 - 5.26
0.01
3.80
0.85 - 5.30
0.01
3.61
0.62 - 7.01
0.01
3.84
0.90 - 5.15
0.02
3.75
1.21 - 6.45
SIMDKR
0.00
0.78
0.74 - 1.02
0.00
1.27
1.11 - 3.47
0.00
0.84
0.75 - 2.19
0.00
0.79
0.70 - 2.03
0.00
0.78
0.71 - 1.56
0.00
0.80
0.73 - 1.64
0.00
0.80
0.74 - 2.11
0.00
0.82
0.79 - 1.16
0.00
0.82
0.78 - 1.21
0.00
0.80
0.73 - 1.91
0.00
0.82
0.79 - 1.01
0.00
0.81
0.73 - 2.05
KRSIMD
0.00
1.89
1.79 - 2.48
0.00
1.39
1.16 - 2.89
0.00
0.63
0.56 - 1.36
0.00
0.54
0.48 - 1.12
0.00
0.53
0.48 - 1.23
0.00
0.54
0.47 - 1.10
0.00
0.54
0.50 - 1.16
0.00
0.59
0.53 - 0.80
0.00
0.58
0.53 - 0.79
0.00
0.56
0.51 - 0.85
0.00
0.61
0.55 - 0.94
0.00
0.96
0.87 - 1.29
EPSM
0.00
0.25
0.23 - 0.37
0.00
0.26
0.23 - 0.54
0.00
1.19
0.86 - 2.90
0.00
0.30
0.25 - 0.60
0.00
0.25
0.22 - 0.53
0.00
0.24
0.21 - 0.57
0.01
0.23
0.20 - 0.64
0.01
0.23
0.22 - 0.32
0.01
0.24
0.22 - 0.34
0.03
0.24
0.21 - 0.59
0.06
0.29
0.27 - 0.48
0.15
0.38
0.33 - 0.89
HC4
0.00
 -
0.00 - 0.00
0.00
1.39
1.27 - 2.45
0.00
1.09
0.51 - 2.66
0.00
0.70
0.47 - 0.93
0.00
0.44
0.32 - 1.30
0.00
0.36
0.29 - 0.99
0.00
0.32
0.26 - 0.79
0.00
13.23
0.26 - 38.98
0.00
75.89
0.34 - 79.09
0.00
136.20
133.91 - 152.30
0.00
293.61
264.78 - 296.65
0.00
 -
583.06 - 583.06
LHC3
0.00
 -
0.00 - 0.00
0.00
2.05
1.30 - 3.95
0.00
1.52
0.57 - 2.97
0.00
0.94
0.68 - 1.32
0.00
0.69
0.43 - 1.35
0.00
1.00
0.38 - 4.84
0.00
2.76
0.29 - 6.03
0.00
3.96
0.71 - 4.71
0.01
4.01
3.92 - 8.33
0.01
3.87
3.57 - 7.04
0.01
4.07
3.92 - 4.82
0.02
3.79
3.55 - 6.57
LHC7
0.00
 -
0.00 - 0.00
0.00
 -
0.00 - 0.00
0.00
0.82
0.74 - 1.11
0.00
0.41
0.35 - 0.54
0.00
0.30
0.26 - 0.57
0.00
0.27
0.23 - 0.63
0.00
0.23
0.21 - 0.45
0.00
0.21
0.20 - 0.32
0.01
0.20
0.19 - 0.32
0.01
0.19
0.17 - 0.36
0.01
0.23
0.19 - 0.30
0.02
0.20
0.18 - 0.46
FHC3
0.00
 -
0.00 - 0.00
0.00
1.96
1.23 - 4.87
0.00
1.27
0.52 - 3.30
0.00
0.72
0.54 - 1.00
0.00
0.57
0.42 - 1.63
0.00
0.63
0.32 - 11.93
0.00
12.49
0.26 - 25.84
0.00
49.79
0.34 - 51.54
0.01
95.40
84.88 - 96.95
0.01
169.27
166.43 - 188.79
0.00
 -
368.04 - 368.04
0.00
 -
667.63 - 667.63
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.