PRAM：基于Markov模型的高效日历队列算法*

基于有限生灭过程建立了日历队列的数学模型,提出了一种基于马尔可夫链的动态预测算法(predict resize algorithm based on Markov,PRAM),弥补了上述方法的不足。给出了算法的相关数学分析,并将其实现在J2EE应用服务器OnceAS中。系统实验表明,当事件到达高度密集或到达分布变化剧烈时,该算法可以解决日历队列的性能不稳定问题,使其仍保持出入队时间复杂度O(1)的特性,并且性能更优。     

On-line life history calendar and sensitive topics: A pilot study

The use of the life history calendar (LHC) or the event history calendar as tools for collecting retrospective data has received increasing attention in many fields of social science and medicine. However, little research has examined the use of this method with web-based surveys. In this study, we adapted this method to an on-line setting to collect information about young adults' life histories, sexual behaviors, and substance use. We hypothesized that the LHC method would help respondents to date sensitive and non-sensitive events more precisely than when using a conventional questionnaire. We conducted an experimental design study comparing university students' responses to an on-line LHC and a conventional on-line question list. A test-retest design in which the respondents completed the survey again two weeks later was also applied to test the precision and reliability of the participants' dating of events. The results showed that whereas the numbers of sensitive and non-sensitive events were generally similar for the two on-line questionnaires, the responses obtained with the LHC were more consistent across the two administrations. Analyses of the respondents' on-line behavior while completing the LHC confirmed that respondents used the LHC's graphic interface to correct and reedit previous answers, thus decreasing data errors.     

ATM网络中一种新的动态优先队列控制方案

ATM网络中支持的突发业务如语音、视频和图像等要求提供不同的服务质量.为了满足这些突发业务的各种服务质量要求,主要以马尔可夫到达过程来模拟ATM网络中的两类具有不同QoS要求的突发业务流,并为各种不同业务提供QoS保证.通过使用嵌入马尔可夫链和灵活的辅助措施,获得用户在离开时刻各类业务的队列长度,并可以推导出任意时刻下的业务队列长度,导出延迟和损耗等性能参数.并对所提出的方案进行了仿真分析,结果表明该方案完全可以满足ATM网络中突发业务的服务质量.     

An analytical comparison of two string searching algorithms

Average case analyses of two algorithms to locate the leftmost occurrence of a string Pattern in a string Text are conducted in this paper. One algorithm is based on a straightforward trial-and-error approach, the other one uses a sophisticated stragegy discovered by Knuth, Morris and Pratt (1977).Costs measured are the expected number of comparisons between individual characters. Let Naive and kmp denote the average case complexities of the two algorithms, respectively. We show that 1?(1/c)+(1/c²) is an accurate approximation for the ratio kmp/Naive, provided both Pattern and Text are random strings over an alphabet of size c.In both cases, the application of Markov chain theory is expedient for performing the analysis. However, in order to get rid of complex conditioning, the Markov chain model for the kmp algorithm is based on some heuristics. This approach is believed to be practically sound. Some indication on the complexity that might be involved in an exact average case analysis of the kmp algorithm can be found in the work by Guibas and Odlyzko (1981).     

CPL+: An improved approach for evaluating the local completeness of event logs

Process mining aims at deriving order relations between tasks recorded by event logs in order to construct their corresponding process models. The quality of the results is not only determined by the mining algorithm being used, but also by the quality of the provided event logs. As a criterion of log quality, completeness measures the magnitude of information for process mining covered by an event log. In this paper, we focus on the evaluation of the local completeness of an event log. In particular, we consider the direct succession (DS) relations between the tasks of a business process. Based on our previous work, an improved approach called CPL+ is proposed in this paper. Experiments show that the proposed CPL+ works better than other approaches, on event logs that contain a small amount of traces. Finally, by further investigating CPL+, we also found that the more distinct DSs observed in an event log, the lower the local completeness of the log is.     

An analytical approach to architecture-based software performance and reliability prediction

Conventional approaches to analyze the behavior of software applications are black box based, that is, the software application is treated as a whole and only its interactions with the outside world are modeled. The black box approaches ignore information about the internal structure of the application and the behavior of the individual parts. Hence, they are inadequate to model the behavior of a realistic software application, which is likely to be made up of several interacting parts. Architecture-based analysis, which seeks to assess the behavior of a software application taking into consideration the behavior of its parts and the interactions among the parts is thus essential. Most of the research in the area of architecture-based analysis has been devoted to developing analytical models, with very little, if any effort being devoted to how these models might be applied to real software applications. In order to apply these models to software applications, methods must be developed to extract the parameters of the analytical models from information collected during the execution of the application. In this paper, we present an experimental approach to extract the parameters of architecture-based models from code coverage measurements obtained during the execution of the application. To facilitate this, we use a coverage analysis tool called automatic test analyzer in C (ATAC), which is a part of Telcordia Software Visualization and Analysis Toolsuite (TSVAT) developed at Telcordia Technologies. We demonstrate the approach by predicting the performance and reliability of an application called Symbolic Hierarchical Automated Reliability Predictor (SHARPE), which has been widely used to solve stochastic models of reliability, performance and performability.     

The pairing heap: A new form of self-adjusting heap

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called theFibonacci heap. Although theoretically efficient, Fibonacci heaps are complicated to implement and not as fast in practice as other kinds of heaps. In this paper we describe a new form of heap, called thepairing heap, intended to be competitive with the Fibonacci heap in theory and easy to implement and fast in practice. We provide a partial complexity analysis of pairing heaps. Complete analysis remains an open problem.Research partially supported by National Science Foundation Grant MCS 82-04031 and by Bell Communications ResearchResearch partially supported by National Science Foundation Grant DCR 85-14922     

一种轮询协议中心站的性能分析

在基本轮询协议的基础上介绍了已有的排队优先权站点耗尽型轮询协议的操作原则,该协议可以优化中心站的延迟特性。通过嵌入马尔科夫链和构造队列母函数的方法,求解出了平衡状态下中心站的队列长度,并通过仿真进行了验证,同时通过仿真方法获得了系统的延迟特性。仿真结果表明,该协议在系统业务量强度较大时,中心站也具有良好的延迟特性。     

An evaluation of the run-time and task-based performance of event detection techniques for Twitter

Twitter׳s increasing popularity as a source of up-to-date news and information about current events has spawned a body of research on event detection techniques for social media data streams. Although all proposed approaches provide some evidence as to the quality of the detected events, none relate this task-based performance to their run-time performance in terms of processing speed, data throughput, or memory usage. In particular, neither a quantitative nor a comparative evaluation of these aspects has been performed to date. In this article, we study the run-time and task-based performance of several state-of-the-art event detection techniques for Twitter. In order to reproducibly compare run-time performance, our approach is based on a general-purpose data stream management system, whereas task-based performance is automatically assessed based on a series of novel measures.     

Simulation-based optimization of Markov decision processes: An empirical process theory approach

We generalize and build on the PAC Learning framework for Markov Decision Processes developed in Jain and Varaiya (2006). We consider the reward function to depend on both the state and the action. Both the state and action spaces can potentially be countably infinite. We obtain an estimate for the value function of a Markov decision process, which assigns to each policy its expected discounted reward. This expected reward can be estimated as the empirical average of the reward over many independent simulation runs. We derive bounds on the number of runs needed for the convergence of the empirical average to the expected reward uniformly for a class of policies, in terms of the V-C or pseudo dimension of the policy class. We then propose a framework to obtain an ?-optimal policy from simulation. We provide sample complexity of such an approach.     

Approximation of event probabilities in noisy cellular processes

Molecular noise, which arises from the randomness of the discrete events in the cell, significantly influences fundamental biological processes. Discrete-state continuous-time stochastic models (CTMC) can be used to describe such effects, but the calculation of the probabilities of certain events is computationally expensive.We present a comparison of two analysis approaches for CTMC. On one hand, we estimate the probabilities of interest using repeated Gillespie simulation and determine the statistical accuracy that we obtain. On the other hand, we apply a numerical reachability analysis that approximates the probability distributions of the system at several time instances. We use examples of cellular processes to demonstrate the superiority of the reachability analysis if accurate results are required.     

A class of high performance Maekawa-type algorithms for distributed systems under heavy demand

Summary Distributed Mutual Exclusion algorithms have been mainly compared using the number of messages exchanged per critical section execution. In such algorithms, no attention has been paid to the serialization order of the requests. Indeed, they adopt FCFS discipline. Conversely, the insertion of priority serialization disciplines, such as Short-Job-First, Head-Of-Line, Shortest-Remaining-Job-First etc., can be useful in many applications to optimize some performance indices. However, such priority disciplines are prone to starvation. The goal of this paper is to investigate and evaluate the impact of the insertion of a priority discipline in Maekawa-type algorithms. Priority serialization disciplines will be inserted by means of agated batch mechanism which avoids starvation. In a distributed algorithm, such a mechanism needs synchronizations among the processes. In order to highlight the usefulness of the priority based serialization discipline, we show how it can be used to improve theaverage response time compared to the FCFS discipline. The gated batch approach exhibits other advantages: algorithms are inherently deadlock-free and messages do not need to piggyback timestamps. We also show that, under heavy demand, algorithms using gated batch exchange less messages than Maekawa-type algorithms per critical section excution. Roberto Baldoni was born in Rome on February 1, 1965. He received the Laurea degree in electronic engineering in 1990 from the University of Rome La Sapienza and the Ph.D. degree in Computer Science from the University of Rome La Sapienza in 1994. Currently, he is a researcher in computer science at IRISA, Rennes (France). His research interests include operating systems, distributed algorithms, network protocols and real-time multimedia applications. Bruno Ciciani received the Laurea degree in electronic engineering in 1980 from the University of Rome La Sapienza. From 1983 to 1991 he has been a researcher at the University of Rome Tor Vergata. He is currently full professor in Computer Science at the University of Rome La Sapienza. His research activities include distributed computer systems, fault-tolerant computing, languages for parallel processing, and computer system performance and reliability evaluation. He has published in IEEE Trans. on Computers, IEEE Trans. on Knowledge and Data Engineering, IEEE Trans. on Software Engineering and IEEE Trans. on Reliability. He is the author of a book titled Manufactoring Yield Evaluation of VLSI/WSI Systems to be published by IEEE Computer Society Press.This research was supported in part by the Consiglio Nazionale delle Ricerche under grant 93.02294.CT12This author is also supported by a grant of the Human Capital and Mobility project of the European Community under contract No. 3702 CABERNET     

Industrial environmental performance evaluation: A Markov-based model considering data uncertainty

Commonly, operational aspects of an industrial process are not included when evaluating the process environmental performance. These aspects are important as operational failures can intensify adverse environmental impacts or can diminish the chance of making any amelioration. This paper proposes to include these operational aspects by applying a method called Industrial Environmental Performance Evaluation. To have a reliable environmental performance measure for assisting policy-making in an organization, two types of uncertainty are considered in the proposed method. The first type is the epistemic uncertainty due to imperfect knowledge about the environmental impacts of the process. Epistemic uncertainty is considered by using the potential probability of material release during operating and non-operating periods of the process. The second type is aleatory uncertainty due to potential stochastic behaviour of the process. Aleatory uncertainty is modelled through a Markov-based model and is considered by the state probability distribution vectors. The proposed method is employed to analyze an existing formaldehyde production process as a case study. The analysis shows the relation between environmental and operational performances of the process. Process owners can use this analysis for improving the environmental and operational aspects of their process and achieve accuracy in their environmental decisions.     

A model-driven approach for facilitating user-friendly design of complex event patterns

Complex Event Processing (CEP) is an emerging technology which allows us to efficiently process and correlate huge amounts of data in order to discover relevant or critical situations of interest (complex events) for a specific domain. This technology requires domain experts to define complex event patterns, where the conditions to be detected are specified by means of event processing languages. However, these experts face the handicap of defining such patterns with editors which are not user-friendly enough. To solve this problem, a model-driven approach for facilitating user-friendly design of complex event patterns is proposed and developed in this paper. Besides, the proposal has been applied to different domains and several event processing languages have been compared. As a result, we can affirm that the presented approach is independent both of the domain where CEP technology has to be applied to and of the concrete event processing language required for defining event patterns.     

The estimation of probability distribution of SDE by only one sample trajectory

This paper focuses on the method of the simulation of a stochastic system and the main method of our paper is the Monte Carlo computation simulation method. Taking the stochastic Logistic equation as an example, we present the simulation of the sample trajectory by Euler scheme and the invariant probability distribution of stochastic differential equations with the Monte Carlo method. We also compare the simulation result with the analytical result for the autonomous stochastic Logistic model. Moreover, the stochastic Logistic equation with Markovian switching which is described by a Markov chain taking values in a finite state space is considered.     

Bayesian approach, theory of empirical risk minimization. Comparative analysis

Error estimates of empirical-risk minimization methods for an infinite number of decision rules are analyzed. Optimal deterministic estimates of the error of the Bayesian classification procedure for independent features are obtained based on averaging over a great number of training samples as a control. For the Boolean case, the Bayesian procedure is equivalent to a classification procedure based on a separating hyperplane. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 39–49, November–December 2008.     

An empirical comparison of learning algorithms for nonparametric scoring: the TreeRank algorithm and other methods

The TreeRank algorithm was recently proposed in [1] and [2] as a scoring-based method based on recursive partitioning of the input space. This tree induction algorithm builds orderings by recursively optimizing the Receiver Operating Characteristic curve through a one-step optimization procedure called LeafRank. One of the aim of this paper is the in-depth analysis of the empirical performance of the variants of TreeRank/LeafRank method. Numerical experiments based on both artificial and real data sets are provided. Further experiments using resampling and randomization, in the spirit of bagging and random forests are developed [3, 4] and we show how they increase both stability and accuracy in bipartite ranking. Moreover, an empirical comparison with other efficient scoring algorithms such as RankBoost and RankSVM is presented on UCI benchmark data sets.     

Markov-chain model and algorithmic procedure for the performance analysis of closed cyclic queues

This paper presents a model and an algorithmic procedure to analyze closed cyclic queues that are subject to blocking. We consider the first two moments of the processing time and present the fitting of phase-type distributions such that the number of phases and transitions is minimal. Using phase-type distributions, we enable the analysis of queueing systems with processing times with any coefficient of variation. We model the closed cyclic queues subject to blocking as continuous-time Markov chains. The implementation procedure covers the state-space generation and the determination of the infinitesimal generator matrix. Apart from rounding errors, we obtain exact results for the queueing model this way. The results are useful as reference values for the output of approximate approaches. Further, the algorithmic procedure enables a repeated analysis of different configuration alternatives as needed in optimization procedures. Though the method is very fast for small cyclic queues, it takes a long computation time for larger systems. Furthermore, the size of the queueing model to be analyzed is restricted due to the limited working memory with its present-day capacity. In a numerical study, the computation times for different configurations are investigated, limits in the size of the applicable queueing model are given, and numerical results of the performance measures are provided.     

MEdit4CEP-CPN: An approach for complex event processing modeling by prioritized colored petri nets

Complex Event Processing (CEP) is an event-based technology that allows us to process and correlate large data streams in order to promptly detect meaningful events or situations and respond to them appropriately. CEP implementations rely on the so-called Event Processing Languages (EPLs), which are used to implement the specific event types and event patterns to be detected for a particular application domain. To spare domain experts this implementation, the MEdit4CEP approach provides them with a graphical modeling editor for CEP domain, event pattern and action definition. From these graphical models, the editor automatically generates a corresponding Esper EPL code. Nevertheless, the generated code is syntactically but not semantically validated. To address this problem, MEdit4CEP is extended in this paper by Prioritized Colored Petri Net (PCPN) formalism, resulting in the MEdit4CEP-CPN approach. This approach provides both a novel PCPN domain-specific modeling language and a graphical editor. By using model transformations, event pattern models can be automatically transformed into PCPN models, and then into the corresponding PCPN code executable by CPN Tools. In addition, by using PCPNs we can compare the expected output with the actual output and can even conduct a quantitative analysis of the scenarios of interest. To illustrate our approach, we have conducted an air quality level detection case study and we show how this novel approach facilitates the modeling, simulation, analysis and semantic validation of complex event-based systems.