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 12:13:29

Text rand256 (alphabet : 256 - size : 1048576 bytes)

248163264128256512102420484096
TVSBS
0.02
3.12
2.67 - 3.78
0.02
2.29
2.12 - 2.97
0.02
1.73
1.52 - 2.39
0.02
1.18
1.12 - 1.45
0.02
1.10
0.84 - 5.33
0.02
0.79
0.71 - 1.07
0.02
0.67
0.59 - 1.24
0.02
0.63
0.55 - 0.89
0.02
0.59
0.53 - 0.69
0.02
0.57
0.51 - 0.79
0.02
0.61
0.52 - 0.85
0.00
 -
0.00 - 0.00
SBNDMQ2
0.01
1.33
1.22 - 1.97
0.01
0.78
0.71 - 1.06
0.01
0.68
0.59 - 1.22
0.01
0.58
0.52 - 0.82
0.01
0.58
0.51 - 0.84
0.01
0.60
0.53 - 0.86
0.01
0.56
0.50 - 0.89
0.01
0.55
0.50 - 0.84
0.01
0.55
0.50 - 0.63
0.01
0.56
0.50 - 0.80
0.01
0.59
0.55 - 0.78
0.01
0.56
0.51 - 0.83
BXS2
0.01
1.94
1.80 - 2.32
0.01
0.84
0.77 - 1.20
0.01
0.68
0.60 - 0.90
0.01
0.58
0.53 - 0.84
0.01
0.66
0.53 - 1.79
0.01
0.60
0.54 - 0.78
0.01
0.55
0.50 - 1.63
0.01
0.56
0.50 - 0.84
0.01
0.55
0.50 - 0.88
0.01
0.56
0.51 - 0.92
0.01
0.58
0.52 - 0.86
0.01
0.55
0.51 - 0.73
FS-W8
0.02
0.95
0.84 - 1.37
0.02
0.72
0.66 - 1.05
0.02
0.82
0.59 - 4.83
0.02
0.61
0.53 - 0.90
0.02
0.61
0.56 - 1.04
0.02
0.59
0.53 - 0.88
0.02
0.54
0.49 - 0.81
0.02
0.54
0.49 - 0.82
0.02
0.53
0.49 - 0.63
0.03
0.54
0.49 - 0.82
0.04
0.58
0.52 - 0.72
0.06
0.57
0.52 - 0.73
FSBNDM-W6
0.01
1.93
1.80 - 2.38
0.01
1.89
1.80 - 2.44
0.01
0.64
0.57 - 0.90
0.01
0.59
0.52 - 0.85
0.01
0.60
0.53 - 0.83
0.01
0.60
0.52 - 0.97
0.01
0.54
0.49 - 0.89
0.01
0.54
0.50 - 0.81
0.01
0.54
0.50 - 0.77
0.01
0.54
0.50 - 0.69
0.01
0.57
0.51 - 0.90
0.01
0.54
0.50 - 0.72
FSBNDMQ20
0.01
1.43
1.33 - 2.07
0.01
0.81
0.73 - 1.22
0.01
0.64
0.58 - 0.88
0.01
0.61
0.53 - 0.91
0.01
0.59
0.54 - 0.76
0.01
0.60
0.52 - 0.80
0.01
0.55
0.51 - 0.77
0.01
0.56
0.51 - 0.79
0.01
0.55
0.51 - 0.64
0.01
0.56
0.51 - 0.84
0.01
0.59
0.52 - 0.89
0.01
0.55
0.51 - 0.80
LWFR4
0.01
1.94
1.80 - 2.60
0.01
1.86
1.78 - 2.41
0.01
0.80
0.73 - 1.19
0.01
0.66
0.58 - 0.93
0.01
0.62
0.57 - 0.95
0.01
0.59
0.51 - 0.89
0.01
0.54
0.50 - 0.82
0.02
0.54
0.49 - 1.02
0.02
0.53
0.49 - 0.75
0.03
0.55
0.50 - 0.84
0.05
0.59
0.53 - 0.77
0.09
0.62
0.56 - 0.96
QF34
0.01
1.93
1.81 - 2.32
0.01
1.10
1.04 - 1.52
0.01
0.73
0.65 - 1.21
0.01
0.65
0.56 - 1.08
0.01
0.62
0.56 - 0.84
0.01
0.57
0.50 - 0.86
0.01
0.53
0.49 - 0.66
0.01
0.53
0.48 - 0.69
0.01
0.52
0.48 - 0.88
0.01
0.53
0.48 - 0.77
0.01
0.54
0.49 - 0.79
0.01
0.53
0.48 - 0.73
QF43
0.01
1.93
1.80 - 2.41
0.01
1.90
1.81 - 2.42
0.01
0.77
0.69 - 1.24
0.01
0.66
0.56 - 1.09
0.01
0.63
0.56 - 0.89
0.01
0.55
0.50 - 0.82
0.01
0.54
0.49 - 0.87
0.01
0.53
0.48 - 0.75
0.01
0.52
0.48 - 0.63
0.01
0.52
0.47 - 0.76
0.01
0.53
0.48 - 0.75
0.01
0.53
0.48 - 0.91
TSA
0.01
1.89
1.76 - 2.73
0.01
1.18
1.11 - 1.59
0.01
0.84
0.77 - 1.01
0.01
0.69
0.62 - 1.06
0.01
0.66
0.58 - 0.90
0.01
0.57
0.51 - 0.91
0.02
0.60
0.54 - 0.89
0.02
0.59
0.54 - 0.72
0.02
0.59
0.54 - 0.75
0.03
0.60
0.54 - 0.98
0.04
0.63
0.55 - 0.98
0.06
0.64
0.56 - 1.02
WFRQ3
0.01
1.93
1.77 - 2.62
0.01
2.04
1.97 - 3.31
0.01
0.89
0.82 - 1.08
0.01
0.64
0.58 - 0.95
0.01
0.62
0.55 - 0.84
0.01
0.56
0.51 - 0.87
0.01
0.56
0.50 - 0.95
0.01
0.53
0.49 - 0.75
0.01
0.53
0.48 - 0.67
0.02
0.53
0.48 - 0.84
0.02
0.54
0.49 - 0.88
0.03
0.55
0.50 - 0.81
TWFR3
0.01
1.94
1.81 - 2.96
0.01
1.64
1.57 - 2.34
0.01
0.80
0.74 - 1.22
0.01
0.63
0.56 - 1.09
0.01
0.61
0.55 - 0.80
0.01
0.56
0.51 - 0.86
0.01
0.59
0.50 - 1.01
0.02
0.53
0.49 - 0.71
0.02
0.53
0.49 - 0.67
0.03
0.55
0.49 - 0.82
0.04
0.55
0.51 - 0.67
0.07
0.59
0.53 - 0.87
TWFRQ4
0.01
1.93
1.80 - 2.27
0.01
1.87
1.78 - 2.87
0.01
0.80
0.73 - 1.19
0.01
0.65
0.58 - 1.02
0.01
0.61
0.56 - 0.84
0.01
0.58
0.51 - 0.86
0.01
0.56
0.50 - 0.83
0.01
0.53
0.49 - 0.75
0.01
0.52
0.48 - 0.64
0.02
0.61
0.54 - 0.88
0.03
0.61
0.54 - 1.11
0.05
0.64
0.57 - 0.95
MUSL1
0.00
1.42
1.33 - 1.82
0.00
1.52
1.44 - 2.32
0.01
0.70
0.63 - 0.92
0.01
0.66
0.58 - 0.94
0.01
0.63
0.58 - 0.83
0.01
0.59
0.54 - 1.00
0.01
0.59
0.53 - 1.01
0.01
0.58
0.53 - 0.74
0.01
0.58
0.53 - 0.65
0.01
0.59
0.52 - 1.01
0.01
0.59
0.53 - 0.96
0.02
0.60
0.53 - 0.98
SIMDKR
0.01
0.59
0.51 - 0.86
0.01
0.57
0.51 - 0.77
0.01
0.57
0.51 - 0.93
0.01
0.58
0.51 - 0.90
0.01
0.60
0.55 - 0.90
0.01
0.56
0.51 - 0.72
0.01
0.57
0.51 - 0.92
0.01
0.55
0.51 - 0.87
0.01
0.56
0.51 - 0.82
0.01
0.59
0.51 - 0.98
0.01
0.56
0.51 - 0.90
0.01
0.58
0.51 - 0.86
EPSM
0.00
0.63
0.55 - 0.87
0.01
0.64
0.58 - 1.05
0.01
0.74
0.67 - 1.01
0.01
0.62
0.57 - 0.96
0.01
0.60
0.54 - 0.83
0.01
0.55
0.50 - 0.88
0.01
0.55
0.50 - 0.77
0.02
0.54
0.50 - 0.76
0.03
0.57
0.51 - 0.88
0.05
0.60
0.54 - 1.08
0.09
0.66
0.60 - 0.86
0.23
0.88
0.76 - 1.58
HC4
0.00
 -
0.00 - 0.00
0.01
1.72
1.63 - 2.21
0.01
0.77
0.70 - 1.21
0.01
0.62
0.56 - 0.81
0.01
0.61
0.54 - 0.83
0.01
0.55
0.50 - 0.86
0.01
0.55
0.49 - 0.89
0.01
0.53
0.48 - 0.86
0.01
0.53
0.48 - 0.82
0.01
0.53
0.48 - 0.82
0.01
0.52
0.48 - 0.72
0.01
0.54
0.49 - 0.67
LHC3
0.00
 -
0.00 - 0.00
0.01
1.13
1.08 - 1.42
0.01
0.73
0.66 - 1.01
0.01
0.63
0.56 - 1.10
0.01
0.60
0.52 - 0.82
0.01
0.56
0.51 - 0.88
0.01
0.54
0.49 - 0.81
0.01
0.53
0.49 - 0.67
0.01
0.53
0.48 - 0.87
0.01
0.56
0.49 - 0.82
0.02
0.53
0.48 - 0.66
0.03
0.54
0.49 - 0.70
LHC7
0.00
 -
0.00 - 0.00
0.00
 -
0.00 - 0.00
0.01
1.70
1.61 - 2.77
0.01
0.79
0.70 - 1.21
0.01
0.64
0.58 - 0.96
0.01
0.57
0.52 - 0.80
0.01
0.55
0.50 - 0.86
0.01
0.53
0.49 - 0.78
0.01
0.54
0.48 - 0.90
0.02
0.62
0.50 - 1.70
0.02
0.53
0.49 - 0.69
0.03
0.55
0.50 - 0.95
FHC3
0.00
 -
0.00 - 0.00
0.01
1.03
1.00 - 1.64
0.01
0.70
0.63 - 0.87
0.01
0.64
0.55 - 1.15
0.01
0.60
0.54 - 0.84
0.01
0.55
0.50 - 0.86
0.01
0.54
0.50 - 0.69
0.01
0.53
0.49 - 0.79
0.01
0.53
0.48 - 0.74
0.01
0.57
0.50 - 1.39
0.01
0.52
0.48 - 0.75
0.02
0.54
0.48 - 0.69
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.