583:
192:
1473:
1047:
So, by working from left to right, one can reconstruct all the fingerprints and the resulting list of integers will be in sorted order. Merging two quotient filters is then a simple matter of converting each quotient filter into such a list, merging the two lists and using it to populate a new larger
988:. A large database, such as Webtable may be composed of smaller sub-tables each of which has an associated filter. Each query is distributed concurrently to all sub-tables. If a sub-table does not contain the requested element, its filter can quickly complete the request without incurring any I/O.
543:
If the canonical slot is occupied then we must locate the quotient's run. The set of slots that hold remainders belonging to the same quotient are stored contiguously and these comprise the quotient's run. The first slot in the run might be the canonical slot but it is also possible that the entire
254:
in which entries contain only a portion of the key plus some additional meta-data bits. These bits are used to deal with the case when distinct keys happen to hash to the same table entry. By way of contrast, other types of hash tables that deal with such collisions by linking to overflow areas are
658:
Insertion follows a path similar to lookup until we ascertain that the key is definitely not in the filter. At that point we insert the remainder in a slot in the current run, a slot chosen to keep the run in sorted order. We shift forward the remainders in any slots in the cluster at or after the
204:
on disk. As keys are added to or removed from the database, the filter is updated to reflect this. Any lookup will first consult the fast quotient filter, then look in the (presumably much slower) database only if the quotient filter reported the presence of the key. If the filter returns absence,
195:
An approximate member query (AMQ) filter used to speed up answers in a key-value storage system. Key-value pairs are stored on a disk which has slow access times. AMQ filter decisions are much faster. However some unnecessary disk accesses are made when the filter reports a positive (in order to
237:
penned the name "quotient filter", described several variants with different metadata encoding trade-offs, showed how to merge and resize quotient filters, presented a write-optimized version of the quotient filter for use on disk, and applied the structure to database storage problems. In 2017,
1043:
By construction the values in a quotient filter are stored in sorted order. Each run is associated with a specific quotient value, which provides the most significant portion of the fingerprint, the runs are stored in order and each slot in the run provides the least significant portion of the
188:). There is a tradeoff between ε, the false positive rate, and storage size; increasing the filter's storage size reduces ε. Other AMQ operations include "insert" and "optionally delete". The more elements are added to the set, the larger the probability of false positives.
208:
A quotient filter has the usual AMQ operations of insert and query. In addition it can also be merged and re-sized without having to re-hash the original keys (thereby avoiding the need to access those keys from secondary storage). This property benefits certain kinds of
547:
To locate the quotient's run we must first locate the start of the cluster. The cluster consists of a contiguous set of runs. Starting with the quotient's canonical slot we can scan left to locate the start of the cluster, then scan right to locate the quotient's run.
794:
Bender argues that clusters are small. This is important because lookups and inserts require locating the start and length of an entire cluster. If the hash function generates uniformly distributed fingerprints then the length of most runs is
569:
indicates the start of another run, thus the end of the previous run, so we decrement the running count. When the running count reaches zero, we are scanning the quotient's run. We can compare the remainder in each slot in the run with
641:
being false. The 1st run is found at index 1, the 2nd at 4 and the 3rd at 5. We compare the remainder held in each slot in the run that starts at index 5. There is only one slot in that run but, in our example, its remainder equals
1036:-trees into larger ones and merging their quotient filters. An essential property of quotient filters is that they can be efficiently merged without having to re-insert the original keys. Given that for large data sets the Wanna-
690:
The figure shows a quotient filter proceeding through a series of states as elements are added. In state 1 three elements have been added. The slot each one occupies forms a one-slot run which is also a distinct cluster.
637:'s run is the 3rd run in the cluster. The scan stops at slot 1, which we detect as the cluster's start because it is not empty and not shifted. Now we must scan right to the 3rd run. The start of a run is indicated by
242:
described a version that uses hardware bit-manipulation instructions to improve performance, supports concurrent updates, and adds support for associating a variable-sized counter to each element.
823:
Bender calculates the probability of a false positive (i.e. when the hash of two keys results in the same fingerprint) in terms of the hash table's remainder size and load factor. Recall that a
1048:
quotient filter. Similarly, we can halve or double the size of a quotient filter without rehashing the keys since the fingerprints can be recomputed using just the quotients and remainders.
966:
555:
is false. This indicates the start of the cluster. Then we scan right keeping a running count of the number of runs we must skip over. Each slot to the left of the canonical slot having
1002:
The space used by quotient filters is comparable to that of Bloom filters. However quotient filters can be efficiently merged within memory without having to re-insert the original keys.
172:, AMQ). A query will elicit a reply specifying either that the element is definitely not in the set or that the element is probably in the set. The former result is definitive;
334:
As described below, the insertion algorithm ensures that all fingerprints having the same quotient are stored in contiguous slots. Such a set of fingerprints is defined as a
196:
weed out the false positives). Overall answer speed is better with the AMQ filter than without it. Use of an AMQ filter for this purpose, however, does increase memory usage.
899:
777:. The runs for quotients 1, 2 and 4 now comprise a cluster, and the presence of those three runs in the cluster is indicated by having slots 1, 2 and 4 being marked as
229:
in 2005. In 2009, Dillinger and
Manolios optimized the structure's metadata, added in-place accommodation of more elements, and applied the structure to explicit-state
857:
1241:; Johnson, Rob; Kraner, Russell; Kuszmaul, Bradley C.; Medjedovic, Dzejla; Montes, Pablo; Shetty, Pradeep; Spillane, Richard P.; Zadok, Erez (27–31 August 2012).
180:. But with the latter result there is some probability, ε, of the test returning "element is in the set" when in fact the element is not present in the set (
1359:
1009:
or LSM-tree. The LSM-tree is actually a collection of trees but which is treated as a single key-value store. One variation of the LSM-Tree is the
976:
Pandey's version of the quotient filter requires less space than a comparable Bloom filter when the target false-positive rate is less than 1/64.
136:
1498:
20:
670:
If we insert a remainder at the start of an existing run, the previous remainder is shifted and becomes a continuation slot, so we set its
540:
is the key's canonical slot. That slot is empty if its three meta-data bits are false. In that case the filter does not contain the key.
1208:; Johnson, Rob; Kuszmaul, Bradley C.; Medjedovic, Dzejla; Montes, Pablo; Shetty, Pradeep; Spillane, Richard P.; Zadok, Erez (June 2011).
1304:
Pandey, Prashant; Bender, Michael A.; Johnson, Rob; Patro, Rob (May 2017). "A General-Purpose
Counting Filter: Making Every Bit Count".
345:. The initial run and all subsequent runs comprise the cluster, which terminates at an unoccupied slot or the start of another cluster.
169:
225:
underlying a quotient filter was described by Cleary in 1984. First known reference to using the structure as an AMQ filter is by Pagh
995:
Two quotient filters can be efficiently merged without affecting their false positive rates. This is not possible with Bloom filters.
338:. Note that a run's first fingerprint might not occupy its canonical slot if the run has been forced right by some run to the left.
574:. If found, we report that the key is (probably) in the filter otherwise we report that the key is definitely not in the filter.
1133:
355:
is set when a slot is the canonical slot for some key stored (somewhere) in the filter (but not necessarily in this slot).
89:
1344:
129:
904:
255:
not compact because the overhead due to linkage can exceed the storage used to store the key. In a quotient filter a
1477:
1090:
1006:
210:
185:
177:
323:. However the canonical slot might already be occupied because multiple keys can hash to the same fingerprint—a
1010:
1425:"Efficient, Scalable, and Versatile Application and System Transaction Management for Direct Storage Layers"
200:
A typical application for quotient filters, and other AMQ filters, is to serve as a proxy for the keys in a
1209:
348:
The three additional bits are used to reconstruct a slot's fingerprint. They have the following function:
165:
122:
1442:
161:
51:
734:
has a quotient of 2. Since its canonical slot is in use, it is shifted into slot 3, and is marked as
1267:
1238:
1205:
105:
28:
1217:
Proceedings of the 3rd USENIX conference on Hot topics in storage and file systems (HotStorage'11)
1014:
1405:
1338:
1283:
1257:
1110:
1040:-trees may not be in memory, accessing them to retrieve the original keys would incur many I/Os.
870:
79:
1367:
OSDI '06: Proceedings of the 7th USENIX Symposium on
Operating Systems Design and Implementation
1242:
1021:-tree has an associated quotient filter. A query on the SAMT is directed at only select Wanna-
842:
1493:
1397:
1309:
1275:
1102:
331:. If the canonical slot is occupied then the remainder is stored in some slot to the right.
327:—or because even when the keys' fingerprints are distinct they can have the same quotient—a
205:
the key is known not to be in the database without any disk accesses having been performed.
341:
However a run whose first fingerprint occupies its canonical slot indicates the start of a
1455:
1424:
1169:
562:
indicates another run to be skipped, so we increment the running count. Each slot having
1271:
1306:
Proceedings of the 2017 ACM International
Conference on Management of Data (SIGMOD '17)
582:
230:
157:
32:
1487:
1114:
1067:
256:
154:
1409:
1287:
544:
run has been shifted to the right by the encroachment from the left of another run.
1062:
1005:
This is particularly important in some log structured storage systems that use the
985:
448:
Slot is holding continuation of run that has been shifted from its canonical slot.
284:
46:
41:
1144:
508:
Slot is holding continuation of run that has been shifted from its canonical slot.
191:
1388:
O'Neil, Patrick; et al. (1996). "The log-structured merge-tree (LSM-tree)".
1129:
110:
70:
510:
Also the run for which this is the canonical slot exists but is shifted right.
480:
Also the run for which this is the canonical slot exists but is shifted right.
251:
222:
1279:
1141:
Proceedings of the
Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
984:
Quotient filters are AMQs and, as such, provide many of the same benefits as
667:
bit because it pertains to the slot, not the remainder contained in the slot.
1314:
1106:
420:
Slot is holding start of run that has been shifted from its canonical slot.
61:
478:
Slot is holding start of run that has been shifted from its canonical slot.
1472:
1401:
757:
so the remainders in slots 1 through 4 must be shifted. Slot 2 receives b
201:
1057:
361:
is set when a slot is occupied but not by the first remainder in a run.
586:
An example quotient filter showing in order the insertion of elements
1028:
The storage system in its normal operation compacts the SAMT's Wanna-
521:
We can test if a quotient filter contains some key, d, as follows.
1262:
84:
1013:
or SAMT. In this variation, a SAMT's component trees are called
998:
A few duplicates can be tolerated efficiently and can be deleted.
367:
is set when the remainder in a slot is not in its canonical slot.
1331:
The Art of
Computer Programming:Searching and Sorting, volume 3
279:
most significant bits is called the quotient, hence the name
1360:"Bigtable: A Distributed Storage System for Structured Data"
629:, which is 4. Scanning left from slot 4 we encounter three
1174:
462:
Slot is holding start of run that is in its canonical slot.
991:
Quotient filters offer two benefits in some applications.
742:. The runs for quotients 1 and 2 now comprise a cluster.
650:
is indeed a member of the filter, with probability 1 - ε.
532:, which comprise its quotient, and its low-order r bits, d
267:
least significant bits is called the remainder while the
1091:"Compact hash tables using bidirectional linear probing"
663:
Shifting a slot's remainder does not affect the slot's
528:, which we then partition into its high-order q bits, d
968:
is approximately the probability of a hard collision.
907:
873:
845:
371:
The various combinations have the following meaning:
1176:. Springer, Lecture Notes in Computer Science 5578.
1168:Dillinger, Peter C.; Manolios, Panagiotis (2009).
960:
893:
851:
831:bit quotient, which determines the table size of
749:has been added. Its quotient is 1. We assume a
722:is shifted into slot 2, and is marked as both a
1243:"Don't thrash: how to cache your hash on flash"
1210:"Don't thrash: how to cache your hash on flash"
1025:-trees as evidenced by their quotient filters.
961:{\displaystyle 1-e^{-\alpha /2^{r}}\leq 2^{-r}}
738:. In addition its canonical slot is marked as
617:. See state 3 in the figure. We would compute
315:. QF will try to store the remainder in slot d
524:We hash the key to produce its fingerprint, d
130:
8:
1333:. Section 6.4, exercise 13: Addison Wesley.
633:slots, at indexes 4, 2 and 1, indicating e
250:The quotient filter is based on a kind of
137:
123:
15:
1313:
1261:
949:
934:
925:
918:
906:
883:
872:
844:
1299:
1297:
1199:
1197:
1195:
1193:
1191:
1189:
1187:
1185:
1183:
1084:
1082:
581:
373:
190:
1078:
536:, which comprise its remainder. Slot d
464:This is also the start of the cluster.
386:
381:
376:
97:
69:
27:
1451:
1440:
1336:
827:bit fingerprint is partitioned into a
659:chosen slot and update the slot bits.
613:Take, for example, looking up element
1134:"An optimal Bloom filter replacement"
815:is the number of slots in the table.
551:We scan left looking for a slot with
7:
859:is the proportion of occupied slots
621:, partition it into its remainder, e
901:. Then, for a good hash function,
681:bit of any remainder that we shift.
170:approximate membership query filter
1143:. pp. 823–829. Archived from
1089:Cleary, John G. (September 1984).
14:
1250:Proceedings of the VLDB Endowment
1170:"Fast, All-Purpose State Storage"
799:(1) and it is highly likely that
706:has a quotient of 1, the same as
1471:
1358:Chang, Fay; et al. (2006).
839:bit remainder. The load factor
294:which hashes to the fingerprint
287:.) The hash table has 2 slots.
1423:Spillane, Richard (May 2012).
1095:IEEE Transactions on Computers
1032:-trees, merging smaller Wanna-
819:Probability of false positives
1:
1499:Probabilistic data structures
176:, the test does not generate
90:Rapidly exploring random tree
1132:; Rao, S. Srinivasa (2005).
894:{\displaystyle \alpha =n/m}
1515:
702:have been added. Element
211:log-structured merge-trees
1007:log-structured merge-tree
1343:: CS1 maint: location (
1280:10.14778/2350229.2350275
319:, which is known as the
160:used to test whether an
1315:10.1145/3035918.3035963
1107:10.1109/TC.1984.1676499
1011:Sorted Array Merge Tree
852:{\displaystyle \alpha }
1450:Cite journal requires
1329:Knuth, Donald (1973).
962:
895:
853:
610:
301:, let its quotient be
263:-bit fingerprint. The
197:
1402:10.1007/s002360050048
1239:Farach-Colton, Martin
1206:Farach-Colton, Martin
963:
896:
854:
585:
308:and the remainder be
246:Algorithm description
194:
153:is a space-efficient
1480:at Wikimedia Commons
1237:Bender, Michael A.;
1204:Bender, Michael A.;
905:
871:
843:
769:. Slot 5 receives e
694:In state 2 elements
106:Randomized algorithm
1272:2012arXiv1208.0290B
761:and is marked as a
745:In state 3 element
958:
891:
849:
646:, indicating that
625:and its quotient e
611:
233:. In 2011, Bender
198:
80:Random binary tree
1476:Media related to
1256:(11): 1627–1637.
972:Space/performance
835:= 2 slots, and a
803:runs have length
773:and is marked as
686:Insertion example
514:
513:
164:is a member of a
147:
146:
1506:
1475:
1460:
1459:
1453:
1448:
1446:
1438:
1436:
1434:
1429:
1420:
1414:
1413:
1390:Acta Informatica
1385:
1379:
1378:
1376:
1374:
1364:
1355:
1349:
1348:
1342:
1334:
1326:
1320:
1319:
1317:
1301:
1292:
1291:
1265:
1247:
1234:
1228:
1227:
1225:
1223:
1214:
1201:
1178:
1177:
1165:
1159:
1158:
1156:
1155:
1149:
1138:
1125:
1119:
1118:
1086:
967:
965:
964:
959:
957:
956:
941:
940:
939:
938:
929:
900:
898:
897:
892:
887:
858:
856:
855:
850:
785:Cost/performance
374:
139:
132:
125:
52:Count–min sketch
16:
1514:
1513:
1509:
1508:
1507:
1505:
1504:
1503:
1484:
1483:
1478:Quotient filter
1468:
1463:
1449:
1439:
1432:
1430:
1427:
1422:
1421:
1417:
1387:
1386:
1382:
1372:
1370:
1362:
1357:
1356:
1352:
1335:
1328:
1327:
1323:
1303:
1302:
1295:
1245:
1236:
1235:
1231:
1221:
1219:
1212:
1203:
1202:
1181:
1167:
1166:
1162:
1153:
1151:
1147:
1136:
1127:
1126:
1122:
1088:
1087:
1080:
1076:
1054:
982:
974:
945:
930:
914:
903:
902:
869:
868:
863:to total slots
841:
840:
821:
792:
787:
772:
760:
756:
752:
721:
717:
713:
688:
672:is_continuation
656:
645:
639:is_continuation
636:
628:
624:
580:
573:
564:is_continuation
539:
535:
531:
527:
519:
509:
479:
463:
389:
384:
383:is_continuation
379:
358:is_continuation
318:
313:
306:
299:
248:
219:
178:false negatives
151:quotient filter
143:
57:Quotient filter
33:data structures
31:
12:
11:
5:
1512:
1510:
1502:
1501:
1496:
1486:
1485:
1482:
1481:
1467:
1466:External links
1464:
1462:
1461:
1452:|journal=
1415:
1396:(4): 351–385.
1380:
1350:
1321:
1293:
1229:
1179:
1160:
1120:
1101:(9): 828–834.
1077:
1075:
1072:
1071:
1070:
1065:
1060:
1053:
1050:
1000:
999:
996:
981:
978:
973:
970:
955:
952:
948:
944:
937:
933:
928:
924:
921:
917:
913:
910:
890:
886:
882:
879:
876:
848:
820:
817:
791:
790:Cluster length
788:
786:
783:
770:
758:
754:
750:
719:
715:
711:
710:. We assume b
687:
684:
683:
682:
675:
668:
655:
652:
643:
634:
626:
622:
579:
578:Lookup example
576:
571:
537:
533:
529:
525:
518:
515:
512:
511:
506:
503:
500:
496:
495:
492:
489:
486:
482:
481:
476:
473:
470:
466:
465:
460:
457:
454:
450:
449:
446:
443:
440:
436:
435:
432:
429:
426:
422:
421:
418:
415:
412:
408:
407:
404:
401:
398:
394:
393:
390:
387:
385:
382:
380:
377:
369:
368:
365:
362:
359:
356:
353:
329:soft collision
325:hard collision
321:canonical slot
316:
311:
304:
297:
247:
244:
231:model checking
218:
215:
186:false positive
158:data structure
145:
144:
142:
141:
134:
127:
119:
116:
115:
114:
113:
108:
100:
99:
95:
94:
93:
92:
87:
82:
74:
73:
67:
66:
65:
64:
59:
54:
49:
44:
36:
35:
25:
24:
13:
10:
9:
6:
4:
3:
2:
1511:
1500:
1497:
1495:
1492:
1491:
1489:
1479:
1474:
1470:
1469:
1465:
1457:
1444:
1426:
1419:
1416:
1411:
1407:
1403:
1399:
1395:
1391:
1384:
1381:
1368:
1361:
1354:
1351:
1346:
1340:
1332:
1325:
1322:
1316:
1311:
1307:
1300:
1298:
1294:
1289:
1285:
1281:
1277:
1273:
1269:
1264:
1259:
1255:
1251:
1244:
1240:
1233:
1230:
1218:
1211:
1207:
1200:
1198:
1196:
1194:
1192:
1190:
1188:
1186:
1184:
1180:
1175:
1171:
1164:
1161:
1150:on 2012-02-04
1146:
1142:
1135:
1131:
1124:
1121:
1116:
1112:
1108:
1104:
1100:
1096:
1092:
1085:
1083:
1079:
1073:
1069:
1068:Cuckoo filter
1066:
1064:
1061:
1059:
1056:
1055:
1051:
1049:
1045:
1044:fingerprint.
1041:
1039:
1035:
1031:
1026:
1024:
1020:
1017:. Each Wanna-
1016:
1015:Wanna-B-trees
1012:
1008:
1003:
997:
994:
993:
992:
989:
987:
986:Bloom filters
979:
977:
971:
969:
953:
950:
946:
942:
935:
931:
926:
922:
919:
915:
911:
908:
888:
884:
880:
877:
874:
866:
862:
846:
838:
834:
830:
826:
818:
816:
814:
810:
806:
802:
798:
789:
784:
782:
780:
776:
768:
764:
748:
743:
741:
737:
733:
729:
725:
709:
705:
701:
697:
692:
685:
680:
676:
673:
669:
666:
662:
661:
660:
653:
651:
649:
640:
632:
620:
616:
609:
605:
601:
597:
593:
589:
584:
577:
575:
568:
565:
561:
558:
554:
549:
545:
541:
522:
516:
507:
504:
501:
498:
497:
493:
490:
487:
484:
483:
477:
474:
471:
468:
467:
461:
458:
455:
452:
451:
447:
444:
441:
438:
437:
433:
430:
427:
424:
423:
419:
416:
413:
410:
409:
405:
402:
399:
396:
395:
391:
375:
372:
366:
363:
360:
357:
354:
351:
350:
349:
346:
344:
339:
337:
332:
330:
326:
322:
314:
307:
300:
293:
290:For some key
288:
286:
282:
278:
274:
270:
266:
262:
258:
257:hash function
253:
245:
243:
241:
236:
232:
228:
224:
216:
214:
212:
206:
203:
193:
189:
187:
183:
179:
175:
171:
167:
163:
159:
156:
155:probabilistic
152:
140:
135:
133:
128:
126:
121:
120:
118:
117:
112:
109:
107:
104:
103:
102:
101:
96:
91:
88:
86:
83:
81:
78:
77:
76:
75:
72:
68:
63:
60:
58:
55:
53:
50:
48:
45:
43:
40:
39:
38:
37:
34:
30:
29:Probabilistic
26:
22:
18:
17:
1443:cite journal
1431:. Retrieved
1418:
1393:
1389:
1383:
1371:. Retrieved
1366:
1353:
1330:
1324:
1305:
1253:
1249:
1232:
1220:. Retrieved
1216:
1173:
1163:
1152:. Retrieved
1145:the original
1140:
1130:Pagh, Rasmus
1128:Pagh, Anna;
1123:
1098:
1094:
1063:Bloom filter
1046:
1042:
1037:
1033:
1029:
1027:
1022:
1018:
1004:
1001:
990:
983:
975:
864:
860:
836:
832:
828:
824:
822:
812:
808:
804:
800:
796:
793:
778:
774:
766:
763:continuation
762:
746:
744:
739:
735:
731:
727:
724:continuation
723:
707:
703:
699:
695:
693:
689:
678:
671:
664:
657:
647:
638:
630:
618:
614:
612:
607:
603:
599:
595:
591:
587:
566:
563:
559:
556:
552:
550:
546:
542:
523:
520:
370:
347:
342:
340:
335:
333:
328:
324:
320:
309:
302:
295:
291:
289:
280:
276:
272:
268:
264:
260:
259:generates a
249:
239:
234:
226:
221:The compact
220:
207:
199:
181:
173:
150:
148:
71:Random trees
56:
47:Count sketch
42:Bloom filter
980:Application
730:. Element
677:We set the
665:is_occupied
631:is_occupied
557:is_occupied
406:Empty Slot
378:is_occupied
352:is_occupied
283:(coined by
281:quotienting
111:HyperLogLog
1488:Categories
1154:2019-01-22
679:is_shifted
553:is_shifted
494:not used.
434:not used.
388:is_shifted
364:is_shifted
252:hash table
223:hash table
1339:cite book
1263:1208.0290
1115:195908955
951:−
943:≤
923:α
920:−
912:−
875:α
847:α
654:Insertion
62:Skip list
1410:12627452
1288:47180056
1052:See also
811:) where
779:occupied
740:occupied
392:meaning
202:database
21:a series
19:Part of
1494:Hashing
1433:21 July
1373:21 July
1268:Bibcode
1222:21 July
1058:MinHash
775:shifted
767:shifted
736:shifted
728:shifted
619:hash(e)
343:cluster
238:Pandey
217:History
162:element
98:Related
1408:
1286:
1113:
753:< b
714:< c
517:Lookup
240:et al.
235:et al.
227:et al.
1428:(PDF)
1406:S2CID
1363:(PDF)
1284:S2CID
1258:arXiv
1246:(PDF)
1213:(PDF)
1148:(PDF)
1137:(PDF)
1111:S2CID
1074:Notes
807:(log
567:clear
285:Knuth
85:Treap
1456:help
1435:2012
1375:2012
1369:: 15
1345:link
1224:2012
765:and
726:and
718:so c
698:and
674:bit.
606:and
184:, a
182:i.e.
174:i.e.
168:(an
1398:doi
1310:doi
1276:doi
1103:doi
867::
801:all
560:set
336:run
166:set
1490::
1447::
1445:}}
1441:{{
1404:.
1394:33
1392:.
1365:.
1341:}}
1337:{{
1308:.
1296:^
1282:.
1274:.
1266:.
1252:.
1248:.
1215:.
1182:^
1172:.
1139:.
1109:.
1099:33
1097:.
1093:.
1081:^
781:.
602:,
598:,
594:,
590:,
275:-
271:=
213:.
149:A
23:on
1458:)
1454:(
1437:.
1412:.
1400::
1377:.
1347:)
1318:.
1312::
1290:.
1278::
1270::
1260::
1254:5
1226:.
1157:.
1117:.
1105::
1038:B
1034:B
1030:B
1023:B
1019:B
954:r
947:2
936:r
932:2
927:/
916:e
909:1
889:m
885:/
881:n
878:=
865:m
861:n
837:r
833:m
829:q
825:p
813:m
809:m
805:O
797:O
771:R
759:R
755:R
751:R
747:a
732:d
720:R
716:R
712:R
708:b
704:c
700:d
696:c
648:e
644:R
642:e
635:Q
627:Q
623:R
615:e
608:a
604:d
600:c
596:f
592:e
588:b
572:R
570:d
538:Q
534:R
530:Q
526:H
505:1
502:1
499:1
491:0
488:1
485:1
475:1
472:0
469:1
459:0
456:0
453:1
445:1
442:1
439:0
431:0
428:1
425:0
417:1
414:0
411:0
403:0
400:0
397:0
317:Q
312:R
310:d
305:Q
303:d
298:H
296:d
292:d
277:r
273:p
269:q
265:r
261:p
138:e
131:t
124:v
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
