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:34:35
Text chineseTexts (alphabet : 128 - size : 1048576 bytes)
| 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | |
| TVSBS | 0.02 2.34 2.02 - 3.13 | 0.02 1.78 1.48 - 2.57 | 0.02 1.31 1.14 - 1.93 | 0.02 1.13 0.87 - 7.01 | 0.02 0.96 0.73 - 5.96 | 0.02 0.70 0.61 - 1.00 | 0.02 0.68 0.57 - 0.98 | 0.02 0.66 0.55 - 1.07 | 0.02 0.68 0.54 - 1.05 | 0.02 0.60 0.52 - 0.90 | 0.02 0.56 0.51 - 0.81 | 0.00 - 0.69 - 0.69 |
| SBNDMQ2 | 0.01 1.45 1.25 - 2.45 | 0.01 0.92 0.72 - 1.73 | 0.01 0.77 0.59 - 1.31 | 0.01 0.77 0.57 - 1.83 | 0.01 0.71 0.56 - 1.19 | 0.01 0.65 0.54 - 0.98 | 0.01 0.66 0.52 - 0.99 | 0.01 0.68 0.54 - 1.24 | 0.01 0.69 0.53 - 1.07 | 0.01 0.65 0.53 - 1.07 | 0.01 0.64 0.54 - 0.92 | 0.01 0.63 0.51 - 1.11 |
| BXS2 | 0.01 1.98 1.81 - 2.62 | 0.01 0.99 0.79 - 1.65 | 0.01 0.79 0.61 - 1.19 | 0.01 0.73 0.57 - 1.03 | 0.01 0.74 0.59 - 1.81 | 0.01 0.66 0.54 - 0.95 | 0.01 0.67 0.54 - 1.01 | 0.01 0.66 0.54 - 0.99 | 0.01 0.66 0.53 - 0.98 | 0.01 0.65 0.54 - 1.04 | 0.01 0.63 0.55 - 0.86 | 0.01 0.64 0.53 - 0.94 |
| FS-W8 | 0.02 1.28 0.90 - 2.35 | 0.02 0.95 0.67 - 1.48 | 0.02 0.79 0.59 - 1.18 | 0.02 0.74 0.56 - 1.33 | 0.02 0.66 0.54 - 1.01 | 0.02 0.63 0.51 - 0.97 | 0.02 0.59 0.50 - 1.04 | 0.02 0.60 0.50 - 0.93 | 0.02 0.56 0.50 - 0.88 | 0.03 0.65 0.53 - 1.30 | 0.04 0.57 0.51 - 0.71 | 0.06 0.61 0.53 - 0.97 |
| FSBNDM-W6 | 0.01 1.97 1.81 - 2.77 | 0.01 2.00 1.82 - 2.65 | 0.01 0.81 0.59 - 1.34 | 0.01 0.81 0.59 - 1.40 | 0.01 0.72 0.59 - 2.28 | 0.01 0.65 0.55 - 1.39 | 0.01 0.65 0.55 - 1.14 | 0.01 0.62 0.54 - 0.86 | 0.01 0.66 0.54 - 1.08 | 0.01 0.65 0.54 - 1.01 | 0.01 0.62 0.54 - 1.00 | 0.01 0.63 0.53 - 1.01 |
| FSBNDMQ20 | 0.01 1.51 1.34 - 2.43 | 0.01 0.92 0.75 - 2.16 | 0.01 0.78 0.60 - 1.23 | 0.01 0.93 0.76 - 5.03 | 0.01 0.71 0.56 - 1.10 | 0.01 0.63 0.53 - 0.95 | 0.01 0.63 0.52 - 0.95 | 0.01 0.63 0.55 - 1.04 | 0.01 0.69 0.56 - 1.11 | 0.01 0.68 0.55 - 1.02 | 0.01 0.66 0.54 - 2.51 | 0.01 0.63 0.52 - 0.98 |
| LWFR4 | 0.01 2.00 1.80 - 2.85 | 0.01 2.00 1.79 - 3.07 | 0.01 0.86 0.73 - 1.33 | 0.02 0.96 0.83 - 4.98 | 0.01 0.68 0.54 - 1.18 | 0.01 0.60 0.51 - 2.20 | 0.01 0.56 0.49 - 0.75 | 0.02 0.55 0.50 - 0.85 | 0.02 0.56 0.50 - 0.87 | 0.03 0.58 0.51 - 0.86 | 0.05 0.58 0.52 - 0.93 | 0.09 0.61 0.56 - 0.94 |
| QF34 | 0.01 2.03 1.82 - 2.90 | 0.01 1.23 1.05 - 2.30 | 0.01 0.81 0.67 - 1.33 | 0.01 0.95 0.79 - 1.76 | 0.01 0.64 0.55 - 0.91 | 0.01 0.60 0.52 - 1.02 | 0.01 0.55 0.50 - 1.14 | 0.01 0.54 0.49 - 0.72 | 0.01 0.58 0.49 - 1.07 | 0.01 0.59 0.49 - 0.91 | 0.01 0.54 0.48 - 1.14 | 0.01 0.54 0.48 - 0.95 |
| QF43 | 0.01 2.03 1.81 - 2.76 | 0.01 2.02 1.83 - 2.62 | 0.01 0.84 0.70 - 1.55 | 0.01 0.81 0.58 - 1.78 | 0.01 0.62 0.53 - 0.92 | 0.01 0.60 0.51 - 0.97 | 0.01 0.58 0.50 - 0.99 | 0.01 0.53 0.49 - 0.78 | 0.01 0.56 0.48 - 0.92 | 0.01 0.56 0.48 - 0.92 | 0.01 0.55 0.48 - 0.84 | 0.01 0.53 0.48 - 0.70 |
| TSA | 0.01 2.13 1.79 - 3.56 | 0.01 1.36 1.16 - 2.28 | 0.01 1.03 0.79 - 1.74 | 0.01 0.79 0.64 - 1.19 | 0.01 0.71 0.58 - 1.03 | 0.01 0.60 0.53 - 1.04 | 0.02 0.74 0.61 - 1.16 | 0.02 0.65 0.58 - 0.84 | 0.02 0.69 0.57 - 1.09 | 0.03 0.74 0.62 - 1.18 | 0.04 0.68 0.59 - 1.00 | 0.06 0.68 0.60 - 0.97 |
| WFRQ3 | 0.01 2.02 1.82 - 2.80 | 0.01 2.33 1.99 - 4.87 | 0.01 1.07 0.84 - 2.15 | 0.01 0.72 0.62 - 1.29 | 0.01 0.66 0.55 - 1.05 | 0.01 0.65 0.52 - 1.05 | 0.01 0.62 0.51 - 1.03 | 0.01 0.56 0.50 - 1.07 | 0.02 0.56 0.49 - 0.92 | 0.02 0.57 0.49 - 0.93 | 0.02 0.54 0.49 - 0.73 | 0.03 0.56 0.50 - 0.86 |
| TWFR3 | 0.01 2.05 1.82 - 3.05 | 0.01 1.78 1.56 - 3.02 | 0.01 1.03 0.80 - 3.05 | 0.01 0.73 0.59 - 1.28 | 0.01 0.64 0.54 - 1.10 | 0.01 0.62 0.52 - 0.95 | 0.01 0.58 0.51 - 0.91 | 0.02 0.56 0.50 - 0.86 | 0.02 0.55 0.50 - 1.08 | 0.03 0.61 0.51 - 0.94 | 0.04 0.56 0.50 - 0.94 | 0.06 0.59 0.53 - 0.96 |
| TWFRQ4 | 0.01 2.07 1.82 - 2.83 | 0.01 1.99 1.79 - 2.90 | 0.01 1.20 0.76 - 7.40 | 0.01 0.96 0.61 - 8.02 | 0.01 0.62 0.53 - 1.14 | 0.01 0.58 0.51 - 0.93 | 0.01 0.57 0.50 - 0.86 | 0.01 0.58 0.50 - 1.04 | 0.01 0.55 0.49 - 0.88 | 0.03 0.74 0.62 - 1.17 | 0.04 0.66 0.57 - 1.00 | 0.06 0.72 0.60 - 1.16 |
| MUSL1 | 0.00 1.39 0.68 - 2.10 | 0.00 1.58 1.27 - 2.21 | 0.01 1.48 0.84 - 12.88 | 0.01 1.20 0.79 - 4.24 | 0.01 0.88 0.70 - 1.36 | 0.01 0.80 0.67 - 1.18 | 0.01 0.71 0.59 - 1.05 | 0.01 0.65 0.57 - 0.98 | 0.01 0.69 0.48 - 1.28 | 0.01 0.71 0.56 - 1.05 | 0.01 0.65 0.55 - 1.03 | 0.02 0.65 0.56 - 1.08 |
| SIMDKR | 0.01 0.69 0.53 - 1.55 | 0.01 0.76 0.52 - 1.90 | 0.01 0.73 0.58 - 1.41 | 0.01 0.68 0.55 - 1.58 | 0.01 0.58 0.52 - 0.93 | 0.01 0.60 0.51 - 1.06 | 0.01 0.59 0.51 - 0.99 | 0.01 0.57 0.51 - 0.87 | 0.01 0.60 0.51 - 1.12 | 0.01 0.63 0.52 - 0.95 | 0.01 0.56 0.51 - 0.85 | 0.01 0.57 0.51 - 0.94 |
| EPSM | 0.00 0.66 0.55 - 1.02 | 0.01 0.69 0.58 - 1.17 | 0.01 0.94 0.72 - 1.61 | 0.01 0.72 0.61 - 1.42 | 0.01 0.58 0.52 - 0.89 | 0.01 0.55 0.50 - 0.91 | 0.01 0.57 0.50 - 0.90 | 0.02 0.54 0.50 - 0.67 | 0.03 0.60 0.52 - 1.01 | 0.05 0.63 0.55 - 0.99 | 0.10 0.66 0.60 - 0.88 | 0.22 0.83 0.74 - 1.35 |
| HC4 | 0.00 - 0.00 - 0.00 | 0.01 1.81 1.64 - 2.34 | 0.01 0.88 0.72 - 1.42 | 0.01 0.73 0.60 - 4.21 | 0.01 0.62 0.53 - 0.99 | 0.01 0.55 0.51 - 0.72 | 0.01 0.55 0.50 - 0.84 | 0.01 0.53 0.49 - 0.77 | 0.01 0.54 0.48 - 0.82 | 0.01 0.54 0.48 - 0.86 | 0.01 0.52 0.48 - 0.66 | 0.01 0.54 0.48 - 0.85 |
| LHC3 | 0.00 - 0.00 - 0.00 | 0.01 1.25 1.09 - 1.99 | 0.01 0.88 0.70 - 3.26 | 0.01 0.78 0.60 - 3.35 | 0.01 0.64 0.54 - 1.03 | 0.01 0.59 0.52 - 0.87 | 0.01 0.56 0.51 - 0.79 | 0.01 0.57 0.50 - 0.94 | 0.01 0.55 0.49 - 0.87 | 0.01 0.55 0.48 - 0.80 | 0.02 0.53 0.49 - 0.69 | 0.03 0.55 0.49 - 0.81 |
| LHC7 | 0.00 - 0.00 - 0.00 | 0.00 - 0.00 - 0.00 | 0.01 1.89 1.64 - 3.40 | 0.01 0.88 0.72 - 1.54 | 0.01 0.65 0.56 - 1.09 | 0.01 0.57 0.52 - 0.76 | 0.01 0.55 0.50 - 0.70 | 0.01 0.58 0.49 - 1.03 | 0.01 0.54 0.48 - 0.96 | 0.01 0.54 0.48 - 0.93 | 0.02 0.55 0.49 - 0.90 | 0.03 0.54 0.50 - 0.74 |
| FHC3 | 0.00 - 0.00 - 0.00 | 0.01 1.17 1.01 - 1.88 | 0.01 0.79 0.64 - 1.14 | 0.01 0.78 0.59 - 2.40 | 0.01 0.59 0.52 - 0.82 | 0.01 0.63 0.52 - 1.09 | 0.01 0.55 0.50 - 0.83 | 0.01 0.62 0.50 - 0.98 | 0.01 0.56 0.49 - 0.89 | 0.01 0.53 0.48 - 0.77 | 0.01 0.55 0.47 - 0.80 | 0.01 0.53 0.48 - 0.99 |
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
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
Best Running Times
TVSBS - Thathoo-Virmani-Sai-Balakrishnan-Sekar
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Detailed plot of the running times relative to the FHC3 algorithm. The plot reports the mean and the distribution of the running times.