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.

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

Consequences of Vertebral Fractures

Vertebral fractures occur due to forces applied to spinal structures. When the bone tissue is weakened, vertebral fractures can result from a minor trauma. Adult vertebral fractures are commonly considered to be an indication for osteoporosis. In children osteoporosis is a rare condition, and pediatric vertebral fractures are usually clearly trauma-related. The aims of this dissertation are to produce knowledge of the epidemiology of osteoporotic vertebral fractures and to analyse their association with total and cause-specific mortality, to find indicators with which to identify individuals who are at great risk of subsequent fractures, to study the incidence of pediatric vertebral fractures and need for their operative treatment and hospital care. The Mobile-Clinic and Mini-Finland Health surveys of the adult population were used as materials in this research. Record linkages to the Finnish Hospital Discharge Register and the Official Cause of Death register were used to study mortality and hospitalization in the same population group. These registers were also used to evaluate epidemiology, mortality, hospitalization and the need for operative management of pediatric vertebral fracture patients. The main findings and conclusions of the present dissertation are: 1. The presence of a thoracic vertebral fracture in adults is a significant predictor of cancer and respiratory mortality. In women, but not in men, vertebral fractures strongly predict mortality due to injuries. Most of these deaths in the study group were hip fracture related. 2. Severe thoracic vertebral fracture in adults was a strong predictor of a subsequent hip fracture, whereas mild or moderate fractures and the number of compressed vertebrae were much weaker predictors, 3. Pediatric spinal fractures were rare: The incidence was 66 per one million children per year. In younger children cervical spine was most often affected, whereas in older children fractures of the thoracic and lumbar spine were more common. Maturation of spinal structures seems to play a major role in the typical injury patterns in children. Thirty per cent of pediatric spinal fractures required surgical treatment. The current study focuses on consequences of vertebral fractures in general, without evaluating further the causation of the studied phenomena. Further studies are needed to clarify the mechanisms of association between vertebral fractures and specific causes of mortality. A severe vertebral fracture appears to indicate a substantial risk of a subsequent hip fracture. If such a fracture is identified from a chest radiograph, urgent clinical evaluation, treatment of osteoporosis and protective measures against falls are recommended.

Mesoporous silica- and silicon-based materials as carriers for poorly water soluble drugs

New chemical entities with unfavorable water solubility properties are continuously emerging in drug discovery. Without pharmaceutical manipulations inefficient concentrations of these drugs in the systemic circulation are probable. Typically, in order to be absorbed from the gastrointestinal tract, the drug has to be dissolved. Several methods have been developed to improve the dissolution of poorly soluble drugs. In this study, the applicability of different types of mesoporous (pore diameters between 2 and 50 nm) silicon- and silica-based materials as pharmaceutical carriers for poorly water soluble drugs was evaluated. Thermally oxidized and carbonized mesoporous silicon materials, ordered mesoporous silicas MCM-41 and SBA-15, and non-treated mesoporous silicon and silica gel were assessed in the experiments. The characteristic properties of these materials are the narrow pore diameters and the large surface areas up to over 900 m²/g. Loading of poorly water soluble drugs into these pores restricts their crystallization, and thus, improves drug dissolution from the materials as compared to the bulk drug molecules. In addition, the wide surface area provides possibilities for interactions between the loaded substance and the carrier particle, allowing the stabilization of the system. Ibuprofen, indomethacin and furosemide were selected as poorly soluble model drugs in this study. Their solubilities are strongly pH-dependent and the poorest (< 100 µg/ml) at low pH values. The pharmaceutical performance of the studied materials was evaluated by several methods. In this work, drug loading was performed successfully using rotavapor and fluid bed equipment in a larger scale and in a more efficient manner than with the commonly used immersion methods. It was shown that several carrier particle properties, in particular the pore diameter, affect the loading efficiency (typically ~25-40 w-%) and the release rate of the drug from the mesoporous carriers. A wide pore diameter provided easier loading and faster release of the drug. The ordering and length of the pores also affected the efficiency of the drug diffusion. However, these properties can also compensate the effects of each other. The surface treatment of porous silicon was important in stabilizing the system, as the non-treated mesoporous silicon was easily oxidized at room temperature. Different surface chemical treatments changed the hydrophilicity of the porous silicon materials and also the potential interactions between the loaded drug and the particle, which further affected the drug release properties. In all of the studies, it was demonstrated that loading into mesoporous silicon and silica materials improved the dissolution of the poorly soluble drugs as compared to the corresponding bulk compounds (e.g. after 30 min ~2-7 times more drug was dissolved depending on the materials). The release profile of the loaded substances remained similar also after 3 months of storage at 30°C/56% RH. The thermally carbonized mesoporous silicon did not compromise the Caco-2 monolayer integrity in the permeation studies and improved drug permeability was observed. The loaded mesoporous silica materials were also successfully compressed into tablets without compromising their characteristic structural and drug releasing properties. The results of this research indicated that mesoporous silicon/silica-based materials are promising materials to improve the dissolution of poorly water soluble drugs. Their feasibility in pharmaceutical laboratory scale processes was also confirmed in this thesis.

Tuning the interfacial properties of supported metal nanoclusters

Nanoclusters are objects made up of several to thousands of atoms and form a transitional state of matter between single atoms and bulk materials. Due to their large surface-to-volume ratio, nanoclusters exhibit exciting and yet poorly studied size dependent properties. When deposited directly on bare metal surfaces, the interaction of the cluster with the substrate leads to alteration of the cluster properties, making it less or even non-functional. Surfaces modified with self-assembled monolayers (SAMs) were shown to form an interesting alternative platform, because of the possibility to control wettability by decreasing the surface reactivity and to add functionalities to pre-formed nanoclusters. In this thesis, the underlying size effects and the influence of the nanocluster environment are investigated. The emphasis is on the structural and magnetic properties of nanoclusters and their interaction with thiol SAMs. We report, for the first time, a ferromagnetic-like spin-glass behaviour of uncapped nanosized Au islands tens of nanometres in size. The flattening kinetics of the nanocluster deposition on thiol SAMs are shown to be mediated mainly by the thiol terminal group, as well as the deposition energy and the particle size distribution. On the other hand, a new mechanism for the penetration of the deposited nanoclusters through the monolayers is presented, which is fundamentally different from those reported for atom deposition on alkanethiols. The impinging cluster is shown to compress the thiol layer against the Au surface and subsequently intercalate at the thiol-Au interface. The compressed thiols try then to straighten and push the cluster away from the surface. Depending on the cluster size, this restoring force may or may not enable a covalent cluster-surface bond formation, giving rise to various cluster-surface binding patterns. Compression and straightening of the thiol molecules pinpoint the elastic nature of the SAMs, which has been investigated in this thesis using nanoindentation. The nanoindenation method has been applied to SAMs of varied tail groups, giving insight into the mechanical properties of thiol modified metal surfaces.

Compression of Weighted Graphs

We propose to compress weighted graphs (networks), motivated by the observation that large networks of social, biological, or other relations can be complex to handle and visualize. In the process also known as graph simplication, nodes and (unweighted) edges are grouped to supernodes and superedges, respectively, to obtain a smaller graph. We propose models and algorithms for weighted graphs. The interpretation (i.e. decompression) of a compressed, weighted graph is that a pair of original nodes is connected by an edge if their supernodes are connected by one, and that the weight of an edge is approximated to be the weight of the superedge. The compression problem now consists of choosing supernodes, superedges, and superedge weights so that the approximation error is minimized while the amount of compression is maximized. In this paper, we formulate this task as the 'simple weighted graph compression problem'. We then propose a much wider class of tasks under the name of 'generalized weighted graph compression problem'. The generalized task extends the optimization to preserve longer-range connectivities between nodes, not just individual edge weights. We study the properties of these problems and propose a range of algorithms to solve them, with dierent balances between complexity and quality of the result. We evaluate the problems and algorithms experimentally on real networks. The results indicate that weighted graphs can be compressed efficiently with relatively little compression error.