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 16:59:31

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

	2	4	8	16	32	64	128	256	512	1024	2048	4096
TVSBS	0.30 5.26 2.95 - 8.80	0.32 3.83 2.37 - 8.20	0.29 2.76 1.78 - 7.34	0.32 2.21 1.47 - 12.30	0.31 1.81 1.28 - 4.58	0.33 1.73 1.18 - 3.12	0.23 1.14 0.68 - 2.37	0.20 0.97 0.64 - 2.18	0.20 1.04 0.75 - 2.10	0.21 1.06 0.78 - 6.66	0.20 0.96 0.66 - 2.24	0.21 0.91 0.63 - 2.01
FJS	0.02 5.50 2.85 - 10.25	0.02 3.46 2.07 - 8.70	0.04 2.77 1.63 - 14.44	0.02 1.93 1.35 - 4.17	0.02 1.69 0.86 - 4.48	0.02 1.74 1.06 - 3.10	0.02 1.13 0.61 - 2.83	0.02 1.00 0.60 - 2.58	0.02 0.96 0.62 - 2.08	0.02 0.95 0.66 - 3.65	0.03 0.87 0.60 - 2.26	0.04 0.83 0.53 - 2.46
HASH8	0.02 3.27 2.18 - 6.40	0.02 2.91 2.17 - 7.64	0.02 17.80 13.15 - 44.43	0.02 2.53 2.18 - 4.41	0.02 1.35 0.95 - 2.46	0.02 1.31 1.03 - 2.80	0.01 0.81 0.56 - 2.22	0.01 0.83 0.52 - 1.66	0.02 0.89 0.69 - 1.73	0.03 0.94 0.69 - 7.40	0.02 0.88 0.59 - 3.85	0.03 0.91 0.54 - 4.51
SO	0.02 2.86 1.82 - 6.92	0.02 2.77 1.74 - 19.34	0.02 2.73 1.75 - 6.16	0.03 2.85 1.84 - 15.71	0.02 2.38 1.33 - 11.27	0.10 2.80 1.64 - 22.57	0.01 1.51 1.08 - 3.34	0.02 1.69 1.07 - 4.00	0.02 1.66 1.09 - 3.62	0.03 1.87 1.13 - 9.88	0.02 1.60 1.10 - 5.34	0.02 1.77 1.08 - 4.08
SBNDM	0.04 4.52 2.70 - 10.53	0.03 2.21 1.41 - 4.33	0.04 1.82 1.04 - 3.30	0.05 1.65 0.94 - 11.25	0.04 1.35 0.73 - 2.33	0.09 1.27 0.66 - 15.34	0.02 1.12 0.65 - 2.61	0.02 1.11 0.65 - 2.33	0.02 0.94 0.64 - 2.25	0.02 1.00 0.64 - 5.06	0.02 1.04 0.64 - 3.43	0.02 1.12 0.70 - 3.17
LBNDM	0.02 4.35 1.69 - 14.29	0.02 3.84 1.57 - 9.24	0.02 2.93 1.58 - 6.27	0.02 2.15 1.29 - 4.64	0.02 1.68 0.98 - 2.71	0.01 0.84 0.57 - 2.12	0.01 0.82 0.51 - 1.90	0.01 0.86 0.53 - 2.03	0.03 0.86 0.55 - 4.37	0.02 0.83 0.56 - 5.46	0.02 0.82 0.57 - 2.28	0.03 1.54 0.74 - 6.77
SBNDM2	0.02 3.11 1.78 - 7.35	0.02 1.93 1.15 - 5.22	0.02 1.59 0.93 - 3.16	0.02 1.68 0.90 - 3.58	0.02 1.43 0.82 - 2.19	0.02 0.99 0.52 - 2.71	0.01 0.89 0.55 - 2.05	0.01 0.83 0.50 - 1.99	0.03 0.99 0.59 - 5.98	0.02 0.88 0.57 - 4.00	0.02 0.88 0.55 - 2.77	0.02 0.99 0.56 - 3.28
SBNDM-BMH	0.03 4.38 2.28 - 8.91	0.03 3.36 1.59 - 7.66	0.03 2.67 1.56 - 5.42	0.03 2.08 1.18 - 4.56	0.03 1.66 0.98 - 2.87	0.02 1.16 0.65 - 2.73	0.02 1.25 0.62 - 2.75	0.02 1.20 0.65 - 2.38	0.20 1.72 0.73 - 18.42	0.02 1.09 0.70 - 6.54	0.02 1.15 0.68 - 3.03	0.03 1.15 0.66 - 3.53
FNDM	0.02 4.37 1.75 - 9.49	0.03 3.16 1.16 - 12.97	0.02 2.63 1.40 - 10.56	0.02 2.41 1.26 - 4.71	0.02 1.56 1.00 - 2.48	0.02 1.22 0.64 - 2.74	0.01 1.10 0.61 - 2.47	0.01 1.03 0.64 - 2.58	0.15 1.78 0.79 - 14.55	0.02 1.07 0.67 - 6.34	0.02 1.43 0.66 - 2.69	0.02 1.15 0.71 - 5.40
FSBNDM	0.02 3.51 1.27 - 7.92	0.02 2.21 1.13 - 6.40	0.02 1.72 0.95 - 3.95	0.02 1.57 0.92 - 3.48	0.02 1.55 0.88 - 2.28	0.01 0.96 0.54 - 2.26	0.01 1.01 0.53 - 2.20	0.01 0.99 0.56 - 2.36	0.08 1.61 0.63 - 10.96	0.01 0.86 0.57 - 2.89	0.02 1.33 0.54 - 2.79	0.02 0.96 0.53 - 2.65
SBNDMQ8	0.02 3.12 2.09 - 6.01	0.03 3.24 2.18 - 17.15	0.03 8.13 4.44 - 27.10	0.02 1.80 1.18 - 3.25	0.02 1.31 0.89 - 2.57	0.02 1.00 0.55 - 2.07	0.02 0.90 0.55 - 1.97	0.02 0.90 0.55 - 1.88	0.04 1.60 0.68 - 9.83	0.02 0.82 0.57 - 2.52	0.02 1.22 0.56 - 2.23	0.02 0.94 0.55 - 2.23
UFNDMQ2	0.03 2.80 1.54 - 5.46	0.03 1.93 1.16 - 6.55	0.03 1.55 0.97 - 4.11	0.03 1.64 0.93 - 2.40	0.02 1.40 0.87 - 2.59	0.01 0.94 0.54 - 2.38	0.01 0.88 0.52 - 2.17	0.01 0.97 0.52 - 2.13	0.03 1.27 0.59 - 16.76	0.01 1.04 0.56 - 2.46	0.01 1.08 0.54 - 8.47	0.01 1.05 0.57 - 5.30
UFNDMQ8	0.03 3.31 2.16 - 7.09	0.02 2.99 2.18 - 6.69	0.04 1.85 1.27 - 5.31	0.03 1.57 1.03 - 2.49	0.01 1.31 0.88 - 2.34	0.01 0.97 0.56 - 2.20	0.01 1.07 0.56 - 2.14	0.01 1.01 0.56 - 2.43	0.08 1.36 0.69 - 13.32	0.01 0.90 0.58 - 2.99	0.02 0.98 0.62 - 3.60	0.01 0.89 0.58 - 3.30
KBNDM	0.02 5.12 3.09 - 8.12	0.02 2.93 1.94 - 9.05	0.02 1.88 1.38 - 4.21	0.02 1.92 1.12 - 3.21	0.02 1.59 0.99 - 2.35	0.02 0.93 0.59 - 1.97	0.02 0.87 0.53 - 1.72	0.02 1.01 0.52 - 2.12	0.02 1.10 0.58 - 9.11	0.02 1.12 0.53 - 2.36	0.03 1.07 0.56 - 6.79	0.02 0.96 0.54 - 2.67
FS-W2	0.06 4.17 2.05 - 8.38	0.06 2.73 1.54 - 9.20	0.06 1.77 1.21 - 4.97	0.07 1.77 1.06 - 2.81	0.07 1.58 0.96 - 2.41	0.04 0.92 0.57 - 2.55	0.05 0.84 0.53 - 2.06	0.05 0.84 0.55 - 1.98	0.05 0.83 0.57 - 4.48	0.06 0.91 0.57 - 2.35	0.08 0.92 0.55 - 2.19	0.12 0.91 0.53 - 3.04
LWFR5	0.02 3.31 2.09 - 7.20	0.02 2.97 2.15 - 6.56	0.11 4.86 2.58 - 20.13	0.11 1.56 0.95 - 2.06	0.11 1.31 0.88 - 1.88	0.08 0.90 0.50 - 2.19	0.07 0.71 0.48 - 1.85	0.08 0.84 0.49 - 1.62	0.09 0.79 0.54 - 8.90	0.09 0.67 0.48 - 2.09	0.12 0.72 0.49 - 2.53	0.19 0.83 0.54 - 2.63
QF43	0.02 3.18 2.16 - 5.21	0.03 3.03 2.12 - 6.77	0.03 2.09 0.86 - 9.04	0.03 1.23 0.89 - 2.26	0.03 1.26 0.82 - 2.15	0.02 0.81 0.47 - 1.88	0.02 0.77 0.47 - 1.76	0.02 0.74 0.46 - 2.34	0.03 0.77 0.53 - 5.90	0.02 0.60 0.43 - 1.76	0.02 0.63 0.42 - 1.77	0.03 0.59 0.43 - 1.55
SBNDM-W2	0.02 3.96 1.49 - 8.52	0.03 3.14 1.28 - 10.45	0.03 1.77 0.95 - 9.42	0.02 1.67 1.04 - 3.41	0.02 1.45 0.90 - 2.44	0.02 0.99 0.56 - 2.25	0.02 1.08 0.56 - 2.24	0.02 0.99 0.58 - 2.43	0.05 1.17 0.68 - 7.26	0.02 0.92 0.59 - 3.01	0.02 1.06 0.56 - 3.12	0.02 1.01 0.63 - 5.03
WFR2	0.09 3.72 2.17 - 6.61	0.10 2.38 1.37 - 11.58	0.10 1.72 0.83 - 6.73	0.09 1.61 0.98 - 2.51	0.09 1.33 0.93 - 3.18	0.07 0.91 0.56 - 2.31	0.06 0.78 0.52 - 1.84	0.08 0.90 0.52 - 1.94	0.10 0.87 0.52 - 6.34	0.08 0.71 0.47 - 2.14	0.10 0.68 0.49 - 1.81	0.15 0.78 0.50 - 2.39
TWFRQ2	0.09 3.27 1.86 - 8.46	0.09 2.06 1.23 - 5.81	0.08 1.32 0.79 - 4.67	0.10 1.66 0.96 - 2.76	0.10 1.36 0.91 - 3.83	0.08 1.06 0.57 - 2.40	0.07 0.85 0.52 - 2.03	0.08 0.91 0.52 - 4.33	0.07 0.75 0.51 - 4.52	0.07 0.65 0.48 - 1.97	0.08 0.74 0.46 - 2.13	0.11 0.80 0.47 - 3.56
TWFRQ4	0.02 3.19 2.18 - 23.00	0.09 3.67 2.36 - 8.61	0.09 1.67 0.88 - 8.37	0.10 1.42 0.92 - 2.23	0.09 1.21 0.84 - 2.62	0.07 0.83 0.50 - 1.84	0.07 0.85 0.48 - 1.94	0.07 0.83 0.48 - 1.66	0.08 0.74 0.50 - 3.36	0.07 0.65 0.47 - 1.99	0.08 0.67 0.45 - 2.12	0.10 0.78 0.46 - 4.18
WOM	0.03 5.61 2.86 - 14.07	0.03 3.64 2.15 - 9.37	0.03 2.06 1.25 - 4.98	0.03 2.27 1.32 - 4.35	0.03 1.72 1.17 - 7.57	0.02 1.23 0.65 - 2.83	0.02 0.94 0.60 - 2.68	0.02 1.02 0.57 - 1.96	0.03 0.97 0.59 - 2.81	0.03 1.01 0.59 - 2.24	0.03 0.95 0.56 - 2.40	0.04 0.82 0.52 - 2.02
LIBC1	0.02 2.71 1.60 - 4.65	0.02 2.18 1.27 - 5.79	0.02 1.75 0.82 - 11.30	0.02 1.54 0.93 - 2.50	0.02 1.35 0.84 - 3.15	0.01 0.92 0.54 - 2.29	0.01 0.80 0.50 - 1.88	0.01 0.75 0.50 - 1.64	0.02 0.88 0.61 - 4.22	0.01 0.89 0.59 - 2.03	0.01 0.81 0.56 - 2.06	0.01 0.90 0.51 - 2.65
MUSL1	0.00 0.02 0.01 - 0.28	0.00 0.07 0.01 - 1.51	0.00 0.55 0.01 - 5.90	0.00 1.17 0.01 - 3.55	0.01 0.94 0.01 - 3.57	0.00 0.51 0.02 - 2.06	0.00 0.48 0.01 - 1.83	0.01 0.54 0.01 - 1.66	0.01 0.45 0.01 - 3.15	0.01 0.46 0.02 - 4.33	0.02 0.46 0.02 - 1.64	0.02 0.43 0.04 - 1.97
SIMDKR	0.04 1.26 0.79 - 5.87	0.02 1.27 0.77 - 2.79	0.02 1.14 0.85 - 3.23	0.03 1.19 0.80 - 3.10	0.02 1.24 0.80 - 2.27	0.01 0.88 0.51 - 2.39	0.01 0.78 0.47 - 2.32	0.01 0.80 0.50 - 2.23	0.02 0.81 0.50 - 3.75	0.02 0.89 0.51 - 5.39	0.02 0.85 0.47 - 3.51	0.01 0.80 0.48 - 2.81
EPSM	0.03 1.25 0.81 - 6.41	0.02 1.24 0.82 - 3.42	0.03 1.28 0.96 - 3.08	0.05 1.38 1.05 - 6.30	0.03 1.12 0.86 - 2.30	0.03 0.89 0.47 - 1.99	0.03 0.82 0.48 - 1.55	0.03 0.64 0.48 - 1.43	0.05 0.73 0.52 - 2.11	0.08 0.73 0.51 - 2.27	0.15 0.86 0.54 - 2.25	0.36 1.19 0.69 - 2.79

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.