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:55:58

Text genome (alphabet : 64 - size : 1048576 bytes)

	2	4	8	16	32	64	128	256	512	1024	2048	4096
TVSBS	0.30 8.66 3.70 - 15.44	0.20 4.30 2.91 - 11.16	0.18 2.99 2.09 - 7.33	0.20 2.48 1.54 - 6.35	0.22 2.37 1.21 - 5.47	0.28 2.78 1.17 - 5.30	0.31 3.09 0.98 - 5.76	0.27 2.74 1.11 - 5.39	0.30 2.97 1.02 - 5.22	0.29 2.82 1.04 - 5.45	0.30 2.95 1.09 - 5.83	0.23 2.22 0.89 - 6.10
FJS	0.02 8.85 4.10 - 14.47	0.01 4.78 3.08 - 12.46	0.01 4.45 2.47 - 13.69	0.01 4.18 1.81 - 11.59	0.02 5.38 1.73 - 12.20	0.02 6.72 1.86 - 12.96	0.02 6.07 1.61 - 13.15	0.02 5.64 1.99 - 13.54	0.03 5.94 1.62 - 11.95	0.04 6.72 1.71 - 12.71	0.05 6.07 1.64 - 13.27	0.06 5.22 1.60 - 13.83
HASH8	0.02 3.25 1.45 - 5.03	0.01 1.90 1.43 - 4.79	0.01 11.73 8.91 - 26.30	0.01 1.87 1.42 - 5.30	0.02 1.72 0.83 - 2.84	0.02 1.32 0.64 - 2.23	0.02 1.08 0.56 - 1.86	0.02 0.95 0.52 - 5.60	0.02 1.04 0.60 - 2.04	0.02 1.07 0.63 - 1.90	0.03 1.30 0.60 - 2.03	0.03 0.89 0.58 - 1.93
SO	0.02 2.64 1.20 - 4.27	0.01 1.70 1.18 - 4.59	0.01 1.73 1.16 - 5.30	0.01 1.56 1.19 - 4.65	0.02 2.68 1.20 - 4.69	0.02 2.32 1.08 - 3.92	0.02 2.15 1.07 - 4.27	0.02 1.85 1.09 - 4.09	0.02 2.42 1.08 - 3.87	0.02 2.01 1.08 - 4.17	0.02 2.06 1.07 - 3.99	0.02 1.72 1.08 - 4.59
SBNDM	0.03 4.63 2.29 - 7.96	0.02 2.32 1.35 - 6.73	0.02 1.92 1.12 - 5.02	0.02 1.36 0.88 - 3.65	0.04 1.75 0.74 - 2.80	0.03 1.72 0.72 - 3.00	0.02 1.39 0.71 - 2.93	0.03 1.64 0.72 - 2.69	0.03 1.62 0.72 - 3.11	0.03 1.58 0.73 - 2.91	0.03 1.79 0.73 - 2.66	0.02 1.31 0.74 - 2.85
LBNDM	0.02 9.23 3.28 - 16.74	0.01 4.41 1.98 - 11.34	0.01 2.44 1.49 - 6.78	0.01 1.55 1.17 - 4.58	0.02 1.67 0.82 - 3.47	0.02 1.64 0.74 - 3.29	0.02 1.44 0.66 - 2.88	0.02 2.82 0.80 - 15.04	0.02 14.05 3.44 - 22.81	0.02 14.66 4.39 - 22.60	0.02 11.65 4.84 - 17.17	0.03 8.66 4.45 - 18.13
SBNDM2	0.02 3.84 1.77 - 7.90	0.01 2.16 1.06 - 7.05	0.01 1.98 1.09 - 5.55	0.01 1.36 0.79 - 3.76	0.02 1.54 0.70 - 2.52	0.01 0.98 0.68 - 2.46	0.02 1.44 0.69 - 2.47	0.02 1.19 0.69 - 2.52	0.02 1.39 0.67 - 2.61	0.02 1.50 0.69 - 8.91	0.02 1.43 0.69 - 2.59	0.02 1.17 0.66 - 2.80
SBNDM-BMH	0.03 7.70 3.31 - 15.21	0.02 3.53 1.73 - 10.55	0.02 2.16 1.29 - 6.44	0.02 1.41 0.97 - 3.81	0.03 1.51 0.73 - 2.86	0.03 1.55 0.73 - 2.73	0.03 1.54 0.75 - 2.58	0.03 1.55 0.74 - 2.88	0.03 1.59 0.73 - 2.62	0.03 1.71 0.76 - 2.72	0.03 1.62 0.74 - 2.54	0.03 1.40 0.72 - 2.76
FNDM	0.02 7.95 2.89 - 15.65	0.01 4.02 1.99 - 11.81	0.01 2.50 1.80 - 6.44	0.01 1.71 1.27 - 4.59	0.02 1.98 0.91 - 3.26	0.02 1.72 0.89 - 3.52	0.02 1.64 0.91 - 3.17	0.02 1.86 0.91 - 3.21	0.02 1.95 0.91 - 3.48	0.02 1.94 0.92 - 3.33	0.02 1.88 0.87 - 3.28	0.02 1.41 0.89 - 3.56
FSBNDM	0.02 7.07 2.83 - 15.54	0.01 3.31 1.83 - 8.36	0.01 2.13 1.37 - 5.15	0.01 1.21 0.87 - 3.62	0.02 1.53 0.70 - 2.72	0.02 1.68 0.73 - 2.43	0.02 1.70 0.72 - 2.87	0.02 1.43 0.72 - 2.40	0.02 1.53 0.68 - 2.58	0.02 1.56 0.71 - 2.47	0.02 1.70 0.73 - 2.49	0.01 1.12 0.70 - 5.60
SBNDMQ8	0.02 3.38 1.45 - 5.53	0.01 2.01 1.44 - 5.03	0.03 4.56 3.03 - 12.09	0.01 1.01 0.74 - 2.89	0.02 1.23 0.56 - 2.33	0.02 1.13 0.55 - 2.35	0.02 1.01 0.54 - 2.38	0.02 1.05 0.55 - 1.98	0.02 1.12 0.55 - 2.13	0.02 1.06 0.55 - 2.35	0.02 0.89 0.55 - 2.16	0.02 0.94 0.54 - 2.20
UFNDMQ2	0.02 3.48 1.66 - 7.62	0.02 2.66 1.38 - 7.09	0.02 2.16 1.26 - 4.61	0.02 1.29 0.88 - 3.46	0.02 1.70 0.70 - 2.85	0.02 1.56 0.69 - 2.70	0.01 1.43 0.69 - 2.83	0.01 1.43 0.67 - 2.70	0.02 1.59 0.68 - 2.83	0.01 1.52 0.69 - 2.99	0.01 1.30 0.69 - 2.82	0.01 1.13 0.66 - 2.98
UFNDMQ8	0.02 2.58 1.44 - 4.68	0.01 1.98 1.45 - 5.46	0.02 1.23 0.82 - 3.00	0.02 0.87 0.62 - 2.55	0.01 1.06 0.56 - 2.17	0.01 1.00 0.55 - 2.33	0.01 1.18 0.56 - 2.46	0.01 1.01 0.56 - 2.15	0.01 1.24 0.56 - 2.32	0.02 1.41 0.58 - 2.09	0.01 0.97 0.55 - 5.76	0.01 0.88 0.56 - 2.12
KBNDM	0.02 5.11 2.91 - 10.90	0.01 2.70 1.68 - 6.69	0.01 1.94 1.30 - 5.32	0.01 1.51 1.02 - 3.92	0.02 1.56 0.82 - 2.78	0.02 1.20 0.66 - 2.50	0.02 1.45 0.62 - 2.27	0.02 1.41 0.64 - 2.56	0.02 1.33 0.62 - 2.29	0.02 1.24 0.60 - 2.26	0.01 0.91 0.62 - 1.93	0.02 0.98 0.61 - 2.51
FS-W2	0.05 6.02 3.40 - 12.21	0.04 3.52 2.06 - 9.11	0.04 2.51 1.53 - 7.02	0.05 2.61 1.00 - 7.40	0.06 2.95 1.12 - 5.67	0.06 2.56 0.97 - 5.95	0.07 2.63 1.00 - 5.10	0.06 1.90 0.89 - 4.71	0.07 2.04 0.83 - 3.95	0.10 2.16 0.80 - 3.89	0.10 1.53 0.74 - 3.76	0.13 1.44 0.72 - 3.91
LWFR5	0.02 2.58 1.45 - 4.40	0.01 1.79 1.39 - 4.94	0.06 2.56 1.75 - 6.93	0.08 1.10 0.60 - 2.63	0.10 1.27 0.53 - 2.04	0.10 1.12 0.51 - 2.16	0.09 0.98 0.50 - 1.90	0.10 1.05 0.51 - 1.90	0.09 0.85 0.48 - 2.07	0.14 1.06 0.47 - 1.92	0.12 0.68 0.49 - 2.10	0.19 0.84 0.51 - 2.63
QF43	0.02 2.40 1.45 - 4.46	0.01 1.98 1.45 - 5.06	0.02 1.12 0.80 - 3.33	0.02 0.91 0.60 - 2.33	0.03 1.11 0.52 - 2.19	0.03 1.07 0.49 - 2.10	0.03 1.02 0.48 - 1.87	0.03 1.05 0.50 - 1.95	0.03 0.98 0.48 - 2.39	0.03 0.97 0.49 - 1.86	0.02 0.60 0.45 - 1.99	0.03 0.99 0.47 - 85.71
SBNDM-W2	0.02 8.84 3.37 - 13.24	0.01 4.06 2.10 - 9.69	0.01 2.12 1.42 - 5.65	0.02 1.75 0.97 - 3.71	0.02 1.54 0.69 - 2.97	0.02 1.21 0.69 - 3.42	0.02 1.53 0.68 - 2.60	0.02 1.38 0.69 - 2.91	0.02 1.45 0.70 - 2.95	0.02 1.40 0.70 - 2.73	0.01 0.96 0.69 - 2.68	0.02 1.27 0.68 - 2.82
WFR2	0.09 5.22 2.16 - 8.94	0.06 2.50 1.22 - 8.04	0.06 1.93 1.04 - 5.06	0.07 1.64 0.86 - 4.11	0.09 1.41 0.64 - 2.69	0.10 1.31 0.58 - 2.15	0.09 1.15 0.54 - 2.12	0.08 0.99 0.53 - 1.90	0.11 1.12 0.49 - 1.87	0.12 1.04 0.47 - 2.07	0.10 0.71 0.49 - 1.83	0.16 0.85 0.48 - 2.19
TWFRQ2	0.09 4.45 1.86 - 9.45	0.06 2.44 1.23 - 6.86	0.06 1.84 1.06 - 4.83	0.07 1.55 0.74 - 3.65	0.09 1.41 0.65 - 2.69	0.09 1.20 0.58 - 2.03	0.09 1.12 0.53 - 2.03	0.10 1.26 0.54 - 2.08	0.08 0.86 0.48 - 1.87	0.10 0.99 0.46 - 1.67	0.09 0.80 0.49 - 1.96	0.10 0.76 0.46 - 2.07
TWFRQ4	0.02 2.69 1.45 - 5.36	0.06 2.44 1.57 - 6.17	0.06 1.07 0.77 - 3.57	0.08 1.12 0.60 - 2.55	0.07 0.97 0.54 - 2.09	0.09 1.10 0.52 - 2.04	0.08 0.99 0.51 - 2.35	0.10 1.22 0.51 - 1.96	0.08 0.87 0.48 - 1.73	0.10 0.94 0.47 - 1.90	0.08 0.74 0.50 - 2.13	0.09 0.74 0.45 - 2.04
WOM	0.02 7.83 3.70 - 15.13	0.02 4.68 2.45 - 12.14	0.02 3.17 1.86 - 8.90	0.02 3.37 1.22 - 8.20	0.03 3.69 1.22 - 7.86	0.03 3.33 1.12 - 6.43	0.02 2.61 1.04 - 5.26	0.03 2.57 1.02 - 5.48	0.03 2.87 0.91 - 4.99	0.03 2.19 0.92 - 4.58	0.03 1.91 0.98 - 4.75	0.04 1.88 0.88 - 4.58
LIBC1	0.01 4.00 1.68 - 6.20	0.01 2.66 1.27 - 7.52	0.01 2.12 1.09 - 6.14	0.01 1.98 0.74 - 4.28	0.01 1.90 0.81 - 3.09	0.02 1.77 0.74 - 2.77	0.01 1.32 0.64 - 2.88	0.01 1.60 0.65 - 3.41	0.01 5.13 1.18 - 10.00	0.01 4.73 1.12 - 10.84	0.01 3.49 1.18 - 12.22	0.01 3.52 1.09 - 10.67
MUSL1	0.00 0.01 0.00 - 0.23	0.00 0.01 0.00 - 0.05	0.00 0.21 0.01 - 3.09	0.00 2.15 0.02 - 8.91	0.00 2.61 0.01 - 10.18	0.01 2.85 0.03 - 10.11	0.01 2.36 0.03 - 9.82	0.01 2.11 0.02 - 8.90	0.01 2.77 0.05 - 9.68	0.02 2.55 0.04 - 10.54	0.03 2.33 0.04 - 13.23	0.06 2.25 0.09 - 9.46
SIMDKR	0.01 1.12 0.73 - 3.24	0.01 1.27 0.88 - 3.20	0.01 1.20 0.85 - 3.27	0.01 1.30 0.83 - 3.82	0.02 1.75 0.85 - 3.15	0.02 1.90 0.82 - 3.30	0.02 1.80 0.83 - 3.19	0.02 1.50 0.83 - 4.10	0.02 1.69 0.82 - 2.88	0.02 1.65 0.84 - 3.01	0.01 1.33 0.82 - 4.83	0.01 1.38 0.82 - 3.24
EPSM	0.01 0.68 0.50 - 1.59	0.01 0.73 0.52 - 2.05	0.02 0.92 0.62 - 2.70	0.03 1.17 0.66 - 2.16	0.03 1.05 0.52 - 1.78	0.03 0.91 0.48 - 1.74	0.03 0.87 0.50 - 1.73	0.04 0.90 0.48 - 1.86	0.07 0.96 0.48 - 1.82	0.10 0.97 0.49 - 2.06	0.15 0.86 0.54 - 2.35	0.31 1.08 0.65 - 2.56

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.