dataesr/scientific-paragraphs-categorization huggingface dataset:
Probabilistic chunking Given the self-adjusting runtime library, we can write various data structures that can respond to data changes efficiently. But the dependency metadata the runtime maintains can be very large, preventing scaling to large datasets. In this section, we show how to reduce the size of dependency metadata by controlling the granularity of dependency tracking, crucially in a way that does not affect performance disproportionately. The basic idea is to track dependencies at the granularity of a block of items. This idea is straightforward to implement: simply place blocks of data into modifiables (e. g. , store an array of integers as a block instead of just one number). As such, if any data in a block changes, the computation that depends on that block must be rerun. While this saves space, the key question for performance is therefore: how to chunk data into blocks without disproportionately affecting the update time? For fast updates, our chunking strategy must ensure that a small change to the input remains small and local, without affecting many other blocks.
Thus, an update costs expected Θ(B log n) time. To conclude, by chunking a dataset into size-B blocks, probabilistic chunking reduces the dependency metadata by a factor of B in expectation. Furthermore, by keeping changes small and local, probabilistic chunking ensures maximum reuse of existing computations. Change propagation works analogously to the non-block version, except that if a block changes, work on the whole block must be redone, thus often increasing the update time by B folds. Working with block sequences. The block sequence abstraction is similar to the list abstraction in Standard ML, except that each unit of a sequence is a block, which is internally represented as a boxed (ordinary) list. There is a function mkCons that takes an (ordinary) list of elements and inserts them into a block sequence, ensuring that they are chunked according to PCS.
Chapter 8 Empirical Evaluation This chapter is based on work on the empirical evaluation of implicit self-adjusting computation  (Chen et al. 2012) , and a language extension for computing with large and dynamic data in self-adjusting computation  (Chen et al. 2014a). We performed extensive empirical evaluation on a range of benchmarks, including standard benchmarks from prior work, as well as new, more involved benchmarks on social network graphs. All our experiments were performed on a 2GHz Intel Xeon with 1 TB memory running Linux. Our implementation is single-threaded and therefore uses only one core. The code was compiled with MLton version 20100608 with flags to measure maximum live memory usage.
Benchmarks We implemented a number of benchmarks in our language, including standard selfadjusting-computation benchmarks from previous work  (Ley-Wild et al. 2008; Acar et al. 2009a) , additional benchmarks on vectors and matrices, and a ray tracer. Our compiler makes it relatively straightforward to derive self-adjusting versions of programs. Specifically, we simply wrote the standard code for our benchmarks and changed the type declarations to allow for changes to the input data. For the ray tracer, we used an unmodified SML implementation of a sphere ray tracer  (King 1998). Our benchmarks include some standard list primitives (map, filter, split), quicksort, and mergesort (qsort, msort). These include simple iteration (map, filter, split), accumulator passing (qsort), and divide-and-conquer algorithms (qsort, msort).
Correctness. To verify that our compiler generates self-adjusting executables that can respond to changes to their data correctly, we used three approaches: type checking, manual inspection, and extensive testing. Our compiler generates self-adjusting code to a text file, which we then type-check and compile along with a stand-alone self-adjustingcomputation library, which we have separately implemented. SML's type system verifies that the translated code satisfies certain invariants. Since we can inspect the translated code manually, we can also spot-check the code, which is not a foolproof method but increases confidence. We have used this facility extensively when implementing the compiler. Additionally, we have developed a testing framework, which makes a massive number of randomly generated changes to the input data, and checks that the executable responds correctly to each such change by comparing its output with that of a "verifier" (reference implementation) that computes the given output using a straightforward, non-incremental algorithm.
This is consistent with the O(log n) bound that we can show analytically. The plot on the right in Figure  8. 1 shows the speedups for different input sizes (x axis): the time for a run of the conventional algorithm divided by the time for change propagation. The plots show that speedups increase linearly with the input size, consistent with the theoretical bound. To obtain this asymptotic improvement, we only insert one keyword in the code and use our compiler to generate the self-adjusting version.
For example, AFL provides an unsafe interface that the quicksort benchmark uses to speed up the partition, creating half as many modifiables as with the standard interface. Our compiler does not directly support these low-level primitives, so we cannot perform the same optimizations. In AFL, programmers need to restructure programs in monadic style, explicitly constructing the dependency graph. This process is similar to doing type inference and translation by hand. Our approach makes self-adjusting programs much easier to write, yet their performance is competitive with carefully-engineered self-adjusting programs. Compared to CPS, our approach is approximately twice as fast, even though the CPS approach requires widespread changes to the program code and ours does not. The primary reason for the performance gap is likely that the CPS-based transformation relies on coarse approximations of true dependencies (based on continuations); our compiler identifies dependencies more precisely by using a type-directed translation.
Additionally, we compared our ray tracer with one based on CPS, where our approach ("Type-Dir. ") is approximately twice as fast as CPS (Table  8. 3). Our approach often uses slightly more space than the CPS based approach, probably because of redundancies in the automatically generated code that can be eliminated manually in the CPS approach. Compared to CEAL  (Hammer et al. 2011 ), our approach is usually faster but occasionally slightly slower. We find this very interesting because the CEAL benchmarks use hand-written, potentially unsound optimizations, such as selective destination-passing and sharing of trace nodes  (Hammer et al. 2011, Sections 7. 2 and 8. 1) , that can result in incorrectly updated output. We also compared our approach to sound versions of CEAL benchmarks, which were a factor of two slower than the unsound versions.
We use up to five times as much space; given that our approach uses space consistent with the other ML based approach ("CPS"), this is probably because of differences between ML, a functional, garbage-collected language, and C. When compared to sound versions of the CEAL benchmarks, which is arguably the more fair comparison, CEAL's space advantage decreases by a factor of two. To summarize, even though our approach accepts conventional code with only a few type annotations, the generated programs perform better than most hand-written code in two programming languages, and are competitive with hand-written code in AFL. Memory usage is comparable to other ML-based approaches.
For the graphs used, this block size is quite natural, as it corresponds roughly to the average degree of a node (the degree ranges between 20 and 200 depending on the graph). For each benchmark, we implemented a batch version-an optimized implementation that operates on unchanging inputs-and a self-adjusting version by using techniques proposed in this paper. We compare these versions by considering a mix of synthetic and real-world data, and by considering different forms of changes ranging from small unit changes (e. g. , insertion/deletion of one item) to aggregate changes consisting of many unit changes (e. g. , insertion/deletion of 1000 items). We describe specific datasets employed and changes performed in the description of each experiment.
Word count A standard microbenchmark for big-data applications is word count, which maintains the frequency of each word in a document. Using our MapReduce library (run with block size 1, 000), we implemented a batch version and a self-adjusting version of this benchmark, which can update the frequencies as the document changes over time. We use this benchmark to illustrate, in isolation, the impact of our precise dependency tracking mechanism. To this end, we implemented two versions of word count: one using prior art  (Chen et al. 2012 ) (which contains redundant dependencies) and the other using the techniques presented in this paper. We use a publicly available Wikipedia dataset  1  and simulate evolution of the document by dividing it into blocks and incrementally adding these blocks to the existing text; the whole text has about 120, 000 words.
Incremental PageRank Another important big data benchmark is the PageRank algorithm, which computes the page rank of a vertex (site) in a graph (network). This algorithm can be implemented in several ways. For example, a domain specific language such as MapReduce can be (and often is) used even though it is known that for this algorithm, the shuffle step required by MapReduce is not needed. We implemented the PageRank algorithm in two ways: once using our MapReduce library and once using a direct implementation, which takes advantage of the expressive power of our framework. Both implementations use the same block size of 100 for the underlying block-list data type. The second implementation is an iterative algorithm, which performs sparse matrix-vector multiplication at each step, until convergence.
Since the average degree per vertex is approximately 100, each aggregate change affects approximately 10 vertices, which can then propagate to other vertices. (Since the vertices are ordered arbitrarily, this aggregate change can be viewed as inserting/deleting 10 arbitrarily chosen vertices). Our PageRank implementation delivers significant speedups at the cost of approximately 10x more memory with different graphs including the datasets Orkut 3  , LiveJournal  4  and Twitter graph  5. For example on the Twitter datasets (labeled Twitter-1) with 30M vertices and 700M edges, our PageRank implementation reaches an average speedup of more than 500x compared to the batch version, at the cost of 10x more memory. Detailed measurements for the first 100 groups, as shown in Figure  8. 7, show that for most trials, speedups usually approximate 4 orders of magnitude.
Dynamic algorithms and data structures Research in the algorithms community focuses primarily on devising dynamic algorithms or dynamic data structures for individual problems. There have been hundreds of papers with several excellent surveys reviewing the work (e. g. ,  (Ramalingam and Reps 1993; Demetrescu et al. 2005). Dynamic algorithms enable computing a desired property while allowing modifications to the input (e. g. , inserting/deleting elements). These algorithms are often carefully designed to exploit problem-specific structures and are therefore highly efficient. But they can be quite complex and difficult to design, analyze, and implement even for problems that are simple in the batch model where no changes to data are allowed. While dynamic algorithms can, in principle, be used with large datasets, space consumption is a major problem  (Demetrescu et al.
DeltaML. In contrast to  Acar et al. (2006c) , who use a library of modal self-adjusting primitives,  Ley-Wild et al. (2008)  give a more programmer-friendly approach where a compiler does the work to translate certain self-adjusting parts of a lightly annotated SML program into a self-adjusting program in continuation-passing style (CPS). This approach dramatically simplifies writing self-adjusting code by enabling the compiler to identify dependencies between code and data (Ley-Wild 2010). Hence, a programmer can more directly see the conventional semantics of the program, without having to be explicit about the higher-order plumbing required in the library-based approach. Though much easier to use than earlier approaches, the programmer must still be explicit about what is incrementally modifiable.
In a follow-up work,  Ley-Wild et al. (2009)  gave a costsemantics for this new source language and proved that the cost semantics predicts the asymptotic efficiency of dynamic updates. Ley-Wild et al. (2012)  extends self-adjusting computation to non-monotonic reuses of subcomputations, and provided a new change propagation algorithm that realizes the semantics of trace reordering, which incurs a logarithmic overhead. CEAL. Hammer et al. (2009)  extends self-adjusting computation to work in low-level languages such as C, where higher-order functions and garbage collection are not avail-able. Hammer et al. (2009)  consider a low-level, self-adjusting language and design a normalization algorithm that transforms the code into closures in C to simulate the use of higher-order functions in functional languages.
Hammer and Acar (2008)  develop a technique that integrates garbage collection with change propagation, making it possible to find and reclaim memory that becomes inaccessible during propagation. An interesting property of this garbage collection algorithm is that it does not have to trace memory to identify inaccessible blocks, but instead takes advantage of the invariants of self-adjusting computation and change propagation to discover them directly. Hammer et al. (2011)  implemented these techniques in CEAL, a language that extends that C language for self-adjusting computation, and formalized the semantics of CEAL  (Hammer 2012). Adapton. Hammer et al. (2014)  developed Adapton, a technique for demand-driven self-adjusting computation in OCaml, where updates may be delayed until they are demanded.
Parallelism. Another line of research realized an interesting duality between incremental and parallel computation-both benefit from identifying independent computationsand proposed techniques for parallel self-adjusting computation. Some work considered techniques for performing efficient parallel updates in the context of a lambda calculus extended with fork-join style parallelism  (Hammer et al. 2007) , as well as POSIX thread-based parallel incremental computation  (Bhatotia et al. 2015). Follow-up work considered the technique in the context of a more sophisticated problem showing both theoretical and empirical results of its effectiveness  (Acar et al. 2011). Burckhardt et al. (2011)  consider a more powerful language based on concurrent-revisions, provide techniques for parallel change propagation for programs written in this language, and perform an experimental evaluation.
Systems There are several systems for big data computations such as MapReduce  (Dean and Ghemawat 2008) , Dryad  (Isard et al. 2007) , Pregel  (Malewicz et al. 2010) , GraphLab  (Low et al. 2012) , and Dremel  (Melnik et al. 2011). While these systems allow for computing with large datasets, they are primarily aimed at supporting the batch model of computation, where data does not change, and consider domain-specific languages such as flat data-parallel algorithms and certain graph algorithms. Bhatotia et al. applies the principles of self-adjusting computation to the big data setting but only in the context of domain-specific languages, including incremental MapReduce programs  (Bhatotia et al. 2011a,b) , incremental sliding windows analytics  (Bhatotia et al. 2014 ) and POSIX thread-based parallel incremental computation  (Bhatotia et al.
2015). Data flow systems like MapReduce and Dryad have been extended with support for incremental computation. MapReduce Online  (Condie et al. 2010 ) can react efficiently to additional input records. Nectar  (Gunda et al. 2010 ) caches the intermediate results of DryadLINQ programs and generates programs that can re-use results from this cache. Naiad  (Murray et al. 2013 ) enables incremental computation on dynamic datasets in programs written with a specific set of data-flow primitives. In Naiad, dynamic updates cannot alter the dependency structure of the computation. Naiad is thus closely related to earlier work on incremental computation with static dependency graphs  (Demers et al. 1981; Yellin and Strom 1991). Percolator  (Peng and Dabek 2010 ) is Google's proprietary system that enables a more general programming model but requires programming in an event-based model with call-backs (notifications), a very low level of abstraction.
GREEDY HEURISTICS In this section, we describe several greedy heuristic algorithms to solve the Bus Evacuation Problem. These heuristics aim to compute a solution in a very fast way. We outline the need for such heuristic procedures to solve real-size instances which are very large. Figure  2  presents the general algorithm of the proposed greedy heuristic, which takes upon entry a sequencing rule R. Let oprlist be the set of the operations that will be assigned on machines, sortlist(i,j) be the set of sorted operations according to the rule R at a given time t, and C m max be the makespan of a machine m. The greedy heuristic's solution is stored in schedulelist. Each operation added in schedulelist will be deleted from oprlist and sortlist(i,j). The function event, presented in the pseudo code of the greedy algorithm (Figure  2 ), checks if there is an event requiring to recalculate the priority list sortlist.
COMPUTATIONAL EXPERIMENTS In this section, we focus on the experimental evaluations of the (IP) solution, and the heuristic algorithms. We first describe how the experimentation have been setup. Environment. All experiments were run on a computer with a 8-core Intel processor, running at 2. 60 GHz with 20MB cache, 8 GB RAM and Windows 7. We wrote our code in C++ , and used the commercial IP solver CPLEX v. 12. 2. CPLEX was pinned to one core for the solution of the time-indexed formulation. Dataset. This work is part research project, called DSS-Evac-Logistic, partially granted by the french research agency ANR. In this project, we consider the real-world instance of Nice (France), as a case study. So, the data sets are randomly generated in such a way that we always have a feasible and realistic instances for Nice city.
5 m, and the layer packing ratio β v = 0. 106 %. These four parameters are perturbed around these nominal conditions. Note that the moisture at extinction M v, ext = 30 %, the fuel particle mass density ρ p = 512. 6 kg m -3 , the effective fuel mineral content s e = 1 % (s t = 5. 55 %), and the heat of combustion h c = 1. 861×10 7 J kg -1 remain constant and correspond to the standard values of the Rothermel's fuel database  (Rothermel, 1972). Figure  2  compares the variability in the ROS when uncertainties are assumed in four parameters, u * w , M v , v and β v. It is found that the ROS values are the most sensitive to  u * w. As for biomass fuel properties, they feature a wide scatter for M v and v , while is less sensitive to β v , indicating that a lack of information in u * w , M v and v results in a significant uncertainty range in the ROS model predictions.
Acknowledgements. The financial support provided by the  Agence Nationale de la Recherche  under the  IDEA 5 project  grant  ANR-09- COSI-006  ( 2010COSI-006 ( -2013 )), by the  LEFE-MANU  grant ( INSU-CNRS program ,  2011-2013 ) and by the  2012 CTR Summer Program 6 (Uncertainty Quantification group ) is greatly appreciated. The authors acknowledge  Ronan Paugam  and  Martin Wooster  ( King's College London ) for sharing the experimental data,  Florent Duchaine  and  Thierry Morel  ( CERFACS ) for support on  Open-PALM ,  Albert Simeoni  ( University of Edinburgh ) for clarifications on Rothermel's model as well as  Gianluca Iaccarino  and  Paul Constantine  ( CTR ) for helpful discussions on uncertainty quantification. They also acknowledge  Marc Bocquet  (CEREA),  Eric Blayo (INRIA) , and  Serge Gratton  ( CERFACS ) for helpful discussions on the properties of the ensemble Kalman filter for parameter estimation and dual parameter-state estimation.
It is worth noting that after some manipulations and rearrangements, the above equations (Eqns (  5 ) and (  6 )) can be written in the following matrix form: d T t p t C T p T p F F a C C C h mo ∂ ∂ ∂ ∂       =∇ ∇             + ⋅∇       +    β     (7) where damping (d a ), diffusion (C), and convection (b) matrices are respectively defined by: d C a T =       0 0 Ω (8) C C C C C L p L p R T p V P sat V P s at l V P s a =       = + ′ - ( ) - ′ 11 12 21 22 λ δ φ δφ ρ δ φ t t l P s at l V K p R T + ( )       δ φ ρ (9) p' sat = ∂p sat /∂T being the derivative of saturation vapour pressure. As for the matrix b, it can be expressed in the following form: β ρ ρ φ ρ = ⋅       = ⋅ - + ∂ ∂ ( )     - ( )  v D D D D v c L T L R T a P a V V V l V 11 12 21 22 ,     ∂ ∂ ( ) ∂ ∂ - ( )     ∂ ∂ ( )         ρ φ ρ φρ ρ φ V V l V V T R T (10) To go further, the current model consists of converting, via MatLab, measurable physical properties of the material such as.
Boundary conditions The applied boundary conditions corresponding to the problem under study are fixed temperature and humidity (Dirichlet boundary conditions) : -A data file supplies hourly values for heat and moisture for a period of more than one year. Intermediate values of time are obtained by interpolation. -No difference in pressure is considered. Numerical modelling of hygrothermal response in building envelopes Note that these conditions allow for a very good case for checking the heat and moisture transfer model. It has already been mentioned that the numerical simulation was performed using the COMSOL Multiphysics software (CMS)  [31] , and the required results are: -Capillary pressure p c , in space and time for the load bearing layer A, and insulation B. -Temperature T(x,t). -Total moisture weight M in each layer.
Conclusion A combined HAM transport model for consolidated porous buildings materials is presented. The model considers the capillary pressure and temperature gradients as driving potentials of the coupled heat and moisture transfer through porous materials of a building envelope. This model is successfully benchmarked against two test cases. The governing partial-differential equations of three transport phenomena are coupled and solved simultaneously for a given temperature and capillary pressure, the latter being considered as the relevant variable. The COMSOL solver is the code chosen to solve governing equations for HM transport. A good agreement with the considered benchmarks evidences the potential of the present model, and suggests that its development and implementation are promising, and thus, that it can be further coupled with an indoor model to create a whole building hygrothermal model, taking into account the multi-dimensional heat, air, and moisture transfer.
We have developed the new publicly available runtime library ASPIC 1 to implement this last approach. The ASPIC code provides all routines needed to quickly derive reheating consistent observable predictions within this class of scenarios. ASPIC has been designed as an evolutive code which presently supports 74 different models, a number that may be compared with three or four representing the present state of the art. In this paper, for each of the ASPIC models, we present and collect new results in a systematic manner, thereby constituting the first Encyclopaedia Inflationaris. Finally, we discuss how this procedure and ASPIC could be used to determine the best model of inflation by means of Bayesian inference.