Shape deformation in continuous map generalization

Given a collection of regions on a map, we seek a method of continuously altering the regions as the scale is varied. This is formalized and brought to rigor as well-defined problems in homotopic deformation. We ask the regions to preserve topology, area-ratios, and relative position as they change over time. A solution is presented using differential methods and computational geometric techniques. Most notably, an application of this method is used to provide an algorithm to obtain cartograms.

An Investigation of Cheating in Online Games

Cheating is rampant in current gameplay on the Internet. However, it isn't as well understood as we might expect. The authors summarize the various known methods of cheating and define a taxonomy of online game cheating with respect to the underlying vulnerability, consequence, and cheating principal. This taxonomy provides a systematic introduction to the characteristics of cheats in online games and how they can arise. Although cheating in online games is largely due to various security failures, the four traditional aspects of security—confidentiality, integrity, availability, and authenticity—are insufficient to explain it. Instead, fairness becomes a vital additional aspect, and its enforcement provides a convincing perspective for understanding security techniques' role in developing and operating online games.     

Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor

We consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the processes to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. We assume that a processor running at speed s uses power s ^α for some constant α>1. For processes that may have side effects or that are not checkpointable, we show an W(m^(a-1)/a2)\Omega(m^{(\alpha -1)/\alpha^{2}}) bound on the competitive ratio of any randomized algorithm. For checkpointable processes without side effects, we give an O(log m)-competitive algorithm. Thus for processes that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable processes without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log ^1/α m) on the competitive ratio of any randomized algorithm for checkpointable processes without side effects.     

Influences on the formation and evolution of Physarum polycephalum inspired emergent transport networks

The single-celled organism Physarum polycephalum efficiently constructs and minimises dynamical nutrient transport networks resembling proximity graphs in the Toussaint hierarchy. We present a particle model which collectively approximates the behaviour of Physarum. We demonstrate spontaneous transport network formation and complex network evolution using the model and show that the model collectively exhibits quasi-physical emergent properties, allowing it to be considered as a virtual computing material. This material is used as an unconventional method to approximate spatially represented geometry problems by representing network nodes as nutrient sources. We demonstrate three different methods for the construction, evolution and minimisation of Physarum-like transport networks which approximate Steiner trees, relative neighbourhood graphs, convex hulls and concave hulls. We extend the model to adapt population size in response to nutrient availability and show how network evolution is dependent on relative node position (specifically inter-node angle), sensor scaling and nutrient concentration. We track network evolution using a real-time method to record transport network topology in response to global differences in nutrient concentration. We show how Steiner nodes are utilised at low nutrient concentrations whereas direct connections to nutrients are favoured when nutrient concentration is high. The results suggest that the foraging and minimising behaviour of Physarum-like transport networks reflect complex interplay between nutrient concentration, nutrient location, maximising foraging area coverage and minimising transport distance. The properties and behaviour of the synthetic virtual plasmodium may be useful in future physical instances of distributed unconventional computing devices, and may also provide clues to the generation of emergent computation behaviour by Physarum.     

SPI success factors within product usability evaluation

This article presents an experience report where we compare 8 years of experience of product related usability testing and evaluation with principles for software process improvement (SPI). In theory the product and the process views are often seen to be complementary, but studies of industry have demonstrated the opposite. Therefore, more empirical studies are needed to understand and improve the present situation. We find areas of close agreement as well as areas where our work illuminates new characteristics. It has been identified that successful SPI is dependent upon being successfully combined with a business orientation. Usability and business orientation also have strong connections although this has not been extensively addressed in SPI publications. Reasons for this could be that usability focuses on product metrics whilst today's SPI mainly focuses on process metrics. Also because today's SPI is dominated by striving towards a standardized, controllable, and predictable software engineering process; whilst successful usability efforts in organisations are more about creating a creative organisational culture advocating a useful product throughout the development and product life cycle. We provide a study and discussion that supports future development when combining usability and product focus with SPI, in particular if these efforts are related to usability process improvement efforts.     

Scalability issues with using FSMWeb to test web applications

Web applications are fast becoming more widespread, larger, more interactive, and more essential to the international use of computers. It is well understood that web applications must be highly dependable, and as a field we are just now beginning to understand how to model and test Web applications. One straightforward technique is to model Web applications as finite state machines. However, large numbers of input fields, input choices and the ability to enter values in any order combine to create a state space explosion problem. This paper evaluates a solution that uses constraints on the inputs to reduce the number of transitions, thus compressing the FSM. The paper presents an analysis of the potential savings of the compression technique and reports actual savings from two case studies.     

Modeling presentation layers of web applications for testing

Web software applications have become complex, sophisticated programs that are based on novel computing technologies. Their most essential characteristic is that they represent a different kind of software deployment—most of the software is never delivered to customers’ computers, but remains on servers, allowing customers to run the software across the web. Although powerful, this deployment model brings new challenges to developers and testers. Checking static HTML links is no longer sufficient; web applications must be evaluated as complex software products. This paper focuses on three aspects of web applications that are unique to this type of deployment: (1) an extremely loose form of coupling that features distributed integration, (2) the ability that users have to directly change the potential flow of execution, and (3) the dynamic creation of HTML forms. Taken together, these aspects allow the potential control flow to vary with each execution, thus the possible control flows cannot be determined statically, prohibiting several standard analysis techniques that are fundamental to many software engineering activities. This paper presents a new way to model web applications, based on software couplings that are new to web applications, dynamic flow of control, distributed integration, and partial dynamic web application development. This model is based on the notion of atomic sections, which allow analysis tools to build the analog of a control flow graph for web applications. The atomic section model has numerous applications in web applications; this paper applies the model to the problem of testing web applications.     

Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models

We demonstrate that certain large-clique graph triangulations can be useful for reducing computational requirements when making queries on mixed stochastic/deterministic graphical models. This is counter to the conventional wisdom that triangulations that minimize clique size are always most desirable for use in computing queries on graphical models. Many of these large-clique triangulations are non-minimal and are thus unattainable via the popular elimination algorithm. We introduce ancestral pairs as the basis for novel triangulation heuristics and prove that no more than the addition of edges between ancestral pairs needs to be considered when searching for state space optimal triangulations in such graphs. Empirical results on random and real world graphs are given. We also present an algorithm and correctness proof for determining if a triangulation can be obtained via elimination, and we show that the decision problem associated with finding optimal state space triangulations in this mixed setting is NP-complete.