Triangle Finding: How Graph Theory can Help the Semantic Web Edward Jimenez, Eric L. Goodman Sandia National Laboratories, Albuquerque, NM, USA {esjimen,elgoodm}@sandia.gov Abstract. RDF data can be thought of as a graph where the subject and objects are vertices and the predicates joining them are edge at- tributes. Despite decades of research in graph theory, very little of this work has been applied to RDF data sets and it has been largely ignored by the Semantic Web research community. We present a case study of triangle finding, where existing algorithms from graph theory provide excellent complexity bounds, growing at a significantly slower rate than algorithms used within existing RDF triple stores. In order to scale to large volumes of data, the Semantic Web community should look to the many existing graph algorithms. 1 Introduction The Semantic Web continues to evolve and grow with data sizes becoming in- creasingly large and unwieldy. As such, we need to utilize the most efficient and effective algorithms in order to scale to meet the growing data requirements. We believe that the graph theory body of research has much to offer in terms of formal analysis and understanding of the Semantic Web. Also, graph theory has much to offer in terms of efficient algorithms that can be employed for the Se- mantic Web. In particular we examine triangle finding. For several decades there have been algorithms for finding triangles that have a temporal complexity of O(m3/2 ) where m is the number of edges [5]. As such, we believe it incumbent of any SPARQL engine to use these methods whenever a triangle appears as part of a query. In Section 2 we introduce formally the notion of triangle finding and the as- sociated notation. In Section 3 we discuss the frequency of triangles in SPARQL query benchmarks. In Section 4 we discuss how SPARQL can be used to find all the triangles in a graph. We then outline the particular triangle finding algorithm we employ in Section 5 that is O(m3/2 ). Section 6 compares experimentally the triangle finding method we employ against Jena1 and Sesame2 , two common open-source RDF/SPARQL engines. Section 7 outlines related work. We then conclude in Section 8. 1 jena.apache.org 2 www.openrdf.org 45 2 Edward Jimenez, Eric L. Goodman 2 Formalisms RDF data can be modeled as a graph, G = (V, E) where V is a set of vertices and E is a set of edges connecting the vertices v ∈ V . We use n to refer to the number of vertices, |V |, and m as the number of edges, |E|. For RDF, the subjects and objects are vertices in V . The predicates can be thought of as attributes associated with each edge. We enumerate the vertices so that each has a unique id in [1, n]. Also, we enumerate the edges of G to be in [1, m]. The notation ei refers to the ith edge under the enumeration. Since RDF is described directionally, i.e. there is a subject uni-directionally related to an object, edges in the graph are also directed. We will use source(ei ) to refer to the source or subject of the edge. target(ei ) refers to the target or object of the edge. We call two vertices v1 , v2 ∈ V adjacent if there is an edge e ∈ E where (source(e) = v1 ∧ target(e) = v2 ) ∨ (source(e) = v2 ∧ target(e) = v1). We use δ(vi ) to denote the total degree, both incoming and outgoing, of a vertex. Below we formally define the notion of a triangle. Definition 1. A triangle in a graph G is a set of three edges, ei , ej , ek ∈ E such that the set of vertices v̂ = {v|v = source(ei ) ∨ target(ei ) ∨ v = source(ej ) ∨ v = target(ej ) ∨ v = source(ek ) ∨ v = target(ek )} have the following properties: 1. |v̂| = 3 2. All v ∈ v̂ are adjacent to one another. We also refer to triads, which we define as pair of edges with a common vertex. It is also useful to define the notion of triangle equality. Definition 2. Two triangles are considered equal if their edge sets are the same. While triangle equality may seem obvious, it is important point to consider when generating result sets via SPARQL. Without care, duplicate triangles can be generated that are not prunable with the DISTINCT keyword. Duplicate trian- gles can be produced that differ in the order in which the nodes and edge labels are presented (i.e. to which variables they are bound), and thus DISTINCT will have no effect on these duplicates. More of this will be discussed in Section 4. 3 Applicability to Current Benchmarks An obvious question when optimizing for triangles in SPARQL queries is how often triangles occur in practice. We examine two popular benchmarks, LUBM [11] and SP2Bench [15]. Two out of the 14 queries in LUBM have triangles in them, namely queries 2 and 9. For brevity and to emphasize the triangle portion of the queries, we omit the prefixes and the type constraints on each of the variables. 46 Triangle Finding 3 Query 2 SELECT ?X, ?Y, ?Z WHERE {?X ub:memberOf ?Z . ?Z ub:subOrganizationOf ?Y . ?X ub:undergraduateDegreeFrom ?Y} Query 9 SELECT ?X, ?Y, ?Z WHERE {?X ub:advisor ?Y . ?Y ub:teacherOf ?Z . ?X ub:takesCourse ?Z} These two queries are also some of the more complicated and time inten- sive ones as reported by various vendors and researchers (e.g. AllegroGraph3 OWLIM4 ), pointing to the need for efficient processing. SP2Bench does not have any queries with triangles in them, but there are several queries that with a natual extension of one more constaint form a triangle. For example, Query 4 requests all distinct pairs of article author names for authors that have published in the same journal. A natural extension is to define a constraint between the two authors, either directly, forming a triangle, or to another common vertex. The latter case forms what is called a quadrangle, and the algorithmic approach is similar and has the same complexity as finding triangles [5]. In conclusion, there appears to be a small but significant portion of queries that contain triangle structures within them. 4 Finding Triangles with SPARQL Expressing a SPARQL query to find all triangles in a graph is surprisingly con- voluted. Figure 1 is a query that finds all unique triangles in an RDF graph, but perhaps more importantly it finds the triangles with no duplication, meaning that no two solution triangles in the result set are equal. We will refer to this query as the Triangle-finding SPARQL query. Note that this query only works on data involving only IRIs as the subjects and objects. According to the standard the STR function is not defined for blank nodes and the function also removes typing and language modifiers on literals which may cause the comparison filter to be incorrect. Before we discuss how this query finds the triangles without duplication, we must first discuss two concepts, that of graph isomorphism and graph automor- phism. Two graphs G and H are isomorphic if there is a bijection, f , mapping the vertex sets of G and H such that two vertices vi and vj are adjacent in G if and only if f (vi ) and f (vj ) are also adjacent in H. A graph automorphism is 3 http://www.franz.com/agraph/allegrograph/agraph_bench_lubm.lhtml 4 http://www.ontotext.com/owlim/benchmark-results/lubm 47 4 Edward Jimenez, Eric L. Goodman SELECT ?X ?Y ?Z WHERE { { ?X ?a ?Y . ?Y ?b ?Z . ?Z ?c ?X FILTER (STR(?X) < STR(?Y)) FILTER (STR(?Y) < STR(?Z)) } UNION { ?X ?a ?Y . ?Y ?b ?Z . ?Z ?c ?X FILTER (STR(?Y) > STR(?Z)) FILTER (STR(?Z) > STR(?X)) } UNION { ?X ?a ?Y . ?Y ?b ?Z . ?X ?c ?Z } } Fig. 1. The above query finds all unique triangles and each is represented once in the result set. when there is a isomorphism of a graph G onto itself, and generally we will be concerned with non-identity mappings. The reason this is important can be understood from the query below: SELECT ?X ?Y ?Z WHERE { { ?X ?a ?Y . ?Y ?b ?Z . ?Z ?c ?X } For this query, every triangle found will appear three times. For instance, a triangle with solution �s1 , s2 , s3 � will also appear as �s2 , s3 , s1 � and �s3 , s1 , s2 �. The reason for this is that each of the vertices s1 , s2 , and s3 each bind to each of the three variables ?X, ?Y, and ?Z under different circumstances. All three solutions satisfy the query, but each solution is the same triangle. DISTINCT does not help because the bindings are different for each duplicate solution. The problem arises because the query graph represented above is automorphic. Each non-trivial automorphism is a mapping to translate from one solution to another solution using the same set of edges. Thus we arrive at the convoluted nature of the query in Figure 1. When constructing the SPARQL query, we need to account for all possible triangles 48 Triangle Finding 5 but not generate duplicates. There are eight types of triangles, shown in Figure 2. However, all eight of these types can be collapsed down to the three unioned clauses in Figure 1. We present this formally as a proof. Fig. 2. The eight possible triangle patterns. Theorem 1. The Triangle-finding SPARQL query finds all triangles in the queried graph and each solution is unique. Proof. First consider that triangle type iii is isomorphic to types iv through viii. The below table outlines the functions needed to show the isomorphisms. As they are isomorphic, type iii is sufficient to represent all the other types iv - viii. Also, type iii is not automorphic, and thus will not produce any duplicate triangles. Finally, the solutions resulting from iii are disjoint from i and ii as there is not mapping from iii to either i or ii. Thus we can deal with the solution sets separately. Mapping ?X ?Y ?Z iii to ... iv ?X ?Z ?Y v ?Y ?X ?Z vi ?Z ?Y ?X vii ?Z ?X ?Y vii ?Y ?Z ?X 49 6 Edward Jimenez, Eric L. Goodman Concerning types i and ii, they are isomorphic under the mapping f (?X) = ?Z, f (?Y ) =?Y , and f (?Z) =?X. Thus, we need only include one of the patterns in the query. We arbitrarily select type i. However, type i is automorphic (as is ii ), and we must concoct a way of avoiding duplicate triples with the available SPARQL language features. We solve the issue by enforcing an ordering on the bindings. The first clause of the Triangle-finding SPARQL query enforces that the string representation of the bindings must obey ?X ?Z >?X. It remains to show that these two orderings will find all triangles of type i without duplication. The table below outlines all possible relations between the variables assuming no self loops. ?X ? ?Y ?Y ? ?Z ?Z ? ?X < < < Empty since ?X Fulfilled directly by first clause < > < Use automorphism f (?X) =?Y, f (?Y ) =?Z, f (?Z) =?X. Fulfilled by first clause. < > > Fulfilled directly by second clause. > < < Use automorphism f (?X) =?Z, f (?Y ) =?X, f (?Z) =?Y . Fulfilled by first clause. > < > Use automorphism f (?X?) =?Z, f (?Y ) =?X, f (?Z) =?Y ). Fulfilled by second clause. > > < Use automorphism f (?X) =?Y, f (?Y ) =?Z, f (?Z) =?X. Fulfilled by second clause. > > > Empty since ?X >?Y ∧?Y >?Z =⇒ ?X >?Z, contradicting the third constraint. Two of the possibilities are invalid because the constraints are contradictory. Another two possibilities directly match the first two clauses of the triangle- finding query. The remaining four cases match the two clauses through an au- tomorphism. Thus, we may conclude that the Triangle-finding SPARQL query does in fact find all triangles in the graph with no duplicates. � 5 An O(m3/2 ) Triangle Finding Algorithm There are many triangle finding algorithms that are O(m3/2 ). For the experi- ments we employ an algorithm presented by Cohen [6]. This algorithm has the benefit of already being described in a parallel fashion in terms of mappers and reduces of the MapReduce paradigm [8]. Also, there is a version implemented in the MultiThreaded Graph Library5 (MTGL) [2]. However, a formal complexity analysis was not outlined in [6], so we perform that here. 5 https://software.sandia.gov/trac/mtgl 50 Triangle Finding 7 Cohen’s algorithm operates on what he calls a simplified graph. Namely, a graph in which self-loops are eliminated, directionality is ignored, and there are no duplicate edges. In our later experiments we do not allow self-loops, but we account for directionality and do allow duplicate edges. This is due to the fact that RDF is directional and multiple edges can be defined between vertices with different edge types (predicate types). We do not want to collapse all of these edge types down into one edge. We do not formally account for these different assumptions in our analysis. Theorem 2. Given a simplified graph G, Cohen’s triangle finding algorithm is O(m3/2 ). Proof. We assume the worst case, that G is completely connected. Relating m to n, we have n−1 � (n − 1)(n) m= i= (1) i=1 2 Cohen’s algorithm is composed of two MapReduce phases. The input to the first map is a list of edges. Each edge has been previously been augmented with the degree of each vertex. If one were to include this preprocessing step in the overall complexity, it is O(m) which is also in O(m3/2 ). Map 1 Map each edge to its low-degree vertex. According to our assumptions, δ(vx ) = δ(vy ) ∀x, y ≤ n. Cohen suggests a tie-breaker based on vertex ordering; we’ll use v1 < v2 < · · · < vn . Below is the composition of the bins. Since directionality is ignored, we’ll use a canonical representation of each edge, �vi , vj �, such that i < j. Bin 1 Bin 2 · · · Bin n − 1 �v1 , v2 � �v2 , v3 � · · · �vn − 1, vn � �v1 , v3 � �v2 , v4 � .. .. . . .. . �v2 , vn � �v1 , vn � Thus, for m edges, perform m mappings; hence, O(m). Reduce 1 Emit a record for each pair of edges in a bin (one for every open triad). For the graph G, the first Map phase created n−1 bins, and bin i contains 51 8 Edward Jimenez, Eric L. Goodman n − i edges. Therefore the number of triads created is �� n−2 n−i � n−2 � (n − i)! = (2) i=1 2 i=1 2(n − (i + 2))! n−2 1� = (n − i)(n − (i + 1)) (3) 2 i=1 n−2 1� < (n − 1)(n − (i + 1)) (4) 2 i=1 n−2 n−1 � = (n − (i + 1)) (5) 2 i=1 n−2 n−1 � = i (6) 2 i=1 n − 1 (n − 1)(n − 2) = (7) √2 2 2(n − 1)3 < (8) 4 � �3/2 (n − 1)2 = (9) 2 � �3/2 n(n − 1) < (10) 2 = m3/2 = O(m3/2 ) (11) Hence, the first MapReduce task has complexity O(m3/2 ). For the second MapReduce phase the input is the emitted records of the first MapReduce phase (O(m3/2 )) as well as the augmented edge list that was used as the input for the first MapReduce phase (O(m)). For the second MapReduce phase, let p be the size of the combined input, note: O(p) = O(m) + O(m3/2 ) = O(m3/2 ). Map 2 Combine degree-augmented file and output from Reduce 1. For the aug- mented edge list we have the following mapping to remove the vertex valences: key1 = [e1 , δ(vx ), δ(vy )] keye1 = [e1 ] key2 = [e2 , δ(vw ), δ(vz )] keye2 = [e2 ] .. ⇒ .. , . . keyn = [en , δ(vu ), δ(vt )] keyen = [en ] and for the records emitted by Reduce 2, we have the identity operation. There- fore, this task is O(p). 52 Triangle Finding 9 Reduce 2 Each bin corresponds with a vertex pair. A bin will contain at most one edge record and any number of triad records. � � With our assumptions of a completely connected graph, bin i contains n−i triad records and one edge �n−i� 2 record, and the reducer will emit 2 triangles. From our previous analysis, this is O(m3/2 ) and therefore the overall complexity is O(m3/2 ). � 6 Experiments We experimentally compare open source RDF/SPARQL engines, Jena, version 2.7.2, and Sesame, version 2.6.8, with MTGL’s implementation of Cohen’s al- gorithm. For both Jena and Sesame we use the in-memory backend version of each. We did need to make some modifications to the MTGL version in order to allow for directionality and duplicate edges. Namely, we created a multimap that gives a the list of edges connecting any two vertices. This allowed us to create multiple triangles from single instances of a triad in the last reduce phase. We used a workstation with 8 GB of memory and a 2.2 GHz Intel Core i7 processor. Detailed times for our experiments can be found in the Appendix. For our experiments we create R-MAT [4] graphs to simulate real-world graph properties such as power-law distributions on degree, small-world graphs, and small diameter. We varied the size of the graph from between n = 25 to n = 219 . Also, we tried three different edge factors (average degree per vertex), namely 16, 32, and 64. R-MAT has four other parameters, a, b, c, and d. These four parameters are probabilities used recursively to determine where edges exist within the adjacency matrix. We set these to the values of the Graph5006 search benchmark: a = 0.57, b = 0.19, c = 0.19, and d = 0.05. To enable the SPARQL engines the ability to process the data, we created IRI’s of the form where i is the vertex id given by the R-MAT generator. Also we made all edges of the same type. Figures 3(a), 3(b), and 3(c) show the individual performance of each of the three platforms as a function of the number of edges. All of the plots have a log- log scale. Figure 3(d) shows the three platforms side by side. For this Figure, we exclude graphs below 8192 edges to give a better idea of the scaling behavior for larger graphs. Both Jena and Sesame exhibit a fair amount of constant overhead per query that dominates the times in the smaller graphs. When excluding this data, the fit of trendlines using power regression is quite good, with R2 all exceeding 0.98. As can be seen from Figure 3(d), Jena has a complexity of around O(m1.83 ), Sesame has O(m1.58 ), and MTGL’s version of Cohen’s algorithm is around O(m1.39 ). The best possible for this data would be around O(m1.12 ), which is rate of growth of triangles for the data as determined experimentally and shown in Figure 3(e). It is clear that both Jena and Sesame are not employing a triangle finding algorithm as their rate of growth is significantly larger than O(m1.5 ). While the differences in powers may seem small between the three, consider that ex- trapolating out to a billion edges, the difference in times between an O(m1.39 ) 6 www.graph500.org 53 10 Edward Jimenez, Eric L. Goodman (a) Jena (b) Sesame (c) MTGL (d) All (e) Triangle Growth Fig. 3. algorithm and one with O(m1.58 ) with the same constant is about a 50x differ- ence. And the difference between O(m1.39 ) and O(m1.83 ) is around 9000x. While not the focus of this paper, it is interesting to note that the MTGL version com- puted the triangles in about two-orders of magnitude less time than either Jena or Sesame. 54 Triangle Finding 11 7 Related Work There is much work within the graph theory community where there is a straight- forward application to the Semantic Web. For the most part, interfacing with the Semantic Web takes place through SPARQL. This largely confines interac- tions to subgraph matching tasks. Under this limitation, we can find work on clique-finding [5,10], or generalizations of cliques such as trusses [6]. An excellent overview of research in subgraph pattern matching over a thirty year timespan can be found in Conte et al. [7]. There are also algorithms outside of subgraph matching that can be of help in analyzing the Semantic Web. Probably one of the most fundamental algo- rithms is breadth-first search. In recent years, the Graph500 list has signifi- cantly increased the competitiveness and visibility of the task, and scalability and performance have increased concomitantly with the greater attention. Other algorithms include single source shortest path [13], betweeness centrality [1], con- nected components [12], and many others. Related to all of these efforts is the task of graph partitioning. Graphs have historically been difficult to partition in a distributed memory setting, where the interconnectedness of the graph make it difficult to divide the data in such a way to minimize communication overhead. Notable efforts include Buluç and Madduri [3] and Devine et al. [9]. Programming models have also been created to aid development of graph- centric algorithms. Notable among them are Google’s Pregel [14] and Signal/Collect by Stutz et al. [16]. These may prove to be valuable paradigms for implementing efficient graph-oriented code that can scale on large distributed systems. 8 Conclusions In order for Semantic Web applications to scale, the community needs to adopt efficient algorithms to use as the computational kernels underlying analytics. In this paper we’ve demonstrated how long existing triangle finding algorithms can be employed to speed up SPARQL queries. We believe there are other algorithms and lessons from graph theory that can utilized to speed up Semantic Web applications and also open up other avenues for analysis. References 1. D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating between- ness centrality. In Proceedings of the 5th international conference on Algorithms and models for the web-graph, WAW’07, pages 124–137, Berlin, Heidelberg, 2007. Springer-Verlag. 2. J. W. Berry, B. Hendrickson, S. Kahan, and P. Konecny. Software and algorithms for graph queries on multithreaded architectures. Parallel and Distributed Process- ing Symposium, International, 0:495, 2007. 55 12 Edward Jimenez, Eric L. Goodman 3. A. Buluç and K. Madduri. Graph partitioning for scalable distributed graph com- putations. In Proc. 10th DIMACS Implementation Challenge Workshop – Graph Partitioning and Graph Clustering, Feb. 2012. 4. D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-mat: A recursive model for graph mining. In M. W. Berry, U. Dayal, C. Kamath, and D. B. Skillicorn, editors, SDM. SIAM, 2004. 5. N. Chiba and T. Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing, 14(1):210–223, 1985. 6. J. Cohen. Graph twiddling in a mapreduce world. Computing in Science Engi- neering, 11(4):29 –41, july-aug. 2009. 7. D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. IJPRAI, pages 265–298, 2004. 8. J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. Commun. ACM, 51:107–113, January 2008. 9. K. D. Devine, E. G. Boman, R. T. Heaphy, R. H. Bisseling, and U. V. Catalyurek. Parallel hypergraph partitioning for scientific computing. In Proceedings of the 20th international conference on Parallel and distributed processing, IPDPS’06, pages 124–124, Washington, DC, USA, 2006. IEEE Computer Society. 10. F. Eisenbrand and F. Grandoni. On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci., 326(1-3):57–67, Oct. 2004. 11. Y. Guo, Z. Pan, and J. Heflin. Lubm: A benchmark for owl knowledge base systems. J. Web Sem., 3(2-3):158–182, 2005. 12. A. Krishnamurthy, S. S. Lumetta, D. E. Culler, and K. Yelick. Connected com- ponents on distributed memory machines. In Parallel Algorithms: 3rd DIMACS Implementation Challenge October 17-19, 1994, volume 30 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 1–21. American Mathematical Society, 1994. 13. K. Madduri, D. Bader, J. Berry, and J. Crobak. An experimental study of a parallel shortest path algorithm for solving large-scale graph instances. In ALENEX, 2007. 14. G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, SIGMOD ’10, pages 135–146, New York, NY, USA, 2010. ACM. 15. M. Schmidt, T. Hornung, G. Lausen, and C. Pinkel. Sp2bench: A sparql perfor- mance benchmark. CoRR, abs/0806.4627, 2008. 16. P. Stutz, A. Bernstein, and W. Cohen. Signal/collect: graph algorithms for the (semantic) web. In Proceedings of the 9th international semantic web conference on The semantic web - Volume Part I, ISWC’10, pages 764–780, Berlin, Heidelberg, 2010. Springer-Verlag. A Experimental Data Below is the data we collected running the triangle query on Jena, Sesame, and MTGL. We divide the data into three tables, one for each edge factor. Times are in seconds. 56 Triangle Finding 13 A.1 Edge Factor = 16 |V | |E| Num Triangles Jena Sesame MTGL 25 512 7,645 0.66 0.39 0.0011 26 1,024 16,159 0.96 0.44 0.0024 27 2,048 33,263 1.23 0.57 0.0081 28 4,096 72,357 1.96 0.88 0.0132 29 8,192 156,716 2.96 1.78 0.0365 210 16,384 333,174 7.79 3.86 0.0721 211 32,768 739,951 26.38 10.67 0.1798 212 65,536 1,648,301 89.72 31.12 0.4696 213 131,072 3,450,520 291.65 92.78 1.1767 214 262,144 7,573,624 1263.91 317.21 3.3691 215 524,288 16,864,063 5550.93 1022.38 8.7734 216 1,048,576 35,286,039 3062.77 21.6454 217 2,097,152 74,837,468 57.1703 218 4,194,304 168,767,188 153.9390 219 8,388,608 357,383,850 409.6070 A.2 Edge Factor = 32 |V | |E| Num Triangles Jena Sesame MTGL 25 1,024 37,561 1.151 0.496 0.0048 26 2,048 66,132 1.288 0.643 0.0115 27 4,096 137,725 1.845 1.083 0.0225 28 8,192 292,062 3.878 2.299 0.0514 29 16,384 624,619 10.916 5.064 0.1197 210 32,768 1,388,020 35.841 13.330 0.2796 211 65,536 3,033,157 122.567 42.596 0.7512 212 131,072 6,537,422 448.030 135.857 1.8940 213 262,144 14,955,653 1829.724 459.467 5.4287 214 524,288 32,521,939 8067.696 1486.286 14.8550 215 1,048,576 73,026,129 4916.445 38.6545 216 2,097,152 155,196,692 100.6970 217 4,194,304 342,379,527 275.3078 218 8,388,608 746,302,590 720.8690 57 14 Edward Jimenez, Eric L. Goodman A.3 Edge Factor = 64 |V | |E| Num Triangles Jena Sesame MTGL 26 4096 303,016 2.510 1.464 0.0432 27 8,192 554,405 5.053 2.937 0.0843 28 16,384 1,151,110 14.524 7.235 0.1872 29 32,768 2,481,009 48.234 19.189 0.4539 210 65,536 5,452,648 168.198 91.224 1.1790 211 131,072 12,051,583 612.075 189.095 3.0500 212 262,144 26,614,815 2674.014 657.880 8.4796 213 524,288 57,835,285 9738.723 2103.770 22.5987 214 1,048,576 131,190,442 63.0300 215 2,097,152 290,104,980 166.7070 216 4,194,304 634,855,745 451.3670 217 8,388,608 1,420,402,577 1250.280 58