================= Decomposition memory consumption analysis TEST 1-a: Decomposition memory consumption (ctxunit count): worst case, Prisms all different (Figure 14a) Prisms Count Context Units 1 3 4 5 10 20 30 40 50 Non-indexed Prisms 3 16 22 35 61 133 195 261 325 Decomposition 3 10 13 19 27 80 134 163 218 saving (%) 0.0 37.5 40.9 45.7 55.7 39.8 31.3 37.5 32.9 TEST 1-b: Memory consumption estimation (KB) (Figure 14b) Prisms Memory [KB] 5 10 20 30 40 50 Jena Model 20.3 37.2 60.4 85.7 115.0 149.7 PRISSMA 141.9 225.8 346.3 553.0 868.3 1072.0 overhead (%) 699.0 607.0 573.3 645.3 755.0 716.1 ================= Search algorithm response time evaluation TEST 2: Search function response time (number of prisms) - Worst case, ( different prisms). Prisms of same size m = 10 cu (Figure 15a) Search algorithm response time O(L) m= 10, n = 10, L = variable Prisms Count ms 10 20 30 40 50 Nexus 4 run1 68 237 370 582 694 run2 66 228 366 563 685 run3 77 214 388 580 700 run4 64 240 383 548 686 run5 65 227 390 518 674 Avg 68.00 229.20 379.40 558.20 687.80 stddev 5.244044241 10.18331969 10.80740487 26.38560213 9.859006035 Nexus 10 run1 51 144 232 324 453 run2 54 138 248 320 460 run3 46 134 225 331 459 run4 40 122 220 338 464 run5 42 141 217 336 439 Avg 46.60 135.80 228.40 329.80 455.00 stddev 5.899152482 8.555699854 12.34098862 7.694153625 9.772410143 Galaxy Mega run1 60 191 332 501 607 run2 59 184 305 499 562 run3 61 162 311 487 597 run4 62 162 332 498 611 run5 63 160 341 483 628 Avg 61.00 171.80 324.20 493.60 601.00 stddev 1.58113883 14.56708619 15.38505769 8.049844719 24.50510151 Galaxy Note run1 65 228 370 539 660 run2 72 205 346 539 667 run3 90 226 352 546 651 run4 71 239 387 514 655 run5 73 229 355 548 677 Avg 74.20 225.40 362.00 537.20 662.00 stddev 9.364827815 12.46194206 16.53783541 13.59043781 10.29563014 Search function response time (number m of context units in input context) 5 different prisms, size n = 2 cu (Figure 15b) n= 2, m = variable, L = 5 O(m^n)= O(m^2) (m) Context Unit count in incoming context ms 10 20 30 40 Nexus 4 run1 15 25 34 65 run2 14 24 35 63 run3 12 26 42 62 run4 13 25 36 64 run5 17 23 32 66 Avg 14.20 24.60 35.80 64.00 stddev 1.923538406 1.140175425 3.768288736 1.58113883 Nexus 10 run1 12 19 29 50 run2 13 17 26 50 run3 12 28 25 50 run4 10 17 27 64 run5 15 14 28 52 Avg 12.40 19.00 27.00 53.20 stddev 1.816590212 5.338539126 1.58113883 6.099180273 Galaxy Mega run1 14 21 32 58 run2 12 23 30 60 run3 11 22 38 59 run4 12 23 33 55 run5 14 21 29 66 Avg 12.60 22.00 32.40 59.60 stddev 1.341640786 1 3.507135583 4.037325848 Galaxy Note run1 18 32 35 78 run2 21 36 50 71 run3 19 30 40 81 run4 20 27 49 74 run5 20 36 45 69 Avg 19.60 32.20 43.80 74.60 stddev 1.140175425 3.898717738 6.300793601 4.929503018 Search function response time (input context constant, 50 context units) 10 different prisms with different sizes (Figure 15c) n= variable, m = 50, L = 5 O(n^2) (m) Context Unit count in each Prism ms 10 20 30 40 50 Nexus 4 run1 49 171 307 508 844 run2 48 177 314 495 831 run3 53 174 326 492 847 run4 47 173 313 505 832 run5 55 180 300 508 834 Avg 50.40 175.00 312.00 501.60 837.60 stddev 3.435112807 3.535533906 9.617692031 7.569676347 7.368853371 Nexus 10 run1 28 91 185 299 482 run2 34 94 179 336 436 run3 52 94 155 344 471 run4 32 102 157 289 442 run5 41 90 176 334 465 Avg 37.40 94.20 170.40 320.40 459.20 stddev 9.423375192 4.711687596 13.55728586 24.64345755 19.53714411 Galaxy Mega run1 38 101 235 452 671 run2 43 86 241 469 628 run3 41 95 284 451 675 run4 42 93 246 486 635 run5 40 124 264 458 702 Avg 40.80 99.80 254.00 463.20 662.20 stddev 1.923538406 14.54991409 19.96246478 14.61848145 30.55650504 Galaxy Note run1 52 136 258 444 741 run2 54 137 237 493 751 run3 55 166 278 477 767 run4 56 117 263 457 748 run5 55 149 294 490 710 Avg 54.40 141.00 266.00 472.20 743.40 stddev 1.516575089 18.069311 21.45926373 21.20613119 20.95948473 Search Algorithm validation (Figure 11) =============== (Test 5) GEO actual positives 25 actual negatives 25 T 0.1 0.2 0.3 0.4 0.50 0.60 0.7 0.8 0.9 decay = 1 True Positives 25 25 25 25 25 25 25 25 25 True negatives 19 1 0 0 0 0 0 0 0 False Positives 6 24 25 25 25 25 25 25 25 False Negatives 0 0 0 0 0 0 0 0 0 geo decay = 2 True Positives 19 25 25 25 25 25 25 25 25 True negatives 24 16 9 1 0 0 0 0 0 False Positives 1 9 16 24 25 25 25 25 25 False Negatives 6 0 0 0 0 0 0 0 0 geo decay = 5 True Positives 13 17 23 25 25 25 25 25 25 True negatives 25 25 23 19 11 8 1 0 0 False Positives 0 0 2 6 14 17 24 25 25 False Negatives 12 8 2 0 0 0 0 0 0 geo decay = 10 True Positives 13 13 14 18 23 25 25 25 25 True negatives 25 25 25 24 23 22 13 10 1 False Positives 0 0 0 1 2 3 12 15 24 False Negatives 12 12 11 7 2 0 0 0 0 geo decay = 25 True Positives 13 13 13 13 14 15 18 21 25 True negatives 25 25 25 25 25 25 24 24 22 False Positives 0 0 0 0 0 0 1 1 3 False Negatives 12 12 12 12 11 10 7 4 0 geo decay = 50 True Positives 13 13 13 13 13 13 13 14 18 True negatives 25 25 25 25 25 25 25 25 25 False Positives 0 0 0 0 0 0 0 0 0 False Negatives 12 12 12 12 12 12 12 11 7 TIME actual positives 25 actual negatives 25 T 0.1 0.2 0.3 0.4 0.50 0.60 0.7 0.8 0.9 time decay = 0.8 True Positives 25 25 25 25 25 25 25 25 25 True negatives 18 0 0 0 0 0 0 0 0 False Positives 7 25 25 25 25 25 25 25 25 False Negatives 0 0 0 0 0 0 0 0 0 time decay = 1 True Positives 25 25 25 25 25 25 25 25 25 True negatives 25 0 0 0 0 0 0 0 0 False Positives 0 25 25 25 25 25 25 25 25 False Negatives 0 0 0 0 0 0 0 0 0 time decay = 2 True Positives 15 25 25 25 25 25 25 25 25 True negatives 25 22 6 0 0 0 0 0 0 False Positives 0 3 19 25 25 25 25 25 25 False Negatives 10 0 0 0 0 0 0 0 0 time decay = 5 True Positives 9 13 18 25 25 25 25 25 25 True negatives 25 25 25 25 16 6 0 0 0 False Positives 0 0 0 0 9 19 25 25 25 False Negatives 16 12 7 0 0 0 0 0 0 time decay = 25 True Positives 6 7 7 9 10 12 13 16 24 True negatives 25 25 25 25 25 25 25 25 25 False Positives 0 0 0 0 0 0 0 0 0 False Negatives 19 18 18 16 15 13 12 9 1 STRING actual positives 25 actual negatives 25 T 0.1 0.2 0.3 0.4 0.50 0.60 0.7 0.8 0.9 Jaro True Positives 3 4 7 12 14 15 15 15 15 True negatives 25 23 20 15 13 13 13 13 13 False Positives 0 2 5 10 12 12 12 12 12 False Negatives 22 21 18 13 11 10 10 10 10 Jaro-Winkler True Positives 7 7 7 16 18 19 19 19 19 True negatives 22 22 17 12 10 10 10 10 10 False Positives 3 3 8 13 15 15 15 15 15 False Negatives 18 18 18 9 7 6 6 6 6 Monge-Elkan True Positives 8 15 25 25 25 25 25 25 25 True negatives 25 24 23 11 3 1 1 0 0 False Positives 0 1 2 14 22 24 24 25 25 False Negatives 17 10 0 0 0 0 0 0 0 Levenshtein True Positives 1 3 4 6 11 12 15 17 24 True negatives 25 25 25 24 21 18 10 8 4 False Positives 0 0 0 1 4 7 15 17 21 False Negatives 24 22 21 19 14 13 10 8 1 TOPOLOGY actual positives 25 actual negatives 25 T 0.1 0.2 0.3 0.4 0.50 0.60 0.7 0.8 0.9 Missing Unit cost = 0.2 True Positives 1 25 25 25 25 25 25 25 25 True negatives 25 0 0 0 0 0 0 0 0 False Positives 0 25 25 25 25 25 25 25 25 False Negatives 24 0 0 0 0 0 0 0 0 Missing Unit cost = 0.4 True Positives 1 1 1 25 25 25 25 25 25 True negatives 25 25 25 0 0 0 0 0 0 False Positives 0 0 0 25 25 25 25 25 25 False Negatives 24 24 24 0 0 0 0 0 0 Missing Unit cost = 0.6 True Positives 1 1 1 1 1 25 25 25 25 True negatives 25 25 25 25 25 0 0 0 0 False Positives 0 0 0 0 0 25 25 25 25 False Negatives 24 24 24 24 24 0 0 0 0 Missing Unit cost = 0.8 True Positives 1 1 1 1 1 1 1 25 25 True negatives 25 25 25 25 25 25 25 0 0 False Positives 0 0 0 0 0 0 0 25 25 False Negatives 24 24 24 24 24 24 24 0 0 COMPLETE PRISMS actual positives 25 actual negatives 25 T 0.1 0.2 0.3 0.4 0.50 0.60 0.7 0.8 0.9 (decay time = 5, decay geo = 10, cost missing =.2, strings = monge-elkan) True Positives 1 5 5 16 25 25 25 25 25 True negatives 25 25 25 25 23 23 23 19 18 False Positives 0 0 0 0 2 2 2 6 7 False Negatives 24 20 20 9 0 0 0 0 0 (decay time = 10, decay geo = 5, cost missing =.2, strings = monge-elkan) True Positives 1 5 12 14 16 25 25 25 25 True negatives 25 25 23 23 23 23 23 23 23 False Positives 0 0 2 2 2 2 2 2 2 False Negatives 24 20 13 11 9 0 0 0 0 (decay time = 10, decay geo = 5, cost missing =.4, strings = monge-elkan) True Positives 1 1 1 14 16 25 25 25 25 True negatives 25 25 25 23 23 23 23 23 23 False Positives 0 0 0 2 2 2 2 2 2 False Negatives 24 24 24 11 9 0 0 0 0 Semantic String similarities vs Monge-Elkan metric (Figure 12) =============== (Test 6) Wu-Palmer True Positives 6 8 8 8 10 15 15 22 24 True negatives 25 24 23 22 19 18 9 5 5 False Positives 0 1 2 3 6 7 16 20 20 False Negatives 19 17 17 17 15 10 10 3 1 Monge-Elkan True Positives 0 0 0 0 0 1 5 18 25 True negatives 25 25 25 25 25 24 23 13 1 False Positives 0 0 0 0 0 1 2 12 24 False Negatives 25 25 25 25 25 24 20 7 0 ms 1 5 10 15 20 Monge-Elkan 7 9 9 11 13 run2 6 12 13 9 13 run3 9 11 12 13 11 run4 9 8 11 12 13 run5 6 10 10 13 11 Avg 7.40 10.00 11.00 11.60 12.20 stddev 1.516575089 1.58113883 1.58113883 1.673320053 1.095445115 Wu-Palmer 140 158 179 189 210 run2 147 152 180 190 212 run3 144 155 174 197 209 run4 140 157 176 195 217 run5 144 162 178 203 208 Avg 143.00 156.80 177.40 194.80 211.20 stddev 3.0000 3.701351105 2.408318916 5.674504384 3.563705936