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.

Bootstrap and Fast Double Bootstrap Tests of Cointegration Rank with Financial Time Series

The likelihood ratio test of cointegration rank is the most widely used test for cointegration. Many studies have shown that its finite sample distribution is not well approximated by the limiting distribution. The article introduces and evaluates by Monte Carlo simulation experiments bootstrap and fast double bootstrap (FDB) algorithms for the likelihood ratio test. It finds that the performance of the bootstrap test is very good. The more sophisticated FDB produces a further improvement in cases where the performance of the asymptotic test is very unsatisfactory and the ordinary bootstrap does not work as well as it might. Furthermore, the Monte Carlo simulations provide a number of guidelines on when the bootstrap and FDB tests can be expected to work well. Finally, the tests are applied to US interest rates and international stock prices series. It is found that the asymptotic test tends to overestimate the cointegration rank, while the bootstrap and FDB tests choose the correct cointegration rank.

Fast- and drift-ice communities in the Bothnian Bay and the impact of UVA radiation on the Baltic Sea ice ecology

The aim of this thesis was to study ecology of Baltic Sea ice from two perspectives. In the first two studies, sea-ice ecology from riverine-influenced fast ice to drift ice in the Bothnian Bay was investigated, whereas the last two studies focus on the sensitivity of sea-ice bacteria and algae to UVA examined in situ. The seasonal sea ice cover is one of the main characteristics of the Baltic Sea, and despite the brackish parental water, the ice structure is similar to polar ice with saline brine inclusions, the sea ice habitat. The decreasing seawater salinity from the northern Baltic Sea to the Bothnian Bay translates to decreasing brine volumes along the gradient, governing the size and community structure of the food webs in ice. However, the drift and fast ice in the Bothnian Bay may differ greatly in this sense, as drift ice may have been formed at more southern locations. Rafting and the formation of snow ice are common processes in the ice field of the Bothnian Bay. As evidenced in this thesis, rafting altered the vertical distribution of organisms and snow-ice formation provided habitable space in the better-illuminated, nitrogen-rich surface layer. The divergence between fast and drift ice became apparent at the more advanced stages, and chlorophyte biomass decreased from fast to drift ice, while the opposite held true for protozoan and metazoan biomass. The brine volumes affected the communities somewhat, and a higher percentage of flagellate species was generally linked to lower brine volumes, whereas chain-forming diatoms were mostly concentrated in layers with larger brine volumes. These results add to knowledge of the ecological significance of the ice cover lasting up to 7 months per year in this area. Sea-ice food webs are generally light-limited, but while increasing light irradiances typically enhance the primary production and further, the secondary production in sea ice, any increase in solar radiation also includes an increase in harmful UVA radiation. The Baltic Sea ice microbial communities were clearly sensitive to UVA and the responses were strongly linked to the earlier light history, as well as to the solar irradiances they were exposed to. The increased biomass of chlorophytes and pennate diatoms, when UVA was excluded, indicates that their normally minor contribution to the biomass in the upper layers of sea ice might be partly dictated by UVA. The effects of UVA on bacterial production in Baltic Sea ice mostly followed the responses in algal growth, but occasionally the exposure to UVA even enhanced the bacterial production. The dominant bacterial class, Flavobacteria, seemed to be UVA-tolerant, whereas all the Alpha-, Beta- and Gammaproteobacteria present in the surface layer showed UVA sensitivity. These results indicate that changes in the light field of ice may alter the community structure and affect the functioning of ice food webs, and are of importance when the effects of thinning of the ice cover are assessed.

Evaluation of the profitability of fast-growing tropical trees.

The profitability of fast-growing trees was investigated in the northeastern and eastern provinces of Thailand. The financial, economic, and tentative environmental-economic profitability was determined separately for three fast-growing plantation tree species and for three categories of plantation managers: the private industry, the state (the Royal Forest Department) and the farmers. Fast-growing tree crops were also compared with teak (Tectona grandis), a traditional medium or long rotation species, and Para rubber (Hevea brasiliensis) which presently is the most common cultivated tree in Thailand. The optimal rotation for Eucalyptus camaldulensis pulpwood production was eight years. This was the most profitable species in pulpwood production. In sawlog production Acacia mangium and Melia azedarach showed a better financial profitability. Para rubber was more profitable and teak less profitable than the three fast-growing species. The economic profitability was higher than the financial one, and the tentative environmental-economic profitability was slightly higher than the economic profitability. The profitability of tree growing is sensitive to plantation yields and labour cost changes and especially to wood prices. Management options which aim at pulpwood production are more sensitive to input or output changes than those options which include sawlog production. There is an urgent need to improve the growth and yield data and to study the environmental impacts of tree plantations for all species and plantation types.

Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.