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 EXP1712145140

Date 2024:04:03 17:30:14

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

	2	4	8	16	32	64	128	256	512	1024	2048	4096
TVSBS	0.20 3.19 2.11 - 8.32	0.19 2.26 1.59 - 7.09	0.23 2.00 1.22 - 6.99	0.19 1.33 0.95 - 3.15	0.21 1.14 0.81 - 3.00	0.19 0.98 0.71 - 2.49	0.34 1.28 0.71 - 7.47	0.19 0.91 0.64 - 2.20	0.25 1.32 0.78 - 6.77	0.23 1.01 0.70 - 3.44	0.22 0.95 0.64 - 2.23	0.21 0.85 0.59 - 3.44
FJS	0.02 2.79 1.89 - 7.30	0.02 2.46 1.34 - 6.53	0.02 1.53 1.00 - 6.00	0.01 1.11 0.78 - 3.01	0.01 0.94 0.67 - 3.23	0.01 0.80 0.60 - 2.09	0.02 0.79 0.57 - 3.49	0.02 0.88 0.57 - 4.53	0.02 0.92 0.61 - 6.57	0.02 0.86 0.62 - 3.63	0.03 0.82 0.58 - 1.88	0.04 0.87 0.59 - 1.82
HASH8	0.01 2.06 1.46 - 5.11	0.01 2.07 1.43 - 5.55	0.02 13.20 8.92 - 29.35	0.02 2.09 1.44 - 9.93	0.01 1.08 0.83 - 3.24	0.01 0.86 0.64 - 2.94	0.01 0.76 0.57 - 3.87	0.02 0.85 0.52 - 1.82	0.02 0.96 0.68 - 4.98	0.02 0.89 0.70 - 2.34	0.02 0.89 0.65 - 4.21	0.02 0.90 0.66 - 2.02
SO	0.01 1.85 1.21 - 5.29	0.02 2.04 1.20 - 4.45	0.02 2.48 1.21 - 5.99	0.01 1.86 1.21 - 6.81	0.02 1.96 1.21 - 7.87	0.02 1.90 1.09 - 4.89	0.01 1.55 1.09 - 3.53	0.02 1.69 1.08 - 4.52	0.02 1.77 1.13 - 6.48	0.02 1.77 1.12 - 7.43	0.02 1.68 1.10 - 8.09	0.02 1.69 1.08 - 4.57
SBNDM	0.02 2.79 1.81 - 7.16	0.02 1.44 0.93 - 4.22	0.03 1.17 0.66 - 2.78	0.02 0.84 0.54 - 4.21	0.02 0.75 0.52 - 1.83	0.02 0.99 0.66 - 2.58	0.02 0.97 0.66 - 2.74	0.02 1.00 0.66 - 2.39	0.03 1.06 0.68 - 11.71	0.03 0.96 0.69 - 3.15	0.02 0.92 0.59 - 2.14	0.02 0.95 0.67 - 2.41
LBNDM	0.02 2.27 1.00 - 7.29	0.02 2.12 0.81 - 4.48	0.02 2.08 0.77 - 6.31	0.01 1.21 0.71 - 3.37	0.01 0.96 0.66 - 2.13	0.01 0.78 0.53 - 1.72	0.01 0.69 0.50 - 2.02	0.02 0.78 0.49 - 2.69	0.02 0.78 0.51 - 4.74	0.03 0.74 0.48 - 3.89	0.01 0.64 0.47 - 1.87	0.02 0.71 0.47 - 2.39
SBNDM2	0.01 2.00 1.23 - 5.67	0.02 1.45 0.71 - 3.59	0.02 1.16 0.54 - 2.89	0.01 0.77 0.51 - 2.47	0.02 0.95 0.50 - 2.34	0.01 0.75 0.49 - 1.77	0.02 0.85 0.51 - 2.64	0.01 0.72 0.50 - 2.02	0.02 0.83 0.52 - 4.10	0.02 0.80 0.52 - 2.66	0.02 0.78 0.51 - 2.16	0.02 0.82 0.50 - 2.41
SBNDM-BMH	0.02 2.43 1.55 - 6.56	0.03 2.26 1.07 - 4.56	0.03 1.75 0.79 - 3.02	0.02 1.37 0.70 - 5.38	0.02 1.01 0.67 - 2.56	0.02 1.00 0.64 - 2.23	0.02 1.19 0.63 - 2.80	0.02 1.00 0.64 - 2.65	0.03 1.06 0.66 - 4.68	0.02 1.00 0.69 - 4.03	0.02 0.97 0.55 - 5.10	0.02 0.86 0.66 - 2.50
FNDM	0.02 1.87 1.06 - 4.82	0.02 1.99 0.87 - 4.74	0.02 1.42 0.70 - 3.70	0.02 1.19 0.68 - 2.88	0.02 0.90 0.67 - 1.79	0.02 1.08 0.63 - 2.56	0.02 1.03 0.65 - 3.06	0.01 0.93 0.63 - 2.84	0.02 1.05 0.69 - 6.76	0.02 0.96 0.66 - 1.97	0.01 0.97 0.65 - 2.50	0.02 1.00 0.64 - 2.63
FSBNDM	0.01 1.49 0.82 - 4.88	0.01 1.17 0.66 - 4.22	0.02 0.97 0.58 - 5.00	0.02 0.92 0.51 - 2.06	0.01 0.71 0.51 - 1.94	0.02 0.88 0.50 - 2.08	0.01 0.78 0.50 - 1.75	0.02 0.89 0.49 - 1.88	0.02 0.84 0.51 - 2.81	0.02 0.81 0.53 - 3.64	0.02 0.81 0.54 - 4.48	0.01 0.71 0.49 - 2.36
SBNDMQ8	0.01 2.01 1.46 - 5.08	0.01 1.89 1.41 - 5.30	0.02 5.73 3.07 - 13.78	0.02 1.37 0.76 - 2.86	0.01 0.80 0.56 - 2.41	0.01 0.81 0.56 - 2.21	0.02 0.92 0.55 - 2.51	0.02 0.82 0.56 - 2.12	0.03 0.98 0.59 - 4.85	0.02 0.94 0.60 - 7.34	0.02 0.92 0.56 - 2.30	0.02 0.91 0.56 - 5.26
UFNDMQ2	0.02 1.64 1.02 - 10.20	0.02 1.21 0.72 - 4.73	0.02 1.00 0.58 - 2.67	0.02 0.88 0.52 - 2.46	0.01 0.77 0.50 - 2.11	0.01 0.73 0.50 - 1.85	0.01 0.84 0.50 - 2.04	0.01 0.72 0.51 - 1.88	0.01 0.83 0.53 - 5.06	0.02 0.82 0.55 - 3.85	0.01 0.77 0.52 - 2.14	0.01 0.84 0.53 - 6.05
UFNDMQ8	0.02 2.13 1.43 - 6.22	0.01 2.00 1.44 - 5.80	0.02 1.57 0.83 - 7.89	0.02 1.19 0.62 - 2.32	0.01 1.05 0.56 - 2.21	0.01 0.94 0.63 - 3.99	0.01 0.94 0.56 - 3.31	0.01 0.86 0.56 - 2.29	0.01 0.94 0.58 - 7.30	0.01 0.95 0.58 - 3.32	0.01 0.92 0.56 - 2.82	0.01 0.97 0.56 - 2.25
KBNDM	0.02 3.47 2.08 - 9.37	0.02 2.27 1.25 - 6.28	0.02 1.38 0.87 - 3.85	0.01 1.01 0.67 - 2.46	0.02 0.92 0.60 - 2.21	0.02 0.97 0.56 - 1.98	0.02 0.73 0.51 - 1.67	0.02 0.77 0.49 - 2.27	0.02 0.92 0.52 - 6.29	0.02 0.84 0.54 - 4.22	0.02 0.82 0.50 - 2.91	0.02 0.80 0.51 - 2.19
FS-W2	0.04 2.20 1.40 - 8.90	0.04 1.62 0.95 - 7.41	0.05 1.23 0.74 - 4.83	0.05 1.06 0.61 - 2.37	0.05 0.99 0.56 - 2.53	0.04 0.74 0.53 - 1.73	0.05 0.80 0.52 - 4.59	0.04 0.73 0.52 - 1.88	0.06 0.90 0.56 - 5.16	0.07 0.83 0.57 - 3.95	0.07 0.79 0.54 - 1.87	0.10 0.87 0.55 - 1.79
LWFR5	0.01 2.00 1.47 - 5.87	0.02 2.34 1.45 - 6.74	0.08 3.90 1.80 - 18.71	0.07 1.04 0.60 - 2.30	0.08 0.97 0.54 - 2.34	0.08 0.93 0.50 - 2.08	0.07 0.76 0.49 - 1.86	0.07 0.71 0.49 - 2.86	0.09 0.79 0.50 - 4.02	0.10 0.75 0.50 - 3.32	0.12 0.74 0.48 - 1.91	0.18 0.81 0.51 - 2.30
QF43	0.01 2.07 1.46 - 5.70	0.02 2.51 1.49 - 8.19	0.02 1.10 0.74 - 3.23	0.02 0.84 0.55 - 2.45	0.02 0.72 0.50 - 1.79	0.02 0.69 0.46 - 1.89	0.02 0.68 0.45 - 1.73	0.02 0.73 0.45 - 3.76	0.03 0.72 0.46 - 4.37	0.03 0.67 0.44 - 3.09	0.03 0.69 0.43 - 1.59	0.03 0.62 0.41 - 1.37
SBNDM-W2	0.02 1.96 1.01 - 8.77	0.02 1.56 0.81 - 4.90	0.01 1.09 0.66 - 3.86	0.02 1.05 0.62 - 2.98	0.02 0.92 0.56 - 3.43	0.02 0.99 0.54 - 2.27	0.01 0.82 0.52 - 2.26	0.02 0.92 0.58 - 3.61	0.02 0.90 0.57 - 4.31	0.02 0.84 0.57 - 3.13	0.02 1.02 0.55 - 2.07	0.02 1.02 0.57 - 1.97
WFR2	0.07 2.91 1.48 - 7.06	0.06 1.37 0.88 - 3.53	0.09 1.52 0.64 - 2.66	0.07 1.02 0.55 - 3.60	0.07 0.88 0.55 - 3.92	0.06 0.74 0.54 - 2.04	0.07 0.82 0.52 - 2.02	0.08 0.93 0.59 - 5.07	0.08 0.80 0.51 - 3.96	0.09 0.73 0.48 - 2.65	0.11 0.70 0.47 - 3.24	0.15 0.80 0.48 - 1.93
TWFRQ2	0.06 2.06 1.18 - 6.40	0.06 1.17 0.76 - 3.71	0.07 1.05 0.61 - 2.42	0.06 0.87 0.56 - 1.98	0.06 0.83 0.58 - 2.23	0.07 0.79 0.55 - 2.01	0.07 0.83 0.52 - 2.41	0.08 0.90 0.54 - 4.02	0.08 0.82 0.51 - 5.13	0.09 0.72 0.47 - 3.73	0.08 0.63 0.46 - 2.57	0.09 0.65 0.46 - 2.21
TWFRQ4	0.02 2.07 1.46 - 5.07	0.07 2.78 1.57 - 7.86	0.07 1.21 0.72 - 9.25	0.06 0.87 0.56 - 2.43	0.06 0.77 0.52 - 2.17	0.07 0.82 0.54 - 5.16	0.06 0.70 0.49 - 1.82	0.07 0.77 0.49 - 4.58	0.08 0.73 0.48 - 3.00	0.08 0.70 0.47 - 2.02	0.08 0.68 0.46 - 1.64	0.09 0.69 0.46 - 1.95
WOM	0.02 3.24 1.94 - 8.15	0.02 2.42 1.40 - 7.63	0.02 1.63 1.02 - 9.67	0.02 1.24 0.78 - 3.97	0.02 1.13 0.64 - 2.82	0.02 0.90 0.60 - 3.77	0.02 0.78 0.55 - 2.41	0.02 0.85 0.53 - 4.76	0.02 0.87 0.56 - 3.54	0.03 0.88 0.58 - 4.10	0.03 0.81 0.57 - 1.94	0.04 0.87 0.56 - 1.88
LIBC1	0.01 1.62 1.07 - 5.08	0.02 1.49 0.85 - 4.20	0.01 1.08 0.64 - 3.20	0.01 0.87 0.53 - 2.99	0.01 0.79 0.53 - 2.53	0.02 0.83 0.57 - 3.77	0.01 0.71 0.51 - 2.21	0.02 1.00 0.54 - 7.66	0.01 0.83 0.56 - 3.27	0.02 0.83 0.57 - 5.21	0.01 0.84 0.55 - 1.72	0.01 0.86 0.56 - 1.92
MUSL1	0.00 0.02 0.00 - 0.65	0.00 0.21 0.00 - 2.94	0.00 0.62 0.01 - 3.49	0.00 0.67 0.01 - 2.40	0.01 0.59 0.01 - 3.58	0.00 0.49 0.01 - 2.78	0.00 0.42 0.01 - 1.41	0.01 0.46 0.01 - 6.42	0.01 0.45 0.02 - 3.00	0.01 0.45 0.02 - 4.60	0.02 0.48 0.02 - 1.46	0.03 0.48 0.04 - 2.43
SIMDKR	0.01 0.80 0.47 - 2.03	0.01 0.74 0.49 - 2.21	0.01 0.71 0.48 - 2.09	0.01 0.84 0.48 - 2.01	0.01 0.78 0.47 - 2.91	0.02 0.81 0.51 - 4.79	0.02 0.78 0.49 - 5.31	0.02 0.80 0.50 - 1.77	0.02 0.78 0.51 - 3.54	0.02 0.76 0.51 - 4.00	0.01 0.70 0.48 - 3.48	0.01 0.68 0.48 - 1.70
EPSM	0.01 0.71 0.50 - 1.90	0.01 0.86 0.53 - 2.11	0.02 0.89 0.58 - 2.95	0.02 0.90 0.66 - 2.14	0.02 0.73 0.52 - 2.10	0.02 0.75 0.52 - 3.47	0.03 0.69 0.49 - 1.79	0.04 0.73 0.48 - 1.69	0.05 0.76 0.51 - 3.16	0.08 0.81 0.52 - 3.72	0.13 0.77 0.55 - 2.09	0.28 0.98 0.67 - 2.82

Table 1. Running times of experimental tests n.EXP1712145140. Each time value is the mean of 500 runs. Running times are in milliseconds.

Best mean times

Heatmap top 5%

Heatmap top 10%

Heatmap top 25%

Heatmap top 50%

Show pre-processing times

Show best and worst running times

Average Running Times

TVSBS

FJS

HASH8

SBNDM

LBNDM

SBNDM2

SBNDM-BMH

FNDM

FSBNDM

SBNDMQ8

UFNDMQ2

UFNDMQ8

KBNDM

FS-W2

LWFR5

QF43

SBNDM-W2

WFR2

TWFRQ2

TWFRQ4

WOM

LIBC1

MUSL1

SIMDKR

EPSM

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

FJS - Franek-Jennings-Smyth

Detailed plot of the running times relative to the FJS algorithm. The plot reports the mean and the distribution of the running times.

HASH8 - Wu-Manber for Single Pattern Matching (q=8)

Detailed plot of the running times relative to the HASH8 algorithm. The plot reports the mean and the distribution of the running times.

SO - Shift-Or

Detailed plot of the running times relative to the SO algorithm. The plot reports the mean and the distribution of the running times.

SBNDM - Simplified BNDM

Detailed plot of the running times relative to the SBNDM algorithm. The plot reports the mean and the distribution of the running times.

LBNDM - long patterns bndm

Detailed plot of the running times relative to the LBNDM algorithm. The plot reports the mean and the distribution of the running times.

SBNDM2 - simplified bndm with loop-unrolling

Detailed plot of the running times relative to the SBNDM2 algorithm. The plot reports the mean and the distribution of the running times.

SBNDM-BMH - sbndm with horspool shift

Detailed plot of the running times relative to the SBNDM-BMH algorithm. The plot reports the mean and the distribution of the running times.

FNDM - forward nondeterministic dawg matching

Detailed plot of the running times relative to the FNDM algorithm. The plot reports the mean and the distribution of the running times.

FSBNDM - forward sbndm

Detailed plot of the running times relative to the FSBNDM algorithm. The plot reports the mean and the distribution of the running times.

SBNDMQ8 - simplified bndm with q-grams

Detailed plot of the running times relative to the SBNDMQ8 algorithm. The plot reports the mean and the distribution of the running times.

UFNDMQ2 - Upper bits fndm with q-grams

Detailed plot of the running times relative to the UFNDMQ2 algorithm. The plot reports the mean and the distribution of the running times.

UFNDMQ8 - Upper bits fndm with q-grams

Detailed plot of the running times relative to the UFNDMQ8 algorithm. The plot reports the mean and the distribution of the running times.

KBNDM - Factorized BNDM

Detailed plot of the running times relative to the KBNDM algorithm. The plot reports the mean and the distribution of the running times.

FS-W2 - Multiple Sliding Windows

Detailed plot of the running times relative to the FS-W2 algorithm. The plot reports the mean and the distribution of the running times.

LWFR5 - Weak Factor Recognizer, Linear Version

Detailed plot of the running times relative to the LWFR5 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.

SBNDM-W2 - SBNDM with lookahead

Detailed plot of the running times relative to the SBNDM-W2 algorithm. The plot reports the mean and the distribution of the running times.

WFR2 - Weak Factor Recognizer (m>=2)

Detailed plot of the running times relative to the WFR2 algorithm. The plot reports the mean and the distribution of the running times.

TWFRQ2 - Tuned Weak Factor Recognizer with q-grams

Detailed plot of the running times relative to the TWFRQ2 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.

WOM - Worst Occurrence Matcher

Detailed plot of the running times relative to the WOM algorithm. The plot reports the mean and the distribution of the running times.

LIBC1 - memmem

Detailed plot of the running times relative to the LIBC1 algorithm. The plot reports the mean and the distribution of the running times.

MUSL1 - musl memmem

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.