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:42:30

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

	2	4	8	16	32	64	128	256	512	1024	2048	4096
TVSBS	0.30 5.09 2.93 - 10.15	0.21 2.84 1.58 - 9.51	0.24 2.43 1.17 - 5.92	0.28 2.15 0.94 - 4.89	0.25 1.51 0.78 - 3.22	0.27 1.45 0.72 - 2.88	0.29 1.45 0.67 - 2.15	0.27 1.27 0.62 - 2.04	0.31 1.75 1.25 - 6.24	0.32 1.74 1.20 - 3.14	0.32 1.54 1.07 - 2.48	0.32 1.47 0.99 - 2.20
FJS	0.02 5.19 2.74 - 10.82	0.02 2.82 1.32 - 9.01	0.02 2.28 0.96 - 5.94	0.01 1.51 0.76 - 4.42	0.02 1.88 0.72 - 3.45	0.02 1.67 0.66 - 3.10	0.02 1.42 0.62 - 2.88	0.02 1.07 0.58 - 2.59	0.03 1.31 0.97 - 3.47	0.04 1.67 0.91 - 2.61	0.05 1.30 0.95 - 2.31	0.06 1.25 0.88 - 2.11
HASH8	0.02 3.08 2.10 - 5.35	0.02 2.39 1.44 - 6.48	0.01 13.93 8.90 - 27.92	0.01 2.26 1.42 - 4.34	0.02 1.40 0.82 - 2.56	0.02 1.34 0.63 - 2.05	0.01 0.83 0.56 - 1.75	0.02 0.89 0.51 - 4.55	0.02 1.30 1.06 - 2.20	0.02 1.32 0.99 - 2.15	0.03 1.41 1.09 - 4.70	0.04 1.42 1.10 - 2.00
SO	0.02 2.94 1.81 - 5.88	0.01 1.89 1.20 - 5.25	0.02 2.51 1.20 - 5.73	0.01 1.78 1.18 - 5.27	0.02 2.60 1.19 - 5.05	0.02 2.43 1.08 - 4.17	0.02 1.93 1.08 - 4.81	0.02 2.25 1.19 - 11.64	0.02 2.20 1.63 - 3.78	0.02 2.20 1.17 - 5.77	0.02 2.21 1.62 - 5.16	0.02 2.35 1.64 - 3.79
SBNDM	0.04 4.50 2.62 - 7.01	0.03 1.99 0.91 - 3.72	0.03 1.28 0.68 - 2.84	0.03 1.13 0.59 - 2.13	0.03 1.13 0.51 - 2.10	0.03 1.43 0.63 - 2.20	0.02 0.89 0.61 - 2.15	0.03 1.46 0.98 - 3.86	0.03 1.47 0.92 - 2.43	0.03 1.45 0.99 - 2.86	0.03 1.39 0.99 - 3.03	0.03 1.63 1.01 - 2.96
LBNDM	0.02 3.89 1.57 - 9.06	0.01 2.64 0.95 - 8.94	0.02 2.41 0.96 - 4.41	0.02 1.90 0.81 - 3.14	0.02 1.35 0.62 - 2.55	0.02 1.26 0.55 - 2.17	0.01 0.75 0.52 - 1.93	0.02 1.07 0.84 - 1.97	0.02 1.15 0.85 - 1.95	0.02 1.20 0.88 - 1.79	0.03 1.47 0.87 - 7.56	0.03 2.07 1.01 - 3.42
SBNDM2	0.02 2.84 1.76 - 4.76	0.02 1.33 0.75 - 4.38	0.02 1.22 0.61 - 2.72	0.02 1.17 0.55 - 2.11	0.02 1.25 0.50 - 2.31	0.02 1.15 0.50 - 2.05	0.01 0.78 0.51 - 2.59	0.02 1.33 0.81 - 3.20	0.02 1.28 0.80 - 2.41	0.02 1.20 0.82 - 2.15	0.04 1.32 0.83 - 7.89	0.02 1.36 0.78 - 2.03
SBNDM-BMH	0.03 4.44 2.30 - 8.39	0.02 2.55 1.11 - 8.01	0.03 2.59 0.86 - 4.34	0.03 1.85 0.82 - 3.49	0.03 1.44 0.62 - 2.37	0.02 1.07 0.62 - 2.22	0.02 0.95 0.62 - 2.79	0.03 1.59 0.99 - 2.37	0.03 1.47 1.00 - 2.61	0.03 1.51 1.01 - 2.71	0.03 1.49 0.99 - 2.92	0.03 1.55 1.04 - 2.38
FNDM	0.02 3.57 1.66 - 7.77	0.02 2.67 0.94 - 6.54	0.02 2.32 0.81 - 4.59	0.02 1.82 0.81 - 3.42	0.02 1.54 0.64 - 2.50	0.02 1.33 0.62 - 2.32	0.01 1.00 0.62 - 2.29	0.02 1.69 0.99 - 2.41	0.02 1.41 0.93 - 3.33	0.02 1.61 0.96 - 2.72	0.02 1.54 0.95 - 2.82	0.02 1.69 0.96 - 2.43
FSBNDM	0.02 3.09 1.33 - 7.51	0.01 1.59 0.67 - 5.87	0.02 1.60 0.60 - 3.51	0.02 1.52 0.57 - 2.63	0.02 1.13 0.52 - 2.32	0.02 1.08 0.51 - 2.02	0.02 1.16 0.51 - 2.08	0.02 1.32 0.83 - 2.03	0.02 1.23 0.79 - 2.72	0.02 1.33 0.80 - 2.80	0.02 1.24 0.80 - 2.41	0.02 1.35 0.84 - 1.94
SBNDMQ8	0.02 3.39 2.16 - 6.27	0.02 2.94 1.46 - 6.34	0.02 6.08 3.07 - 12.87	0.02 1.68 0.76 - 2.45	0.02 0.90 0.55 - 1.76	0.02 1.09 0.54 - 1.86	0.02 1.07 0.55 - 1.73	0.02 1.34 0.89 - 2.59	0.02 1.26 0.89 - 2.13	0.02 1.23 0.89 - 2.42	0.02 1.28 0.91 - 2.58	0.02 1.31 0.88 - 1.79
UFNDMQ2	0.03 2.78 1.57 - 5.97	0.02 1.36 0.76 - 4.36	0.02 1.38 0.61 - 3.25	0.02 1.13 0.55 - 2.13	0.01 1.29 0.55 - 2.13	0.01 1.22 0.51 - 2.06	0.01 1.14 0.50 - 1.92	0.02 1.43 0.84 - 2.27	0.02 1.24 0.82 - 2.37	0.01 1.23 0.83 - 2.30	0.02 1.40 0.82 - 2.12	0.02 1.42 0.81 - 2.33
UFNDMQ8	0.02 3.49 2.15 - 6.21	0.02 2.63 1.43 - 6.55	0.02 1.22 0.81 - 2.69	0.02 0.98 0.63 - 1.95	0.01 1.16 0.56 - 1.83	0.01 0.98 0.58 - 2.42	0.01 0.85 0.59 - 1.74	0.02 1.34 0.92 - 1.96	0.01 1.17 0.89 - 2.06	0.01 1.29 0.91 - 2.15	0.02 1.34 0.93 - 2.16	0.02 1.37 0.91 - 3.98
KBNDM	0.02 5.58 3.08 - 17.93	0.02 2.26 1.30 - 5.06	0.02 1.86 0.91 - 3.25	0.02 1.30 0.72 - 2.75	0.02 1.11 0.63 - 2.25	0.02 1.03 0.56 - 1.92	0.02 1.12 0.51 - 1.71	0.03 1.32 0.83 - 2.61	0.03 1.30 0.90 - 2.16	0.02 1.30 0.84 - 2.21	0.02 1.27 0.84 - 2.96	0.03 1.35 0.81 - 1.99
FS-W2	0.07 4.50 1.99 - 8.44	0.04 1.65 0.96 - 4.94	0.05 1.63 0.78 - 3.86	0.04 1.19 0.62 - 2.81	0.05 1.15 0.61 - 2.46	0.06 1.16 0.57 - 2.34	0.06 1.14 0.54 - 2.01	0.07 1.29 0.83 - 2.14	0.07 1.17 0.90 - 2.86	0.08 1.21 0.90 - 2.53	0.10 1.17 0.86 - 1.91	0.17 1.30 0.82 - 2.13
LWFR5	0.02 3.15 2.17 - 6.31	0.01 2.24 1.45 - 6.26	0.09 3.89 1.75 - 7.30	0.10 1.41 0.65 - 2.22	0.09 1.06 0.56 - 1.82	0.10 1.11 0.54 - 1.85	0.09 0.94 0.49 - 1.57	0.11 1.13 0.78 - 2.01	0.10 0.90 0.65 - 1.90	0.12 0.95 0.70 - 2.61	0.17 1.06 0.73 - 1.89	0.26 1.15 0.77 - 1.94
QF43	0.02 2.91 2.15 - 5.93	0.01 2.23 1.43 - 6.17	0.03 1.76 0.72 - 3.58	0.02 0.91 0.56 - 1.94	0.03 0.97 0.49 - 1.89	0.03 0.98 0.50 - 1.72	0.03 0.85 0.46 - 1.57	0.04 1.12 0.75 - 1.61	0.03 0.86 0.57 - 7.44	0.04 0.87 0.64 - 3.99	0.04 1.00 0.63 - 1.78	0.04 0.98 0.63 - 1.53
SBNDM-W2	0.02 4.18 1.53 - 10.50	0.02 2.32 0.84 - 5.64	0.02 1.62 0.76 - 4.00	0.01 0.97 0.63 - 2.55	0.02 1.32 0.55 - 2.16	0.02 1.33 0.57 - 2.09	0.02 1.27 0.55 - 2.17	0.02 1.38 0.88 - 2.21	0.02 1.17 0.80 - 2.62	0.02 1.20 0.87 - 6.60	0.02 1.35 0.89 - 2.80	0.02 1.35 0.84 - 2.19
WFR2	0.09 3.90 2.35 - 7.18	0.07 1.79 0.87 - 4.17	0.08 1.58 0.72 - 3.26	0.08 1.34 0.61 - 2.38	0.07 1.08 0.57 - 2.24	0.08 1.03 0.56 - 2.01	0.09 1.06 0.52 - 1.81	0.11 1.32 0.84 - 1.70	0.11 1.07 0.60 - 2.28	0.11 0.97 0.70 - 2.38	0.15 1.08 0.71 - 1.80	0.21 1.13 0.73 - 1.88
TWFRQ2	0.10 3.41 1.81 - 5.14	0.07 1.64 0.79 - 4.50	0.07 1.16 0.62 - 2.72	0.09 1.31 0.58 - 2.18	0.08 1.20 0.58 - 2.24	0.10 1.31 0.55 - 1.88	0.08 0.95 0.52 - 2.02	0.10 1.24 0.85 - 1.91	0.09 0.94 0.66 - 1.77	0.09 0.91 0.69 - 1.90	0.11 0.98 0.68 - 1.80	0.15 1.16 0.69 - 1.64
TWFRQ4	0.02 3.20 2.17 - 4.56	0.06 2.36 1.52 - 6.06	0.08 1.47 0.72 - 3.11	0.08 1.07 0.59 - 2.08	0.08 1.00 0.52 - 1.72	0.09 1.03 0.49 - 1.68	0.07 0.86 0.48 - 1.68	0.11 1.23 0.76 - 1.53	0.10 1.00 0.57 - 1.72	0.12 1.06 0.70 - 6.69	0.12 1.05 0.70 - 1.80	0.14 1.12 0.68 - 1.81
WOM	0.03 6.04 2.78 - 10.13	0.02 2.72 1.42 - 7.47	0.02 2.29 1.04 - 4.64	0.02 1.67 0.81 - 3.50	0.03 1.59 0.69 - 2.72	0.03 1.42 0.65 - 2.57	0.02 1.18 0.60 - 2.10	0.03 1.46 0.87 - 2.05	0.03 1.31 0.86 - 2.11	0.07 1.57 0.97 - 8.11	0.04 1.32 0.93 - 2.16	0.06 1.28 0.83 - 1.80
LIBC1	0.02 2.59 1.59 - 4.25	0.01 1.34 0.81 - 6.68	0.01 1.05 0.62 - 3.65	0.01 1.24 0.57 - 2.47	0.02 1.37 0.51 - 2.07	0.01 1.13 0.53 - 1.96	0.01 0.86 0.51 - 1.80	0.02 1.21 0.84 - 1.67	0.02 1.28 0.93 - 2.57	0.02 1.37 0.89 - 4.40	0.01 1.18 0.87 - 2.15	0.02 1.30 0.83 - 1.99
MUSL1	0.00 0.04 0.01 - 0.89	0.00 0.13 0.01 - 1.77	0.00 0.98 0.01 - 4.61	0.00 1.17 0.01 - 4.11	0.00 0.84 0.01 - 2.61	0.00 0.54 0.01 - 2.05	0.01 0.65 0.02 - 1.80	0.01 0.69 0.02 - 1.92	0.01 0.63 0.02 - 1.88	0.01 0.71 0.02 - 2.53	0.02 0.63 0.03 - 2.10	0.04 0.66 0.05 - 1.63
SIMDKR	0.02 1.26 0.80 - 2.48	0.01 0.86 0.49 - 2.94	0.01 0.95 0.50 - 2.38	0.02 1.22 0.50 - 2.57	0.02 1.22 0.48 - 2.53	0.02 0.98 0.48 - 2.47	0.02 1.05 0.47 - 2.22	0.02 1.27 0.81 - 2.72	0.02 1.23 0.78 - 2.64	0.02 1.17 0.80 - 2.45	0.02 1.19 0.79 - 2.81	0.02 1.36 0.81 - 2.28
EPSM	0.01 1.17 0.80 - 1.86	0.01 0.94 0.52 - 1.70	0.02 1.24 0.57 - 3.91	0.03 1.36 0.66 - 2.64	0.03 1.06 0.54 - 1.76	0.03 1.02 0.49 - 1.60	0.04 1.13 0.48 - 1.73	0.06 1.20 0.79 - 1.68	0.08 1.16 0.79 - 2.31	0.11 1.12 0.78 - 2.45	0.24 1.34 0.85 - 2.64	0.49 1.68 1.02 - 2.35

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.