Materialized view selection under the maintenance time constraint

A data warehouse is a data repository which collects and maintains a large amount of data from multiple distributed, autonomous and possibly heterogeneous data sources. Often the data is stored in the form of materialized views in order to provide fast access to the integrated data. One of the most important decisions in designing a data warehouse is the selection of views for materialization. The objective is to select an appropriate set of views that minimizes the total query response time with the constraint that the total maintenance time for these materialized views is within a given bound. This view selection problem is totally different from the view selection problem under the disk space constraint. In this paper the view selection problem under the maintenance time constraint is investigated. Two efficient, heuristic algorithms for the problem are proposed. The key to devising the proposed algorithms is to define good heuristic functions and to reduce the problem to some well-solved optimization problems. As a result, an approximate solution of the known optimization problem will give a feasible solution of the original problem. (C) 2001 Elsevier Science B.V. All rights reserved.

Anticipation of a non-aversive reaction time task facilitates the blink startle reflex

The conditions under which blink startle facilitation can be found in anticipation of a reaction time task were investigated to resolve inconsistent findings across previous studies. Four groups of participants (n = 64) were presented with two visual stimuli, one predicting a reaction time task (S+) and the second presented alone (S-). Participants were asked to make a speeded response to the offset of the S+ (S1 paradigm) or were asked to respond to a tactile stimulus presented at the offset of the S+ (S1-S2 paradigm). Half of the participants in each paradigm condition received performance feedback. Overall, blink latency shortening and magnitude facilitation were larger during S+ than during S-. More detailed analyses, however, found these differences to be reliable only in the Feedback conditions. Ratings of S+ pleasantness did not change across the experiment. Electrodermal responses to S+ were larger than to S- in all groups with differential electrodermal responding emerging earlier in the S1 paradigm. Taken together, the data support the notion that startle facilitation can occur during non-aversive Pavlovian conditioning. (C) 2002 Elsevier Science B.V. All rights reserved.

Probing the time course of nonlinear discriminations during human electrodermal conditioning

Animal-based theories of Pavlovian conditioning propose that patterning discriminations are solved using unique cues or immediate configuring. Recent studies with humans, however, provided evidence that in positive and negative patterning two different rules are utilized. The present experiment was designed to provide further support for this proposal by tracking the time course of the allocation of cognitive resources. One group was trained in a positive patterning; schedule (A-, B-, AB+) and a second in a negative patterning schedule (A+, B+, AB-). Electrodermal responses and secondary task probe reaction time were measured. In negative patterning, reaction times were slower during reinforced stimuli than during non-reinforced stimuli at both probe positions while there were no differences in positive patterning. These results support the assumption that negative patterning is solved using a rule that is more complex and requires more resources than does the rule employed to solve positive patterning. (C) 2001 Elsevier Science (USA).

One-dimensional quantum walk with unitary noise

The effect of unitary noise on the discrete one-dimensional quantum walk is studied using computer simulations. For the noiseless quantum walk, starting at the origin (n=0) at time t=0, the position distribution P-t(n) at time t is very different from the Gaussian distribution obtained for the classical random walk. Furthermore, its standard deviation, sigma(t) scales as sigma(t)similar tot, unlike the classical random walk for which sigma(t)similar toroott. It is shown that when the quantum walk is exposed to unitary noise, it exhibits a crossover from quantum behavior for short times to classical-like behavior for long times. The crossover time is found to be Tsimilar toalpha(-2), where alpha is the standard deviation of the noise.

A new method for analysing the equilibrium and time-dependent behaviour of Markovian models

Many large-scale stochastic systems, such as telecommunications networks, can be modelled using a continuous-time Markov chain. However, it is frequently the case that a satisfactory analysis of their time-dependent, or even equilibrium, behaviour is impossible. In this paper, we propose a new method of analyzing Markovian models, whereby the existing transition structure is replaced by a more amenable one. Using rates of transition given by the equilibrium expected rates of the corresponding transitions of the original chain, we are able to approximate its behaviour. We present two formulations of the idea of expected rates. The first provides a method for analysing time-dependent behaviour, while the second provides a highly accurate means of analysing equilibrium behaviour. We shall illustrate our approach with reference to a variety of models, giving particular attention to queueing and loss networks. (C) 2003 Elsevier Ltd. All rights reserved.

The reliability of video based time motion analysis

Time motion analysis is extensively used to assess the demands of team sports. At present there is only limited information on the reliability of measurements using this analysis tool. The aim of this study was to establish the reliability of an individual observer's time motion analysis of rugby union. Ten elite level rugby players were individually tracked in Southern Hemisphere Super 12 matches using a digital video camera. The video footage was subsequently analysed by a single researcher on two occasions one month apart. The test-retest reliability was quantified as the typical error of measurement (TEM) and rated as either good (10% TEM). The total time spent in the individual movements of walking, jogging, striding, sprinting, static exertion and being stationary had moderate to poor reliability (5.8-11.1% TEM). The frequency of individual movements had good to poor reliability (4.3-13.6% TEM), while the mean duration of individual movements had moderate reliability (7.1-9.3% TEM). For the individual observer in the present investigation, time motion analysis was shown to be moderately reliable as an evaluation tool for examining the movement patterns of players in competitive rugby. These reliability values should be considered when assessing the movement patterns of rugby players within competition.

Reproducibility of a laboratory-based 40-km cycle time-trial on a stationary wind-trainer in highly trained cyclists

The purpose of the present study was to examine the reproducibility of laboratory-based 40-km cycle time-trial performance on a stationary wind-trainer. Each week, for three consecutive weeks, and on different days, forty-three highly trained male cyclists ((x) over bar +/- SD; age = 25 +/- 6 y; mass = 75 +/- 7 kg; peak oxygen uptake [(V) over dot O-2 peak] = 64.8 +/- 5.2 ml x kg(-1) x min(-1)) performed: 1) a (V) over dot O-2 peak test, and 2) a 40-km time-trial on their own racing bicycle mounted to a stationary wind-trainer (Cateye - Cyclosimulator). Data from all tests were compared using a one-way analysis of variance. Performance on the second and third 40-km time-trials were highly related (r = 0.96; p < 0.001), not significantly different (57:21 +/- 2:57 vs. 57:12 +/- 3:14 min:s), and displayed a low coefficient of variation (CV) = 0.9 +/- 0.7%. Although the first 40-km time-trial (58:43 +/- 3:17min:s) was not significantly different from the second and third tests (p = 0.06), inclusion of the first test in the assessment of reliability increased within-subject CV to 3.0 +/- 2.9%. 40-km time-trial speed (km x h(-1)) was significantly (p < 0.001) related to peak power output (W; r = 0.75), (V) over dot O-2 peak (1 x min(-1); r = 0.53), and the second ventilatory turnpoint (1 x min(-1); r = 0.68) measured during the progressive exercise tests. These data demonstrate that the assessment of 40-km cycle time-trial performance in well-trained endurance cyclists on a stationary wind-trainer is reproducible, provided the athletes perform a familiarization trial.

Preliminary clinical trial in percutaneous nephrolithotomy using a real-time navigation system for percutaneous kidney access

Background: Precise needle puncture of renal calyces is a challenging and essential step for successful percutaneous nephrolithotomy. This work tests and evaluates, through a clinical trial, a real-time navigation system to plan and guide percutaneous kidney puncture. Methods: A novel system, entitled i3DPuncture, was developed to aid surgeons in establishing the desired puncture site and the best virtual puncture trajectory, by gathering and processing data from a tracked needle with optical passive markers. In order to navigate and superimpose the needle to a preoperative volume, the patient, 3D image data and tracker system were previously registered intraoperatively using seven points that were strategically chosen based on rigid bone structures and nearby kidney area. In addition, relevant anatomical structures for surgical navigation were automatically segmented using a multi-organ segmentation algorithm that clusters volumes based on statistical properties and minimum description length criterion. For each cluster, a rendering transfer function enhanced the visualization of different organs and surrounding tissues. Results: One puncture attempt was sufficient to achieve a successful kidney puncture. The puncture took 265 seconds, and 32 seconds were necessary to plan the puncture trajectory. The virtual puncture path was followed correctively until the needle tip reached the desired kidney calyceal. Conclusions: This new solution provided spatial information regarding the needle inside the body and the possibility to visualize surrounding organs. It may offer a promising and innovative solution for percutaneous punctures.

Real-time hand tracking for rehabilitation and character animation

Hand and finger tracking has a major importance in healthcare, for rehabilitation of hand function required due to a neurological disorder, and in virtual environment applications, like characters animation for on-line games or movies. Current solutions consist mostly of motion tracking gloves with embedded resistive bend sensors that most often suffer from signal drift, sensor saturation, sensor displacement and complex calibration procedures. More advanced solutions provide better tracking stability, but at the expense of a higher cost. The proposed solution aims to provide the required precision, stability and feasibility through the combination of eleven inertial measurements units (IMUs). Each unit captures the spatial orientation of the attached body. To fully capture the hand movement, each finger encompasses two units (at the proximal and distal phalanges), plus one unit at the back of the hand. The proposed glove was validated in two distinct steps: a) evaluation of the sensors’ accuracy and stability over time; b) evaluation of the bending trajectories during usual finger flexion tasks based on the intra-class correlation coefficient (ICC). Results revealed that the glove was sensitive mainly to magnetic field distortions and sensors tuning. The inclusion of a hard and soft iron correction algorithm and accelerometer and gyro drift and temperature compensation methods provided increased stability and precision. Finger trajectories evaluation yielded high ICC values with an overall reliability within application’s satisfying limits. The developed low cost system provides a straightforward calibration and usability, qualifying the device for hand and finger tracking in healthcare and animation industries.

A-scan ultrasound system for real-time puncture safety assessment during percutaneous nephrolithotomy

Background: Kidney stone is a major universal health problem, affecting 10% of the population worldwide. Percutaneous nephrolithotomy is a first-line and established procedure for disintegration and removal of renal stones. Its surgical success depends on the precise needle puncture of renal calyces, which remains the most challenging task for surgeons. This work describes and tests a new ultrasound based system to alert the surgeon when undesirable anatomical structures are in between the puncture path defined through a tracked needle. Methods: Two circular ultrasound transducers were built with a single 3.3-MHz piezoelectric ceramic PZT SN8, 25.4 mm of radius and resin-epoxy matching and backing layers. One matching layer was designed with a concave curvature to work as an acoustic lens with long focusing. The A-scan signals were filtered and processed to automatically detect reflected echoes. Results: The transducers were mapped in water tank and tested in a study involving 45 phantoms. Each phantom mimics different needle insertion trajectories with a percutaneous path length between 80 and 150 mm. Results showed that the beam cross-sectional area oscillates around the ceramics radius and it was possible to automatically detect echo signals in phantoms with length higher than 80 mm. Conclusions: This new solution may alert the surgeon about anatomical tissues changes during needle insertion, which may decrease the need of X-Ray radiation exposure and ultrasound image evaluation during percutaneous puncture.

Real-time energy resources scheduling considering intensive wind penetration

The use of distributed energy resources, based on natural intermittent power sources, like wind generation, in power systems imposes the development of new adequate operation management and control methodologies. A short-term Energy Resource Management (ERM) methodology performed in two phases is proposed in this paper. The first one addresses the day-ahead ERM scheduling and the second one deals with the five-minute ahead ERM scheduling. The ERM scheduling is a complex optimization problem due to the high quantity of variables and constraints. In this paper the main goal is to minimize the operation costs from the point of view of a virtual power player that manages the network and the existing resources. The optimization problem is solved by a deterministic mixedinteger non-linear programming approach. A case study considering a distribution network with 33 bus, 66 distributed generation, 32 loads with demand response contracts and 7 storage units and 1000 electric vehicles has been implemented in a simulator developed in the field of the presented work, in order to validate the proposed short-term ERM methodology considering the dynamic power system behavior.

Virtual power players dealing with excessive wind power situations using real time pricing

The increasing importance given by environmental policies to the dissemination and use of wind power has led to its fast and large integration in power systems. In most cases, this integration has been done in an intensive way, causing several impacts and challenges in current and future power systems operation and planning. One of these challenges is dealing with the system conditions in which the available wind power is higher than the system demand. This is one of the possible applications of demand response, which is a very promising resource in the context of competitive environments that integrates even more amounts of distributed energy resources, as well as new players. The methodology proposed aims the maximization of the social welfare in a smart grid operated by a virtual power player that manages the available energy resources. When facing excessive wind power generation availability, real time pricing is applied in order to induce the increase of consumption so that wind curtailment is minimized. The proposed method is especially useful when actual and day-ahead wind forecast differ significantly. The proposed method has been computationally implemented in GAMS optimization tool and its application is illustrated in this paper using a real 937-bus distribution network with 20310 consumers and 548 distributed generators, some of them with must take contracts.

Supporting intra-task parallelism in real-time multiprocessor systems

Os sistemas de tempo real modernos geram, cada vez mais, cargas computacionais pesadas e dinâmicas, começando-se a tornar pouco expectável que sejam implementados em sistemas uniprocessador. Na verdade, a mudança de sistemas com um único processador para sistemas multi- processador pode ser vista, tanto no domínio geral, como no de sistemas embebidos, como uma forma eficiente, em termos energéticos, de melhorar a performance das aplicações. Simultaneamente, a proliferação das plataformas multi-processador transformaram a programação paralela num tópico de elevado interesse, levando o paralelismo dinâmico a ganhar rapidamente popularidade como um modelo de programação. A ideia, por detrás deste modelo, é encorajar os programadores a exporem todas as oportunidades de paralelismo através da simples indicação de potenciais regiões paralelas dentro das aplicações. Todas estas anotações são encaradas pelo sistema unicamente como sugestões, podendo estas serem ignoradas e substituídas, por construtores sequenciais equivalentes, pela própria linguagem. Assim, o modo como a computação é na realidade subdividida, e mapeada nos vários processadores, é da responsabilidade do compilador e do sistema computacional subjacente. Ao retirar este fardo do programador, a complexidade da programação é consideravelmente reduzida, o que normalmente se traduz num aumento de produtividade. Todavia, se o mecanismo de escalonamento subjacente não for simples e rápido, de modo a manter o overhead geral em níveis reduzidos, os benefícios da geração de um paralelismo com uma granularidade tão fina serão meramente hipotéticos. Nesta perspetiva de escalonamento, os algoritmos que empregam uma política de workstealing são cada vez mais populares, com uma eficiência comprovada em termos de tempo, espaço e necessidades de comunicação. Contudo, estes algoritmos não contemplam restrições temporais, nem outra qualquer forma de atribuição de prioridades às tarefas, o que impossibilita que sejam diretamente aplicados a sistemas de tempo real. Além disso, são tradicionalmente implementados no runtime da linguagem, criando assim um sistema de escalonamento com dois níveis, onde a previsibilidade, essencial a um sistema de tempo real, não pode ser assegurada. Nesta tese, é descrita a forma como a abordagem de work-stealing pode ser resenhada para cumprir os requisitos de tempo real, mantendo, ao mesmo tempo, os seus princípios fundamentais que tão bons resultados têm demonstrado. Muito resumidamente, a única fila de gestão de processos convencional (deque) é substituída por uma fila de deques, ordenada de forma crescente por prioridade das tarefas. De seguida, aplicamos por cima o conhecido algoritmo de escalonamento dinâmico G-EDF, misturamos as regras de ambos, e assim nasce a nossa proposta: o algoritmo de escalonamento RTWS. Tirando partido da modularidade oferecida pelo escalonador do Linux, o RTWS é adicionado como uma nova classe de escalonamento, de forma a avaliar na prática se o algoritmo proposto é viável, ou seja, se garante a eficiência e escalonabilidade desejadas. Modificar o núcleo do Linux é uma tarefa complicada, devido à complexidade das suas funções internas e às fortes interdependências entre os vários subsistemas. Não obstante, um dos objetivos desta tese era ter a certeza que o RTWS é mais do que um conceito interessante. Assim, uma parte significativa deste documento é dedicada à discussão sobre a implementação do RTWS e à exposição de situações problemáticas, muitas delas não consideradas em teoria, como é o caso do desfasamento entre vários mecanismo de sincronização. Os resultados experimentais mostram que o RTWS, em comparação com outro trabalho prático de escalonamento dinâmico de tarefas com restrições temporais, reduz significativamente o overhead de escalonamento através de um controlo de migrações, e mudanças de contexto, eficiente e escalável (pelo menos até 8 CPUs), ao mesmo tempo que alcança um bom balanceamento dinâmico da carga do sistema, até mesmo de uma forma não custosa. Contudo, durante a avaliação realizada foi detetada uma falha na implementação do RTWS, pela forma como facilmente desiste de roubar trabalho, o que origina períodos de inatividade, no CPU em questão, quando a utilização geral do sistema é baixa. Embora o trabalho realizado se tenha focado em manter o custo de escalonamento baixo e em alcançar boa localidade dos dados, a escalonabilidade do sistema nunca foi negligenciada. Na verdade, o algoritmo de escalonamento proposto provou ser bastante robusto, não falhando qualquer meta temporal nas experiências realizadas. Portanto, podemos afirmar que alguma inversão de prioridades, causada pela sub-política de roubo BAS, não compromete os objetivos de escalonabilidade, e até ajuda a reduzir a contenção nas estruturas de dados. Mesmo assim, o RTWS também suporta uma sub-política de roubo determinística: PAS. A avaliação experimental, porém, não ajudou a ter uma noção clara do impacto de uma e de outra. No entanto, de uma maneira geral, podemos concluir que o RTWS é uma solução promissora para um escalonamento eficiente de tarefas paralelas com restrições temporais.

Evaluating P-NET message's response time with fixed priority queuing at application process level

P-NET is a multi-master fieldbus standard based on a virtual token passing scheme. In P-NET each master is allowed to transmit only one message per token visit. In the worst-case, the communication response time can be derived considering that, in each token cycle, all stations use the token to transmit a message. In this paper, we define a more sophisticated P-NET model, which considers the actual token utilisation. We then analyse the possibility of implementing a local priority-based scheduling policy to improve the real-time behaviour of P-NET.

Communication response time in P-NET networks: worst-case analysis considering the actual token utilisation

Fieldbus networks aim at the interconnection of field devices such as sensors, actuators and small controllers. Therefore, they are an effective technology upon which Distributed Computer Controlled Systems (DCCS) can be built. DCCS impose strict timeliness requirements to the communication network. In essence, by timeliness requirements we mean that traffic must be sent and received within a bounded interval, otherwise a timing fault is said to occur. P-NET is a multi-master fieldbus standard based on a virtual token passing scheme. In P-NET each master is allowed to transmit only one message per token visit, which means that in the worst-case the communication response time could be derived considering that the token is fully utilised by all stations. However, such analysis can be proved to be quite pessimistic. In this paper we propose a more sophisticated P-NET timing analysis model, which considers the actual token utilisation by different masters. The major contribution of this model is to provide a less pessimistic, and thus more accurate, analysis for the evaluation of the worst-case communication response time in P-NET fieldbus networks.