Sampled longest common prefix array

When augmented with the longest common prefix (LCP) array and some other structures, the suffix array can solve many string processing problems in optimal time and space. A compressed representation of the LCP array is also one of the main building blocks in many compressed suffix tree proposals. In this paper, we describe a new compressed LCP representation: the sampled LCP array. We show that when used with a compressed suffix array (CSA), the sampled LCP array often offers better time/space trade-offs than the existing alternatives. We also show how to construct the compressed representations of the LCP array directly from a CSA

Fast in-memory XPath search using compressed indexes

A large fraction of an XML document typically consists of text data. The XPath query language allows text search via the equal, contains, and starts-with predicates. Such predicates can be efficiently implemented using a compressed self-index of the document's text nodes. Most queries, however, contain some parts querying the text of the document, plus some parts querying the tree structure. It is therefore a challenge to choose an appropriate evaluation order for a given query, which optimally leverages the execution speeds of the text and tree indexes. Here the SXSI system is introduced. It stores the tree structure of an XML document using a bit array of opening and closing brackets plus a sequence of labels, and stores the text nodes of the document using a global compressed self-index. On top of these indexes sits an XPath query engine that is based on tree automata. The engine uses fast counting queries of the text index in order to dynamically determine whether to evaluate top-down or bottom-up with respect to the tree structure. The resulting system has several advantages over existing systems: (1) on pure tree queries (without text search) such as the XPathMark queries, the SXSI system performs on par or better than the fastest known systems MonetDB and Qizx, (2) on queries that use text search, SXSI outperforms the existing systems by 1-3 orders of magnitude (depending on the size of the result set), and (3) with respect to memory consumption, SXSI outperforms all other systems for counting-only queries.

Intonation of Finnish Verbs

A production experiment investigated the tonal shape of Finnish finite verbs in transitive sentences without narrow focus. Traditional descriptions of Finnish stating that non- focused finite verbs do not receive accents were only partly supported. Verbs were found to have a consistently smaller pitch range than words in other word classes, but their pitch contours were neither flat nor explainable by pure interpolation.

Acquisition of focus by normal hearing and Cochlear implanted children

Two experiments investigated the perception of compound vs. phrasal stress and narrow focus in normally hearing children and children with Cochlear Implants (CI). Additionally, we investigated whether musical experience would predict children’s performance in these tasks. The results showed no difference between CI and normal-hearing (NH) children in either experiment. However, whereas we found no clear effect of age in the children’s stress detection, there was a clear age related trajectory in the ability to recognise (narrow) focus. Moreover, this trend was similar to what has been found previously for English children. Importantly, prior music experience was significantly linked to CI children’s perception of focus.

Diffraction and Total Cross-Section at the Tevatron and the LHC

At the Tevatron, the total p_bar-p cross-section has been measured by CDF at 546 GeV and 1.8 TeV, and by E710/E811 at 1.8 TeV. The two results at 1.8 TeV disagree by 2.6 standard deviations, introducing big uncertainties into extrapolations to higher energies. At the LHC, the TOTEM collaboration is preparing to resolve the ambiguity by measuring the total p-p cross-section with a precision of about 1 %. Like at the Tevatron experiments, the luminosity-independent method based on the Optical Theorem will be used. The Tevatron experiments have also performed a vast range of studies about soft and hard diffractive events, partly with antiproton tagging by Roman Pots, partly with rapidity gap tagging. At the LHC, the combined CMS/TOTEM experiments will carry out their diffractive programme with an unprecedented rapidity coverage and Roman Pot spectrometers on both sides of the interaction point. The physics menu comprises detailed studies of soft diffractive differential cross-sections, diffractive structure functions, rapidity gap survival and exclusive central production by Double Pomeron Exchange.

Storage and retrieval of individual genomes

A repetitive sequence collection is one where portions of a base sequence of length n are repeated many times with small variations, forming a collection of total length N. Examples of such collections are version control data and genome sequences of individuals, where the differences can be expressed by lists of basic edit operations. Flexible and efficient data analysis on a such typically huge collection is plausible using suffix trees. However, suffix tree occupies O(N log N) bits, which very soon inhibits in-memory analyses. Recent advances in full-text self-indexing reduce the space of suffix tree to O(N log σ) bits, where σ is the alphabet size. In practice, the space reduction is more than 10-fold, for example on suffix tree of Human Genome. However, this reduction factor remains constant when more sequences are added to the collection. We develop a new family of self-indexes suited for the repetitive sequence collection setting. Their expected space requirement depends only on the length n of the base sequence and the number s of variations in its repeated copies. That is, the space reduction factor is no longer constant, but depends on N / n. We believe the structures developed in this work will provide a fundamental basis for storage and retrieval of individual genomes as they become available due to rapid progress in the sequencing technologies.

How Can Sustainable Agricultural Systems Promote Food Security in a Changing Climate?

A theoretical framework of the link between climate change, rural development, sustainable agriculture, poverty, and food security is presented. Some options to respond to climate change are described. Current knowledge and potential effects on agricultural productivity is discussed. Necessary conditions for successful adaptation includes secured property rights to land, institutions that make market access possible and credit possibilities. The options of mitigation and enhanced adaptive capacity and the requirements for their implementation are discussed.

TOTEM Physics

This article discusses the physics programme of the TOTEM experiment at the LHC. A new special beam optics with beta* = 90 m, enabling the measurements of the total cross-section, elastic pp scattering and diffractive phenomena already at early LHC runs, is explained. For this and the various other TOTEM running scenarios, the acceptances of the leading proton detectors and of the forward tracking stations for some physics processes are described.

Elämän jatkumo Leibnizillä

Leeuwenhoekin kokeilut mikroskoopilla 1600-luvun lopulla olivat G. W. Leibnizille suuri innoituksen lähde. Monadologia-teoksessaan Leibniz hehkutti keksinnön merkitystä ja antoi ymmärtää, että sillä löydetyt pikkuruiset eliöt todistivat hänen metafyysisen pluralisminsa oikeaksi. Hänen mukaansa "huomataan, että pienimmässäkin osasessa ainetta on kokonainen elävien olioiden, eläinten, entelekhioiden ja sielujen maailma." Näin Leibnizin ajatus elämän jatkumosta sai uutta pontta. Keksinnön vaikutus näkyy myös Leibnizin teoksessa Uusia esseitä inhimillisestä ymmärryksestä, jossa hän esittelee pienet perseptiot, joita voidaan pitää tietoteoreettisena vastineena pieneliöille. Tarkastelen esitelmässäni Leibnizin reaktioita mikroskooppiin ja sen antamaan uuteen kuvaan elämästä ja keskustelen joistakin Leibnizin filosofian piirteistä, joissa voidaan huomata uuden keksinnön vaikutusta.

Collecting data from distributed FOSS projects

A key trait of Free and Open Source Software (FOSS) development is its distributed nature. Nevertheless, two project-level operations, the fork and the merge of program code, are among the least well understood events in the lifespan of a FOSS project. Some projects have explicitly adopted these operations as the primary means of concurrent development. In this study, we examine the effect of highly distributed software development, is found in the Linux kernel project, on collection and modelling of software development data. We find that distributed development calls for sophisticated temporal modelling techniques where several versions of the source code tree can exist at once. Attention must be turned towards the methods of quality assurance and peer review that projects employ to manage these parallel source trees. Our analysis indicates that two new metrics, fork rate and merge rate, could be useful for determining the role of distributed version control systems in FOSS projects. The study presents a preliminary data set consisting of version control and mailing list data.

Collecting data from distributed FOSS projects

A key trait of Free and Open Source Software (FOSS) development is its distributed nature. Nevertheless, two project-level operations, the fork and the merge of program code, are among the least well understood events in the lifespan of a FOSS project. Some projects have explicitly adopted these operations as the primary means of concurrent development. In this study, we examine the effect of highly distributed software development, is found in the Linux kernel project, on collection and modelling of software development data. We find that distributed development calls for sophisticated temporal modelling techniques where several versions of the source code tree can exist at once. Attention must be turned towards the methods of quality assurance and peer review that projects employ to manage these parallel source trees. Our analysis indicates that two new metrics, fork rate and merge rate, could be useful for determining the role of distributed version control systems in FOSS projects. The study presents a preliminary data set consisting of version control and mailing list data.

An Experimental Study of Home Gateway Characteristics

Many residential and small business users connect to the Internet via home gateways, such as DSL and cable modems. The characteristics of these devices heavily influence the quality and performance of the Internet service that these users receive. Anecdotal evidence suggests that an extremely diverse set of behaviors exists in the deployed base, forcing application developers to design for the lowest common denominator. This paper experimentally analyzes some characteristics of a substantial number of different home gateways: binding timeouts, queuing delays, throughput, protocol support and others.