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 EXP1742206914

Date 2025-03-17 11:21:54

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

248163264128256512102420484096
TVSBS
0.02
5.11
3.96 - 6.33
0.02
5.26
3.94 - 7.08
0.02
5.49
3.04 - 7.97
0.02
5.63
2.42 - 8.51
0.02
5.54
1.95 - 8.17
0.02
5.68
1.52 - 8.63
0.02
5.49
1.55 - 8.51
0.02
5.44
1.81 - 7.91
0.02
5.49
1.90 - 8.27
0.02
5.52
2.37 - 8.31
0.02
5.36
1.89 - 7.82
0.00
 -
7.39 - 7.39
SBNDMQ2
0.01
4.87
4.54 - 6.52
0.01
4.87
3.04 - 5.81
0.01
3.29
1.58 - 3.89
0.01
1.87
1.57 - 2.31
0.01
1.18
1.08 - 1.48
0.01
1.14
1.04 - 1.44
0.01
1.13
1.06 - 1.61
0.01
1.10
1.06 - 1.47
0.01
1.10
1.03 - 1.29
0.01
1.14
1.05 - 1.68
0.01
1.10
1.04 - 1.91
0.01
1.10
1.04 - 1.30
BXS2
0.01
1.94
1.81 - 2.29
0.01
5.68
3.36 - 6.95
0.01
3.79
1.70 - 4.36
0.01
2.13
1.86 - 2.74
0.01
1.32
1.21 - 1.68
0.01
1.33
1.21 - 1.67
0.01
1.33
1.22 - 1.72
0.01
1.30
1.20 - 1.65
0.01
1.32
1.20 - 1.73
0.01
1.33
1.19 - 1.71
0.01
1.31
1.16 - 1.48
0.01
1.31
1.22 - 1.39
FS-W8
0.02
8.70
8.03 - 9.68
0.02
6.88
4.87 - 8.64
0.02
5.17
2.74 - 6.83
0.02
3.82
2.56 - 5.45
0.02
3.01
2.02 - 4.13
0.02
2.45
1.80 - 3.41
0.02
2.05
1.36 - 3.01
0.02
1.74
1.26 - 2.73
0.03
1.55
1.10 - 2.68
0.04
1.46
0.96 - 2.24
0.06
1.31
0.98 - 1.87
0.09
1.26
0.94 - 1.75
FSBNDM-W6
0.01
1.94
1.81 - 2.28
0.01
1.93
1.81 - 2.29
0.00
 -
0.01 - 14.26
0.00
 -
0.01 - 0.01
0.00
 -
0.01 - 0.01
0.00
 -
0.01 - 0.01
0.00
 -
0.01 - 0.01
0.00
 -
0.01 - 17.70
0.00
 -
0.01 - 0.01
0.00
 -
0.01 - 0.01
0.00
 -
0.01 - 17.87
0.00
 -
0.01 - 0.01
FSBNDMQ20
0.01
5.02
4.60 - 5.50
0.01
4.80
2.98 - 5.76
0.01
3.23
1.55 - 3.86
0.01
1.84
1.61 - 2.29
0.01
1.16
1.08 - 1.50
0.01
1.17
1.06 - 1.56
0.01
1.17
1.06 - 1.60
0.01
1.12
1.05 - 1.64
0.01
1.15
1.03 - 1.61
0.01
1.16
1.07 - 1.55
0.01
1.12
1.02 - 1.27
0.01
1.12
1.07 - 1.24
LWFR4
0.01
1.92
1.81 - 2.36
0.01
2.90
2.51 - 3.82
0.01
2.48
1.20 - 3.48
0.01
1.61
0.97 - 2.16
0.01
1.06
0.90 - 1.37
0.01
0.86
0.74 - 1.14
0.01
0.73
0.63 - 0.95
0.02
0.64
0.58 - 0.71
0.03
0.75
0.56 - 6.17
0.04
34.78
0.60 - 196.25
0.00
 -
360.11 - 360.11
0.00
 -
693.75 - 693.75
QF34
0.01
1.94
1.80 - 2.96
0.01
4.62
2.88 - 6.95
0.01
3.61
1.15 - 4.74
0.01
2.71
1.50 - 5.20
0.01
3.83
1.20 - 11.18
0.01
13.22
0.99 - 20.07
0.01
26.61
1.13 - 29.07
0.01
47.69
46.26 - 52.35
0.01
94.15
90.28 - 112.73
0.01
180.63
174.80 - 207.98
0.00
 -
341.89 - 341.89
0.00
 -
717.17 - 717.17
QF43
0.01
1.93
1.80 - 2.46
0.01
1.94
1.76 - 2.34
0.01
2.63
1.12 - 4.80
0.01
1.58
0.95 - 2.18
0.01
1.20
0.88 - 1.67
0.01
1.07
0.74 - 2.62
0.01
6.01
0.71 - 20.26
0.01
32.96
1.04 - 36.48
0.01
64.76
62.24 - 69.62
0.01
122.09
117.88 - 127.76
0.01
237.56
231.24 - 250.74
0.00
 -
475.82 - 475.82
TSA
0.01
4.59
4.33 - 5.27
0.01
3.93
3.16 - 4.92
0.01
2.70
2.16 - 3.27
0.01
1.66
1.49 - 2.04
0.01
1.10
1.01 - 1.46
0.01
0.83
0.73 - 1.17
0.02
6.94
1.30 - 9.05
0.03
6.64
1.51 - 9.21
0.04
6.97
2.07 - 9.01
0.05
6.75
1.64 - 9.64
0.10
6.81
1.58 - 9.22
0.17
7.01
2.48 - 10.53
WFRQ3
0.01
1.93
1.82 - 2.35
0.01
4.53
3.78 - 5.52
0.01
4.06
1.87 - 5.75
0.01
1.53
1.14 - 2.10
0.01
1.06
0.89 - 1.39
0.01
0.83
0.72 - 1.07
0.01
0.71
0.63 - 1.01
0.01
0.62
0.56 - 0.98
0.01
0.64
0.55 - 0.86
0.00
 -
0.56 - 529.13
0.00
 -
999.00 - 1033.12
0.00
 -
999.00 - 2100.14
TWFR3
0.01
1.93
1.81 - 2.26
0.01
4.40
3.61 - 5.54
0.01
4.02
1.70 - 6.02
0.01
1.82
1.30 - 2.50
0.01
1.21
1.02 - 1.54
0.01
0.90
0.78 - 1.26
0.01
0.74
0.65 - 1.10
0.01
0.64
0.57 - 0.84
0.02
0.73
0.55 - 12.18
0.00
 -
0.63 - 441.55
0.00
 -
855.43 - 855.43
0.00
 -
999.00 - 1685.30
TWFRQ4
0.01
1.94
1.81 - 2.37
0.01
3.24
3.04 - 3.78
0.01
2.58
1.22 - 3.66
0.01
1.41
1.11 - 1.86
0.01
0.88
0.74 - 1.27
0.01
0.72
0.63 - 1.07
0.01
0.68
0.59 - 0.90
0.01
0.61
0.56 - 0.90
0.01
0.64
0.54 - 0.85
0.05
7.22
1.72 - 9.22
0.09
7.32
1.71 - 9.49
0.17
7.48
2.57 - 9.85
MUSL1
0.00
5.42
4.75 - 7.29
0.00
2.54
2.20 - 3.33
0.01
6.66
3.07 - 9.79
0.01
6.93
2.70 - 10.03
0.01
7.45
1.84 - 10.25
0.01
7.80
2.12 - 10.33
0.01
7.82
1.40 - 10.97
0.01
7.54
1.63 - 10.26
0.01
7.90
2.35 - 10.54
0.02
7.55
1.68 - 9.77
0.03
7.66
1.70 - 10.36
0.05
7.75
2.60 - 10.20
SIMDKR
0.01
1.55
1.34 - 4.30
0.01
2.33
2.10 - 3.82
0.01
1.62
1.45 - 5.04
0.01
1.58
1.41 - 4.63
0.01
1.58
1.41 - 3.34
0.01
1.53
1.39 - 4.46
0.01
1.52
1.39 - 4.39
0.01
1.45
1.39 - 2.49
0.01
1.52
1.39 - 4.87
0.01
1.46
1.39 - 4.39
0.01
1.45
1.39 - 4.36
0.01
1.45
1.39 - 4.05
EPSM
0.00
0.62
0.55 - 1.07
0.01
0.66
0.58 - 0.99
0.01
2.31
1.83 - 3.12
0.01
0.70
0.61 - 1.06
0.01
0.64
0.57 - 0.93
0.01
0.62
0.55 - 0.93
0.01
0.62
0.55 - 0.93
0.02
0.58
0.53 - 0.71
0.03
0.62
0.54 - 0.88
0.06
0.61
0.57 - 1.00
0.12
0.70
0.63 - 0.79
0.30
0.90
0.83 - 1.17
HC4
0.00
 -
0.00 - 0.00
0.01
2.80
2.53 - 4.34
0.01
2.24
1.13 - 3.22
0.01
1.44
0.99 - 1.83
0.01
1.02
0.84 - 1.38
0.01
0.87
0.73 - 1.14
0.01
0.85
0.65 - 11.04
0.01
36.50
0.56 - 123.91
0.01
239.46
1.01 - 294.07
0.00
 -
480.56 - 480.56
0.00
 -
949.39 - 949.39
0.00
 -
999.00 - 1878.31
LHC3
0.00
 -
0.00 - 0.00
0.01
4.34
2.92 - 5.90
0.01
3.16
1.27 - 4.05
0.01
1.90
1.24 - 2.62
0.01
1.49
1.02 - 3.93
0.01
2.16
0.87 - 7.37
0.01
6.00
0.76 - 11.30
0.01
7.95
1.51 - 8.92
0.01
8.42
7.77 - 9.39
0.02
8.14
7.56 - 8.98
0.02
8.07
7.48 - 8.99
0.04
8.10
7.44 - 8.99
LHC7
0.00
 -
0.00 - 0.00
0.00
 -
0.00 - 0.00
0.01
1.96
1.74 - 2.68
0.01
0.96
0.80 - 1.32
0.01
0.77
0.63 - 1.01
0.01
0.70
0.60 - 0.96
0.01
0.60
0.55 - 0.81
0.01
0.55
0.50 - 0.85
0.01
0.56
0.50 - 0.75
0.02
0.53
0.49 - 0.80
0.02
0.53
0.49 - 0.64
0.04
0.55
0.51 - 0.70
FHC3
0.00
 -
0.00 - 0.00
0.01
3.94
2.61 - 5.84
0.01
2.57
1.14 - 3.56
0.01
1.52
1.11 - 1.97
0.01
1.22
0.94 - 1.79
0.01
1.27
0.77 - 7.80
0.01
28.38
0.64 - 61.35
0.01
93.21
0.79 - 111.60
0.02
181.80
175.46 - 202.18
0.00
 -
350.24 - 350.24
0.00
 -
693.30 - 693.30
0.00
 -
999.00 - 1355.05
Table 1. Running times of experimental tests n.EXP1742206914. 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
LWFR4
QF34
QF43
TSA
WFRQ3
TWFR3
TWFRQ4
MUSL1
SIMDKR
EPSM
HC4
LHC3
LHC7
FHC3


Chart 1. Plot of the running times of experimental tests n.EXP1742206914. 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.
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.
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.