This document is the report for the authors' joint effort in researching and designing a query optimizer for Fast's next-generation search platform, known as MARS. The work was done during our master's thesis at the Department of Computer and Information Science at the Norwegian University of Science and Technology, spring 2009. MARS does not currently employ any form of query optimizer, but does have a parser and a runtime system. The report therefore focuses on the core query optimizing aspects, like plan generation and optimizer design. First, we give an introduction to query optimizers and selected problems. Then, we describe previous and ongoing efforts regarding query optimizers, before shifting focus to our own design and results. MARS supports DAG-structured query plans for more efficient execution, which means that the optimizer must do so too. This turned out to be a greater task than what it might seem like --- since we must use algorithms that greatly differ from the optimizers we were familiar with. The optimizer also needed to be extensible, including the ability to deal with future query operators, as well as supporting arbitrary cost models. During the course of the master's thesis, we have laid out the design of an optimizer that satisfies these goals. The optimizer is able recognize common sub-expressions and construct DAGs from non-DAG inputs. Extensibility is solved by loose coupling between optimizer components. Rules are used to model operators, and the cost model is a separate, customizable component. We have also implemented a prototype that demonstrates that the design actually works. The optimizer itself is designed as separate component, not tied up to MARS. We have been able to inject it into the MARS query pipeline and run queries end-to-end with optimization enabled, improving the query evaluation time. For now, the project depends on MARS assemblies, but reusing it for another engine and algebra is entirely feasible.

The goal for this master thesis is finding trends and behaviors in a highly available database cluster using InfiniBand and RDMA. This will be used to optimize configuration of the segment size in such systems. To find these trends and behaviors, a mockup model has been developed. The model consists of a simple DBMS that uses only the main memory for storing data and a checkpoint method to repair nodes after a node failure. During a repair, the model simulates use of InfiniBand and RDMA during checkpointing. To simulate clients connecting to and using the database, the model includes write operations on the database and measures how many write operations it can process per second. During a repair in a database cluster, one node will flush all of its data to a new node. This is done in small batches, just like in a checkpoint. In this model, it is simulated by a checkpoint module continuously simulating flushing data from one node to another. When the checkpoint is flushing a small part of the database fragment, the model uses Copy on Write to prevent lockout for the transactions. When a node fails the system is repaired by a second node which takes over as fast as possible. The second node must process transactions while transferring all of its data to a spare node. To achieve fast repair time, the system should transfer as big segments as possible. The problem with big segments is that it takes a long time to perform Copy on Write on them. With the mockup model, the repair time is measured, how many write operations are being performed per second and CPU usage depending on the segment size and number of clients using the database. This will give a good indication of what segment size is preferable. The results from the thesis show that there are huge advantages by using state-of-the-art technology such as InfiniBand and RDMA for repair in highly available database clusters. This technology and optimal configuration improves the availability and this thesis gives an indication that the segment size should not be more than 1 % of the database size. With use of InfiniBand and RDMA using this configuration and physical repair, the availability reaches class 9.

This project continues the work started in our depth study project in the fall of 2004, develop- ing a framework for mobile collaborative applications on mobile phones utilizing Personal Area Networks (PANs). This paper describes central, theoretical concepts connected to the Peer-to-Peer (P2P) comput- ing, the Mobile Ad Hoc NETworks (MANETs) and the Computer Supported Cooperative Work (CSCW) domains, focusing on "Same-Place-Same-Time" collaboration. We argue how the spread of PAN technology and mobile phones enable for a broad range of new collaborative applications supporting both collocated work and spontaneous interaction. Updated information about relevant technologies and related projects are discussed and evaluated. The requirements for the Peer2Me framework are presented and updated along with a revised and improved design. The design and the requirements are a product of an explorative development effort to develop the next generation of the Peer2Me framework using Java 2 Micro Edition and the Java APIs for Bluetooth wireless technology (JABWT). The Peer2Me framework is then tested on actual developers in a workshop arranged in May 2005. Data gathered from this workshop is used to illustrate the benefits of using a framework like Peer2Me for developing mobile collaborative applications. In addition to the actual Peer2Me framework implementation along with its Bluetooth network module, example applications are designed, implemented and tested in order to verify the suit- ability of the Peer2Me framework in the problem domain. These applications illustrate different kinds of aspects of the Peer2Me framework and the domain of mobile collaborative applications. The tests of these applications are done through enactment of the usage scenarios from which the applications were derived. The main results of this project are the technical products comprised of the Peer2Me framework, the Bluetooth Network module and the example Peer2Me applications, as well as the empirical data supporting the advantages of Peer2Me and the evaluations upon the suitability of the applied technologies.

This report investigates different methods in computer graphics and virtual reality that can be applied to develop a system that provides analysis for the changes that occur when removing outlier points in plots for principal component analysis. The main results of the report show that the use of animation gives a better understanding for the movement of individual points in the plots, before and after removal.

Denne oppgaven presenterer et rammeverk for representasjon av og resonnering med temporale data i CBR-systemet TrollCreek. Slik funksjonalitet vil forbedre TrollCreek’s ytelse innenfor prediksjonsproblemer, det vil si: Kunne prediktere hva som vil skje i en ny problemsituasjon basert på sammenligninger med lagrede problemsituasjoner. Representasjonen er basert på å legge til en eller flere tidslinjer til et case. Resonneringsmekanismen abstraherer disse tidslinjene inn i en enkelt tidslinje, og sammenligner deretter denne tidslinjen med andre abstraherte tidslinjer i case-basen. I denne oppgaven har vi implementert en enkel ikke-kunnskapsintensiv metode for denne abstraksjonsoppgaven og vi har brukt metoder for sekvenssammenligning for å sammenligne tidslinjene. Oppgaven inneholder også et eksempel av rammeverket i bruk. Eksempelet er av en ”proof-of-concept”-type, og involverer et imagniært domene.

Multiarch is a mechanism for packages supporting multiple architectures to be installed at the same time on the same machine in the same operating system. This paper shows a sample implementation of one way do do this on a UNIX-like system using the dpkg package manager. It shows the needed changes to both packages and the package manager itself.

A framework for JIT compilation that specifically caters to the resource constraints of new generations of small devices is presented. Preliminary results obtained from a prototype implementation show average speedup of 5.5 over a conventional interpreter-based Java implementation, with only a 15% increase in the static memory footprint and an adjustable, highly predictable dynamic footprint.

Existing models of Norwegian offshore platforms are generally incomplete and lack the accuracy needed to eliminate clashes between the existing parts on the platform and new systems, before construction. Laser scanning is today used to a growing extent to make models with the necessary accuracy and thus resolve clashes prior to construction. However these models only show the surface of the plant and do not have the non-visible attributes or “intelligent information” contained in the existing models of the platform. I will in this thesis present how the intelligent information from an existing as-built model can be assigned to a scan model, and thus replace the old and inaccurate as-built model used today during the design of new systems.

Atmel is inventing a new microcontroller that is capable of running Java pro- grams through an implementation of the Java Virtual Machine. Compared to industry standard PCs the microcontroller has limited processing power and main memory. When running interactive programs on this microcontroller it is important that the program interruption time is kept to a minimum. In a Java Virtual machine the garbage collector is responsible for reclaiming unused main memory and making it available for the Java program again. This process creates a program interruption where the Java program is halted and the garbage collector is working. At the project start the Atmel Virtual Machine was using the mark-sweep garbage collector. This garbage collector could produce a program interruption greater than one second and was not suitable for interactive programs. The Memory-Constrained Copying algorithm is a new garbage collection algorithm that is incremental and therefore only collects a little bit of main memory at a time compared to the implemented mark-sweep garbage collector. A theoretical comparison of the mark sweep algorithm and the Memory- Constrained Copying algorithm was performed. This comparison showed that the mark-sweep algorithm would have a much longer program interruption than the Memory-Constrained Copying algorithm. The two algorithms should in the- ory also produce equal throughput. The penalty for the short program interrup- tion time in the Memory-Constrained Copying algorithm is its high algorithmic complexity. After a few modfications to the Virtual Machine, the Memory-Constrained Copying algorithm was implemented and tested functionally. To test the pro- gram interruption and throughput of the garbage collection algorithms a set of benchmarks were chosen. The EDN Embedded Microprocessor Benchmark Consortium Java benchmark suite was selected as the most accurate benchmarks available. The practical comparison of the two garbage collection algorithms showed that the theoretical comparison was correct. The mark-sweep algorithm pro- duced in the worst case an interruption of 3 seconds, while the Memory-Constrained Copying algorithm's maximum program interruption was 44 milliseconds. The results of the benchmarking confirms the results that the inventors of the Memory-Constrained Copying algorithm achieved in their test. Their test was not performed on a microcontroller, but on a standard desktop computer. This implementation has also confirmed that it is possible to implement the Memory-Constrained Copying algorithm in a microcontroller. During the implementation of the Memory-Constrained Copying algorithm a hardware bug was found in the microcontroller. This bug was identified and reported so the hardware could be modified.

Botnets are compromised hosts under a common command and control infrastructure. These nets have become very popular because of their potential for various malicious activity. They are frequently used for distributed denial-of-service attacks, spamming, spreading malware and privacy invasion. Manually uncovering and responding to such hosts is difficult and costly. In this thesis a technique for uncovering and reporting botnet activity in an internet service provider environment is presented and tested. Using a list of known botnet controllers, an ISP can proactivly warn customers of likely compromised hosts while at the same time mitigate future ill-effects by severing communications between the compromised host and the controller. A prototype system is developed to route traffic destined for controllers to a sinkhole host, then analyse and drop the traffic. After using the system in a live environment at the norwegian reasearch and education network the technique has proven to be a feasable one, and is used in a incident response test-case, warning two big customers of likely compromised hosts. However, there are challenges in tracking down and following up such hosts, especially ``roaming'' hosts such as laptops. The scope of the problem is found to be serious, with the expected number of new hosts found to be about 75 per day. Considering that the list used represents only part of the actual controllers active on the internet, the need for an automated incident response seems clear.