Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures

A RkNN query returns all objects whose nearest k neighbors
contain the query object. In this paper, we consider RkNN
query processing in the case where the distances between
attribute values are not necessarily metric. Dissimilarities
between objects could then be a monotonic aggregate of dissimilarities
between their values, such aggregation functions
being specified at query time. We outline real world cases
that motivate RkNN processing in such scenarios. We consider
the AL-Tree index and its applicability in RkNN query
processing. We develop an approach that exploits the group
level reasoning enabled by the AL-Tree in RkNN processing.
We evaluate our approach against a Naive approach
that performs sequential scans on contiguous data and an
improved block-based approach that we provide. We use
real-world datasets and synthetic data with varying characteristics
for our experiments. This extensive empirical
evaluation shows that our approach is better than existing
methods in terms of computational and disk access costs,
leading to significantly better response times.

Automating fault tolerance in high-performance computational biological jobs using multi-agent approaches

Background: Large-scale biological jobs on high-performance computing systems require manual intervention if one or more computing cores on which they execute fail. This places not only a cost on the maintenance of the job, but also a cost on the time taken for reinstating the job and the risk of losing data and execution accomplished by the job before it failed. Approaches which can proactively detect computing core failures and take action to relocate the computing core's job onto reliable cores can make a significant step towards automating fault tolerance. Method: This paper describes an experimental investigation into the use of multi-agent approaches for fault tolerance. Two approaches are studied, the first at the job level and the second at the core level. The approaches are investigated for single core failure scenarios that can occur in the execution of parallel reduction algorithms on computer clusters. A third approach is proposed that incorporates multi-agent technology both at the job and core level. Experiments are pursued in the context of genome searching, a popular computational biology application. Result: The key conclusion is that the approaches proposed are feasible for automating fault tolerance in high-performance computing systems with minimal human intervention. In a typical experiment in which the fault tolerance is studied, centralised and decentralised checkpointing approaches on an average add 90% to the actual time for executing the job. On the other hand, in the same experiment the multi-agent approaches add only 10% to the overall execution time

Computational Thinking across a Life Course

Symposium of papers on Computational Thinking

Computational methods in the fractional calculus of variations and optimal control

The fractional calculus of variations and fractional optimal control are generalizations of the corresponding classical theories, that allow problem modeling and formulations with arbitrary order derivatives and integrals. Because of the lack of analytic methods to solve such fractional problems, numerical techniques are developed. Here, we mainly investigate the approximation of fractional operators by means of series of integer-order derivatives and generalized finite differences. We give upper bounds for the error of proposed approximations and study their efficiency. Direct and indirect methods in solving fractional variational problems are studied in detail. Furthermore, optimality conditions are discussed for different types of unconstrained and constrained variational problems and for fractional optimal control problems. The introduced numerical methods are employed to solve some illustrative examples.

Interactions of cetaceans with Spanish and Portuguese fisheries in Atlantic waters : costs, benefits and implications for management

With the aim to provide new insights into operational cetacean-fishery interactions in Atlantic waters, this thesis assesses interactions of cetaceans with Spanish and Portuguese fishing vessels operating in Iberian and South West Atlantic waters. Different opportunistic research methodologies were applied, including an interview survey with fishers (mainly skippers) and onboard observations by fisheries observers and skippers, to describe different types of interactions and to identify potential hotspots for cetacean-fishery interactions and the cetacean species most involved, and to quantify the extent and the consequences of these interactions in terms of benefits and costs for cetaceans and fisheries. In addition, the suitability of different mitigation strategies was evaluated and discussed. The results of this work indicate that cetaceans interact frequently with Spanish and Portuguese fishing vessels, sometimes in a beneficial way (e.g. cetaceans indicate fish schools in purse seine fisheries), but mostly with negative consequences (depredation on catch, gear damage and cetacean bycatch). Significant economic loss and high bycatch rates are, however, only reported for certain fisheries and associated with particular cetacean species. In Galician fisheries, substantial economic loss was reported as a result of bottlenose dolphins damaging artisanal coastal gillnets, while high catch loss may arise from common dolphins scattering fish in purse seine fisheries. High cetacean bycatch mortality arises in trawl fisheries, mainly of common dolphin and particularly during trawling in water depths below 350 m, and in coastal set gillnet fisheries (mainly common and bottlenose dolphins). In large-scale bottom-set longline fisheries in South West Atlantic waters, sperm whales may significantly reduce catch rates through depredation on catch. The high diversity of cetacean-fishery interactions observed in the study area indicates that case-specific management strategies are needed to reduce negative impacts on fisheries and cetaceans. Acoustic deterrent devices (pingers) may be used to prevent small cetaceans from approaching and getting entangled in purse seines and set gillnets, although possible problems include cetacean habituation to the pinger sounds, as well as negative side effects on non-target cetaceans (habitat exclusion) and fisheries target species (reduced catch rates). For sardine and horse mackerel, target species of Iberian Atlantic fisheries, no aversive reaction to pinger sounds was detected during tank experiments conducted in the scope of this thesis. Bycatch in trawls may be reduced by the implementation of time/area restrictions of fishing activity. In addition, the avoidance of fishing areas with high cetacean abundance combined with the minimization of fishery-specific sound cues that possibly attract cetaceans, may also help to decrease interactions. In large-scale bottom-set longline fisheries, cetacean depredation on catch may be reduced by covering hooked fish with net sleeves ("umbrellas") provided that catch rates are not negatively affected by this gear modification. Trap fishing, as an alternative fishing method to bottom-set gillnetting and longlining, also has the potential to reduce cetacean bycatch and depredation, given that fish catch rates are similar to the rates obtained by bottom-set gillnets and longlines, whereas cetacean by-catch is unlikely. Economic incentives, such as the eco-certification of dolphin-safe fishing methods, should be promoted in order to create an additional source of income for fishers negatively affected by interactions with cetaceans, which, in turn, may also increase fishers’ willingness to accept and adopt mitigation measures. Although the opportunistic sampling methods applied in this work have certain restrictions concerning their reliability and precision, the results are consistent with previous studies in the same area. Moreover, they allow for the active participation of fishers that can provide important complementary ecological and technical knowledge required for cetacean management and conservation.

O problema da árvore de suporte de custo mínimo com restrições de peso

Nesta tese abordam-se várias formulações e diferentes métodos para resolver o Problema da Árvore de Suporte de Custo Mínimo com Restrições de Peso (WMST – Weight-constrained Minimum Spanning Tree Problem). Este problema, com aplicações no desenho de redes de comunicações e telecomunicações, é um problema de Otimização Combinatória NP-difícil. O Problema WMST consiste em determinar, numa rede com custos e pesos associados às arestas, uma árvore de suporte de custo mínimo de tal forma que o seu peso total não exceda um dado limite especificado. Apresentam-se e comparam-se várias formulações para o problema. Uma delas é usada para desenvolver um procedimento com introdução de cortes baseado em separação e que se tornou bastante útil na obtenção de soluções para o problema. Tendo como propósito fortalecer as formulações apresentadas, introduzem-se novas classes de desigualdades válidas que foram adaptadas das conhecidas desigualdades de cobertura, desigualdades de cobertura estendida e desigualdades de cobertura levantada. As novas desigualdades incorporam a informação de dois conjuntos de soluções: o conjunto das árvores de suporte e o conjunto saco-mochila. Apresentam-se diversos algoritmos heurísticos de separação que nos permitem usar as desigualdades válidas propostas de forma eficiente. Com base na decomposição Lagrangeana, apresentam-se e comparam-se algoritmos simples, mas eficientes, que podem ser usados para calcular limites inferiores e superiores para o valor ótimo do WMST. Entre eles encontram-se dois novos algoritmos: um baseado na convexidade da função Lagrangeana e outro que faz uso da inclusão de desigualdades válidas. Com o objetivo de obter soluções aproximadas para o Problema WMST usam-se métodos heurísticos para encontrar uma solução inteira admissível. Os métodos heurísticos apresentados são baseados nas estratégias Feasibility Pump e Local Branching. Apresentam-se resultados computacionais usando todos os métodos apresentados. Os resultados mostram que os diferentes métodos apresentados são bastante eficientes para encontrar soluções para o Problema WMST.

A computational study of ionic liquids used in the production of fuels and biofuels

For the past decades it has been a worldwide concern to reduce the emission of harmful gases released during the combustion of fossil fuels. This goal has been addressed through the reduction of sulfur-containing compounds, and the replacement of fossil fuels by biofuels, such as bioethanol, produced in large scale from biomass. For this purpose, a new class of solvents, the Ionic Liquids (ILs), has been applied, aiming at developing new processes and replacing common organic solvents in the current processes. ILs can be composed by a large number of different combinations of cations and anions, which confer unique but desired properties to ILs. The ability of fine-tuning the properties of ILs to meet the requirements of a specific application range by mixing different cations and anions arises as the most relevant aspect for rendering ILs so attractive to researchers. Nonetheless, due to the huge number of possible combinations between the ions it is required the use of cheap predictive approaches for anticipating how they will act in a given situation. Molecular dynamics (MD) simulation is a statistical mechanics computational approach, based on Newton’s equations of motion, which can be used to study macroscopic systems at the atomic level, through the prediction of their properties, and other structural information. In the case of ILs, MD simulations have been extensively applied. The slow dynamics associated to ILs constitutes a challenge for their correct description that requires improvements and developments of existent force fields, as well as larger computational efforts (longer times of simulation). The present document reports studies based on MD simulations devoted to disclose the mechanisms of interaction established by ILs in systems representative of fuel and biofuels streams, and at biomass pre-treatment process. Hence, MD simulations were used to evaluate different systems composed of ILs and thiophene, benzene, water, ethanol and also glucose molecules. For the latter molecules, it was carried out a study aiming to ascertain the performance of a recently proposed force field (GROMOS 56ACARBO) to reproduce the dynamic behavior of such molecules in aqueous solution. The results here reported reveal that the interactions established by ILs are dependent on the individual characteristics of each IL. Generally, the polar character of ILs is deterministic in their propensity to interact with the other molecules. Although it is unquestionable the advantage of using MD simulations, it is necessary to recognize the need for improvements and developments of force fields, not only for a successful description of ILs, but also for other relevant compounds such as the carbohydrates.

A computational study of a parallel Branch and Bound algorithm for the quadratic 0-1 programming problem on transputers

Discrete optimization problems are very difficult to solve, even if the dimantion is small. For most of them the problem of finding an ε-approximate solution is already NP-hard.

Computational intelligence

The Centre for Intelligent Systems (CIS) is a multidisciplinary research and development centre, founded in 2001, in a very young university, the University of Algarve, in the south of Portugal. The centr's mission is to promote fundamental research in Computational Intelligence (CI) methodology.

The Impacts of Variety on the Costs and Profits of a Hotel Chain’s Properties

In the hotel industry, undistributed operating expenses represent a significant portion of the operating costs for a hotel. Exactly how most of these expenses arise is not well understood. Using data from more than 40 hotels operated by a major chain, the authors examine the links between the variety of a hotel’s products and customers and its undistributed operating expenses and revenues. Their findings show that undistributed operating expenses are related to the extent of the property’s business and product-services mix. The results suggest that although increasing a property's product-service mix results in higher undistributed operating expenses, the incremental costs are compensated for by higher revenues. However, increasing business mix while increasing undistributed operating expenses does not result in higher revenues.

Serving More Segments and Offering More Products: What Are the Costs and Where Are the Profits?

Making more money involves more than targeting new customer segments and offering new services.

Internalising the external costs of light goods vehicle transport in Britain

Report produced as part of the Green Logistics project (EPSRC and Department for Transport funded). To what extent do the taxes paid by the light goods vehicles (LGVs) users in Britain cover their allocated infrastructural, environmental and congestion costs? This report is a continuation of a study on the internalisation of the external costs of heavy goods vehicle activity. Research undertaken jointly by the Transport Studies Group at University of Westminster and Logistics Research Centre at Heriot-Watt University has attempted to answer this question using official government transport statistics and monetary valuations for the external costs.

Internalising the external costs of light and heavy goods vehicle transport in London

Report produced as part of the Green Logistics project (EPSRC and Department for Transport funded). This report provides estimates of the total external costs of LGV and HGV operations in London. In 2006, total LGV and HGV activity imposed external costs of approximately £1.75-£1.8 billion using low, medium and high emission cost values. About 27 per cent of these costs were internalised by duties and taxes paid by LGV operators, compared with 26% in the case of HGVs. If congestion costs are excluded, taxes and duties paid by LGV operators are estimated to be 155% of LGVs' allocated infrastructural and environmental costs, compared with 85% in the case of HGVs. When using the medium emission cost values, LGVs accounted for 56% of these external costs in London and HGVs for 44%.