Rehabilitation of an unloved child: semi‐splaying

Splay trees are widely considered as the classic examples of self‐adjusting binary search trees and are part of most courses on data structures and algorithms. Already in the first seminal paper on splay trees (J. Assoc. Comput. Mach. 1985; 32(3):652–686) alternative operations were introduced, among which is semi‐splaying. On the one hand, the analysis of semi‐splaying gives a smaller constant for the amortized complexity, but on the other hand the authors write: Whether any version of semi‐splaying is an improvement over splaying depends on the access sequence. Semi‐splaying may be better when the access pattern is stable, but splaying adapts much faster to changes in usage. Maybe this sentence was the reason that nobody seriously ran tests to compare the performance of semi‐splaying and splaying. Semi‐splaying is conceptually simpler than splaying, has the same asymptotic amortized complexity and, as will be clear from empirical data presented in this paper, the practical performance is better for a very broad variety of access patterns. Therefore, its efficiency is a good reason to use semi‐splaying for applications instead of its more prominent brother. Moreover, its simplicity also makes it very attractive for teaching purposes. Copyright © 2008 John Wiley & Sons, Ltd.     

Cost‐effective queue schemes for reducing head‐of‐line blocking in fat‐trees

The fat‐tree is one of the most common topologies among the interconnection networks of the systems currently used for high‐performance parallel computing. Among other advantages, fat‐trees allow the use of simple but very efficient routing schemes. One of them is a deterministic routing algorithm that has been recently proposed, offering a similar (or better) performance than adaptive routing while reducing complexity and guaranteeing in‐order packet delivery. However, as other deterministic routing proposals, this deterministic routing algorithm cannot react when high traffic loads or hot‐spot traffic scenarios produce severe contention for the use of network resources, leading to the appearance of Head‐of‐Line (HoL) blocking, which spoils the network performance. In that sense, we describe in this paper two simple, cost‐effective strategies for dealing with the HoL‐blocking problem that may appear in fat‐trees with the aforementioned deterministic routing algorithm. From the results presented in the paper, we conclude that, in the mentioned environment, these proposals considerably reduce HoL‐blocking without significantly increasing switch complexity and the required silicon area. Copyright © 2011 John Wiley & Sons, Ltd.     

Partial match queries in relaxed multidimensional search trees

Partial match queries arise frequently in the context of large databases, where each record contains a distinct multidimensional key, that is, the key of each record is aK-tuple of values. The components of a key are called thecoordinates orattributes of the key. In a partial match query we specify the value ofs attributes, 0<s<K, and leave the remainingK —s attributes unspecified. The goal is to retrieve all the records in the database that match the specified attributes. In this paper we present several results about the average performance and variance of partial matches in relaxedK-dimensional trees (search trees and digital tries). These data structures are variants of the well knownK d-trees andK d-tries. In relaxed trees the sequence of attributes used to guide a query is explicitly stored at the nodes of the tree and randomly generated and, in general, will be different for different search paths. In the standard variants, the sequence of attributes that guides a query examines the attributes in a cyclic fashion, fixed and identical for all search paths. We show that the probabilistic analysis of the relaxed multidimensional trees is very similar to that of standardK d-trees andK d-tries, and also to the analysis of quadtrees. In fact, besides the average cost and variance of partial match in relaxedK d-trees andK d-tries, we also obtain the variance of partial matches in two-dimensional quadtrees. We also compute the average cost of partial matches in other relaxed multidimensional digital tries, namely, relaxedK d-Patricia and relaxedK d-digital search trees. This research was supported by Acciones Integradas Hispano-Austríacas HU1997-0016 (Austrian-Spanish Scientific Exchange Program). The first author was also supported by ESPRIT LTR 20244 (ALCOM IT), CICYT TIC97-1475-CE, DGES PB95-0787 (KOALA), and CIRIT 1997SGR-00366 (SGR). The second author was also supported by the Austrian Research Society (FWF) under Project P12599-MAT. Online publication October 13, 2000.     

Relativistic red‐black trees

This paper presents algorithms for concurrently reading and modifying a red‐black tree (RBTree). The algorithms allow wait‐free, linearly scalable lookups in the presence of concurrent inserts and deletes. They have deterministic response times for a given tree size and uncontended read performance that is at least 60% faster than other known approaches. The techniques used to derive these algorithms arise from a concurrent programming methodology called relativistic programming. Relativistic programming introduces write‐side delay primitives that allow the writer to pay most of the cost of synchronization between readers and writers. Only minimal synchronization overhead is placed on readers. Relativistic programming avoids unnecessarily strict ordering of read and write operations while still providing the capability to enforce linearizability. This paper shows how relativistic programming can be used to build a concurrent RBTree with synchronization‐free readers and both lock‐based and transactional memory‐based writers. Copyright © 2013 John Wiley & Sons, Ltd.     

Why We Distort in Self‐Report: Predictors of Self‐Report Errors in Video Game Play

Using Cognitive Dissonance and Balance Theory, this study investigates factors that predict how and why MMO players inaccurately report their game playing time. It was hypothesized that players belonging to categories other than the stereotypical game player (e.g. younger, less educated, male) would be likely to underreport playing time. It was also hypothesized that those players who held less positive attitudes toward the game would be more likely to underreport their playing time. Comparing people's self‐reported weekly usage of an MMO, EverQuest II, with their actual average weekly usage of the game, data showed that age, education, lack of enjoyment playing the game, and lack of an online sense of community predicted greater levels of underreporting.     

Multi‐Variable Direct Self‐Organizing Fuzzy Neural Network Control for Wastewater Treatment Process

A multi‐variable direct self‐organizing fuzzy neural network control (M‐DSNNC) method is proposed for the multi‐variable control of the wastewater treatment process (WWTP). In this paper, the proposed control system is an essential multi‐variable control method for the WWTP. No exact plant model is required, which avoids the difficulty of establishing the mathematics model of WWTP. The M‐DSNNC system is comprised of a fuzzy neural network controller and a compensation controller. The fuzzy neural network is used for approximating the ideal control law under a general nonlinear system. Moreover, the neural network is designed in a self‐organizing mode to adapt the uncertainty environment. Simulation results, based on the international benchmark simulation model No.1 (BSM1), demonstrate that the control accuracy is improved under the proposed M‐DSNNC method, and the controller has a much stronger decoupling ability.     

Self‐regulation during e‐learning: using behavioural evidence from navigation log files

The current paper examined the relationship between perceived characteristics of the learning environment in an e‐module in relation to test performance among a group of e‐learners. Using structural equation modelling, the relationship between these variables is further explored in terms of the proposed double mediation as outlined by Ning and Downing. These authors initially proposed that motivation and self‐regulation strategies are mediators between the perception of the learning environment and performance. In our replication and extension study, we substituted self‐reported self‐regulation with behavioural indicators of self‐regulation using navigation log files and focused on test‐taking rather than general motivation. We proposed that navigational patterns captured using log files can also help deduce self‐regulation in e‐modules and provide information in the absence of self‐reports. Path analyses provide partial support for our navigational hypotheses and the model. Implications of our results for the use of e‐module data and conclusions based on navigation are discussed.     

Improved methods for extracting frequent itemsets from interim‐support trees

Mining association rules in relational databases is a significant computational task with lots of applications. A fundamental ingredient of this task is the discovery of sets of attributes (itemsets) whose frequency in the data exceeds some threshold value. In this paper we describe two algorithms for completing the calculation of frequent sets using a tree structure for storing partial supports, called interim‐support (IS) tree. The first of our algorithms (T‐Tree‐First (TTF)) uses a novel tree pruning technique, based on the notion of (fixed‐prefix) potential inclusion, which is specially designed for trees that are implemented using only two pointers per node. This allows to implement the IS tree in a space‐efficient manner. The second algorithm (P‐Tree‐First (PTF)) explores the idea of storing the frequent itemsets in a second tree structure, called the total support tree (T‐tree); the main innovation lies in the use of multiple pointers per node, which provides rapid access to the nodes of the T‐tree and makes it possible to design a new, usually faster, method for updating them. Experimental comparison shows that these techniques result in considerable speedup for both algorithms compared with earlier approaches that also use IS trees (Principles of Data Mining and Knowledge Discovery, Proceedings of the 5th European Conference, PKDD, 2001, Freiburg, September 2001 (Lecture Notes in Artificial Intelligence, vol. 2168). Springer: Berlin, Heidelberg, 54–66; Journal of Knowledge‐Based Syst. 2000; 13 :141–149). Further comparison between the two new algorithms, shows that the PTF is generally faster on instances with a large number of frequent itemsets, provided that they are relatively short, whereas TTF is more appropriate whenever there exist few or quite long frequent itemsets; in addition, TTF behaves well on instances in which the densities of the items of the database have a high variance. Copyright © 2008 John Wiley & Sons, Ltd.     

Multi‐Tracking of First Order Multi‐Agent Networks Via Self‐Triggered Control

A multi‐tracking problem of multi‐agent networks is investigated in this paper where multi‐tracking refers to that the states of multiple agents in each subnetwork asymptotically converge to the same desired trajectory in the presence of information exchanges among subnetworks. The multi‐tracking of first order multi‐agent networks with directed topologies was studied. Self‐triggered protocols were proposed along with triggering functions to solve the stationary multi‐tracking and bounded dynamic multi‐tracking. The self‐triggered scheduling is obtained, and the system does not exhibit Zeno behavior. Numerical examples are provided to illustrate the effectiveness of the obtained criteria.     

Self‐oscillating mixer using six port power divider

A self‐oscillating mixer (SOM) that uses a six port microstrip power divider is presented in this article. The oscillation and mixing functions are executed using a pair of identical GaAs field effect transistors. The power division and combination of the RF and local oscillator (LO) signals involved in the operation are implemented using the six port network. The RF input port of the proposed SOM is totally isolated from the operation of the LO which is a desirable feature in many applications. The proposed structure can work as a stand‐alone oscillator with a frequency of 4.71 GHz and a power level of 16.1 dBm. When fed with a RF signal, the proposed structure becomes a fully functional SOM exhibiting a conversion gain of 5.2 dBm. The simulation and measurement results of the proposed SOM are presented to validate the design concept. © 2014 Wiley Periodicals, Inc. Int J RF and Microwave CAE 25:269–276, 2015.     

Distributed Control for Coupled Nonholonomic Mobile Robots under the Event‐Triggered and Self‐Triggered Frameworks

In this paper, a coordinated tracking problem for coupled nonholonomic mobile robots is considered. An event‐triggered control strategy is first proposed to guarantee that the robots can form a prespecified geometric pattern while the centroid of the geometric pattern can track a reference signal. The results are then extended to the self‐triggered case, where continuous monitoring of the agent states is not needed. The stability of the system is proved with the aid of the Lyapunov techniques. Finally, numerical examples are presented to verify the validity of the theoretical results.     

Self‐efficacy,learning method appropriation and software skills acquisition in learner‐controlled CSSTS environments

A computer‐simulated software training system (CSSTS) delivers a specific form of computer‐based training in which participants are allowed to select various training features within a simulated software environment. Given the growing use of these systems as end‐user training (EUT) aids, there is a need for greater understanding of how participants use these systems, as well as whether participant‐controlled learning environments are truly effective. The present research examines how a particular learner characteristic, software self‐efficacy, drives appropriation in a high learner control, CSSTS environment. Contrary to notions in the literature, results from spreadsheet and database software training courses reveal that pre‐training specific software self‐efficacy constitutes a significant, negative predictor of faithful appropriations of the CSSTS. This research also establishes a positive relationship between faithful appropriation and increases in software self‐efficacy (SSE). In essence, faithful appropriations lead to greater increases in SSE, which influences software skills performance. In addition, the research validates prior EUT research by extending prior findings to a database training environment. A psychometrically sound measure is put forth to capture database self‐efficacy.     

Self‐diplexed antenna based on loading asymmetric grounding‐vias

This article presents a simple and efficient method for the design of a self‐diplexed antenna based on loading asymmetric grounding‐vias. The structure consists of two antenna elements loaded with two asymmetric grounding‐vias, specifying the uplink and downlink operation frequencies. By choosing the appropriate positions of the two grounding‐vias, high isolation between the two antennas can be achieved. To validate the feasibility of the proposed structure, two self‐diplexed antennas with different operational frequencies have been fabricated and tested. Experimental results verify the multi‐functionalities of the proposed compact structure in terms of high isolation and low cross‐polarization discrimination.     

Gpc‐Based Self‐Tuning PI Controller for Speed Servo System of PMSLM

In this paper, a generalized predictive control (GPC)‐based two degrees of freedom (2 DOF) proportional integral (PI) controller is proposed for the speed servo system of a permanent magnet synchronous linear motor (PMSLM). In this new approach, based on a dynamic model of a servo system, a simplified and high‐performance GPC supplies a 2 DOF PI controller with suitable control parameters, according to the varied operating conditions. In previous studies, GPC‐based proportional integral derivative (PID) controllers have been designed using a step‐type or ramp‐type reference input. In our work, however, the speed command for PMSLM usually is required to be a trapezium‐type signal because of the limited travel range. Hence, control performance of a speed servo system using a GPC‐based 2 DOF PI controller is enhanced for tracking a trapezium‐type command. The validity and usefulness of the proposed controller are verified through simulation and experiments.     

Self‐triggered model predictive control for networked control systems based on first‐order hold

In this work, a new self‐triggered model predictive control (STMPC) algorithm is proposed for continuous‐time networked control systems. Compared with existing STMPC algorithms, the proposed STMPC is implemented based on linear interpolation (first‐order hold) rather than the standard zero‐order hold, which helps further reduce the difference between the self‐triggered control signal and the original time‐triggered counterpart and thus reduce the rate of triggering. Based on the first‐order hold implementation, a self‐triggering condition is derived and the corresponding theoretical properties of the closed‐loop system are analyzed. Finally, the comparison between the proposed algorithm and the zero‐order hold–based STMPC is carried out through both theoretical analysis and a simulation example to illustrate the effectiveness of the proposed method.     

Self‐triggered state‐feedback control of linear plants under bounded disturbances

This paper addresses the problem of self‐triggered state‐feedback control for linear plants under bounded disturbances. In a self‐triggered scenario, the controller is allowed to choose when the next sampling time should occur and does so based on the current sampled state and on a priori knowledge about the plant. Besides comparing some existing approaches to self‐triggered control available in the literature, we propose a new self‐triggered control strategy that allows for the consideration of model‐based controllers, a class of controllers that includes as a special case static controllers with a zero‐order hold of the last state measurement. We show that our proposed control strategy renders the solutions of the closed‐loop system globally uniformly ultimately bounded. We further show that there exists a minimum time interval between sampling times and provide a method for computing a lower bound for it. An illustrative example with numerical results is included in order to compare the existing strategies and the proposed one. Copyright © 2014 John Wiley & Sons, Ltd.     

Self‐calibration three‐dimensional light field display based on scalable multi‐LCDs

Approach to achieve self‐calibration three‐dimensional (3D) light field display is investigated in this paper. The proposed 3D light field display is constructed up on spliced multi‐LCDs, lens and diaphragm arrays, and directional diffuser. The light field imaging principle, hardware configuration, diffuser characteristic, and image reconstruction simulation are described and analyzed, respectively. Besides the light field imaging, a self‐calibration method is proposed to improve the imaging performance. An image sensor is deployed to capture calibration patterns projected onto and then reflected by the polymer dispersed liquid crystal film, which is attached to and shaped the diffuser. These calibration components are assembled with the display unit and can be switched between display mode and calibration mode. In the calibration mode, the imperfect imaging relations of optical components are captured and calibrated automatically. We demonstrate our design by implementing the prototype of proposed 3D light field display by using modified off‐the‐shelf products. The proposed approach successfully meets the requirement of real application on scalable configuration, fast calibration, large viewing angular range, and smooth motion parallax.     

Toward Self‐Motivated,Cognitive, Continually Planning Agents

We present a flexible initial framework for defining self‐motivated, self‐aware agents in simulated worlds, planning continuously so as to maximize long‐term rewards. While such agents employ reasoned exploration of feasible sequences of actions and corresponding states, they also behave opportunistically and recover from failure, thanks to their continual plan updates and quest for rewards. Our framework allows for both specific and general (quantified) knowledge and for epistemic predicates such as knowing‐that and knowing‐whether. Because realistic agents have only partial knowledge of their world, the reasoning of the proposed agents uses a weakened closed‐world assumption; this has consequences for epistemic reasoning, in particular introspection. The planning operators allow for quantitative, gradual change and side effects such as the passage of time, changes in distances and rewards, and language production, using a uniform procedural attachment method. Question answering (involving introspection) and experimental runs are shown for our particular agent ME in a simple world, demonstrating the value of continual deliberate, reward‐driven planning. Though the primary merit of agents definable in our framework is that they combine all of the aforementioned features, they can also be configured as single or multiple goal‐seeking agents and as such perform comparably with some recent experimental agents.     

Continuous Self‐Collision Detection for Deformable Surfaces Interacting with Solid Models

In this paper, we propose a new continuous self‐collision detection (CSCD) method for a deformable surface that interacts with a simple solid model. The method is developed based on the radial‐view‐based culling method. Our method is suitable for the deformable surface that has large contact region with the solid model. The deformable surface may consist of small round‐shaped holes. At the pre‐processing stage, the holes of the deformable surface are filled with ghost triangles so as to make the mesh of the deformable surface watertight. An observer primitive (i.e. a point or a line segment) is computed so that it lies inside the solid model. At the runtime stage, the orientations of triangles with respect to the observer primitive are evaluated. The collision status of the deformable surface is then determined. We evaluated our method for several animations including virtual garments. Experimental results show that our method improves the process of CSCD.