Perturbation Analysis and Optimization of Multiclass Multiobjective Stochastic Flow Models

Stochastic Flow Models (SFMs) are stochastic hybrid systems that abstract the dynamics of many complex discrete event systems and provide the basis for their control and optimization. SFMs have been used to date to study systems with a single user class or some multiclass settings in which performance metrics are not class-dependent. In this paper, we develop a SFM framework for multiple classes and class-dependent performance objectives, where competing classes employ threshold control policies and service is provided on a First Come First Serve (FCFS) basis. In this framework, we analyze new phenomena that result from the interaction of the different classes and give rise to a new class of “induced” events that capture delays in the SFM dynamics. We derive Infinitesimal Perturbation Analysis (IPA) estimators for derivatives of various class-dependent objectives, and use them as the basis for on-line optimization algorithms that apply to the underlying discrete event system (not the SFM). This allows us to contrast system-centric and user-centric objectives, thus putting the resource contention problem in a game framework. The unbiasedness of IPA estimators is established and numerical results are provided to illustrate the effectiveness of our method for the case where there are no constraints on the controllable thresholds and to demonstrate the gap between the results of system-centric optimization and user-centric optimization.     

Algorithm,software, and hardware optimizations for Delaunay mesh generation on simultaneous multithreaded architectures

This article focuses on the optimization of PCDM, a parallel, two-dimensional (2D) Delaunay mesh generation application, and its interaction with parallel architectures based on simultaneous multithreading (SMT) processors. We first present the step-by-step effect of a series of optimizations on performance. These optimizations improve the performance of PCDM by up to a factor of six. They target issues that very often limit the performance of scientific computing codes. We then evaluate the interaction of PCDM with a real SMT-based SMP system, using both high-level metrics, such as execution time, and low-level information from hardware performance counters.     

Efficient search based on content similarity over self-organizing P2P networks

The advent of the World Wide Web has made an enormous amount of information available to everyone and the widespread use of digital equipment enables end-users (peers) to produce their own digital content. This vast amount of information requires scalable data management systems. Peer-to-peer (P2P) systems have so far been well established in several application areas, with file-sharing being the most prominent. The next challenge that needs to be addressed is (more complex) data sharing, management and query processing, thus facilitating the delivery of a wide spectrum of novel data-centric applications to the end-user, while providing high Quality-of-Service. In this paper, we propose a self-organizing P2P system that is capable to identify peers with similar content and intentionally assign them to the same super-peer. During content retrieval, fewer super-peers need to be contacted and therefore efficient similarity search is supported, in terms of reduced network traffic and contacted peers. Our approach increases the responsiveness and reliability of a P2P system and we demonstrate the advantages of our approach using large-scale simulations.     

Two heads better than one: pattern discovery in time-evolving multi-aspect data

Data stream values are often associated with multiple aspects. For example each value observed at a given time-stamp from environmental sensors may have an associated type (e.g., temperature, humidity, etc.) as well as location. Time-stamp, type and location are the three aspects, which can be modeled using a tensor (high-order array). However, the time aspect is special, with a natural ordering, and with successive time-ticks having usually correlated values. Standard multiway analysis ignores this structure. To capture it, we propose 2 Heads Tensor Analysis (2-heads), which provides a qualitatively different treatment on time. Unlike most existing approaches that use a PCA-like summarization scheme for all aspects, 2-heads treats the time aspect carefully. 2-heads combines the power of classic multilinear analysis with wavelets, leading to a powerful mining tool. Furthermore, 2-heads has several other advantages as well: (a) it can be computed incrementally in a streaming fashion, (b) it has a provable error guarantee and, (c) it achieves significant compression ratio against competitors. Finally, we show experiments on real datasets, and we illustrate how 2-heads reveals interesting trends in the data. This is an extended abstract of an article published in the Data Mining and Knowledge Discovery journal.     

Computer methods for automating preoperative dental implant planning: implant positioning and size assignment

The paper presents computer-aided methods that allocate a dental implant and suggest its size, during the pre-operative planning stage, in conformance with introduced optimization criteria and established clinical requirements. Based on computed tomography data of the jaw and prosthesis anatomy, single tooth cases are planned for the best-suited implant insertion at a user-defined region. An optimum implantation axis line is produced and cylindrical implants of various candidate sizes are then automatically positioned, while their occlusal end is leveled to bone ridge, and evaluated. Radial safety margins are used for the assessment of the implant safety distance from neighboring anatomical structures and bone quantity and quality are estimated and taken into consideration. A case study demonstrates the concept and allows for its discussion.     

Optimal Control of Two-Stage Discrete Event Systems with Real-Time Constraints

We consider discrete event systems (DES) involving tasks with real-time constraints and seek to control processing times so as to minimize a cost function subject to each task meeting its own constraint. When tasks are processed over a single stage, it has been shown that there are structural properties of the optimal sample path that lead to very efficient solutions of such problems. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, these properties no longer hold and no obvious extensions are known. We consider a two-stage problem with homogeneous cost functions over all tasks at each stage and derive several new optimality properties. These properties lead to the idea of introducing “virtual” deadlines at the first stage, thus partially decoupling the stages so that the known efficient solutions for single-stage problems can be used. We prove that the solution obtained by an iterative virtual deadline algorithm (VDA) converges to the global optimal solution of the two-stage problem and illustrate the efficiency of the VDA through numerical examples.

Quantifiable data mining using ratio rules

Association Rule Mining algorithms operate on a data matrix (e.g., customers products) to derive association rules [AIS93b, SA96]. We propose a new paradigm, namely, Ratio Rules, which are quantifiable in that we can measure the “goodness” of a set of discovered rules. We also propose the “guessing error” as a measure of the “goodness”, that is, the root-mean-square error of the reconstructed values of the cells of the given matrix, when we pretend that they are unknown. Another contribution is a novel method to guess missing/hidden values from the Ratio Rules that our method derives. For example, if somebody bought $10 of milk and $3 of bread, our rules can “guess” the amount spent on butter. Thus, unlike association rules, Ratio Rules can perform a variety of important tasks such as forecasting, answering “what-if” scenarios, detecting outliers, and visualizing the data. Moreover, we show that we can compute Ratio Rules in a single pass over the data set with small memory requirements (a few small matrices), in contrast to association rule mining methods which require multiple passes and/or large memory. Experiments on several real data sets (e.g., basketball and baseball statistics, biological data) demonstrate that the proposed method: (a) leads to rules that make sense; (b) can find large itemsets in binary matrices, even in the presence of noise; and (c) consistently achieves a “guessing error” of up to 5 times less than using straightforward column averages. Received: March 15, 1999 / Accepted: November 1, 1999     

Estimation of the Water Resources Potential in the Island System of the Aegean Archipelago,Greece

Abstract

The present paper tries to estimate the surface water resources potential in some of the major Aegean islands in an effort to provide a means for the continuous development of the region, and, by extension, for similar areas around the world. The islands have to confront the challenge of surviving in a semiarid environment under the constraints of uneven water resources distribution both in space and time. In addition to these, tourism development, industrialization and highly water consumptive life styles have exacerbated perennial problems in water resources and water resources management. The framework of the present effort has a two-prong emphasis. In the first part, a simulation model is presented, which tries to estimate the potential surface runoff under physical, structural organizational, and institutional constraints. The methodology and the premises of the simulation process are delineated. In the second part, the results of the model's application in distinct cases are demarcated. The final product, namely the model and the resulting runoff coefficients, are presented in the form of a standard, which may provide practitioners in the field as well as decisionmakers the means for an initial reference in pertinent developmental efforts. Finally, the conclusions and recommendations raise the question of ecosystem resilience and point towards the urgent and continuous need for the application of integrated water resources management principles.