1990_能量转换效率达10.2%的非晶硅单结太阳能电池

Probabilistic Model Checking ofan Anonymity SystemVitaly ShmatikovSRI International333Ravenswood AvenueMenlo Park,CA94025U.S.A.shmat@AbstractWe use the probabilistic model checker PRISM to analyze the Crowds system for anonymous Web browsing.This case study demonstrates howprobabilistic model checking techniques can be used to formally analyze se-curity properties of a peer-to-peer group communication system based onrandom message routing among members.The behavior of group mem-bers and the adversary is modeled as a discrete-time Markov chain,and thedesired security properties are expressed as PCTL formulas.The PRISMmodel checker is used to perform automated analysis of the system and ver-ify anonymity guarantees it provides.Our main result is a demonstration ofhow certain forms of probabilistic anonymity degrade when group size in-creases or random routing paths are rebuilt,assuming that the corrupt groupmembers are able to identify and/or correlate multiple routing paths originat-ing from the same sender.1IntroductionFormal analysis of security protocols is a well-establishedfield.Model checking and theorem proving techniques[Low96,MMS97,Pau98,CJM00]have been ex-tensively used to analyze secrecy,authentication and other security properties ofprotocols and systems that employ cryptographic primitives such as public-key en-cryption,digital signatures,etc.Typically,the protocol is modeled at a highly ab-stract level and the underlying cryptographic primitives are treated as secure“black boxes”to simplify the model.This approach discovers attacks that would succeed even if all cryptographic functions were perfectly secure.Conventional formal analysis of security is mainly concerned with security against the so called Dolev-Yao attacks,following[DY83].A Dolev-Yao attacker is a non-deterministic process that has complete control over the communication net-work and can perform any combination of a given set of attacker operations,such as intercepting any message,splitting messages into parts,decrypting if it knows the correct decryption key,assembling fragments of messages into new messages and replaying them out of context,etc.Many proposed systems for anonymous communication aim to provide strong, non-probabilistic anonymity guarantees.This includes proxy-based approaches to anonymity such as the Anonymizer[Ano],which hide the sender’s identity for each message by forwarding all communication through a special server,and MIX-based anonymity systems[Cha81]that blend communication between dif-ferent senders and recipients,thus preventing a global eavesdropper from linking sender-recipient pairs.Non-probabilistic anonymity systems are amenable to for-mal analysis in the same non-deterministic Dolev-Yao model as used for verifica-tion of secrecy and authentication protocols.Existing techniques for the formal analysis of anonymity in the non-deterministic model include traditional process formalisms such as CSP[SS96]and a special-purpose logic of knowledge[SS99].In this paper,we use probabilistic model checking to analyze anonymity prop-erties of a gossip-based system.Such systems fundamentally rely on probabilistic message routing to guarantee anonymity.The main representative of this class of anonymity systems is Crowds[RR98].Instead of protecting the user’s identity against a global eavesdropper,Crowds provides protection against collaborating local eavesdroppers.All communication is routed randomly through a group of peers,so that even if some of the group members collaborate and share collected lo-cal information with the adversary,the latter is not likely to distinguish true senders of the observed messages from randomly selected forwarders.Conventional formal analysis techniques that assume a non-deterministic at-tacker in full control of the communication channels are not applicable in this case. Security properties of gossip-based systems depend solely on the probabilistic be-havior of protocol participants,and can be formally expressed only in terms of relative probabilities of certain observations by the adversary.The system must be modeled as a probabilistic process in order to capture its properties faithfully.Using the analysis technique developed in this paper—namely,formalization of the system as a discrete-time Markov chain and probabilistic model checking of2this chain with PRISM—we uncovered two subtle properties of Crowds that causedegradation of the level of anonymity provided by the system to the users.First,if corrupt group members are able to detect that messages along different routingpaths originate from the same(unknown)sender,the probability of identifyingthat sender increases as the number of observed paths grows(the number of pathsmust grow with time since paths are rebuilt when crowd membership changes).Second,the confidence of the corrupt members that they detected the correct senderincreases with the size of the group.Thefirstflaw was reported independently byMalkhi[Mal01]and Wright et al.[W ALS02],while the second,to the best ofour knowledge,was reported for thefirst time in the conference version of thispaper[Shm02].In contrast to the analysis by Wright et al.that relies on manualprobability calculations,we discovered both potential vulnerabilities of Crowds byautomated probabilistic model checking.Previous research on probabilistic formal models for security focused on(i)probabilistic characterization of non-interference[Gra92,SG95,VS98],and(ii)process formalisms that aim to faithfully model probabilistic properties of crypto-graphic primitives[LMMS99,Can00].This paper attempts to directly model andanalyze security properties based on discrete probabilities,as opposed to asymp-totic probabilities in the conventional cryptographic sense.Our analysis methodis applicable to other probabilistic anonymity systems such as Freenet[CSWH01]and onion routing[SGR97].Note that the potential vulnerabilities we discovered inthe formal model of Crowds may not manifest themselves in the implementationsof Crowds or other,similar systems that take measures to prevent corrupt routersfrom correlating multiple paths originating from the same sender.2Markov Chain Model CheckingWe model the probabilistic behavior of a peer-to-peer communication system as adiscrete-time Markov chain(DTMC),which is a standard approach in probabilisticverification[LS82,HS84,Var85,HJ94].Formally,a Markov chain can be definedas consisting in afinite set of states,the initial state,the transition relation such that,and a labeling functionfrom states to afinite set of propositions.In our model,the states of the Markov chain will represent different stages ofrouting path construction.As usual,a state is defined by the values of all systemvariables.For each state,the corresponding row of the transition matrix de-fines the probability distributions which govern the behavior of group members once the system reaches that state.32.1Overview of PCTLWe use the temporal probabilistic logic PCTL[HJ94]to formally specify properties of the system to be checked.PCTL can express properties of the form“under any scheduling of processes,the probability that event occurs is at least.”First,define state formulas inductively as follows:where atomic propositions are predicates over state variables.State formulas of the form are explained below.Define path formulas as follows:Unlike state formulas,which are simplyfirst-order propositions over a single state,path formulas represent properties of a chain of states(here path refers to a sequence of state space transitions rather than a routing path in the Crowds speci-fication).In particular,is true iff is true for every state in the chain;is true iff is true for all states in the chain until becomes true,and is true for all subsequent states;is true iff and there are no more than states before becomes true.For any state and path formula,is a state formula which is true iff state space paths starting from satisfy path formula with probability greater than.For the purposes of this paper,we will be interested in formulas of the form ,evaluated in the initial state.Here specifies a system con-figuration of interest,typically representing a particular observation by the adver-sary that satisfies the definition of a successful attack on the protocol.Property is a liveness property:it holds in iff will eventually hold with greater than probability.For instance,if is a state variable represent-ing the number of times one of the corrupt members received a message from the honest member no.,then holds in iff the prob-ability of corrupt members eventually observing member no.twice or more is greater than.Expressing properties of the system in PCTL allows us to reason formally about the probability of corrupt group members collecting enough evidence to success-fully attack anonymity.We use model checking techniques developed for verifica-tion of discrete-time Markov chains to compute this probability automatically.42.2PRISM model checkerThe automated analyses described in this paper were performed using PRISM,aprobabilistic model checker developed by Kwiatkowska et al.[KNP01].The toolsupports both discrete-and continuous-time Markov chains,and Markov decisionprocesses.As described in section4,we model probabilistic peer-to-peer com-munication systems such as Crowds simply as discrete-time Markov chains,andformalize their properties in PCTL.The behavior of the system processes is specified using a simple module-basedlanguage inspired by Reactive Modules[AH96].State variables are declared in thestandard way.For example,the following declarationdeliver:bool init false;declares a boolean state variable deliver,initialized to false,while the followingdeclarationconst TotalRuns=4;...observe1:[0..TotalRuns]init0;declares a constant TotalRuns equal to,and then an integer array of size,indexed from to TotalRuns,with all elements initialized to.State transition rules are specified using guarded commands of the form[]<guard>-><command>;where<guard>is a predicate over system variables,and<command>is the tran-sition executed by the system if the guard condition evaluates to mandoften has the form<expression>...<expression>, which means that in the next state(i.e.,that obtained after the transition has beenexecuted),state variable is assigned the result of evaluating arithmetic expres-sion<expression>If the transition must be chosen probabilistically,the discrete probability dis-tribution is specified as[]<guard>-><prob1>:<command1>+...+<probN>:<commandN>;Transition represented by command is executed with probability prob,and prob.Security properties to be checked are stated as PCTL formulas (see section2.1).5Given a formal system specification,PRISM constructs the Markov chain and determines the set of reachable states,using MTBDDs and BDDs,respectively. Model checking a PCTL formula reduces to a combination of reachability-based computation and solving a system of linear equations to determine the probability of satisfying the formula in each reachable state.The model checking algorithms employed by PRISM include[BdA95,BK98,Bai98].More details about the im-plementation and operation of PRISM can be found at http://www.cs.bham. /˜dxp/prism/and in[KNP01].Since PRISM only supports model checking offinite DTMC,in our case study of Crowds we only analyze anonymity properties offinite instances of the system. By changing parameters of the model,we demonstrate how anonymity properties evolve with changes in the system configuration.Wright et al.[W ALS02]investi-gated related properties of the Crowds system in the general case,but they do not rely on tool support and their analyses are manual rather than automated.3Crowds Anonymity SystemProviding an anonymous communication service on the Internet is a challenging task.While conventional security mechanisms such as encryption can be used to protect the content of messages and transactions,eavesdroppers can still observe the IP addresses of communicating computers,timing and frequency of communi-cation,etc.A Web server can trace the source of the incoming connection,further compromising anonymity.The Crowds system was developed by Reiter and Ru-bin[RR98]for protecting users’anonymity on the Web.The main idea behind gossip-based approaches to anonymity such as Crowds is to hide each user’s communications by routing them randomly within a crowd of similar users.Even if an eavesdropper observes a message being sent by a particular user,it can never be sure whether the user is the actual sender,or is simply routing another user’s message.3.1Path setup protocolA crowd is a collection of users,each of whom is running a special process called a jondo which acts as the user’s proxy.Some of the jondos may be corrupt and/or controlled by the adversary.Corrupt jondos may collaborate and share their obser-vations in an attempt to compromise the honest users’anonymity.Note,however, that all observations by corrupt group members are local.Each corrupt member may observe messages sent to it,but not messages transmitted on the links be-tween honest jondos.An honest crowd member has no way of determining whether6a particular jondo is honest or corrupt.The parameters of the system are the total number of members,the number of corrupt members,and the forwarding probability which is explained below.To participate in communication,all jondos must register with a special server which maintains membership information.Therefore,every member of the crowd knows identities of all other members.As part of the join procedure,the members establish pairwise encryption keys which are used to encrypt pairwise communi-cation,so the contents of the messages are secret from an external eavesdropper.Anonymity guarantees provided by Crowds are based on the path setup pro-tocol,which is described in the rest of this section.The path setup protocol is executed each time one of the crowd members wants to establish an anonymous connection to a Web server.Once a routing path through the crowd is established, all subsequent communication between the member and the Web server is routed along it.We will call one run of the path setup protocol a session.When crowd membership changes,the existing paths must be scrapped and a new protocol ses-sion must be executed in order to create a new random routing path through the crowd to the destination.Therefore,we’ll use terms path reformulation and proto-col session interchangeably.When a user wants to establish a connection with a Web server,its browser sends a request to the jondo running locally on her computer(we will call this jondo the initiator).Each request contains information about the intended desti-nation.Since the objective of Crowds is to protect the sender’s identity,it is not problematic that a corrupt router can learn the recipient’s identity.The initiator starts the process of creating a random path to the destination as follows: The initiator selects a crowd member at random(possibly itself),and for-wards the request to it,encrypted by the corresponding pairwise key.We’ll call the selected member the forwarder.The forwarderflips a biased coin.With probability,it delivers the request directly to the destination.With probability,it selects a crowd member at random(possibly itself)as the next forwarder in the path,and forwards the request to it,re-encrypted with the appropriate pairwise key.The next forwarder then repeats this step.Each forwarder maintains an identifier for the created path.If the same jondo appears in different positions on the same path,identifiers are different to avoid infinite loops.Each subsequent message from the initiator to the destination is routed along this path,i.e.,the paths are static—once established,they are not altered often.This is necessary to hinder corrupt members from linking multiple7paths originating from the same initiator,and using this information to compromise the initiator’s anonymity as described in section3.2.3.3.2Anonymity properties of CrowdsThe Crowds paper[RR98]describes several degrees of anonymity that may be provided by a communication system.Without using anonymizing techniques, none of the following properties are guaranteed on the Web since browser requests contain information about their source and destination in the clear.Beyond suspicion Even if the adversary can see evidence of a sent message,the real sender appears to be no more likely to have originated it than any other potential sender in the system.Probable innocence The real sender appears no more likely to be the originator of the message than to not be the originator,i.e.,the probability that the adversary observes the real sender as the source of the message is less thanupper bound on the probability of detection.If the sender is observed by the adversary,she can then plausibly argue that she has been routing someone else’s messages.The Crowds paper focuses on providing anonymity against local,possibly co-operating eavesdroppers,who can share their observations of communication in which they are involved as forwarders,but cannot observe communication involv-ing only honest members.We also limit our analysis to this case.3.2.1Anonymity for a single routeIt is proved in[RR98]that,for any given routing path,the path initiator in a crowd of members with forwarding probability has probable innocence against collaborating crowd members if the following inequality holds:(1)More formally,let be the event that at least one of the corrupt crowd members is selected for the path,and be the event that the path initiator appears in8the path immediately before a corrupt crowd member(i.e.,the adversary observes the real sender as the source of the messages routed along the path).Condition 1guarantees thatproving that,given multiple linked paths,the initiator appears more often as a sus-pect than a random crowd member.The automated analysis described in section6.1 confirms and quantifies this result.(The technical results of[Shm02]on which this paper is based had been developed independently of[Mal01]and[W ALS02],be-fore the latter was published).In general,[Mal01]and[W ALS02]conjecture that there can be no reliable anonymity method for peer-to-peer communication if in order to start a new communication session,the initiator must originate thefirst connection before any processing of the session commences.This implies that anonymity is impossible in a gossip-based system with corrupt routers in the ab-sence of decoy traffic.In section6.3,we show that,for any given number of observed paths,the adversary’s confidence in its observations increases with the size of the crowd.This result contradicts the intuitive notion that bigger crowds provide better anonymity guarantees.It was discovered by automated analysis.4Formal Model of CrowdsIn this section,we describe our probabilistic formal model of the Crowds system. Since there is no non-determinism in the protocol specification(see section3.1), the model is a simple discrete-time Markov chain as opposed to a Markov deci-sion process.In addition to modeling the behavior of the honest crowd members, we also formalize the adversary.The protocol does not aim to provide anonymity against global eavesdroppers.Therefore,it is sufficient to model the adversary as a coalition of corrupt crowd members who only have access to local communication channels,i.e.,they can only make observations about a path if one of them is se-lected as a forwarder.By the same token,it is not necessary to model cryptographic functions,since corrupt members know the keys used to encrypt peer-to-peer links in which they are one of the endpoints,and have no access to links that involve only honest members.The modeling technique presented in this section is applicable with minor mod-ifications to any probabilistic routing system.In each state of routing path construc-tion,the discrete probability distribution given by the protocol specification is used directly to define the probabilistic transition rule for choosing the next forwarder on the path,if any.If the protocol prescribes an upper bound on the length of the path(e.g.,Freenet[CSWH01]),the bound can be introduced as a system parameter as described in section4.2.3,with the corresponding increase in the size of the state space but no conceptual problems.Probabilistic model checking can then be used to check the validity of PCTL formulas representing properties of the system.In the general case,forwarder selection may be governed by non-deterministic10runCount goodbad lastSeen observelaunchnewstartrundeliver recordLast badObserve4.2Model of honest members4.2.1InitiationPath construction is initiated as follows(syntax of PRISM is described in section 2.2):[]launch->runCount’=TotalRuns&new’=true&launch’=false;[]new&(runCount>0)->(runCount’=runCount-1)&new’=false&start’=true;[]start->lastSeen’=0&deliver’=false&run’=true&start’=false;4.2.2Forwarder selectionThe initiator(i.e.,thefirst crowd member on the path,the one whose identity must be protected)randomly chooses thefirst forwarder from among all group mem-bers.We assume that all group members have an equal probability of being chosen, but the technique can support any discrete probability distribution for choosing for-warders.Forwarder selection is a single step of the protocol,but we model it as two probabilistic state transitions.Thefirst determines whether the selected forwarder is honest or corrupt,the second determines the forwarder’s identity.The randomly selected forwarder is corrupt with probability badCbe next on the path.Any of the honest crowd members can be selected as the forwarder with equal probability.To illustrate,for a crowd with10honest members,the following transition models the second step of forwarder selection: []recordLast&CrowdSize=10->0.1:lastSeen’=0&run’=true&recordLast’=false+0.1:lastSeen’=1&run’=true&recordLast’=false+...0.1:lastSeen’=9&run’=true&recordLast’=false;According to the protocol,each honest crowd member must decide whether to continue building the path byflipping a biased coin.With probability,the forwarder selection transition is enabled again and path construction continues, and with probability the path is terminated at the current forwarder,and all requests arriving from the initiator along the path will be delivered directly to the recipient.[](good&!deliver&run)->//Continue path constructionPF:good’=false+//Terminate path constructionnotPF:deliver’=true;The specification of the Crowds system imposes no upper bound on the length of the path.Moreover,the forwarders are not permitted to know their relative position on the path.Note,however,that the amount of information about the initiator that can be extracted by the adversary from any path,or anyfinite number of paths,isfinite(see sections4.3and4.5).In systems such as Freenet[CSWH01],requests have a hops-to-live counter to prevent infinite paths,except with very small probability.To model this counter,we may introduce an additional state variable pIndex that keeps track of the length of the path constructed so far.The path construction transition is then coded as follows://Example with Hops-To-Live//(NOT CROWDS)////Forward with prob.PF,else deliver13[](good&!deliver&run&pIndex<MaxPath)->PF:good’=false&pIndex’=pIndex+1+notPF:deliver’=true;//Terminate if reached MaxPath,//but sometimes not//(to confuse adversary)[](good&!deliver&run&pIndex=MaxPath)->smallP:good’=false+largeP:deliver’=true;Introduction of pIndex obviously results in exponential state space explosion, decreasing the maximum system size for which model checking is feasible.4.2.4Transition matrix for honest membersTo summarize the state space of the discrete-time Markov chain representing cor-rect behavior of protocol participants(i.e.,the state space induced by the abovetransitions),let be the state in which links of the th routing path from the initiator have already been constructed,and assume that are the honestforwarders selected for the path.Let be the state in which path constructionhas terminated with as thefinal path,and let be an auxiliary state. Then,given the set of honest crowd members s.t.,the transi-tion matrix is such that,,(see section4.2.2),i.e.,the probability of selecting the adversary is equal to the cumulative probability of selecting some corrupt member.14This abstraction does not limit the class of attacks that can be discovered using the approach proposed in this paper.Any attack found in the model where indi-vidual corrupt members are kept separate will be found in the model where their capabilities are combined in a single worst-case adversary.The reason for this is that every observation made by one of the corrupt members in the model with separate corrupt members will be made by the adversary in the model where their capabilities are combined.The amount of information available to the worst-case adversary and,consequently,the inferences that can be made from it are at least as large as those available to any individual corrupt member or a subset thereof.In the adversary model of[RR98],each corrupt member can only observe its local network.Therefore,it only learns the identity of the crowd member imme-diately preceding it on the path.We model this by having the corrupt member read the value of the lastSeen variable,and record its observations.This cor-responds to reading the source IP address of the messages arriving along the path. For example,for a crowd of size10,the transition is as follows:[]lastSeen=0&badObserve->observe0’=observe0+1&deliver’=true&run’=true&badObserve’=false;...[]lastSeen=9&badObserve->observe9’=observe9+1&deliver’=true&run’=true&badObserve’=false;The counters observe are persistent,i.e.,they are not reset for each session of the path setup protocol.This allows the adversary to accumulate observations over several path reformulations.We assume that the adversary can detect when two paths originate from the same member whose identity is unknown(see sec-tion3.2.2).The adversary is only interested in learning the identity of thefirst crowd mem-ber in the path.Continuing path construction after one of the corrupt members has been selected as a forwarder does not provide the adversary with any new infor-mation.This is a very important property since it helps keep the model of the adversaryfinite.Even though there is no bound on the length of the path,at most one observation per path is useful to the adversary.To simplify the model,we as-sume that the path terminates as soon as it reaches a corrupt member(modeled by deliver’=true in the transition above).This is done to shorten the average path length without decreasing the power of the adversary.15Each forwarder is supposed toflip a biased coin to decide whether to terminate the path,but the coinflips are local to the forwarder and cannot be observed by other members.Therefore,honest members cannot detect without cooperation that corrupt members always terminate paths.In any case,corrupt members can make their observable behavior indistinguishable from that of the honest members by continuing the path with probability as described in section4.2.3,even though this yields no additional information to the adversary.4.4Multiple pathsThe discrete-time Markov chain defined in sections4.2and4.3models construc-tion of a single path through the crowd.As explained in section3.2.2,paths have to be reformulated periodically.The decision to rebuild the path is typically made according to a pre-determined schedule,e.g.,hourly,daily,or once enough new members have asked to join the crowd.For the purposes of our analysis,we sim-ply assume that paths are reformulated somefinite number of times(determined by the system parameter=TotalRuns).We analyze anonymity properties provided by Crowds after successive path reformulations by considering the state space produced by successive execu-tions of the path construction protocol described in section4.2.As explained in section4.3,the adversary is permitted to combine its observations of some or all of the paths that have been constructed(the adversary only observes the paths for which some corrupt member was selected as one of the forwarders).The adversary may then use this information to infer the path initiator’s identity.Because for-warder selection is probabilistic,the adversary’s ability to collect enough informa-tion to successfully identify the initiator can only be characterized probabilistically, as explained in section5.4.5Finiteness of the adversary’s state spaceThe state space of the honest members defined by the transition matrix of sec-tion4.2.4is infinite since there is no a priori upper bound on the length of each path.Corrupt members,however,even if they collaborate,can make at most one observation per path,as explained in section4.3.As long as the number of path reformulations is bounded(see section4.4),only afinite number of paths will be constructed and the adversary will be able to make only afinite number of observa-tions.Therefore,the adversary only needsfinite memory and the adversary’s state space isfinite.In general,anonymity is violated if the adversary has a high probability of making a certain observation(see section5).Tofind out whether Crowds satisfies16。

公共政策终结理论研究综述摘要：政策终结是政策过程的一个环节，是政策更新、政策发展、政策进步的新起点。

政策终结是20世纪70年代末西方公共政策研究领域的热点问题。

公共政策终结是公共政策过程的一个重要阶段，对政策终结的研究不仅有利于促进政策资源的合理配置，更有利于提高政府的政策绩效。

本文简要回顾了公共政策终结研究的缘起、内涵、类型、方式、影响因素、促成策略以及发展方向等内容，希望能够对公共政策终结理论有一个比较全面深入的了解。

关键词：公共政策，政策终结，理论研究行政有着古老的历史，但是，在一个相当长的历史时期中，行政所赖以治理社会的工具主要是行政行为。

即使是公共行政出现之后，在一个较长的时期内也还主要是借助于行政行为去开展社会治理，公共行政与传统行政的区别在于，找到了行政行为一致性的制度模式，确立了行政行为的（官僚制）组织基础。

到了公共行政的成熟阶段，公共政策作为社会治理的一个重要途径引起了人们的重视。

与传统社会中主要通过行政行为进行社会治理相比，公共政策在解决社会问题、降低社会成本、调节社会运行等方面都显示出了巨大的优势。

但是，如果一项政策已经失去了存在的价值而又继续被保留下来了，就可能会发挥极其消极的作用。

因此，及时、有效地终结一项或一系列错误的或没有价值的公共政策，有利于促进公共政策的更新与发展、推进公共政策的周期性循环、缓解和解决公共政策的矛盾和冲突，从而实现优化和调整公共政策系统的目标。

这就引发了学界对政策终结理论的思考和探索。

自政策科学在美国诞生以来，公共政策过程理论都是学术界所关注的热点。

1956年，拉斯韦尔在《决策过程》一书中提出了决策过程的七个阶段，即情报、建议、规定、行使、运用、评价和终止。

此种观点奠定了政策过程阶段论在公共政策研究中的主导地位。

一时间，对于政策过程各个阶段的研究成为政策学界的主要课题。

然而，相对于其他几个阶段的研究来说，政策终结的研究一直显得非常滞后。

这种情况直到20世纪70年代末80年代初，才有了明显的改善。

A File is Not a File:Understanding the I/O Behaviorof Apple Desktop ApplicationsTyler Harter,Chris Dragga,Michael Vaughn,Andrea C.Arpaci-Dusseau,Remzi H.Arpaci-DusseauDepartment of Computer SciencesUniversity of Wisconsin,Madison{harter,dragga,vaughn,dusseau,remzi}@ABSTRACTWe analyze the I/O behavior of iBench,a new collection of produc-tivity and multimedia application workloads.Our analysis reveals a number of differences between iBench and typicalfile-system workload studies,including the complex organization of modern files,the lack of pure sequential access,the influence of underlying frameworks on I/O patterns,the widespread use offile synchro-nization and atomic operations,and the prevalence of threads.Our results have strong ramifications for the design of next generation local and cloud-based storage systems.1.INTRODUCTIONThe design and implementation offile and storage systems has long been at the forefront of computer systems research.Inno-vations such as namespace-based locality[21],crash consistency via journaling[15,29]and copy-on-write[7,34],checksums and redundancy for reliability[5,7,26,30],scalable on-disk struc-tures[37],distributedfile systems[16,35],and scalable cluster-based storage systems[9,14,18]have greatly influenced how data is managed and stored within modern computer systems.Much of this work infile systems over the past three decades has been shaped by measurement:the deep and detailed analysis of workloads[4,10,11,16,19,25,33,36,39].One excellent example is found in work on the Andrew File System[16];de-tailed analysis of an early AFS prototype led to the next-generation protocol,including the key innovation of callbacks.Measurement helps us understand the systems of today so we can build improved systems for tomorrow.Whereas most studies offile systems focus on the corporate or academic intranet,mostfile-system users work in the more mun-dane environment of the home,accessing data via desktop PCs, laptops,and compact devices such as tablet computers and mo-bile phones.Despite the large number of previous studies,little is known about home-user applications and their I/O patterns. Home-user applications are important today,and their impor-tance will increase as more users store data not only on local de-vices but also in the ers expect to run similar applications across desktops,laptops,and phones;therefore,the behavior of these applications will affect virtually every system with which a Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on thefirst page.To copy otherwise,to republish,to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.Copyright2011ACM978-1-59593-591-5/07/0010...$er interacts.I/O behavior is especially important to understand since it greatly impacts how users perceive overall system latency and application performance[12].While a study of how users typically exercise these applications would be interesting,thefirst step is to perform a detailed study of I/O behavior under typical but controlled workload tasks.This style of application study,common in thefield of computer archi-tecture[40],is different from the workload study found in systems research,and can yield deeper insight into how the applications are constructed and howfile and storage systems need to be designed in response.Home-user applications are fundamentally large and complex, containing millions of lines of code[20].In contrast,traditional U NIX-based applications are designed to be simple,to perform one task well,and to be strung together to perform more complex tasks[32].This modular approach of U NIX applications has not prevailed[17]:modern applications are standalone monoliths,pro-viding a rich and continuously evolving set of features to demand-ing users.Thus,it is beneficial to study each application individu-ally to ascertain its behavior.In this paper,we present thefirst in-depth analysis of the I/O behavior of modern home-user applications;we focus on produc-tivity applications(for word processing,spreadsheet manipulation, and presentation creation)and multimedia software(for digital mu-sic,movie editing,and photo management).Our analysis centers on two Apple software suites:iWork,consisting of Pages,Num-bers,and Keynote;and iLife,which contains iPhoto,iTunes,and iMovie.As Apple’s market share grows[38],these applications form the core of an increasingly popular set of workloads;as de-vice convergence continues,similar forms of these applications are likely to access userfiles from both stationary machines and mov-ing cellular devices.We call our collection the iBench task suite. To investigate the I/O behavior of the iBench suite,we build an instrumentation framework on top of the powerful DTrace tracing system found inside Mac OS X[8].DTrace allows us not only to monitor system calls made by each traced application,but also to examine stack traces,in-kernel functions such as page-ins and page-outs,and other details required to ensure accuracy and com-pleteness.We also develop an application harness based on Apple-Script[3]to drive each application in the repeatable and automated fashion that is key to any study of GUI-based applications[12]. Our careful study of the tasks in the iBench suite has enabled us to make a number of interesting observations about how applica-tions access and manipulate stored data.In addition to confirming standard pastfindings(e.g.,mostfiles are small;most bytes ac-cessed are from largefiles[4]),wefind the following new results. Afile is not afile.Modern applications manage large databases of information organized into complex directory trees.Even simple word-processing documents,which appear to users as a“file”,arein actuality smallfile systems containing many sub-files(e.g.,a Microsoft.docfile is actually a FATfile system containing pieces of the document).File systems should be cognizant of such hidden structure in order to lay out and access data in these complexfiles more effectively.Sequential access is not sequential.Building on the trend no-ticed by V ogels for Windows NT[39],we observe that even for streaming media workloads,“pure”sequential access is increas-ingly rare.Sincefile formats often include metadata in headers, applications often read and re-read thefirst portion of afile before streaming through its contents.Prefetching and other optimizations might benefit from a deeper knowledge of thesefile formats. Auxiliaryfiles dominate.Applications help users create,mod-ify,and organize content,but userfiles represent a small fraction of thefiles touched by modern applications.Mostfiles are helper files that applications use to provide a rich graphical experience, support multiple languages,and record history and other metadata. File-system placement strategies might reduce seeks by grouping the hundreds of helperfiles used by an individual application. Writes are often forced.As the importance of home data in-creases(e.g.,family photos),applications are less willing to simply write data and hope it is eventuallyflushed to disk.Wefind that most written data is explicitly forced to disk by the application;for example,iPhoto calls fsync thousands of times in even the sim-plest of tasks.Forfile systems and storage,the days of delayed writes[22]may be over;new ideas are needed to support applica-tions that desire durability.Renaming is popular.Home-user applications commonly use atomic operations,in particular rename,to present a consistent view offiles to users.Forfile systems,this may mean that trans-actional capabilities[23]are needed.It may also necessitate a re-thinking of traditional means offile locality;for example,placing afile on disk based on its parent directory[21]does not work as expected when thefile isfirst created in a temporary location and then renamed.Multiple threads perform I/O.Virtually all of the applications we study issue I/O requests from a number of threads;a few ap-plications launch I/Os from hundreds of threads.Part of this us-age stems from the GUI-based nature of these applications;it is well known that threads are required to perform long-latency oper-ations in the background to keep the GUI responsive[24].Thus,file and storage systems should be thread-aware so they can better allocate bandwidth.Frameworks influence I/O.Modern applications are often de-veloped in sophisticated IDEs and leverage powerful libraries,such as Cocoa and Carbon.Whereas UNIX-style applications often di-rectly invoke system calls to read and writefiles,modern libraries put more code between applications and the underlyingfile system; for example,including"cocoa.h"in a Mac application imports 112,047lines of code from689differentfiles[28].Thus,the be-havior of the framework,and not just the application,determines I/O patterns.Wefind that the default behavior of some Cocoa APIs induces extra I/O and possibly unnecessary(and costly)synchro-nizations to disk.In addition,use of different libraries for similar tasks within an application can lead to inconsistent behavior be-tween those tasks.Future storage design should take these libraries and frameworks into account.This paper contains four major contributions.First,we describe a general tracing framework for creating benchmarks based on in-teractive tasks that home users may perform(e.g.,importing songs, exporting video clips,saving documents).Second,we deconstruct the I/O behavior of the tasks in iBench;we quantify the I/O behav-ior of each task in numerous ways,including the types offiles ac-cessed(e.g.,counts and sizes),the access patterns(e.g.,read/write, sequentiality,and preallocation),transactional properties(e.g.,dura-bility and atomicity),and threading.Third,we describe how these qualitative changes in I/O behavior may impact the design of future systems.Finally,we present the34traces from the iBench task suite;by making these traces publicly available and easy to use,we hope to improve the design,implementation,and evaluation of the next generation of local and cloud storage systems:/adsl/Traces/ibench The remainder of this paper is organized as follows.We begin by presenting a detailed timeline of the I/O operations performed by one task in the iBench suite;this motivates the need for a systematic study of home-user applications.We next describe our methodol-ogy for creating the iBench task suite.We then spend the majority of the paper quantitatively analyzing the I/O characteristics of the full iBench suite.Finally,we summarize the implications of our findings onfile-system design.2.CASE STUDYThe I/O characteristics of modern home-user applications are distinct from those of U NIX applications studied in the past.To motivate the need for a new study,we investigate the complex I/O behavior of a single representative task.Specifically,we report in detail the I/O performed over time by the Pages(4.0.3)application, a word processor,running on Mac OS X Snow Leopard(10.6.2)as it creates a blank document,inserts15JPEG images each of size 2.5MB,and saves the document as a Microsoft.docfile.Figure1shows the I/O this task performs(see the caption for a description of the symbols used).The top portion of thefigure il-lustrates the accesses performed over the full lifetime of the task:at a high level,it shows that more than385files spanning six different categories are accessed by eleven different threads,with many in-tervening calls to fsync and rename.The bottom portion of the figure magnifies a short time interval,showing the reads and writes performed by a single thread accessing the primary.doc productiv-ityfile.From this one experiment,we illustrate eachfinding de-scribed in the introduction.Wefirst focus on the single access that saves the user’s document(bottom),and then consider the broader context surrounding thisfile save,where we observe aflurry of ac-cesses to hundreds of helperfiles(top).Afile is not afile.Focusing on the magnified timeline of reads and writes to the productivity.docfile,we see that thefile format comprises more than just a simplefile.Microsoft.docfiles are based on the FATfile system and allow bundling of multiplefiles in the single.docfile.This.docfile contains a directory(Root),three streams for large data(WordDocument,Data,and1Table),and a stream for small data(Ministream).Space is allocated in thefile with three sections:afile allocation table(FAT),a double-indirect FAT(DIF)region,and a ministream allocation region(Mini). Sequential access is not sequential.The complex FAT-based file format causes random access patterns in several ways:first,the header is updated at the beginning and end of the magnified access; second,data from individual streams is fragmented throughout the file;and third,the1Table stream is updated before and after each image is appended to the WordDocument stream.Auxiliaryfiles dominate.Although saving the single.doc we have been considering is the sole purpose of this task,we now turn our attention to the top timeline and see that385differentfiles are accessed.There are several reasons for this multitude offiles. First,Pages provides a rich graphical experience involving many images and other forms of multimedia;together with the15in-serted JPEGs,this requires118multimediafiles.Second,usersF i l e sSequential RunsF i l e O f f s e t (K B )Figure 1:Pages Saving A Word Document.The top graph shows the 75-second timeline of the entire run,while the bottom graph is a magnified view of seconds 54to 58.In the top graph,annotations on the left categorize files by type and indicate file count and amount of I/O;annotations on the right show threads.Black bars are file accesses (reads and writes),with thickness logarithmically proportional to bytes of I/O./is an fsync ;\is a rename ;X is both.In the bottom graph,individual reads and writes to the .doc file are shown.Vertical bar position and bar length represent the offset within the file and number of bytes touched.Thick white bars are reads;thin gray bars are writes.Repeated runs are marked with the number of repetitions.Annotations on the right indicate the name of each file section.want to use Pages in their native language,so application text is not hard-coded into the executable but is instead stored in25different .stringsfiles.Third,to save user preferences and other metadata, Pages uses a SQLite database(2files)and a number of key-value stores(218.plistfiles).Writes are often forced;renaming is popular.Pages uses both of these actions to enforce basic transactional guarantees.It uses fsync toflush write data to disk,making it durable;it uses rename to atomically replace oldfiles with newfiles so that afile never contains inconsistent data.The timeline shows these invo-cations numerous times.First,Pages regularly uses fsync and rename when updating the key-value store of a.plistfile.Second, fsync is used on the SQLite database.Third,for each of the15 image insertions,Pages calls fsync on afile named“tempData”(classified as“other”)to update its automatic backup.Multiple threads perform I/O.Pages is a multi-threaded appli-cation and issues I/O requests from many different threads during the ing multiple threads for I/O allows Pages to avoid blocking while I/O requests are outstanding.Examining the I/O behavior across threads,we see that Thread1performs the most significant portion of I/O,but ten other threads are also involved.In most cases,a single thread exclusively accesses afile,but it is not uncommon for multiple threads to share afile.Frameworks influence I/O.Pages was developed in a rich pro-gramming environment where frameworks such as Cocoa or Car-bon are used for I/O;these libraries impact I/O patterns in ways the developer might not expect.For example,although the appli-cation developers did not bother to use fsync or rename when saving the user’s work in the.docfile,the Cocoa library regularly uses these calls to atomically and durably update relatively unim-portant metadata,such as“recently opened”lists stored in.plist files.As another example,when Pages tries to read data in512-byte chunks from the.doc,each read goes through the STDIO library, which only reads in4KB chunks.Thus,when Pages attempts to read one chunk from the1Table stream,seven unrequested chunks from the WordDocument stream are also incidentally read(off-set12039KB).In other cases,regions of the.docfile are repeat-edly accessed unnecessarily.For example,around the3KB off-set,read/write pairs occur dozens of times.Pages uses a library to write2-byte words;each time a word is written,the library reads, updates,and writes back an entire512-byte chunk.Finally,we see evidence of redundancy between libraries:even though Pages has a backing SQLite database for some of its properties,it also uses.plistfiles,which function across Apple applications as generic property stores.This one detailed experiment has shed light on a number of in-teresting I/O behaviors that indicate that home-user applications are indeed different than traditional workloads.A new workload suite is needed that more accurately reflects these applications.3.IBENCH TASK SUITEOur goal in constructing the iBench task suite is two-fold.First, we would like iBench to be representative of the tasks performed by home users.For this reason,iBench contains popular applications from the iLife and iWork suites for entertainment and productivity. Second,we would like iBench to be relatively simple for others to use forfile and storage system analysis.For this reason,we auto-mate the interactions of a home user and collect the resulting traces of I/O system calls.The traces are available online at this site: /adsl/Traces/ibench.We now describe in more detail how we met these two goals.3.1RepresentativeTo capture the I/O behavior of home users,iBench models the ac-tions of a“reasonable”user interacting with iPhoto,iTunes,iMovie, Pages,Numbers,and Keynote.Since the research community does not yet have data on the exact distribution of tasks that home users perform,iBench contains tasks that we believe are common and usesfiles with sizes that can be justified for a reasonable user. iBench contains34different tasks,each representing a home user performing one distinct operation.If desired,these tasks could be combined to create more complex workflows and I/O workloads. The six applications and corresponding tasks are as follows.iLife iPhoto8.1.1(419):digital photo album and photo manip-ulation software.iPhoto stores photos in a library that contains the data for the photos(which can be in a variety of formats,including JPG,TIFF,and PNG),a directory of modifiedfiles,a directory of scaled down images,and twofiles of thumbnail images.The library stores metadata in a SQLite database.iBench contains six tasks ex-ercising user actions typical for iPhoto:starting the application and importing,duplicating,editing,viewing,and deleting photos in the library.These tasks modify both the imagefiles and the underlying database.Each of the iPhoto tasks operates on4002.5MB photos, representing a user who has imported12megapixel photos(2.5MB each)from a full1GBflash card on his or her camera.iLife iTunes9.0.3(15):a media player capable of both audio and video playback.iTunes organizes itsfiles in a private library and supports most common music formats(e.g.,MP3,AIFF,W A VE, AAC,and MPEG-4).iTunes does not employ a database,keeping media metadata and playlists in both a binary and an XMLfile. iBench containsfive tasks for iTunes:starting iTunes,importing and playing an album of MP3songs,and importing and playing an MPEG-4movie.Importing requires copyingfiles into the library directory and,for music,analyzing each songfile for gapless play-back.The music tasks operate over an album(or playlist)of ten songs while the movie tasks use a single3-minute movie.iLife iMovie8.0.5(820):video editing software.iMovie stores its data in a library that contains directories for raw footage and projects,andfiles containing video footage thumbnails.iMovie supports both MPEG-4and Quicktimefiles.iBench contains four tasks for iMovie:starting iMovie,importing an MPEG-4movie, adding a clip from this movie into a project,and exporting a project to MPEG-4.The tasks all use a3-minute movie because this is a typical length found from home users on video-sharing websites. iWork Pages4.0.3(766):a word processor.Pages uses a ZIP-basedfile format and can export to DOC,PDF,RTF,and basic text. iBench includes eight tasks for Pages:starting up,creating and saving,opening,and exporting documents with and without images and with different formats.The tasks use15page documents. iWork Numbers2.0.3(332):a spreadsheet application.Num-bers organizes itsfiles with a ZIP-based format and exports to XLS and PDF.The four iBench tasks for Numbers include starting Num-bers,generating a spreadsheet and saving it,opening the spread-sheet,and exporting that spreadsheet to XLS.To model a possible home user working on a budget,the tasks utilize afive page spread-sheet with one column graph per sheet.iWork Keynote5.0.3(791):a presentation and slideshow appli-cation.Keynote saves to a.key ZIP-based format and exports to Microsoft’s PPT format.The seven iBench tasks for Keynote in-clude starting Keynote,creating slides with and without images, opening and playing presentations,and exporting to PPT.Each Keynote task uses a20-slide presentation.Accesses I/O MB Name DescriptionFiles (MB)Accesses (MB)RD%WR%/CPU Sec/CPU Seci L i f e i P h o t oStart Open iPhoto with library of 400photos 779(336.7)828(25.4)78.821.2151.1 4.6Imp Import 400photos into empty library 5900(1966.9)8709(3940.3)74.425.626.712.1Dup Duplicate 400photos from library2928(1963.9)5736(2076.2)52.447.6237.986.1Edit Sequentially edit 400photos from library 12119(4646.7)18927(12182.9)69.830.219.612.6Del Sequentially delete 400photos;empty trash 15246(23.0)15247(25.0)21.878.2280.90.5View Sequentially view 400photos 2929(1006.4)3347(1005.0)98.1 1.924.17.2i T u n e s Start Open iTunes with 10song album 143(184.4)195(9.3)54.745.372.4 3.4ImpS Import 10song album to library 68(204.9)139(264.5)66.333.775.2143.1ImpM Import 3minute movie to library 41(67.4)57(42.9)48.052.0152.4114.6PlayS Play album of 10songs 61(103.6)80(90.9)96.9 3.10.40.5PlayM Play 3minute movie56(77.9)69(32.0)92.37.7 2.2 1.0i M o v i e Start Open iMovie with 3minute clip in project 433(223.3)786(29.4)99.90.1134.8 5.0Imp Import 3minute .m4v (20MB)to “Events”184(440.1)383(122.3)55.644.429.39.3Add Paste 3minute clip from “Events”to project 210(58.3)547(2.2)47.852.2357.8 1.4Exp Export 3minute video clip 70(157.9)546(229.9)55.144.9 2.3 1.0i W o r kP a g e s Start Open Pages218(183.7)228(2.3)99.90.197.7 1.0New Create 15text page document;save as .pages 135(1.6)157(1.0)73.326.750.80.3NewP Create 15JPG document;save as .pages 408(112.0)997(180.9)60.739.354.69.9Open Open 15text page document 103(0.8)109(0.6)99.50.557.60.3PDF Export 15page document as .pdf 107(1.5)115(0.9)91.09.041.30.3PDFP Export 15JPG document as .pdf 404(77.4)965(110.9)67.432.649.7 5.7DOC Export 15page document as .doc 112(1.0)121(1.0)87.912.144.40.4DOCP Export 15JPG document as .doc 385(111.3)952(183.8)61.138.946.38.9N u m b e r s Start Open Numbers283(179.9)360(2.6)99.60.4115.50.8New Save 5sheets/column graphs as .numbers 269(4.9)313(2.8)90.79.39.60.1Open Open 5sheet spreadsheet119(1.3)137(1.3)99.80.248.70.5XLS Export 5sheets/column graphs as .xls 236(4.6)272(2.7)94.9 5.18.50.1K e y n o t e Start Open Keynote517(183.0)681(1.1)99.80.2229.80.4New Create 20text slides;save as .key 637(12.1)863(5.4)92.47.6129.10.8NewP Create 20JPG slides;save as .key654(92.9)901(103.3)66.833.270.88.1Play Open and play presentation of 20text slides 318(11.5)385(4.9)99.80.295.0 1.2PlayP Open and play presentation of 20JPG slides 321(45.4)388(55.7)69.630.472.410.4PPT Export 20text slides as .ppt 685(12.8)918(10.1)78.821.2115.2 1.3PPTP Export 20JPG slides as .ppt 723(110.6)996(124.6)57.642.461.07.6Table 1:34Tasks of the iBench Suite.The table summarizes the 34tasks of iBench,specifying the application,a short name for the task,and a longer description of the actions modeled.The I/O is characterized according to the number of files read or written,the sum of the maximum sizes of all accessed files,the number of file accesses that read or write data,the number of bytes read or written,the percentage of I/O bytes that are part of a read (or write),and the rate of I/O per CPU-second in terms of both file accesses and bytes.Each core is counted individually,so at most 2CPU-seconds can be counted per second on our dual-core test machine.CPU utilization is measured with the UNIX top utility,which in rare cases produces anomalous CPU utilization snapshots;those values are ignored.Table 1contains a brief description of each of the 34iBench tasks as well as the basic I/O characteristics of each task when running on Mac OS X Snow Leopard 10.6.2.The table illustrates that the iBench tasks perform a significant amount of I/O.Most tasks access hundreds of files,which in aggregate contain tens or hundreds of megabytes of data.The tasks typically access files hundreds of times.The tasks perform widely differing amounts of I/O,from less than a megabyte to more than a gigabyte.Most of the tasks perform many more reads than writes.Finally,the tasks exhibit high I/O throughput,often transferring tens of megabytes of data for every second of computation.3.2Easy to UseTo enable other system evaluators to easily use these tasks,the iBench suite is packaged as a set of 34system call traces.To ensure reproducible results,the 34user tasks were first automated with AppleScript,a general-purpose GUI scripting language.Apple-Script provides generic commands to emulate mouse clicks through menus and application-specific commands to capture higher-level operations.Application-specific commands bypass a small amount of I/O by skipping dialog boxes;however,we use them whenever possible for expediency.The system call traces were gathered using DTrace [8],a kernel and user level dynamic instrumentation tool.DTrace is used toinstrument the entry and exit points of all system calls dealing with the file system;it also records the current state of the system and the parameters passed to and returned from each call.While tracing with DTrace was generally straightforward,we ad-dressed four challenges in collecting the iBench traces.First,file sizes are not always available to DTrace;thus,we record every file’s initial size and compute subsequent file size changes caused by system calls such as write or ftruncate .Second,iTunes uses the ptrace system call to disable tracing;we circumvent this block by using gdb to insert a breakpoint that automatically re-turns without calling ptrace .Third,the volfs pseudo-file sys-tem in HFS+(Hierarchical File System)allows files to be opened via their inode number instead of a file name;to include path-names in the trace,we instrument the build path function to obtain the full path when the task is run.Fourth,tracing system calls misses I/O resulting from memory-mapped files;therefore,we purged memory and instrumented kernel page-in functions to measure the amount of memory-mapped file activity.We found that the amount of memory-mapped I/O is negligible in most tasks;we thus do not include this I/O in the iBench traces or analysis.To provide reproducible results,the traces must be run on a sin-gle file-system image.Therefore,the iBench suite also contains snapshots of the initial directories to be restored before each run;initial state is critical in file-system benchmarking [1].4.ANALYSIS OF IBENCH TASKSThe iBench task suite enables us to study the I/O behavior of a large set of home-user actions.As shown from the timeline of I/O behavior for one particular task in Section2,these tasks are likely to accessfiles in complex ways.To characterize this complex behavior in a quantitative manner across the entire suite of34tasks, we focus on answering four categories of questions.•What different types offiles are accessed and what are the sizes of thesefiles?•How arefiles accessed for reads and writes?Arefiles ac-cessed sequentially?Is space preallocated?•What are the transactional properties?Are writesflushed with fsync or performed atomically?•How do multi-threaded applications distribute I/O across dif-ferent threads?Answering these questions has two benefits.First,the answers can guidefile and storage system developers to target their systems better to home-user applications.Second,the characterization will help users of iBench to select the most appropriate traces for eval-uation and to understand their resulting behavior.All measurements were performed on a Mac Mini running Mac OS X Snow Leopard version10.6.2and the HFS+file system. The machine has2GB of memory and a2.26GHz Intel Core Duo processor.4.1Nature of FilesOur analysis begins by characterizing the high-level behavior of the iBench tasks.In particular,we study the different types offiles opened by each iBench task as well as the sizes of thosefiles. 4.1.1File TypesThe iLife and iWork applications store data across a variety of files in a number of different formats;for example,iLife applica-tions tend to store their data in libraries(or data directories)unique to each user,while iWork applications organize their documents in proprietary ZIP-basedfiles.The extent to which tasks access dif-ferent types offiles greatly influences their I/O behavior.To understand accesses to differentfile types,we place eachfile into one of six categories,based onfile name extensions and us-age.Multimediafiles contain images(e.g.,JPEG),songs(e.g., MP3,AIFF),and movies(e.g.,MPEG-4).Productivityfiles are documents(e.g.,.pages,DOC,PDF),spreadsheets(e.g.,.numbers, XLS),and presentations(e.g.,.key,PPT).SQLitefiles are database files.Plistfiles are property-listfiles in XML containing key-value pairs for user preferences and application properties.Stringsfiles contain strings for localization of application text.Finally,Other contains miscellaneousfiles such as plain text,logs,files without extensions,and binaryfiles.Figure2shows the frequencies with which tasks open and ac-cessfiles of each type;most tasks perform hundreds of these ac-cesses.Multimediafile opens are common in all workloads,though they seldom predominate,even in the multimedia-heavy iLife ap-plications.Conversely,opens of productivityfiles are rare,even in iWork applications that use them;this is likely because most iWork tasks create or view a single productivityfile.Because.plistfiles act as generic helperfiles,they are relatively common.SQLitefiles only have a noticeable presence in iPhoto,where they account for a substantial portion of the observed opens.Stringsfiles occupy a significant minority of most workloads(except iPhoto and iTunes). Finally,between5%and20%offiles are of type“Other”(except for iTunes,where they are more prevalent).Figure3displays the percentage of I/O bytes accessed for each file type.In bytes,multimedia I/O dominates most of the iLife tasks,while productivity I/O has a significant presence in the iWork tasks;file descriptors on multimedia and productivityfiles tend to receive large amounts of I/O.SQLite,Plist,and Stringsfiles have a smaller share of the total I/O in bytes relative to the number of openedfiles;this implies that tasks access only a small quantity of data for each of thesefiles opened(e.g.,several key-value pairs in a.plist).In most tasks,files classified as“Other”receive a more significant portion of the I/O(the exception is iTunes). Summary:Home applications access a wide variety offile types, generally opening multimediafiles the most frequently.iLife tasks tend to access bytes primarily from multimedia orfiles classified as“Other”;iWork tasks access bytes from a broader range offile types,with some emphasis on productivityfiles.4.1.2File SizesLarge and smallfiles present distinct challenges to thefile sys-tem.For largefiles,finding contiguous space can be difficult,while for smallfiles,minimizing initial seek time is more important.We investigate two different questions regardingfile size.First,what is the distribution offile sizes accessed by each task?Second,what portion of accessed bytes resides infiles of various sizes?To answer these questions,we recordfile sizes when each unique file descriptor is closed.We categorize sizes as very small(<4KB), small(<64KB),medium(<1MB),large(<10MB),or very large (≥10MB).We track how many accesses are tofiles in each cate-gory and how many of the bytes belong tofiles in each category. Figure4shows the number of accesses tofiles of each size.Ac-cesses to very smallfiles are extremely common,especially for iWork,accounting for over half of all the accesses in every iWork task.Smallfile accesses have a significant presence in the iLife tasks.The large quantity of very small and smallfiles is due to frequent use of.plistfiles that store preferences,settings,and other application data;thesefiles oftenfill just one or two4KB pages. Figure5shows the proportion of thefiles in which the bytes of accessedfiles rge and very largefiles dominate every startup workload and nearly every task that processes multimedia files.Smallfiles account for few bytes and very smallfiles are essentially negligible.Summary:Agreeing with many previous studies(e.g.,[4]),we find that while applications tend to open many very smallfiles (<4KB),most of the bytes accessed are in largefiles(>1MB).4.2Access PatternsWe next examine how the nature offile accesses has changed, studying the read and write patterns of home applications.These patterns include whetherfiles are used for reading,writing,or both; whetherfiles are accessed sequentially or randomly;andfinally, whether or not blocks are preallocated via hints to thefile system.4.2.1File AccessesOne basic characteristic of our workloads is the division between reading and writing on openfile descriptors.If an application uses an openfile only for reading(or only for writing)or performs more activity onfile descriptors of a certain type,then thefile system may be able to make more intelligent memory and disk allocations. To determine these characteristics,we classify each openedfile descriptor based on the types of accesses–read,write,or both read and write–performed during its lifetime.We also ignore the ac-tualflags used when opening thefile since we found they do not accurately reflect behavior;in all workloads,almost all write-only file descriptors were opened with O RDWR.We measure both the。

【老机专版SP2】深度联盟GHOST【老机专版SP2】深度联盟GHOST_XP_SP2低配置电脑专业版V5.5图片:Snap3.jpg图片:Snap4.jpg图片:Snap5.jpg图片:Snap6.jpg图片:Snap7.jpg图片:Snap8.jpg图片:Snap9.jpg=======================【老机专版SP2】深度联盟GHOST_XP_SP2低配置电脑专业版V5.5=======================首要说明：本系统精心制作面向老机，低配置计算机，珍藏版。

封装母盘：深度技术论坛精简优化版SP2（2008年）驱动包：雨林木风更新的驱动包（2010年2月4日）封装工具：雨林木风SysPacker 3.65.2.7系统格式：FAT32雨林木风SysPacker 3.65.2.7+雨林木风更新的驱动包+深度技术论坛精简优化版SP2=完美组合=======================深度联盟GHOST系统采用最新的封装技术，全面提升系统在计算机上的部署速度，恢复效率更高.系统中集成2010年2月以前流行的各种硬件驱动和部分版本最常用的软件。

完美通过微软正版验证，支持在线更新。

适合电脑维护人员快速给各类计算机安装和恢复系统使用。

本系统主要适用于笔记本、品牌机，也支持组装兼容机，安装后自动激活可供品牌机专卖店及普通用户安装使用，系统安装简便快速，3-8分钟内即可安装完成=======================更新提示说明：1、Adobe Flash Player for IE_11.2；2、优化系统响应速度以及软件运行速度，最大化优化各项设置。

3、采用雨林木风2010年4月最后一次更新的驱动包，对于老机支持更全面。

并采用雨林木风最后一次更新的封装工具进行封装，驱动和封装工具搭配的更完美，雨林木风的驱动务必和雨林木风的封装工具搭配使用才是最佳的。

4、封装母盘采用深度技术论坛2008年的SP2精简版，稳定性以及各方面优化都是首屈一指的。

More informationQuantum Computing for Computer ScientistsThe multidisciplinaryfield of quantum computing strives to exploit someof the uncanny aspects of quantum mechanics to expand our computa-tional horizons.Quantum Computing for Computer Scientists takes read-ers on a tour of this fascinating area of cutting-edge research.Writtenin an accessible yet rigorous fashion,this book employs ideas and tech-niques familiar to every student of computer science.The reader is notexpected to have any advanced mathematics or physics background.Af-ter presenting the necessary prerequisites,the material is organized tolook at different aspects of quantum computing from the specific stand-point of computer science.There are chapters on computer architecture,algorithms,programming languages,theoretical computer science,cryp-tography,information theory,and hardware.The text has step-by-stepexamples,more than two hundred exercises with solutions,and program-ming drills that bring the ideas of quantum computing alive for today’scomputer science students and researchers.Noson S.Yanofsky,PhD,is an Associate Professor in the Departmentof Computer and Information Science at Brooklyn College,City Univer-sity of New York and at the PhD Program in Computer Science at TheGraduate Center of CUNY.Mirco A.Mannucci,PhD,is the founder and CEO of HoloMathics,LLC,a research and development company with a focus on innovative mathe-matical modeling.He also serves as Adjunct Professor of Computer Sci-ence at George Mason University and the University of Maryland.QUANTUM COMPUTING FORCOMPUTER SCIENTISTSNoson S.YanofskyBrooklyn College,City University of New YorkandMirco A.MannucciHoloMathics,LLCMore informationMore informationcambridge university pressCambridge,New York,Melbourne,Madrid,Cape Town,Singapore,S˜ao Paulo,DelhiCambridge University Press32Avenue of the Americas,New York,NY10013-2473,USAInformation on this title:/9780521879965C Noson S.Yanofsky and Mirco A.Mannucci2008This publication is in copyright.Subject to statutory exceptionand to the provisions of relevant collective licensing agreements,no reproduction of any part may take place withoutthe written permission of Cambridge University Press.First published2008Printed in the United States of AmericaA catalog record for this publication is available from the British Library.Library of Congress Cataloging in Publication dataYanofsky,Noson S.,1967–Quantum computing for computer scientists/Noson S.Yanofsky andMirco A.Mannucci.p.cm.Includes bibliographical references and index.ISBN978-0-521-87996-5(hardback)1.Quantum computers.I.Mannucci,Mirco A.,1960–II.Title.QA76.889.Y352008004.1–dc222008020507ISBN978-0-521-879965hardbackCambridge University Press has no responsibility forthe persistence or accuracy of URLs for external orthird-party Internet Web sites referred to in this publicationand does not guarantee that any content on suchWeb sites is,or will remain,accurate or appropriate.More informationDedicated toMoishe and Sharon Yanofskyandto the memory ofLuigi and Antonietta MannucciWisdom is one thing:to know the tho u ght by which all things are directed thro u gh allthings.˜Heraclitu s of Ephe s u s(535–475B C E)a s quoted in Dio g ene s Laertiu s’sLives and Opinions of Eminent PhilosophersBook IX,1. More informationMore informationContentsPreface xi1Complex Numbers71.1Basic Definitions81.2The Algebra of Complex Numbers101.3The Geometry of Complex Numbers152Complex Vector Spaces292.1C n as the Primary Example302.2Definitions,Properties,and Examples342.3Basis and Dimension452.4Inner Products and Hilbert Spaces532.5Eigenvalues and Eigenvectors602.6Hermitian and Unitary Matrices622.7Tensor Product of Vector Spaces663The Leap from Classical to Quantum743.1Classical Deterministic Systems743.2Probabilistic Systems793.3Quantum Systems883.4Assembling Systems974Basic Quantum Theory1034.1Quantum States1034.2Observables1154.3Measuring1264.4Dynamics1294.5Assembling Quantum Systems1325Architecture1385.1Bits and Qubits138viiMore informationviii Contents5.2Classical Gates1445.3Reversible Gates1515.4Quantum Gates1586Algorithms1706.1Deutsch’s Algorithm1716.2The Deutsch–Jozsa Algorithm1796.3Simon’s Periodicity Algorithm1876.4Grover’s Search Algorithm1956.5Shor’s Factoring Algorithm2047Programming Languages2207.1Programming in a Quantum World2207.2Quantum Assembly Programming2217.3Toward Higher-Level Quantum Programming2307.4Quantum Computation Before Quantum Computers2378Theoretical Computer Science2398.1Deterministic and Nondeterministic Computations2398.2Probabilistic Computations2468.3Quantum Computations2519Cryptography2629.1Classical Cryptography2629.2Quantum Key Exchange I:The BB84Protocol2689.3Quantum Key Exchange II:The B92Protocol2739.4Quantum Key Exchange III:The EPR Protocol2759.5Quantum Teleportation27710Information Theory28410.1Classical Information and Shannon Entropy28410.2Quantum Information and von Neumann Entropy28810.3Classical and Quantum Data Compression29510.4Error-Correcting Codes30211Hardware30511.1Quantum Hardware:Goals and Challenges30611.2Implementing a Quantum Computer I:Ion Traps31111.3Implementing a Quantum Computer II:Linear Optics31311.4Implementing a Quantum Computer III:NMRand Superconductors31511.5Future of Quantum Ware316Appendix A Historical Bibliography of Quantum Computing319 by Jill CirasellaA.1Reading Scientific Articles319A.2Models of Computation320More informationContents ixA.3Quantum Gates321A.4Quantum Algorithms and Implementations321A.5Quantum Cryptography323A.6Quantum Information323A.7More Milestones?324Appendix B Answers to Selected Exercises325Appendix C Quantum Computing Experiments with MATLAB351C.1Playing with Matlab351C.2Complex Numbers and Matrices351C.3Quantum Computations354Appendix D Keeping Abreast of Quantum News:QuantumComputing on the Web and in the Literature357by Jill CirasellaD.1Keeping Abreast of Popular News357D.2Keeping Abreast of Scientific Literature358D.3The Best Way to Stay Abreast?359Appendix E Selected Topics for Student Presentations360E.1Complex Numbers361E.2Complex Vector Spaces362E.3The Leap from Classical to Quantum363E.4Basic Quantum Theory364E.5Architecture365E.6Algorithms366E.7Programming Languages368E.8Theoretical Computer Science369E.9Cryptography370E.10Information Theory370E.11Hardware371Bibliography373Index381More informationPrefaceQuantum computing is a fascinating newfield at the intersection of computer sci-ence,mathematics,and physics,which strives to harness some of the uncanny as-pects of quantum mechanics to broaden our computational horizons.This bookpresents some of the most exciting and interesting topics in quantum computing.Along the way,there will be some amazing facts about the universe in which we liveand about the very notions of information and computation.The text you hold in your hands has a distinctflavor from most of the other cur-rently available books on quantum computing.First and foremost,we do not assumethat our reader has much of a mathematics or physics background.This book shouldbe readable by anyone who is in or beyond their second year in a computer scienceprogram.We have written this book specifically with computer scientists in mind,and tailored it accordingly:we assume a bare minimum of mathematical sophistica-tion,afirst course in discrete structures,and a healthy level of curiosity.Because thistext was written specifically for computer people,in addition to the many exercisesthroughout the text,we added many programming drills.These are a hands-on,funway of learning the material presented and getting a real feel for the subject.The calculus-phobic reader will be happy to learn that derivatives and integrals are virtually absent from our text.Quite simply,we avoid differentiation,integra-tion,and all higher mathematics by carefully selecting only those topics that arecritical to a basic introduction to quantum computing.Because we are focusing onthe fundamentals of quantum computing,we can restrict ourselves to thefinite-dimensional mathematics that is required.This turns out to be not much more thanmanipulating vectors and matrices with complex entries.Surprisingly enough,thelion’s share of quantum computing can be done without the intricacies of advancedmathematics.Nevertheless,we hasten to stress that this is a technical textbook.We are not writing a popular science book,nor do we substitute hand waving for rigor or math-ematical precision.Most other texts in thefield present a primer on quantum mechanics in all its glory.Many assume some knowledge of classical mechanics.We do not make theseassumptions.We only discuss what is needed for a basic understanding of quantumxiMore informationxii Prefacecomputing as afield of research in its own right,although we cite sources for learningmore about advanced topics.There are some who consider quantum computing to be solely within the do-main of physics.Others think of the subject as purely mathematical.We stress thecomputer science aspect of quantum computing.It is not our intention for this book to be the definitive treatment of quantum computing.There are a few topics that we do not even touch,and there are severalothers that we approach briefly,not exhaustively.As of this writing,the bible ofquantum computing is Nielsen and Chuang’s magnificent Quantum Computing andQuantum Information(2000).Their book contains almost everything known aboutquantum computing at the time of its publication.We would like to think of ourbook as a usefulfirst step that can prepare the reader for that text.FEATURESThis book is almost entirely self-contained.We do not demand that the reader comearmed with a large toolbox of skills.Even the subject of complex numbers,which istaught in high school,is given a fairly comprehensive review.The book contains many solved problems and easy-to-understand descriptions.We do not merely present the theory;rather,we explain it and go through severalexamples.The book also contains many exercises,which we strongly recommendthe serious reader should attempt to solve.There is no substitute for rolling up one’ssleeves and doing some work!We have also incorporated plenty of programming drills throughout our text.These are hands-on exercises that can be carried out on your laptop to gain a betterunderstanding of the concepts presented here(they are also a great way of hav-ing fun).We hasten to point out that we are entirely language-agnostic.The stu-dent should write the programs in the language that feels most comfortable.Weare also paradigm-agnostic.If declarative programming is your favorite method,gofor it.If object-oriented programming is your game,use that.The programmingdrills build on one another.Functions created in one programming drill will be usedand modified in later drills.Furthermore,in Appendix C,we show how to makelittle quantum computing emulators with MATLAB or how to use a ready-madeone.(Our choice of MATLAB was dictated by the fact that it makes very easy-to-build,quick-and-dirty prototypes,thanks to its vast amount of built-in mathematicaltools.)This text appears to be thefirst to handle quantum programming languages in a significant way.Until now,there have been only research papers and a few surveyson the topic.Chapter7describes the basics of this expandingfield:perhaps some ofour readers will be inspired to contribute to quantum programming!This book also contains several appendices that are important for further study:Appendix A takes readers on a tour of major papers in quantum computing.This bibliographical essay was written by Jill Cirasella,Computational SciencesSpecialist at the Brooklyn College Library.In addition to having a master’s de-gree in library and information science,Jill has a master’s degree in logic,forwhich she wrote a thesis on classical and quantum graph algorithms.This dualbackground uniquely qualifies her to suggest and describe further readings.More informationPreface xiii Appendix B contains the answers to some of the exercises in the text.Othersolutions will also be found on the book’s Web page.We strongly urge studentsto do the exercises on their own and then check their answers against ours.Appendix C uses MATLAB,the popular mathematical environment and an es-tablished industry standard,to show how to carry out most of the mathematicaloperations described in this book.MATLAB has scores of routines for manip-ulating complex matrices:we briefly review the most useful ones and show howthe reader can quickly perform a few quantum computing experiments with al-most no effort,using the freely available MATLAB quantum emulator Quack.Appendix D,also by Jill Cirasella,describes how to use online resources to keepup with developments in quantum computing.Quantum computing is a fast-movingfield,and this appendix offers guidelines and tips forfinding relevantarticles and announcements.Appendix E is a list of possible topics for student presentations.We give briefdescriptions of different topics that a student might present before a class of hispeers.We also provide some hints about where to start looking for materials topresent.ORGANIZATIONThe book begins with two chapters of mathematical preliminaries.Chapter1con-tains the basics of complex numbers,and Chapter2deals with complex vectorspaces.Although much of Chapter1is currently taught in high school,we feel thata review is in order.Much of Chapter2will be known by students who have had acourse in linear algebra.We deliberately did not relegate these chapters to an ap-pendix at the end of the book because the mathematics is necessary to understandwhat is really going on.A reader who knows the material can safely skip thefirsttwo chapters.She might want to skim over these chapters and then return to themas a reference,using the index and the table of contents tofind specific topics.Chapter3is a gentle introduction to some of the ideas that will be encountered throughout the rest of the ing simple models and simple matrix multipli-cation,we demonstrate some of the fundamental concepts of quantum mechanics,which are then formally developed in Chapter4.From there,Chapter5presentssome of the basic architecture of quantum computing.Here one willfind the notionsof a qubit(a quantum generalization of a bit)and the quantum analog of logic gates.Once Chapter5is understood,readers can safely proceed to their choice of Chapters6through11.Each chapter takes its title from a typical course offered in acomputer science department.The chapters look at that subfield of quantum com-puting from the perspective of the given course.These chapters are almost totallyindependent of one another.We urge the readers to study the particular chapterthat corresponds to their favorite course.Learn topics that you likefirst.From thereproceed to other chapters.Figure0.1summarizes the dependencies of the chapters.One of the hardest topics tackled in this text is that of considering two quan-tum systems and combining them,or“entangled”quantum systems.This is donemathematically in Section2.7.It is further motivated in Section3.4and formallypresented in Section4.5.The reader might want to look at these sections together.xivPrefaceFigure 0.1.Chapter dependencies.There are many ways this book can be used as a text for a course.We urge instructors to find their own way.May we humbly suggest the following three plans of action:(1)A class that provides some depth might involve the following:Go through Chapters 1,2,3,4,and 5.Armed with that background,study the entirety of Chapter 6(“Algorithms”)in depth.One can spend at least a third of a semester on that chapter.After wrestling a bit with quantum algorithms,the student will get a good feel for the entire enterprise.(2)If breadth is preferred,pick and choose one or two sections from each of the advanced chapters.Such a course might look like this:(1),2,3,4.1,4.4,5,6.1,7.1,9.1,10.1,10.2,and 11.This will permit the student to see the broad outline of quantum computing and then pursue his or her own path.(3)For a more advanced class (a class in which linear algebra and some mathe-matical sophistication is assumed),we recommend that students be told to read Chapters 1,2,and 3on their own.A nice course can then commence with Chapter 4and plow through most of the remainder of the book.If this is being used as a text in a classroom setting,we strongly recommend that the students make presentations.There are selected topics mentioned in Appendix E.There is no substitute for student participation!Although we have tried to include many topics in this text,inevitably some oth-ers had to be left out.Here are a few that we omitted because of space considera-tions:many of the more complicated proofs in Chapter 8,results about oracle computation,the details of the (quantum)Fourier transforms,and the latest hardware implementations.We give references for further study on these,as well as other subjects,throughout the text.More informationMore informationPreface xvANCILLARIESWe are going to maintain a Web page for the text at/∼noson/qctext.html/The Web page will containperiodic updates to the book,links to interesting books and articles on quantum computing,some answers to certain exercises not solved in Appendix B,anderrata.The reader is encouraged to send any and all corrections tonoson@Help us make this textbook better!ACKNOLWEDGMENTSBoth of us had the great privilege of writing our doctoral theses under the gentleguidance of the recently deceased Alex Heller.Professor Heller wrote the follow-ing1about his teacher Samuel“Sammy”Eilenberg and Sammy’s mathematics:As I perceived it,then,Sammy considered that the highest value in mathematicswas to be found,not in specious depth nor in the overcoming of overwhelmingdifficulty,but rather in providing the definitive clarity that would illuminate itsunderlying order.This never-ending struggle to bring out the underlying order of mathematical structures was always Professor Heller’s everlasting goal,and he did his best to passit on to his students.We have gained greatly from his clarity of vision and his viewof mathematics,but we also saw,embodied in a man,the classical and sober ideal ofcontemplative life at its very best.We both remain eternally grateful to him.While at the City University of New York,we also had the privilege of inter-acting with one of the world’s foremost logicians,Professor Rohit Parikh,a manwhose seminal contributions to thefield are only matched by his enduring com-mitment to promote younger researchers’work.Besides opening fascinating vis-tas to us,Professor Parikh encouraged us more than once to follow new directionsof thought.His continued professional and personal guidance are greatly appre-ciated.We both received our Ph.D.’s from the Department of Mathematics in The Graduate Center of the City University of New York.We thank them for providingus with a warm and friendly environment in which to study and learn real mathemat-ics.Thefirst author also thanks the entire Brooklyn College family and,in partic-ular,the Computer and Information Science Department for being supportive andvery helpful in this endeavor.1See page1349of Bass et al.(1998).More informationxvi PrefaceSeveral faculty members of Brooklyn College and The Graduate Center were kind enough to read and comment on parts of this book:Michael Anshel,DavidArnow,Jill Cirasella,Dayton Clark,Eva Cogan,Jim Cox,Scott Dexter,EdgarFeldman,Fred Gardiner,Murray Gross,Chaya Gurwitz,Keith Harrow,JunHu,Yedidyah Langsam,Peter Lesser,Philipp Rothmaler,Chris Steinsvold,AlexSverdlov,Aaron Tenenbaum,Micha Tomkiewicz,Al Vasquez,Gerald Weiss,andPaula Whitlock.Their comments have made this a better text.Thank you all!We were fortunate to have had many students of Brooklyn College and The Graduate Center read and comment on earlier drafts:Shira Abraham,RachelAdler,Ali Assarpour,Aleksander Barkan,Sayeef Bazli,Cheuk Man Chan,WeiChen,Evgenia Dandurova,Phillip Dreizen,C.S.Fahie,Miriam Gutherc,RaveHarpaz,David Herzog,Alex Hoffnung,Matthew P.Johnson,Joel Kammet,SerdarKara,Karen Kletter,Janusz Kusyk,Tiziana Ligorio,Matt Meyer,James Ng,SeverinNgnosse,Eric Pacuit,Jason Schanker,Roman Shenderovsky,Aleksandr Shnayder-man,Rose B.Sigler,Shai Silver,Justin Stallard,Justin Tojeira,John Ma Sang Tsang,Sadia Zahoor,Mark Zelcer,and Xiaowen Zhang.We are indebted to them.Many other people looked over parts or all of the text:Scott Aaronson,Ste-fano Bettelli,Adam Brandenburger,Juan B.Climent,Anita Colvard,Leon Ehren-preis,Michael Greenebaum,Miriam Klein,Eli Kravits,Raphael Magarik,JohnMaiorana,Domenico Napoletani,Vaughan Pratt,Suri Raber,Peter Selinger,EvanSiegel,Thomas Tradler,and Jennifer Whitehead.Their criticism and helpful ideasare deeply appreciated.Thanks to Peter Rohde for creating and making available to everyone his MAT-LAB q-emulator Quack and also for letting us use it in our appendix.We had a gooddeal of fun playing with it,and we hope our readers will too.Besides writing two wonderful appendices,our friendly neighborhood librar-ian,Jill Cirasella,was always just an e-mail away with helpful advice and support.Thanks,Jill!A very special thanks goes to our editor at Cambridge University Press,HeatherBergman,for believing in our project right from the start,for guiding us through thisbook,and for providing endless support in all matters.This book would not existwithout her.Thanks,Heather!We had the good fortune to have a truly stellar editor check much of the text many times.Karen Kletter is a great friend and did a magnificent job.We also ap-preciate that she refrained from killing us every time we handed her altered draftsthat she had previously edited.But,of course,all errors are our own!This book could not have been written without the help of my daughter,Hadas-sah.She added meaning,purpose,and joy.N.S.Y.My dear wife,Rose,and our two wondrous and tireless cats,Ursula and Buster, contributed in no small measure to melting my stress away during the long andpainful hours of writing and editing:to them my gratitude and love.(Ursula is ascientist cat and will read this book.Buster will just shred it with his powerful claws.)M.A.M.。

References[Bai 2001a] X. Bai, W. T. Tsai, R. Paul, T. Shen and B. Li, “Distributed End-to-End Testing Management”, to appear in Proc. of IEEE EDOC, 2001.[Bai 2001b] X. Bai, W. T. Tsai, R. Paul, K. Feng, L. Yu, “Scenario-Based Business Modeling”, Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287, 2001.[Beizer 1990] B. Beizer, Software Testing, 2nd edition, Van Nostrand Reinhold, New York, New York, 1990.[Beizer 1995] B. Beizer, Black-Box Testing: Techniques for Functional Testing of Software and Systems, John Wiley & Sons, New York, New York, 1995.[Binder 2000] R. Binder, Testing Object-Oriented Systems: Models, Patterns, and Tools, Addison Wesley, Reading, MA, 2000.[Burns 1990] A. Burns and A. Wellings, Real-Time Systems and Their Programming Languages, Addison Wesley, Reading, MA, 1990.[DoD 1999] DoD OASD C3I Investment and Acquisition, “Year 2000 Management Plan”, 1999.[DoD 2000] DoD OASD C3I Investment and Acquisition, “Guide for Remediating Latent Year 2000 Defects Caused by Date Windowing”, 2000.[DoD 2001] DoD OASD C3I Investment and Acquisition, “End-to-End Integration Testing Guidebook”, 2001.[Fewster 1999] M. Fewster and D. Graham, Software Test Automation: Effective Use of Test Execution Tools, Addison Wesley, Reading, MA, 1999.[Grehan 1998] R. Grehan, R. Moote, and I. Cyliax, Real-Time Programming: A Guide to 32-bit Embedded Development, Addison Wesley, Reading, MA, 1998.[Harmelen 2001] M. V. Harmelen, editor, Object Modeling and User Interface Design, Addison Wesley, Reading, MA, 2001.[Kalinowski 2001] K. Kalinowski, “GDLS Vetronics Software Strategy”, NDIA 2001 Vehicle Technologies Symposium, Intelligent Systems for the Objective Fleet, May 2001.[Kaner 1999] C. Kaner, J. Falk, and H. Q. Nguyen, Testing Computer Software, 2nd Edition, Wiley, New York, New York, 1999.[Kirani 1994] S. Kirani and W. T. Tsai, “Method Sequence Specification and Verification of Classes”, Journal of Object-Oriented Programming, 1994.[Kulak 1998] D. Kulak and E. Guiney, Use Cases: Requirements in Context, ACM Press, Addison Wesley, Reading, MA, 1998.[Kung 1999] D. C. Kung, P. Hsia, and J. Gao, Testing Object-Oriented Software, IEEE Computer Society Press, Los Alamitos, CA, 1999.[Leveson 1995] N. Leveson, Safeware: System Safety and Computers, Addison Wesley, Reading, MA, 1995.[Lyu 1996] M. Lyu, editor, Handbook of Software Reliability Engineering, IEEE Computer Society Press, McGraw Hill, New York, New York, 1996.[Marick 1995] B. Marick, The Craft of Software Testing, Prentice Hall, Englewood Cliffs, NJ, 1995.[Mojdehbakhsh 1994] R. Mojdehbakhsh, S. Kirani, W. T. Tsai, and L. Elliot, "Retrofitting Software Safety in an Implantable Medical Device", IEEE Software, Vol. 11, No. 1, Jan. 1994, pp. 41-50.[Mosley 2000] D. J. Mosley, Client-Server Software Testing on the Desktop and the Web, Prentice Hall PTR, Upper Saddle River, NJ, 2000.[Musa 1987] J. Musa, A. Iannino, and K. Okumoto, Software Reliability: Measurement, Prediction, Application, McGraw-Hill, New York, New York, 1987.[Nguyen 2001] H. Q. Nguyen, Testing Applications on the Web, Testing Planning for Internet-Based Sys tems, Wiley, 2001.[Onoma 1998] A. K. Onoma, W. T. Tsai, M. Poonawala, and H. Suganuma, “Regression Testing in an Industrial Environment”, Communications of ACM, May 1998.[Paul 2000] R. Paul and W. T. Tsai, “Assurance-Based Testing – A New Quality Assurance Technique”, Proc. of Quality Week, Europe, 2000.[Paul 2001] R. Paul, W.T. Tsai, B. Li, and X. Bai, “XML-Based Test Assets Management”, Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287, 2001.[Poonawala 1997] M. Poonawala, S. Subramanian, R. Vishnuvajjala, W. T. Tsai, R. Mojdehbakhsh and L. Elliott,"Testing Safety-Critical Systems -- A Reuse-Oriented Approach", Proc. of 9th International Conference on SEKE, 1997, pp. 271-278. [Pressman 2000] R. Pressman, Software Engineering: A Practitioner’s Approach,5th edition, McGraw-Hill, New York, New York, 2000.[RAC 1998] Reliability Toolkit: Commercial Practices Edition, A Practical Guide for Commercial Products and Military Systems Under Acquisition Reform, Reliability Analysis Center (RAC), Rome Laboratory.[RTCA 1992] RTCA/DO-178B, "Software Considerations in Airborne Systems and Equipment Certification," December 1, 1992.[Rumbaugh 1999] J. Rumbaugh, I. Jacobson, and G. Booch, The Unified Modeling Language Reference Manual, Addison Wesley, Reading, MA, 1999.[Sommerville 2000] I. Sommerville, Software Engineering, 6th edition, Addison Wesley, Reading, MA, 2000.[Storey 1996] N. Storey, Safety-Critical Computer Systems, Addison-Wesley, Reading, MA, 1996.[Tsai 1998] W. T. Tsai, R. Mojdehbakhsh and F. Zhu, "Ensuring System and Software Reliability in Safety-Critical Applications", in Proc. of IEEE Application-Specific Software Engineering Technology, 1998.[Tsai 1999a] W. T. Tsai, R. Paul, W. Shao, S. Rayadurgam, and J. Li, “Assurance-Based Y2K Testing”, 1999 Proc. 4th IEEE International Symposium on High-Assurance Systems Engineering, pp. 27-34.[Tsai 1999b] W. T. Tsai, Y. Tu, W. Shao and E. Ebner, “Testing Extensible Design Patterns in Object-Oriented Frameworks through Hierarchical Scenario Templates”, Proc. COMPSAC’99, 1999, pp. 166-171.[Tsai 1999c] W. T. Tsai, R. Vishnuvajjala and D. Zhang, “Verification and Validation of Knowledge-Based Systems”, IEEE Trans. on Knowledge and Data Engineering, 1999.[Tsai 2001a] W.T. Tsai, X. Bai, R. Paul, W. Shao, V. Agarwal, T. Sheng, and B. Li, “End-to-End Integration Testing Design”, to appear in Proc. of IEEE COMPSAC 2001.[Tsai 2001b] W.T. Tsai, X. Bai, R. Paul, and L. Yu, “Scenario-Based Functional Regression Testing”, to appear in Proc. of IEEE COMPSAC, 2001.[Uehara 2000] S. Uehara, W. T. Tsai, T. Sano and Baba, Software Maintenance and Re-Engineering, Kyoritsu Publication, Japan, 2000.[Vishnuvajjala 2001] R. Vishnuvajjala, W. T. Tsai, R. Paul, “Testing Timing Constraints in Time-Critical Systems: Problems, Techniques and Patterns”, draft DoD OASD C3I Investment and Acquisition Guidebook, 2001.[Zhu 1998] F. Zhu and W. T. Tsai, "Automating Regression Testing for Real-Time Software in a Distributed Environment", Proc. of IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, 1998.Website References[FAA_web] Federal Aviation Administration (FAA), Department of Transportation, “Quality Assurance of Software Used in Aircraft or Related Products”, AC 21-33, /software/Policy%20&%20Guidance/ac21-33.pdf.[FDA_web_1] Food and Drug Administration (FDA) “General Principle of Software Validation: Guidance for Industries,”/cdrh/comp/swareval.html.[FDA_web_2] Food and Drug Administration (FDA) “Medical Device Use-Safety:Incorporating Human Factors Engineering into Risk Management,”/cdrh/humfac/1497.pdf[Johnson_web 1998] L. A. Johnson, “Do-198B, ‘Software Consideration in Airborne Systems and Equipment Certification’”, /CrossTalk/1998/oct/schad.asp.[Musa_web] J. D. Musa and J. Widmaier “Software-Reliability-Engineered Testing,”/crosstalk/1996/jun/Reliabil.asp.[NASA_web_1] NASA Software Assurance Standards, NASA-STD-2201-93, /assure/astd.txt.[NASA_web_2] NASA Software Assurance Guidebook, NASA-GB-A201, /assure/agb.txt.[NASA_web_3] NASA, Software Safety NASA Technical Standards, NASA-STD-8719.13A, 1997, /assure/nss8719_13.html.[NRC_web] Office of Nuclear Regulatory Research, U.S. Nuclear Regulatory Commission (NRC), Fault Tree Handbook, 1981. Available at the website /NRC/NUREGS/SR0492/index.html.[Parasoft_web] Parasoft, “Jtest,”/products/jtest/index.htm Website Addresses for Similar Courses Offered at Other Universities orConferencesCMU (/~koopman/)Southern Polytechnic State University Southern Polytechnic State University (SPSU) (/pbobbie/embsys.htm)Georgia Tech (/~hamblen/489X/)University of Colorado at Bounder (/embedded.html), University of California at Irvine (/~rgupta/iec.html)Depaul University (/kbernstein/SE540/)University of Texas at Austin (/~bev ans/)Dublin City University at Ireland (papp.dcu.ie/~dsinclai/rtes.html) University of Florida (/)The Embedded Object-Based Systems Workshop(/news/meetings/embedded2001/progam.htm)The Embedded System Conference (/sf/classes.htm)Case Studies:[NRC_CASE1 1996] Office of Nuclear Regulatory Research, U.S. Nuclear Regulatory Commission, “Guide to Verification and Validation of the SCALE-4 Criticality Safety Software”, 1996. Available at the website /NRC/NRREGS/CR6483/index.html.[NRC_CASE2 1996] Office of Nuclear Regulatory Research, U.S. Nuclear Regulatory Commission,”Guide to Verification and Validation of the SCALE-4 Radiation Shielding Software”, 1996. Available at the website /NRC/NUREGS/CR6484/cr6484.pdf.。

SymbRecorder 5.0.0 User ManualSymbsoft StudioSymbRecorder 5.0.0 Features•T otally new business level call recorder & voice recorder!•Phone call recording automatically or manually, BEEP FREE!•Voice memo recording, make your phone as a Dictaphone.•Most advanced beep suppression technique, 3 Beep Suppression Modes:◦Mode1Perfect quality in AMR/WAV format without audio gaps, the device side will hear a beep butthe other side will NOT, for newer cellphones.◦Mode2Perfect quality in AMR/WAV format without audio gaps, both sides will NOT hear the beep,profile will be changed before recording and recovered after recording automatically, for oldercellphones.◦Mode3With some loss of audio (This is tunable, so it can usually be improved) in AMR format, bothsides will NOT hear the beep, for all cellphones.•Recording quality (AMR/WAV) can be adjusted by setting different Sampling Bitrate.•All S60 devices even those with few keys like N8/C7/5800 can use hotkey to start/stop recording conveniently. Y ou can choose a key from a list (21 keys including key XpressMedia and key Menu) and select a press method (PressLong/PressOnce/PressT wice/PressThrice) to act as a hotkey.•Recording all calls, or some of the calls according to the Include List/Exclude List.•Auto Send the clip via MMS/Email after recording.•Manually send clips via MMS/Email/Bluetooth/Infrared.•The clip can be stored in any drive, such as C, E, F, etc.•T otal Disk Limited can be set. The oldest clips will be erased automatically when the total size of clips exceeds the setting value.•Use advanced RDBMS/SQL technique to manage clips, you can add note to a certain clip, view the detailed clip information, search, play back, delete, copy and move clips conveniently and quickly.•Password protection, no other program can visit your clips. Y ou can copy/move your clips to other folders if you want to share them.•Client/Server structure, the server program which runs in the background is powerful but it is really tiny (less than 60KB) with less consumption of resources.•FREE Updates for the life of your device, if you purchase SymbRecorder directly from .CompatibilitySupport all of the following phones:•Symbian^3(Currently may beep on both sides, we're working on an update)[Symbian^3]Nokia C6-01[Symbian^3]Nokia C7-00[Symbian^3]Nokia E7-00[Symbian^3]Nokia N8-00•S60 5th(Beep suppression Mode1 and Mode3 are applicable)[Symbian 9.4]Nokia C5-03[Symbian 9.4]Nokia 5250[Symbian 9.4]Nokia 5228[Symbian 9.4]Nokia 5233[Symbian 9.4]Nokia C6-00[Symbian 9.4]Nokia 5230 Nuron[Symbian 9.4]Nokia 5235 Ovi Music Unlimited[Symbian 9.4]Nokia N97 mini[Symbian 9.4]Nokia X6-00[Symbian 9.4]Nokia 5230[Symbian 9.4]Nokia 5530 XpressMusic[Symbian 9.4]Nokia N97[Symbian 9.4]Nokia 5800 XpressMusic•S60 3rd FP2(Beep suppression Mode1 and Mode3 are applicable) [Symbian 9.3]Nokia X5-01[Symbian 9.3]Nokia E73 Mode[Symbian 9.3]Nokia C5-01[Symbian 9.3]Nokia X5-00[Symbian 9.3]Nokia E5-00[Symbian 9.3]Nokia 6788i[Symbian 9.3]Nokia C5-00[Symbian 9.3]Nokia 6700 slide[Symbian 9.3]Nokia 6788[Symbian 9.3]Nokia 6760 slide[Symbian 9.3]Nokia 6790 slide[Symbian 9.3]Nokia 6790 Surge[Symbian 9.3]Nokia E72[Symbian 9.3]Nokia 6730 classic[Symbian 9.3]Nokia E52[Symbian 9.3]Nokia E71x[Symbian 9.3]Nokia 5730 XpressMusic[Symbian 9.3]Nokia N86 8MP[Symbian 9.3]Nokia 6710 Navigator[Symbian 9.3]Nokia 6720 classic[Symbian 9.3]Nokia E55[Symbian 9.3]Nokia E75[Symbian 9.3]Nokia 5630 XpressMusic[Symbian 9.3]Nokia N79[Symbian 9.3]Nokia N85[Symbian 9.3]Nokia N96-3[Symbian 9.3]Nokia 5320 XpressMusic[Symbian 9.3]Nokia 6650 fold[Symbian 9.3]Nokia 6210 Navigator[Symbian 9.3]Nokia 6220 classic[Symbian 9.3]Nokia N78[Symbian 9.3]Nokia N96•S60 3rd FP1(Beep suppression Mode2 and Mode3 are applicable) [Symbian 9.2]Nokia E63[Symbian 9.2]Nokia E66[Symbian 9.2]Nokia E71[Symbian 9.2]Nokia 6124 classic[Symbian 9.2]Nokia N82[Symbian 9.2]Nokia E51[Symbian 9.2]Nokia N95-3 NAM[Symbian 9.2]Nokia N81[Symbian 9.2]Nokia N81 8GB[Symbian 9.2]Nokia N95 8GB[Symbian 9.2]Nokia 6121 classic[Symbian 9.2]Nokia 6120 classic[Symbian 9.2]Nokia 5700 XpressMusic[Symbian 9.2]Nokia 6110 Navigator[Symbian 9.2]Nokia E90 Communicator[Symbian 9.2]Nokia N76[Symbian 9.2]Nokia 6290[Symbian 9.2]Nokia N95•S60 3rd(Beep suppression Mode3 is applicable)[Symbian 9.1]Nokia E61i[Symbian 9.1]Nokia E65[Symbian 9.1]Nokia N77[Symbian 9.1]Nokia N93i[Symbian 9.1]Nokia N91 8GB[Symbian 9.1]Nokia E62[Symbian 9.1]Nokia E50[Symbian 9.1]Nokia 5500 Sport[Symbian 9.1]Nokia N73[Symbian 9.1]Nokia N93[Symbian 9.1]Nokia N71[Symbian 9.1]Nokia N80[Symbian 9.1]Nokia N92[Symbian 9.1]Nokia E60[Symbian 9.1]Nokia E61[Symbian 9.1]Nokia E70[Symbian 9.1]Nokia 3250[Symbian 9.1]Nokia N91RegistrationBy default, the software first installed is Demo Edition, which is full featured for free for 14 days. 14 days later it's limited to record only 1 minute each time. T o remove this limit you need to purchase a Register Code. The software will be changed automatically from Demo Edition to Professional Edition which has no limit after inputting the Register Code on your phone.NoticeDue to regular firmware updates, maybe some features don't work on your phone. Prior to purchase please download and install the Demo Edition which is full featured for 14 days.Server / Client programSymbRecorder has two separate executable programs - a server program and a client program packed in the same application .sisx file. The server program is the most important one, it starts up automatically upon power on by default, and continue running in the background with no visible user interface, waiting for phone call events and hot key events to start/stop recording. The client program provides screens for user to change settings and manage recorded clips. Y ou should start up the client program manually, and stop it when you don't use it.Main screenOptions (Left Softkey)•Start Recording - Manually start phone call recording while on a call, or start voice memo recording while not on a call.•Stop Recording - Manually stop phone call recording while on a call, or stop voice memo recordingwhile not on a call.•Phone Call Clips - Open the Phone Call Clips screen to manage the recorded phone call clips.•Voice Memo Clips - Open the Voice Memo Clips screen to manage the recorded voice memo clips.•Settings - Open the Settings screen.•Include List - If the Auto Record Mode setting on the settings screen is set to "Include List", this menu item is visible, otherwise it is invisible.•Exclude List - If the Auto Record Mode setting on the settings screen is set to "Exclude List", this menu item is visible, otherwise it is invisible.•Register - Input your Register Code.•About - Display the version and the registration state of the software.Exit (Right Softkey) - Exit the client program. However the server program running in the background will remain running, continue to monitor phone call events and hotkey events.Phone Call Clips screenOptions (Left Softkey)•Play Back - Play back the current clip in the list displayed.•Details - Display the detailed information of the current clip, such as telephone number, contact, call direction, date, time, duration, file size, drive, note, etc.•Add Note - Add a note to the current clip, up to 255 chars.•Search - Input any part of the telephone number, any part of the contact, any part of the note, start date and end date to retrieve clips.•Mark/Unmark - Mark one or more clips to perform an action like delete, copy, move, send•Delete - Delete marked clips. If there is no clip marked, the current clip will be deleted.•Copy T o - Copy the marked clips to a folder. If there is no clip marked, the current clip will be copied.•Move T o - Copy the marked clips to a folder then delete them from the SymbRecorder database. If there is no clip marked, the current clip will be moved.•Send - Send the marked clips via MMS/Email/Bluetooth/Infrared. If there is no clip marked, the current clip will be sent.Back (Right Softkey) - Return to the Main screen.Voice Memo Clips screenOptions (Left Softkey)•Play Back - Play back the current clip in the list displayed.•Details - Display the detailed information of the current clip, such as date, time, duration, file size, drive, note, etc.•Add Note - Add a note to the current clip, up to 255 chars.•Search - Input any part of the telephone number, any part of the contact, any part of the note, start date and end date to retrieve clips.•Mark/Unmark - Mark one or more clips to perform an action like delete, copy, move, send.•Delete - Delete marked clips. If there is no clip marked, the current clip will be deleted.•Copy T o - Copy the marked clips to a folder. If there is no clip marked, the current clip will be copied.•Move T o - Copy the marked clips to a folder then delete them from the SymbRecorder database. If there is no clip marked, the current clip will be moved.•Send - Send the marked clips via MMS/Email/Bluetooth/Infrared. If there is no clip marked, the current clip will be sent.Back (Right Softkey) - Return to the Main screen.Application Settings screenOptions (Left Softkey) - Switch to Application settings, Phone Call Settings or Voice Memo Settings screen.•Password Protection◦Y es - Enable software password protection.◦No - Disable software password protection.•PasswordSet the password to enter the software (if Password Protection is set to "Y es"), up to 32characters.•Auto Start Server◦Y es - Enable the server program to start up automatically upon power on. This item must be set to "Y es" if you want to record phone calls automatically.◦No - Disable the server program to start up automatically upon power on.•HotkeySelect one of the 21 keys to be a hotkey: #, *, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, Up Arrow, Down Arrow,Left Arrow, Right Arrow, Back Space(C key), Application Menu, Green key(Send/Answer key), Red key(Hangup key), XpressMusic key•Hotkey Mode◦Press Long - Press and hold the hotkey for more than 0.5 second to trigger the action of starting/stopping recording.◦Press Once - Press the hotkey once to trigger the action◦Press T wice - Press the hotkey twice quickly to trigger the action◦Press Thrice - Press the hotkey thrice quickly to trigger the action◦Disabled - Disable the hotkey.•Recording Indicator◦At T op Left - Display a red indicator at the top left corner of the screen during recording.◦At T op Middle - Display a red indicator at the top middle position of the screen during recording.◦At T op Right - Display a red indicator at the top right corner of the screen during recording.◦Don't Display - Don't display any indicator during recording.Back (Right Softkey) - Return to the Main screen.Phone Call Settings screenOptions (Left Softkey) - Switch to Application settings, Phone Call Settings or Voice Memo Settings screen.•Auto Record Mode◦All - Record all incoming/outgoing calls automatically.◦Include List - Record the incoming/outgoing calls automatically only if the phone number is in the Include List.◦Exclude List - Record the incoming/outgoing calls automatically only if the phone number is not in the Exclude List.◦Disabled - Don't record any call automatically.•Sampling Bitrate◦Medium - Set the sampling bitrate to the medium value your phone supported, the recording quality and the file size will be in a good balance.◦High - Set the sampling bitrate to the highest value your phone supported, the recording quality will be better, but the file size will be Larger.◦Low - Set the sampling bitrate to the lowest value your phone supported, the recording quality will be poorer, but the file size will be smaller.•Beep Suppress Mode◦Disabled - Perfect quality in AMR/WAV format without audio gaps, both sides will hear a beep, for all phones.◦Mode1 - Perfect quality in AMR/WAV format without audio gaps, the device side will hear a beep but the other side will NOT, for newer phones.◦Mode2 - Perfect quality in AMR/WAV format without audio gaps, both sides will NOT hear the beep, profile will be changed before recording and recovered after recording automatically,for older phones.◦Mode3 - With some loss of audio in AMR format, both sides will NOT hear the beep, for all phones (the Beep Suppress T une item should be adjusted).•Beep Suppress T uneThis item is visible only if the Beep Suppress Mode was set to "Mode3". The larger the value ofthis item is, the better the recording quality will be. But when the value exceeds a certain pointdepending on your phone, both sides will hear a beep. T o suppress the beep you must set thevalue below that point for "Mode3".•Record Format◦AMR - Record in AMR format (suggested, file size is much more smaller).◦WAV - Record in WAV format.•Record Save In◦Drive C◦Drive E◦Drive F◦...◦Drive I•T otal Disk Limit (MB)If the value of this item is larger than 0, the oldest phone call clips will be erased automaticallywhen the total size of phone call clips exceeds the value.•Ask Before Save◦Y es - Ask you if you want to save the clip or not at the end of recording.◦No - Don't ask, save the clip directly at the end of recording.•Sum After Record◦Y es - Display a summary information of the clip at the end of recording. If the Ask Before Save is set to "Y es", this item will be ignored.◦No - Don't display a summary information of the clip at the end of recording.•Auto Send Mode◦Disabled - Don't send the clip automatically at the end of recording.◦By Email - Send the clip automatically to the email address defined in the Recipient Email item at the end of recording.◦By MMS - Send the clip automatically to the telephone number defined in the Recipient MMS T ele item at the end of recording.•Recipient EmailSet the email address to receive phone call clips sent by email automatically. The value of thisitem is also used as the default recipient email address when you manually send clips by email.• Recipient MMS T eleSet the telephone number to receive phone call clips sent by mms automatically. The value of this item is also used as the default recipient telephone number when you manually send clips bymms.• Delete After Send◦Y es - If the clip is successfully sent automatically by email or by mms at the end of recording, it will be deleted immediately.◦No - Don't delete the clip automatically after send.Back (Right Softkey) - Return to the Main screen.Voice Memo Settings screenOptions (Left Softkey) - Switch to Application settings, Phone Call Settings or Voice Memo Settings screen.•Sampling Bitrate◦Medium - Set the sampling bitrate to the medium value your phone supported, the recording quality and the file size will be in a good balance.◦High - Set the sampling bitrate to the highest value your phone supported, the recording quality will be better, but the file size will be Larger.◦Low - Set the sampling bitrate to the lowest value your phone supported, the recording quality will be poorer, but the file size will be smaller.•Record Format◦AMR - Record in AMR format (suggested, file size is much more smaller).◦WAV - Record in WAV format.•Record Save In◦Drive C◦Drive E◦Drive F◦...◦Drive I•T otal Disk Limit (MB)If the value of this item is larger than 0, the oldest voice memo clips will be erased automatically when the total size of voice memo clips exceeds the value.•Ask Before Save◦Y es - Ask you if you want to save the clip or not at the end of recording.◦No - Don't ask, save the clip directly at the end of recording.•Sum After Record◦Y es - Display a summary information of the clip at the end of recording. If the Ask Before Save is set to "Y es", this item will be ignored.◦No - Don't display a summary information of the clip at the end of recording.•Auto Send Mode◦Disabled - Don't send the clip automatically at the end of recording.◦By Email - Send the clip automatically to the email address defined in the Recipient Emailitem at the end of recording.◦By MMS - Send the clip automatically to the telephone number defined in the Recipient MMS T ele item at the end of recording.•Recipient EmailSet the email address to receive voice memo clips sent by email automatically. The value of this item is also used as the default recipient email address when you manually send clips by email.• Recipient MMS T eleSet the telephone number to receive voice memo clips sent by mms automatically. The value of this item is also used as the default recipient telephone number when you manually send clips by mms.• Delete After Send◦Y es - If the clip is successfully sent automatically by email or by mms at the end of recording, it will be deleted immediately.◦No - Don't delete the clip automatically after send.Back (Right Softkey) - Return to the Main screen.Include List screenOptions (Left Softkey)•Select From Addr Book - Select contacts from address book and add the telephone number, name to the Include List.•Add T ele Manually - Add telephone number, name to the Include List manually.•Mark/Unmark - Mark one or more entries to perform an action of delete.•Delete - Delete marked entries. If there is no entry marked, the current entry will be deleted. Back (Right Softkey) - Return to the Main screen.Exclude List screenOptions (Left Softkey)•Select From Addr Book - Select contacts from address book and add the telephone number, name to the Exclude List.•Add T ele Manually - Add telephone number, name to the Exclude List manually.•Mark/Unmark - Mark one or more entries to perform an action of delete.•Delete - Delete marked entries. If there is no entry marked, the current entry will be deleted. Back (Right Softkey) - Return to the Main screen.Note1T o send clips by email, automatically or manually, you must create at least one email box in the "Messaging/Settings/E-Mail/Mailboxes" on your phone. Please refer to the user guide of your phone to do that, and confirm the email box can be used to send email successfully.Note2The maximum size of clips to be sent by MMS is limited by your phone, your GSM/CDMA network, your communication operator. It's different from country to country, region to region. If the recorded clip is too large it may fail to send by MMS.。

425 BibliographyH.A KAIKE(1974).Markovian representation of stochastic processes and its application to the analysis of autoregressive moving average processes.Annals Institute Statistical Mathematics,vol.26,pp.363-387. B.D.O.A NDERSON and J.B.M OORE(1979).Optimal rmation and System Sciences Series, Prentice Hall,Englewood Cliffs,NJ.T.W.A NDERSON(1971).The Statistical Analysis of Time Series.Series in Probability and Mathematical Statistics,Wiley,New York.R.A NDRE-O BRECHT(1988).A new statistical approach for the automatic segmentation of continuous speech signals.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-36,no1,pp.29-40.R.A NDRE-O BRECHT(1990).Reconnaissance automatique de parole`a partir de segments acoustiques et de mod`e les de Markov cach´e s.Proc.Journ´e es Etude de la Parole,Montr´e al,May1990(in French).R.A NDRE-O BRECHT and H.Y.S U(1988).Three acoustic labellings for phoneme based continuous speech recognition.Proc.Speech’88,Edinburgh,UK,pp.943-950.U.A PPEL and A.VON B RANDT(1983).Adaptive sequential segmentation of piecewise stationary time rmation Sciences,vol.29,no1,pp.27-56.L.A.A ROIAN and H.L EVENE(1950).The effectiveness of quality control procedures.Jal American Statis-tical Association,vol.45,pp.520-529.K.J.A STR¨OM and B.W ITTENMARK(1984).Computer Controlled Systems:Theory and rma-tion and System Sciences Series,Prentice Hall,Englewood Cliffs,NJ.M.B AGSHAW and R.A.J OHNSON(1975a).The effect of serial correlation on the performance of CUSUM tests-Part II.Technometrics,vol.17,no1,pp.73-80.M.B AGSHAW and R.A.J OHNSON(1975b).The influence of reference values and estimated variance on the ARL of CUSUM tests.Jal Royal Statistical Society,vol.37(B),no3,pp.413-420.M.B AGSHAW and R.A.J OHNSON(1977).Sequential procedures for detecting parameter changes in a time-series model.Jal American Statistical Association,vol.72,no359,pp.593-597.R.K.B ANSAL and P.P APANTONI-K AZAKOS(1986).An algorithm for detecting a change in a stochastic process.IEEE rmation Theory,vol.IT-32,no2,pp.227-235.G.A.B ARNARD(1959).Control charts and stochastic processes.Jal Royal Statistical Society,vol.B.21, pp.239-271.A.E.B ASHARINOV andB.S.F LEISHMAN(1962).Methods of the statistical sequential analysis and their radiotechnical applications.Sovetskoe Radio,Moscow(in Russian).M.B ASSEVILLE(1978).D´e viations par rapport au maximum:formules d’arrˆe t et martingales associ´e es. Compte-rendus du S´e minaire de Probabilit´e s,Universit´e de Rennes I.M.B ASSEVILLE(1981).Edge detection using sequential methods for change in level-Part II:Sequential detection of change in mean.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-29,no1,pp.32-50.426B IBLIOGRAPHY M.B ASSEVILLE(1982).A survey of statistical failure detection techniques.In Contribution`a la D´e tectionS´e quentielle de Ruptures de Mod`e les Statistiques,Th`e se d’Etat,Universit´e de Rennes I,France(in English). M.B ASSEVILLE(1986).The two-models approach for the on-line detection of changes in AR processes. In Detection of Abrupt Changes in Signals and Dynamical Systems(M.Basseville,A.Benveniste,eds.). Lecture Notes in Control and Information Sciences,LNCIS77,Springer,New York,pp.169-215.M.B ASSEVILLE(1988).Detecting changes in signals and systems-A survey.Automatica,vol.24,pp.309-326.M.B ASSEVILLE(1989).Distance measures for signal processing and pattern recognition.Signal Process-ing,vol.18,pp.349-369.M.B ASSEVILLE and A.B ENVENISTE(1983a).Design and comparative study of some sequential jump detection algorithms for digital signals.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-31, no3,pp.521-535.M.B ASSEVILLE and A.B ENVENISTE(1983b).Sequential detection of abrupt changes in spectral charac-teristics of digital signals.IEEE rmation Theory,vol.IT-29,no5,pp.709-724.M.B ASSEVILLE and A.B ENVENISTE,eds.(1986).Detection of Abrupt Changes in Signals and Dynamical Systems.Lecture Notes in Control and Information Sciences,LNCIS77,Springer,New York.M.B ASSEVILLE and I.N IKIFOROV(1991).A unified framework for statistical change detection.Proc.30th IEEE Conference on Decision and Control,Brighton,UK.M.B ASSEVILLE,B.E SPIAU and J.G ASNIER(1981).Edge detection using sequential methods for change in level-Part I:A sequential edge detection algorithm.IEEE Trans.Acoustics,Speech,Signal Processing, vol.ASSP-29,no1,pp.24-31.M.B ASSEVILLE, A.B ENVENISTE and G.M OUSTAKIDES(1986).Detection and diagnosis of abrupt changes in modal characteristics of nonstationary digital signals.IEEE rmation Theory,vol.IT-32,no3,pp.412-417.M.B ASSEVILLE,A.B ENVENISTE,G.M OUSTAKIDES and A.R OUG´E E(1987a).Detection and diagnosis of changes in the eigenstructure of nonstationary multivariable systems.Automatica,vol.23,no3,pp.479-489. M.B ASSEVILLE,A.B ENVENISTE,G.M OUSTAKIDES and A.R OUG´E E(1987b).Optimal sensor location for detecting changes in dynamical behavior.IEEE Trans.Automatic Control,vol.AC-32,no12,pp.1067-1075.M.B ASSEVILLE,A.B ENVENISTE,B.G ACH-D EVAUCHELLE,M.G OURSAT,D.B ONNECASE,P.D OREY, M.P REVOSTO and M.O LAGNON(1993).Damage monitoring in vibration mechanics:issues in diagnos-tics and predictive maintenance.Mechanical Systems and Signal Processing,vol.7,no5,pp.401-423.R.V.B EARD(1971).Failure Accommodation in Linear Systems through Self-reorganization.Ph.D.Thesis, Dept.Aeronautics and Astronautics,MIT,Cambridge,MA.A.B ENVENISTE and J.J.F UCHS(1985).Single sample modal identification of a nonstationary stochastic process.IEEE Trans.Automatic Control,vol.AC-30,no1,pp.66-74.A.B ENVENISTE,M.B ASSEVILLE and G.M OUSTAKIDES(1987).The asymptotic local approach to change detection and model validation.IEEE Trans.Automatic Control,vol.AC-32,no7,pp.583-592.A.B ENVENISTE,M.M ETIVIER and P.P RIOURET(1990).Adaptive Algorithms and Stochastic Approxima-tions.Series on Applications of Mathematics,(A.V.Balakrishnan,I.Karatzas,M.Yor,eds.).Springer,New York.A.B ENVENISTE,M.B ASSEVILLE,L.E L G HAOUI,R.N IKOUKHAH and A.S.W ILLSKY(1992).An optimum robust approach to statistical failure detection and identification.IFAC World Conference,Sydney, July1993.B IBLIOGRAPHY427 R.H.B ERK(1973).Some asymptotic aspects of sequential analysis.Annals Statistics,vol.1,no6,pp.1126-1138.R.H.B ERK(1975).Locally most powerful sequential test.Annals Statistics,vol.3,no2,pp.373-381.P.B ILLINGSLEY(1968).Convergence of Probability Measures.Wiley,New York.A.F.B ISSELL(1969).Cusum techniques for quality control.Applied Statistics,vol.18,pp.1-30.M.E.B IVAIKOV(1991).Control of the sample size for recursive estimation of parameters subject to abrupt changes.Automation and Remote Control,no9,pp.96-103.R.E.B LAHUT(1987).Principles and Practice of Information Theory.Addison-Wesley,Reading,MA.I.F.B LAKE and W.C.L INDSEY(1973).Level-crossing problems for random processes.IEEE r-mation Theory,vol.IT-19,no3,pp.295-315.G.B ODENSTEIN and H.M.P RAETORIUS(1977).Feature extraction from the encephalogram by adaptive segmentation.Proc.IEEE,vol.65,pp.642-652.T.B OHLIN(1977).Analysis of EEG signals with changing spectra using a short word Kalman estimator. Mathematical Biosciences,vol.35,pp.221-259.W.B¨OHM and P.H ACKL(1990).Improved bounds for the average run length of control charts based on finite weighted sums.Annals Statistics,vol.18,no4,pp.1895-1899.T.B OJDECKI and J.H OSZA(1984).On a generalized disorder problem.Stochastic Processes and their Applications,vol.18,pp.349-359.L.I.B ORODKIN and V.V.M OTTL’(1976).Algorithm forfinding the jump times of random process equation parameters.Automation and Remote Control,vol.37,no6,Part1,pp.23-32.A.A.B OROVKOV(1984).Theory of Mathematical Statistics-Estimation and Hypotheses Testing,Naouka, Moscow(in Russian).Translated in French under the title Statistique Math´e matique-Estimation et Tests d’Hypoth`e ses,Mir,Paris,1987.G.E.P.B OX and G.M.J ENKINS(1970).Time Series Analysis,Forecasting and Control.Series in Time Series Analysis,Holden-Day,San Francisco.A.VON B RANDT(1983).Detecting and estimating parameters jumps using ladder algorithms and likelihood ratio test.Proc.ICASSP,Boston,MA,pp.1017-1020.A.VON B RANDT(1984).Modellierung von Signalen mit Sprunghaft Ver¨a nderlichem Leistungsspektrum durch Adaptive Segmentierung.Doctor-Engineer Dissertation,M¨u nchen,RFA(in German).S.B RAUN,ed.(1986).Mechanical Signature Analysis-Theory and Applications.Academic Press,London. L.B REIMAN(1968).Probability.Series in Statistics,Addison-Wesley,Reading,MA.G.S.B RITOV and L.A.M IRONOVSKI(1972).Diagnostics of linear systems of automatic regulation.Tekh. Kibernetics,vol.1,pp.76-83.B.E.B RODSKIY and B.S.D ARKHOVSKIY(1992).Nonparametric Methods in Change-point Problems. Kluwer Academic,Boston.L.D.B ROEMELING(1982).Jal Econometrics,vol.19,Special issue on structural change in Econometrics. L.D.B ROEMELING and H.T SURUMI(1987).Econometrics and Structural Change.Dekker,New York. D.B ROOK and D.A.E VANS(1972).An approach to the probability distribution of Cusum run length. Biometrika,vol.59,pp.539-550.J.B RUNET,D.J AUME,M.L ABARR`E RE,A.R AULT and M.V ERG´E(1990).D´e tection et Diagnostic de Pannes.Trait´e des Nouvelles Technologies,S´e rie Diagnostic et Maintenance,Herm`e s,Paris(in French).428B IBLIOGRAPHY S.P.B RUZZONE and M.K AVEH(1984).Information tradeoffs in using the sample autocorrelation function in ARMA parameter estimation.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-32,no4, pp.701-715.A.K.C AGLAYAN(1980).Necessary and sufficient conditions for detectability of jumps in linear systems. IEEE Trans.Automatic Control,vol.AC-25,no4,pp.833-834.A.K.C AGLAYAN and R.E.L ANCRAFT(1983).Reinitialization issues in fault tolerant systems.Proc.Amer-ican Control Conf.,pp.952-955.A.K.C AGLAYAN,S.M.A LLEN and K.W EHMULLER(1988).Evaluation of a second generation reconfigu-ration strategy for aircraftflight control systems subjected to actuator failure/surface damage.Proc.National Aerospace and Electronic Conference,Dayton,OH.P.E.C AINES(1988).Linear Stochastic Systems.Series in Probability and Mathematical Statistics,Wiley, New York.M.J.C HEN and J.P.N ORTON(1987).Estimation techniques for tracking rapid parameter changes.Intern. Jal Control,vol.45,no4,pp.1387-1398.W.K.C HIU(1974).The economic design of cusum charts for controlling normal mean.Applied Statistics, vol.23,no3,pp.420-433.E.Y.C HOW(1980).A Failure Detection System Design Methodology.Ph.D.Thesis,M.I.T.,L.I.D.S.,Cam-bridge,MA.E.Y.C HOW and A.S.W ILLSKY(1984).Analytical redundancy and the design of robust failure detection systems.IEEE Trans.Automatic Control,vol.AC-29,no3,pp.689-691.Y.S.C HOW,H.R OBBINS and D.S IEGMUND(1971).Great Expectations:The Theory of Optimal Stop-ping.Houghton-Mifflin,Boston.R.N.C LARK,D.C.F OSTH and V.M.W ALTON(1975).Detection of instrument malfunctions in control systems.IEEE Trans.Aerospace Electronic Systems,vol.AES-11,pp.465-473.A.C OHEN(1987).Biomedical Signal Processing-vol.1:Time and Frequency Domain Analysis;vol.2: Compression and Automatic Recognition.CRC Press,Boca Raton,FL.J.C ORGE and F.P UECH(1986).Analyse du rythme cardiaque foetal par des m´e thodes de d´e tection de ruptures.Proc.7th INRIA Int.Conf.Analysis and optimization of Systems.Antibes,FR(in French).D.R.C OX and D.V.H INKLEY(1986).Theoretical Statistics.Chapman and Hall,New York.D.R.C OX and H.D.M ILLER(1965).The Theory of Stochastic Processes.Wiley,New York.S.V.C ROWDER(1987).A simple method for studying run-length distributions of exponentially weighted moving average charts.Technometrics,vol.29,no4,pp.401-407.H.C S¨ORG¨O and L.H ORV´ATH(1988).Nonparametric methods for change point problems.In Handbook of Statistics(P.R.Krishnaiah,C.R.Rao,eds.),vol.7,Elsevier,New York,pp.403-425.R.B.D AVIES(1973).Asymptotic inference in stationary gaussian time series.Advances Applied Probability, vol.5,no3,pp.469-497.J.C.D ECKERT,M.N.D ESAI,J.J.D EYST and A.S.W ILLSKY(1977).F-8DFBW sensor failure identification using analytical redundancy.IEEE Trans.Automatic Control,vol.AC-22,no5,pp.795-803.M.H.D E G ROOT(1970).Optimal Statistical Decisions.Series in Probability and Statistics,McGraw-Hill, New York.J.D ESHAYES and D.P ICARD(1979).Tests de ruptures dans un mod`e pte-Rendus de l’Acad´e mie des Sciences,vol.288,Ser.A,pp.563-566(in French).B IBLIOGRAPHY429 J.D ESHAYES and D.P ICARD(1983).Ruptures de Mod`e les en Statistique.Th`e ses d’Etat,Universit´e deParis-Sud,Orsay,France(in French).J.D ESHAYES and D.P ICARD(1986).Off-line statistical analysis of change-point models using non para-metric and likelihood methods.In Detection of Abrupt Changes in Signals and Dynamical Systems(M. Basseville,A.Benveniste,eds.).Lecture Notes in Control and Information Sciences,LNCIS77,Springer, New York,pp.103-168.B.D EVAUCHELLE-G ACH(1991).Diagnostic M´e canique des Fatigues sur les Structures Soumises`a des Vibrations en Ambiance de Travail.Th`e se de l’Universit´e Paris IX Dauphine(in French).B.D EVAUCHELLE-G ACH,M.B ASSEVILLE and A.B ENVENISTE(1991).Diagnosing mechanical changes in vibrating systems.Proc.SAFEPROCESS’91,Baden-Baden,FRG,pp.85-89.R.D I F RANCESCO(1990).Real-time speech segmentation using pitch and convexity jump models:applica-tion to variable rate speech coding.IEEE Trans.Acoustics,Speech,Signal Processing,vol.ASSP-38,no5, pp.741-748.X.D ING and P.M.F RANK(1990).Fault detection via factorization approach.Systems and Control Letters, vol.14,pp.431-436.J.L.D OOB(1953).Stochastic Processes.Wiley,New York.V.D RAGALIN(1988).Asymptotic solutions in detecting a change in distribution under an unknown param-eter.Statistical Problems of Control,Issue83,Vilnius,pp.45-52.B.D UBUISSON(1990).Diagnostic et Reconnaissance des Formes.Trait´e des Nouvelles Technologies,S´e rie Diagnostic et Maintenance,Herm`e s,Paris(in French).A.J.D UNCAN(1986).Quality Control and Industrial Statistics,5th edition.Richard D.Irwin,Inc.,Home-wood,IL.J.D URBIN(1971).Boundary-crossing probabilities for the Brownian motion and Poisson processes and techniques for computing the power of the Kolmogorov-Smirnov test.Jal Applied Probability,vol.8,pp.431-453.J.D URBIN(1985).Thefirst passage density of the crossing of a continuous Gaussian process to a general boundary.Jal Applied Probability,vol.22,no1,pp.99-122.A.E MAMI-N AEINI,M.M.A KHTER and S.M.R OCK(1988).Effect of model uncertainty on failure detec-tion:the threshold selector.IEEE Trans.Automatic Control,vol.AC-33,no12,pp.1106-1115.J.D.E SARY,F.P ROSCHAN and D.W.W ALKUP(1967).Association of random variables with applications. Annals Mathematical Statistics,vol.38,pp.1466-1474.W.D.E WAN and K.W.K EMP(1960).Sampling inspection of continuous processes with no autocorrelation between successive results.Biometrika,vol.47,pp.263-280.G.F AVIER and A.S MOLDERS(1984).Adaptive smoother-predictors for tracking maneuvering targets.Proc. 23rd Conf.Decision and Control,Las Vegas,NV,pp.831-836.W.F ELLER(1966).An Introduction to Probability Theory and Its Applications,vol.2.Series in Probability and Mathematical Statistics,Wiley,New York.R.A.F ISHER(1925).Theory of statistical estimation.Proc.Cambridge Philosophical Society,vol.22, pp.700-725.M.F ISHMAN(1988).Optimization of the algorithm for the detection of a disorder,based on the statistic of exponential smoothing.In Statistical Problems of Control,Issue83,Vilnius,pp.146-151.R.F LETCHER(1980).Practical Methods of Optimization,2volumes.Wiley,New York.P.M.F RANK(1990).Fault diagnosis in dynamic systems using analytical and knowledge based redundancy -A survey and new results.Automatica,vol.26,pp.459-474.430B IBLIOGRAPHY P.M.F RANK(1991).Enhancement of robustness in observer-based fault detection.Proc.SAFEPRO-CESS’91,Baden-Baden,FRG,pp.275-287.P.M.F RANK and J.W¨UNNENBERG(1989).Robust fault diagnosis using unknown input observer schemes. In Fault Diagnosis in Dynamic Systems-Theory and Application(R.Patton,P.Frank,R.Clark,eds.). International Series in Systems and Control Engineering,Prentice Hall International,London,UK,pp.47-98.K.F UKUNAGA(1990).Introduction to Statistical Pattern Recognition,2d ed.Academic Press,New York. S.I.G ASS(1958).Linear Programming:Methods and Applications.McGraw Hill,New York.W.G E and C.Z.F ANG(1989).Extended robust observation approach for failure isolation.Int.Jal Control, vol.49,no5,pp.1537-1553.W.G ERSCH(1986).Two applications of parametric time series modeling methods.In Mechanical Signature Analysis-Theory and Applications(S.Braun,ed.),chap.10.Academic Press,London.J.J.G ERTLER(1988).Survey of model-based failure detection and isolation in complex plants.IEEE Control Systems Magazine,vol.8,no6,pp.3-11.J.J.G ERTLER(1991).Analytical redundancy methods in fault detection and isolation.Proc.SAFEPRO-CESS’91,Baden-Baden,FRG,pp.9-22.B.K.G HOSH(1970).Sequential Tests of Statistical Hypotheses.Addison-Wesley,Cambridge,MA.I.N.G IBRA(1975).Recent developments in control charts techniques.Jal Quality Technology,vol.7, pp.183-192.J.P.G ILMORE and R.A.M C K ERN(1972).A redundant strapdown inertial reference unit(SIRU).Jal Space-craft,vol.9,pp.39-47.M.A.G IRSHICK and H.R UBIN(1952).A Bayes approach to a quality control model.Annals Mathematical Statistics,vol.23,pp.114-125.A.L.G OEL and S.M.W U(1971).Determination of the ARL and a contour nomogram for CUSUM charts to control normal mean.Technometrics,vol.13,no2,pp.221-230.P.L.G OLDSMITH and H.W HITFIELD(1961).Average run lengths in cumulative chart quality control schemes.Technometrics,vol.3,pp.11-20.G.C.G OODWIN and K.S.S IN(1984).Adaptive Filtering,Prediction and rmation and System Sciences Series,Prentice Hall,Englewood Cliffs,NJ.R.M.G RAY and L.D.D AVISSON(1986).Random Processes:a Mathematical Approach for Engineers. Information and System Sciences Series,Prentice Hall,Englewood Cliffs,NJ.C.G UEGUEN and L.L.S CHARF(1980).Exact maximum likelihood identification for ARMA models:a signal processing perspective.Proc.1st EUSIPCO,Lausanne.D.E.G USTAFSON, A.S.W ILLSKY,J.Y.W ANG,M.C.L ANCASTER and J.H.T RIEBWASSER(1978). ECG/VCG rhythm diagnosis using statistical signal analysis.Part I:Identification of persistent rhythms. Part II:Identification of transient rhythms.IEEE Trans.Biomedical Engineering,vol.BME-25,pp.344-353 and353-361.F.G USTAFSSON(1991).Optimal segmentation of linear regression parameters.Proc.IFAC/IFORS Symp. Identification and System Parameter Estimation,Budapest,pp.225-229.T.H¨AGGLUND(1983).New Estimation Techniques for Adaptive Control.Ph.D.Thesis,Lund Institute of Technology,Lund,Sweden.T.H¨AGGLUND(1984).Adaptive control of systems subject to large parameter changes.Proc.IFAC9th World Congress,Budapest.B IBLIOGRAPHY431 P.H ALL and C.C.H EYDE(1980).Martingale Limit Theory and its Application.Probability and Mathemat-ical Statistics,a Series of Monographs and Textbooks,Academic Press,New York.W.J.H ALL,R.A.W IJSMAN and J.K.G HOSH(1965).The relationship between sufficiency and invariance with applications in sequential analysis.Ann.Math.Statist.,vol.36,pp.576-614.E.J.H ANNAN and M.D EISTLER(1988).The Statistical Theory of Linear Systems.Series in Probability and Mathematical Statistics,Wiley,New York.J.D.H EALY(1987).A note on multivariate CuSum procedures.Technometrics,vol.29,pp.402-412.D.M.H IMMELBLAU(1970).Process Analysis by Statistical Methods.Wiley,New York.D.M.H IMMELBLAU(1978).Fault Detection and Diagnosis in Chemical and Petrochemical Processes. Chemical Engineering Monographs,vol.8,Elsevier,Amsterdam.W.G.S.H INES(1976a).A simple monitor of a system with sudden parameter changes.IEEE r-mation Theory,vol.IT-22,no2,pp.210-216.W.G.S.H INES(1976b).Improving a simple monitor of a system with sudden parameter changes.IEEE rmation Theory,vol.IT-22,no4,pp.496-499.D.V.H INKLEY(1969).Inference about the intersection in two-phase regression.Biometrika,vol.56,no3, pp.495-504.D.V.H INKLEY(1970).Inference about the change point in a sequence of random variables.Biometrika, vol.57,no1,pp.1-17.D.V.H INKLEY(1971).Inference about the change point from cumulative sum-tests.Biometrika,vol.58, no3,pp.509-523.D.V.H INKLEY(1971).Inference in two-phase regression.Jal American Statistical Association,vol.66, no336,pp.736-743.J.R.H UDDLE(1983).Inertial navigation system error-model considerations in Kalmanfiltering applica-tions.In Control and Dynamic Systems(C.T.Leondes,ed.),Academic Press,New York,pp.293-339.J.S.H UNTER(1986).The exponentially weighted moving average.Jal Quality Technology,vol.18,pp.203-210.I.A.I BRAGIMOV and R.Z.K HASMINSKII(1981).Statistical Estimation-Asymptotic Theory.Applications of Mathematics Series,vol.16.Springer,New York.R.I SERMANN(1984).Process fault detection based on modeling and estimation methods-A survey.Auto-matica,vol.20,pp.387-404.N.I SHII,A.I WATA and N.S UZUMURA(1979).Segmentation of nonstationary time series.Int.Jal Systems Sciences,vol.10,pp.883-894.J.E.J ACKSON and R.A.B RADLEY(1961).Sequential and tests.Annals Mathematical Statistics, vol.32,pp.1063-1077.B.J AMES,K.L.J AMES and D.S IEGMUND(1988).Conditional boundary crossing probabilities with appli-cations to change-point problems.Annals Probability,vol.16,pp.825-839.M.K.J EERAGE(1990).Reliability analysis of fault-tolerant IMU architectures with redundant inertial sen-sors.IEEE Trans.Aerospace and Electronic Systems,vol.AES-5,no.7,pp.23-27.N.L.J OHNSON(1961).A simple theoretical approach to cumulative sum control charts.Jal American Sta-tistical Association,vol.56,pp.835-840.N.L.J OHNSON and F.C.L EONE(1962).Cumulative sum control charts:mathematical principles applied to their construction and use.Parts I,II,III.Industrial Quality Control,vol.18,pp.15-21;vol.19,pp.29-36; vol.20,pp.22-28.432B IBLIOGRAPHY R.A.J OHNSON and M.B AGSHAW(1974).The effect of serial correlation on the performance of CUSUM tests-Part I.Technometrics,vol.16,no.1,pp.103-112.H.L.J ONES(1973).Failure Detection in Linear Systems.Ph.D.Thesis,Dept.Aeronautics and Astronautics, MIT,Cambridge,MA.R.H.J ONES,D.H.C ROWELL and L.E.K APUNIAI(1970).Change detection model for serially correlated multivariate data.Biometrics,vol.26,no2,pp.269-280.M.J URGUTIS(1984).Comparison of the statistical properties of the estimates of the change times in an autoregressive process.In Statistical Problems of Control,Issue65,Vilnius,pp.234-243(in Russian).T.K AILATH(1980).Linear rmation and System Sciences Series,Prentice Hall,Englewood Cliffs,NJ.L.V.K ANTOROVICH and V.I.K RILOV(1958).Approximate Methods of Higher Analysis.Interscience,New York.S.K ARLIN and H.M.T AYLOR(1975).A First Course in Stochastic Processes,2d ed.Academic Press,New York.S.K ARLIN and H.M.T AYLOR(1981).A Second Course in Stochastic Processes.Academic Press,New York.D.K AZAKOS and P.P APANTONI-K AZAKOS(1980).Spectral distance measures between gaussian pro-cesses.IEEE Trans.Automatic Control,vol.AC-25,no5,pp.950-959.K.W.K EMP(1958).Formula for calculating the operating characteristic and average sample number of some sequential tests.Jal Royal Statistical Society,vol.B-20,no2,pp.379-386.K.W.K EMP(1961).The average run length of the cumulative sum chart when a V-mask is used.Jal Royal Statistical Society,vol.B-23,pp.149-153.K.W.K EMP(1967a).Formal expressions which can be used for the determination of operating character-istics and average sample number of a simple sequential test.Jal Royal Statistical Society,vol.B-29,no2, pp.248-262.K.W.K EMP(1967b).A simple procedure for determining upper and lower limits for the average sample run length of a cumulative sum scheme.Jal Royal Statistical Society,vol.B-29,no2,pp.263-265.D.P.K ENNEDY(1976).Some martingales related to cumulative sum tests and single server queues.Stochas-tic Processes and Appl.,vol.4,pp.261-269.T.H.K ERR(1980).Statistical analysis of two-ellipsoid overlap test for real time failure detection.IEEE Trans.Automatic Control,vol.AC-25,no4,pp.762-772.T.H.K ERR(1982).False alarm and correct detection probabilities over a time interval for restricted classes of failure detection algorithms.IEEE rmation Theory,vol.IT-24,pp.619-631.T.H.K ERR(1987).Decentralizedfiltering and redundancy management for multisensor navigation.IEEE Trans.Aerospace and Electronic systems,vol.AES-23,pp.83-119.Minor corrections on p.412and p.599 (May and July issues,respectively).R.A.K HAN(1978).Wald’s approximations to the average run length in cusum procedures.Jal Statistical Planning and Inference,vol.2,no1,pp.63-77.R.A.K HAN(1979).Somefirst passage problems related to cusum procedures.Stochastic Processes and Applications,vol.9,no2,pp.207-215.R.A.K HAN(1981).A note on Page’s two-sided cumulative sum procedures.Biometrika,vol.68,no3, pp.717-719.B IBLIOGRAPHY433 V.K IREICHIKOV,V.M ANGUSHEV and I.N IKIFOROV(1990).Investigation and application of CUSUM algorithms to monitoring of sensors.In Statistical Problems of Control,Issue89,Vilnius,pp.124-130(in Russian).G.K ITAGAWA and W.G ERSCH(1985).A smoothness prior time-varying AR coefficient modeling of non-stationary covariance time series.IEEE Trans.Automatic Control,vol.AC-30,no1,pp.48-56.N.K LIGIENE(1980).Probabilities of deviations of the change point estimate in statistical models.In Sta-tistical Problems of Control,Issue83,Vilnius,pp.80-86(in Russian).N.K LIGIENE and L.T ELKSNYS(1983).Methods of detecting instants of change of random process prop-erties.Automation and Remote Control,vol.44,no10,Part II,pp.1241-1283.J.K ORN,S.W.G ULLY and A.S.W ILLSKY(1982).Application of the generalized likelihood ratio algorithm to maneuver detection and estimation.Proc.American Control Conf.,Arlington,V A,pp.792-798.P.R.K RISHNAIAH and B.Q.M IAO(1988).Review about estimation of change points.In Handbook of Statistics(P.R.Krishnaiah,C.R.Rao,eds.),vol.7,Elsevier,New York,pp.375-402.P.K UDVA,N.V ISWANADHAM and A.R AMAKRISHNAN(1980).Observers for linear systems with unknown inputs.IEEE Trans.Automatic Control,vol.AC-25,no1,pp.113-115.S.K ULLBACK(1959).Information Theory and Statistics.Wiley,New York(also Dover,New York,1968). K.K UMAMARU,S.S AGARA and T.S¨ODERSTR¨OM(1989).Some statistical methods for fault diagnosis for dynamical systems.In Fault Diagnosis in Dynamic Systems-Theory and Application(R.Patton,P.Frank,R. Clark,eds.).International Series in Systems and Control Engineering,Prentice Hall International,London, UK,pp.439-476.A.K USHNIR,I.N IKIFOROV and I.S AVIN(1983).Statistical adaptive algorithms for automatic detection of seismic signals-Part I:One-dimensional case.In Earthquake Prediction and the Study of the Earth Structure,Naouka,Moscow(Computational Seismology,vol.15),pp.154-159(in Russian).L.L ADELLI(1990).Diffusion approximation for a pseudo-likelihood test process with application to de-tection of change in stochastic system.Stochastics and Stochastics Reports,vol.32,pp.1-25.T.L.L A¨I(1974).Control charts based on weighted sums.Annals Statistics,vol.2,no1,pp.134-147.T.L.L A¨I(1981).Asymptotic optimality of invariant sequential probability ratio tests.Annals Statistics, vol.9,no2,pp.318-333.D.G.L AINIOTIS(1971).Joint detection,estimation,and system identifirmation and Control, vol.19,pp.75-92.M.R.L EADBETTER,G.L INDGREN and H.R OOTZEN(1983).Extremes and Related Properties of Random Sequences and Processes.Series in Statistics,Springer,New York.L.L E C AM(1960).Locally asymptotically normal families of distributions.Univ.California Publications in Statistics,vol.3,pp.37-98.L.L E C AM(1986).Asymptotic Methods in Statistical Decision Theory.Series in Statistics,Springer,New York.E.L.L EHMANN(1986).Testing Statistical Hypotheses,2d ed.Wiley,New York.J.P.L EHOCZKY(1977).Formulas for stopped diffusion processes with stopping times based on the maxi-mum.Annals Probability,vol.5,no4,pp.601-607.H.R.L ERCHE(1980).Boundary Crossing of Brownian Motion.Lecture Notes in Statistics,vol.40,Springer, New York.L.L JUNG(1987).System Identification-Theory for the rmation and System Sciences Series, Prentice Hall,Englewood Cliffs,NJ.。

专利名称：GAMING SYSTEM FOR TRACKING PLAYER ACTIVITY DURING VIRTUAL SESSIONS AT AGAMING MACHINE发明人：KAMMLER, Keith, Donald,MCNAMEE, J.,Christopher,SHELDON, Alan,Gael,O'DONNELL, Robert, L.申请号：US2004029353申请日：20040907公开号：WO05/026906P1公开日：20050324专利内容由知识产权出版社提供摘要：A gaming system (11) has a central authority (21) connected to a plurality of gaming machines (13,15,17). Player activity is tracked at the gaming machines (13,15,17) during regular gaming sessions and during virtual gaming sessions. Such data is transmitted to the central authority (21) for providing player points in a player account file of a central database (25). Regular gaming sessions occur between player card insertion as well as after player card insertion. For example, a coin-in event prior to player card insertion will establish a virtual session, and credits remaining on the credit meter at a card-out event will establish a virtual gaming session.申请人：KAMMLER, Keith, Donald,MCNAMEE, J., Christopher,SHELDON, Alan,Gael,O'DONNELL, Robert, L.地址：71 Longueville Road Lane Cove, NSW AU,9179 Sangria Lane Las Vegas, NV 89147 US,7897 Nookfield Drive Las Vegas, NV 89147 US,265 Powerbilt Avenue Las Vegas, NV 89148 US,5055 W. Hacienda Ave. #1220 Las Vegas, NV 89118 US国籍：AU,US,US,US,US代理机构：CARROLL , Christopher, R.更多信息请下载全文后查看。

Netware服务器在Windows95对等网中的应用
庄明
【期刊名称】《微型机与应用》
【年(卷),期】2000(019)009
【摘要】在Windows 95对等网中连入Netware服务器,使得网络在系统管理和软件使用等方面变得非常方便、快捷、安全.
【总页数】2页(P58-59)
【作者】庄明
【作者单位】浙江师大数理与信息学院50#信箱,321000
【正文语种】中文
【中图分类】TP3
【相关文献】
ware服务器在Windows95对等网中的几点应用 [J], 庄明
2.互联NetWare下分布式数据库／应用服务器的应用开发 [J], 宋传杰;姚念馥
3.利用Windows95建立对等网下的Web服务器 [J], 周永胜
4.CD-ROM虚拟驱动器及其在Windows95对等网中的应用 [J], 刘俊英;李光仲
5.利用Windows95建立对等网下的Web服务器 [J], 周永胜
因版权原因，仅展示原文概要，查看原文内容请购买。

Multilevel Hypergraph Partitioning:Applications in VLSI DomainGeorge Karypis,Rajat Aggarwal,Vipin Kumar,Senior Member,IEEE,and Shashi Shekhar,Senior Member,IEEE Abstract—In this paper,we present a new hypergraph-partitioning algorithm that is based on the multilevel paradigm.In the multilevel paradigm,a sequence of successivelycoarser hypergraphs is constructed.A bisection of the smallesthypergraph is computed and it is used to obtain a bisection of theoriginal hypergraph by successively projecting and refining thebisection to the next levelfiner hypergraph.We have developednew hypergraph coarsening strategies within the multilevelframework.We evaluate their performance both in terms of thesize of the hyperedge cut on the bisection,as well as on the runtime for a number of very large scale integration circuits.Ourexperiments show that our multilevel hypergraph-partitioningalgorithm produces high-quality partitioning in a relatively smallamount of time.The quality of the partitionings produced by ourscheme are on the average6%–23%better than those producedby other state-of-the-art schemes.Furthermore,our partitioningalgorithm is significantly faster,often requiring4–10times lesstime than that required by the other schemes.Our multilevelhypergraph-partitioning algorithm scales very well for largehypergraphs.Hypergraphs with over100000vertices can bebisected in a few minutes on today’s workstations.Also,on thelarge hypergraphs,our scheme outperforms other schemes(inhyperedge cut)quite consistently with larger margins(9%–30%).Index Terms—Circuit partitioning,hypergraph partitioning,multilevel algorithms.I.I NTRODUCTIONH YPERGRAPH partitioning is an important problem withextensive application to many areas,including very largescale integration(VLSI)design[1],efficient storage of largedatabases on disks[2],and data mining[3].The problemis to partition the vertices of a hypergraphintois definedas a set ofvertices[4],and the size ofa hyperedge is the cardinality of this subset.Manuscript received April29,1997;revised March23,1998.This workwas supported under IBM Partnership Award NSF CCR-9423082,by theArmy Research Office under Contract DA/DAAH04-95-1-0538,and by theArmy High Performance Computing Research Center,the Department of theArmy,Army Research Laboratory Cooperative Agreement DAAH04-95-2-0003/Contract DAAH04-95-C-0008.G.Karypis,V.Kumar,and S.Shekhar are with the Department of ComputerScience and Engineering,Minneapolis,University of Minnesota,Minneapolis,MN55455-0159USA.R.Aggarwal is with the Lattice Semiconductor Corporation,Milpitas,CA95131USA.Publisher Item Identifier S1063-8210(99)00695-2.During the course of VLSI circuit design and synthesis,itis important to be able to divide the system specification intoclusters so that the inter-cluster connections are minimized.This step has many applications including design packaging,HDL-based synthesis,design optimization,rapid prototyping,simulation,and testing.In particular,many rapid prototyp-ing systems use partitioning to map a complex circuit ontohundreds of interconnectedfield-programmable gate arrays(FPGA’s).Such partitioning instances are challenging becausethe timing,area,and input/output(I/O)resource utilizationmust satisfy hard device-specific constraints.For example,ifthe number of signal nets leaving any one of the clustersis greater than the number of signal p-i-n’s available in theFPGA,then this cluster cannot be implemented using a singleFPGA.In this case,the circuit needs to be further partitioned,and thus implemented using multiple FPGA’s.Hypergraphscan be used to naturally represent a VLSI circuit.The verticesof the hypergraph can be used to represent the cells of thecircuit,and the hyperedges can be used to represent the netsconnecting these cells.A high quality hypergraph-partitioningalgorithm greatly affects the feasibility,quality,and cost ofthe resulting system.A.Related WorkThe problem of computing an optimal bisection of a hy-pergraph is at least NP-hard[5].However,because of theimportance of the problem in many application areas,manyheuristic algorithms have been developed.The survey byAlpert and Khang[1]provides a detailed description andcomparison of such various schemes.In a widely used class ofiterative refinement partitioning algorithms,an initial bisectionis computed(often obtained randomly)and then the partitionis refined by repeatedly moving vertices between the twoparts to reduce the hyperedge cut.These algorithms oftenuse the Schweikert–Kernighan heuristic[6](an extension ofthe Kernighan–Lin(KL)heuristic[7]for hypergraphs),or thefaster Fiduccia–Mattheyses(FM)[8]refinement heuristic,toiteratively improve the quality of the partition.In all of thesemethods(sometimes also called KLFM schemes),a vertex ismoved(or a vertex pair is swapped)if it produces the greatestreduction in the edge cuts,which is also called the gain formoving the vertex.The partition produced by these methodsis often poor,especially for larger hypergraphs.Hence,thesealgorithms have been extended in a number of ways[9]–[12].Krishnamurthy[9]tried to introduce intelligence in the tie-breaking process from among the many possible moves withthe same high gain.He used a Look Ahead()algorithm,which looks ahead uptoa move.PROP [11],introduced by Dutt and Deng,used a probabilistic gain computation model for deciding which vertices need to move across the partition line.These schemes tend to enhance the performance of the basic KLFM family of refinement algorithms,at the expense of increased run time.Dutt and Deng [12]proposed two new methods,namely,CLIP and CDIP,for computing the gains of hyperedges that contain more than one node on either side of the partition boundary.CDIP in conjunctionwithand CLIP in conjunction with PROP are two schemes that have shown the best results in their experiments.Another class of hypergraph-partitioning algorithms [13]–[16]performs partitioning in two phases.In the first phase,the hypergraph is coarsened to form a small hypergraph,and then the FM algorithm is used to bisect the small hypergraph.In the second phase,these algorithms use the bisection of this contracted hypergraph to obtain a bisection of the original hypergraph.Since FM refinement is done only on the small coarse hypergraph,this step is usually fast,but the overall performance of such a scheme depends upon the quality of the coarsening method.In many schemes,the projected partition is further improved using the FM refinement scheme [15].Recently,a new class of partitioning algorithms was devel-oped [17]–[20]based upon the multilevel paradigm.In these algorithms,a sequence of successively smaller (coarser)graphs is constructed.A bisection of the smallest graph is computed.This bisection is now successively projected to the next-level finer graph and,at each level,an iterative refinement algorithm such as KLFM is used to further improve the bisection.The various phases of multilevel bisection are illustrated in Fig.1.Iterative refinement schemes such as KLFM become quite powerful in this multilevel context for the following reason.First,the movement of a single node across a partition bound-ary in a coarse graph can lead to the movement of a large num-ber of related nodes in the original graph.Second,the refined partitioning projected to the next level serves as an excellent initial partitioning for the KL or FM refinement algorithms.This paradigm was independently studied by Bui and Jones [17]in the context of computing fill-reducing matrix reorder-ing,by Hendrickson and Leland [18]in the context of finite-element mesh-partitioning,and by Hauck and Borriello (called Optimized KLFM)[20],and by Cong and Smith [19]for hy-pergraph partitioning.Karypis and Kumar extensively studied this paradigm in [21]and [22]for the partitioning of graphs.They presented new graph coarsening schemes for which even a good bisection of the coarsest graph is a pretty good bisec-tion of the original graph.This makes the overall multilevel paradigm even more robust.Furthermore,it allows the use of simplified variants of KLFM refinement schemes during the uncoarsening phase,which significantly speeds up the refine-ment process without compromising overall quality.METIS [21],a multilevel graph partitioning algorithm based upon this work,routinely finds substantially better bisections and is often two orders of magnitude faster than the hitherto state-of-the-art spectral-based bisection techniques [23],[24]for graphs.The improved coarsening schemes of METIS work only for graphs and are not directly applicable to hypergraphs.IftheFig.1.The various phases of the multilevel graph bisection.During the coarsening phase,the size of the graph is successively decreased;during the initial partitioning phase,a bisection of the smaller graph is computed,and during the uncoarsening and refinement phase,the bisection is successively refined as it is projected to the larger graphs.During the uncoarsening and refinement phase,the dashed lines indicate projected partitionings and dark solid lines indicate partitionings that were produced after refinement.G 0is the given graph,which is the finest graph.G i +1is the next level coarser graph of G i ,and vice versa,G i is the next level finer graph of G i +1.G 4is the coarsest graph.hypergraph is first converted into a graph (by replacing each hyperedge by a set of regular edges),then METIS [21]can be used to compute a partitioning of this graph.This technique was investigated by Alpert and Khang [25]in their algorithm called GMetis.They converted hypergraphs to graphs by simply replacing each hyperedge with a clique,and then they dropped many edges from each clique randomly.They used METIS to compute a partitioning of each such random graph and then selected the best of these partitionings.Their results show that reasonably good partitionings can be obtained in a reasonable amount of time for a variety of benchmark problems.In particular,the performance of their resulting scheme is comparable to other state-of-the art schemes such as PARABOLI [26],PROP [11],and the multilevel hypergraph partitioner from Hauck and Borriello [20].The conversion of a hypergraph into a graph by replacing each hyperedge with a clique does not result in an equivalent representation since high-quality partitionings of the resulting graph do not necessarily lead to high-quality partitionings of the hypergraph.The standard hyperedge-to-edge conversion [27]assigns a uniform weightofisthe of the hyperedge,i.e.,thenumber of vertices in the hyperedge.However,the fundamen-tal problem associated with replacing a hyperedge by its clique is that there exists no scheme to assign weight to the edges of the clique that can correctly capture the cost of cutting this hyperedge [28].This hinders the partitioning refinement algo-rithm since vertices are moved between partitions depending on how much this reduces the number of edges they cut in the converted graph,whereas the real objective is to minimize the number of hyperedges cut in the original hypergraph.Furthermore,the hyperedge-to-clique conversion destroys the natural sparsity of the hypergraph,significantly increasing theKARYPIS et al.:MULTILEVEL HYPERGRAPH PARTITIONING:APPLICATIONS IN VLSI DOMAIN 71run time of the partitioning algorithm.Alpert and Khang [25]solved this problem by dropping many edges of the clique randomly,but this makes the graph representation even less accurate.A better approach is to develop coarsening and refinement schemes that operate directly on the hypergraph.Note that the multilevel scheme by Hauck and Borriello [20]operates directly on hypergraphs and,thus,is able to perform accurate refinement during the uncoarsening phase.However,all coarsening schemes studied in [20]are edge-oriented;i.e.,they only merge pairs of nodes to construct coarser graphs.Hence,despite a powerful refinement scheme (FM with theuse oflook-ahead)during the uncoarsening phase,their performance is only as good as that of GMetis [25].B.Our ContributionsIn this paper,we present a multilevel hypergraph-partitioning algorithm hMETIS that operates directly on the hypergraphs.A key contribution of our work is the development of new hypergraph coarsening schemes that allow the multilevel paradigm to provide high-quality partitions quite consistently.The use of these powerful coarsening schemes also allows the refinement process to be simplified considerably (even beyond plain FM refinement),making the multilevel scheme quite fast.We investigate various algorithms for the coarsening and uncoarsening phases which operate on the hypergraphs without converting them into graphs.We have also developed new multiphase refinement schemes(-cycles)based on the multilevel paradigm.These schemes take an initial partition as input and try to improve them using the multilevel scheme.These multiphase schemes further reduce the run times,as well as improve the solution quality.We evaluate their performance both in terms of the size of the hyperedge cut on the bisection,as well as on run time on a number of VLSI circuits.Our experiments show that our multilevel hypergraph-partitioning algorithm produces high-quality partitioning in a relatively small amount of time.The quality of the partitionings produced by our scheme are on the average 6%–23%better than those produced by other state-of-the-art schemes [11],[12],[25],[26],[29].The difference in quality over other schemes becomes even greater for larger hypergraphs.Furthermore,our partitioning algorithm is significantly faster,often requiring 4–10times less time than that required by the other schemes.For many circuits in the well-known ACM/SIGDA benchmark set [30],our scheme is able to find better partitionings than those reported in the literature for any other hypergraph-partitioning algorithm.The remainder of this paper is organized as follows.Section II describes the different algorithms used in the three phases of our multilevel hypergraph-partitioning algorithm.Section III describes a new partitioning refinement algorithm based on the multilevel paradigm.Section IV compares the results produced by our algorithm to those produced by earlier hypergraph-partitioning algorithms.II.M ULTILEVEL H YPERGRAPH B ISECTIONWe now present the framework of hMETIS ,in which the coarsening and refinement scheme work directly with hyper-edges without using the clique representation to transform them into edges.We have developed new algorithms for both the phases,which,in conjunction,are capable of delivering very good quality solutions.A.Coarsening PhaseDuring the coarsening phase,a sequence of successively smaller hypergraphs are constructed.As in the case of mul-tilevel graph bisection,the purpose of coarsening is to create a small hypergraph,such that a good bisection of the small hypergraph is not significantly worse than the bisection di-rectly obtained for the original hypergraph.In addition to that,hypergraph coarsening also helps in successively reducing the sizes of the hyperedges.That is,after several levels of coarsening,large hyperedges are contracted to hyperedges that connect just a few vertices.This is particularly helpful,since refinement heuristics based on the KLFM family of algorithms [6]–[8]are very effective in refining small hyperedges,but are quite ineffective in refining hyperedges with a large number of vertices belonging to different partitions.Groups of vertices that are merged together to form single vertices in the next-level coarse hypergraph can be selected in different ways.One possibility is to select pairs of vertices with common hyperedges and to merge them together,as illustrated in Fig.2(a).A second possibility is to merge together all the vertices that belong to a hyperedge,as illustrated in Fig.2(b).Finally,a third possibility is to merge together a subset of the vertices belonging to a hyperedge,as illustrated in Fig.2(c).These three different schemes for grouping vertices together for contraction are described below.1)Edge Coarsening (EC):The heavy-edge matching scheme used in the multilevel-graph bisection algorithm can also be used to obtain successively coarser hypergraphs by merging the pairs of vertices connected by many hyperedges.In this EC scheme,a heavy-edge maximal 1matching of the vertices of the hypergraph is computed as follows.The vertices are visited in a random order.For eachvertex are considered,and the one that is connected via the edge with the largest weight is matchedwithandandofsize72IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION(VLSI)SYSTEMS,VOL.7,NO.1,MARCH1999Fig.2.Various ways of matching the vertices in the hypergraph and the coarsening they induce.(a)In edge-coarsening,connected pairs of vertices are matched together.(b)In hyperedge-coarsening,all the vertices belonging to a hyperedge are matched together.(c)In MHEC,we match together all the vertices in a hyperedge,as well as all the groups of vertices belonging to a hyperedge.weight of successively coarser graphs does not decrease very fast.In order to ensure that for every group of vertices that are contracted together,there is a decrease in the hyperedge weight in the coarser graph,each such group of vertices must be connected by a hyperedge.This is the motivation behind the HEC scheme.In this scheme,an independent set of hyperedges is selected and the vertices that belong to individual hyperedges are contracted together.This is implemented as follows.The hyperedges are initially sorted in a nonincreasing hyperedge-weight order and the hyperedges of the same weight are sorted in a nondecreasing hyperedge size order.Then,the hyperedges are visited in that order,and for each hyperedge that connects vertices that have not yet been matched,the vertices are matched together.Thus,this scheme gives preference to the hyperedges that have large weight and those that are of small size.After all of the hyperedges have been visited,the groups of vertices that have been matched are contracted together to form the next level coarser graph.The vertices that are not part of any contracted hyperedges are simply copied to the next level coarser graph.3)Modified Hyperedge Coarsening(MHEC):The HEC algorithm is able to significantly reduce the amount of hyperedge weight that is left exposed in successively coarser graphs.However,during each coarsening phase,a majority of the hyperedges do not get contracted because vertices that belong to them have been contracted via other hyperedges. This leads to two problems.First,the size of many hyperedges does not decrease sufficiently,making FM-based refinement difficult.Second,the weight of the vertices(i.e.,the number of vertices that have been collapsed together)in successively coarser graphs becomes significantly different,which distorts the shape of the contracted hypergraph.To correct this problem,we implemented a MHEC scheme as follows.After the hyperedges to be contracted have been selected using the HEC scheme,the list of hyperedges is traversed again,and for each hyperedge that has not yet been contracted,the vertices that do not belong to any other contracted hyperedge are contracted together.B.Initial Partitioning PhaseDuring the initial partitioning phase,a bisection of the coarsest hypergraph is computed,such that it has a small cut, and satisfies a user-specified balance constraint.The balance constraint puts an upper bound on the difference between the relative size of the two partitions.Since this hypergraph has a very small number of vertices(usually less than200),the time tofind a partitioning using any of the heuristic algorithms tends to be small.Note that it is not useful tofind an optimal partition of this coarsest graph,as the initial partition will be sub-stantially modified during the refinement phase.We used the following two algorithms for computing the initial partitioning. Thefirst algorithm simply creates a random bisection such that each part has roughly equal vertex weight.The second algorithm starts from a randomly selected vertex and grows a region around it in a breadth-first fashion[22]until half of the vertices are in this region.The vertices belonging to the grown region are then assigned to thefirst part,and the rest of the vertices are assigned to the second part.After a partitioning is constructed using either of these algorithms,the partitioning is refined using the FM refinement algorithm.Since both algorithms are randomized,different runs give solutions of different quality.For this reason,we perform a small number of initial partitionings.At this point,we can select the best initial partitioning and project it to the original hypergraph,as described in Section II-C.However,the parti-tioning of the coarsest hypergraph that has the smallest cut may not necessarily be the one that will lead to the smallest cut in the original hypergraph.It is possible that another partitioning of the coarsest hypergraph(with a higher cut)will lead to a bet-KARYPIS et al.:MULTILEVEL HYPERGRAPH PARTITIONING:APPLICATIONS IN VLSI DOMAIN 73ter partitioning of the original hypergraph after the refinement is performed during the uncoarsening phase.For this reason,instead of selecting a single initial partitioning (i.e.,the one with the smallest cut),we propagate all initial partitionings.Note that propagation of.Thus,by increasing the value ofis to drop unpromising partitionings as thehypergraph is uncoarsened.For example,one possibility is to propagate only those partitionings whose cuts arewithinissufficiently large,then all partitionings will be maintained and propagated in the entire refinement phase.On the other hand,if the valueof,many partitionings may be available at the coarsest graph,but the number of such available partitionings will decrease as the graph is uncoarsened.This is useful for two reasons.First,it is more important to have many alternate partitionings at the coarser levels,as the size of the cut of a partitioning at a coarse level is a less accurate reflection of the size of the cut of the original finest level hypergraph.Second,refinement is more expensive at the fine levels,as these levels contain far more nodes than the coarse levels.Hence,by choosing an appropriate valueof(from 10%to a higher value such as 20%)did not significantly improve the quality of the partitionings,although it did increase the run time.C.Uncoarsening and Refinement PhaseDuring the uncoarsening phase,a partitioning of the coarser hypergraph is successively projected to the next-level finer hypergraph,and a partitioning refinement algorithm is used to reduce the cut set (and thus to improve the quality of the partitioning)without violating the user specified balance con-straints.Since the next-level finer hypergraph has more degrees of freedom,such refinement algorithms tend to improve the solution quality.We have implemented two different partitioning refinement algorithms.The first is the FM algorithm [8],which repeatedly moves vertices between partitions in order to improve the cut.The second algorithm,called hyperedge refinement (HER),moves groups of vertices between partitions so that an entire hyperedge is removed from the cut.These algorithms are further described in the remainder of this section.1)FM:The partitioning refinement algorithm by Fiduccia and Mattheyses [8]is iterative in nature.It starts with an initial partitioning of the hypergraph.In each iteration,it tries to find subsets of vertices in each partition,such that moving them to other partitions improves the quality of the partitioning (i.e.,the number of hyperedges being cut decreases)and this does not violate the balance constraint.If such subsets exist,then the movement is performed and this becomes the partitioning for the next iteration.The algorithm continues by repeating the entire process.If it cannot find such a subset,then the algorithm terminates since the partitioning is at a local minima and no further improvement can be made by this algorithm.In particular,for eachvertexto the other partition.Initially allvertices are unlocked ,i.e.,they are free to move to the other partition.The algorithm iteratively selects an unlockedvertex is moved,it is locked ,and the gain of the vertices adjacentto[8].For refinement in the context of multilevel schemes,the initial partitioning obtained from the next level coarser graph is actually a very good partition.For this reason,we can make a number of optimizations to the original FM algorithm.The first optimization limits the maximum number of passes performed by the FM algorithm to only two.This is because the greatest reduction in the cut is obtained during the first or second pass and any subsequent passes only marginally improve the quality.Our experience has shown that this optimization significantly improves the run time of FM without affecting the overall quality of the produced partitionings.The second optimization aborts each pass of the FM algorithm before actually moving all the vertices.The motivation behind this is that only a small fraction of the vertices being moved actually lead to a reduction in the cut and,after some point,the cut tends to increase as we move more vertices.When FM is applied to a random initial partitioning,it is quite likely that after a long sequence of bad moves,the algorithm will climb74IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI)SYSTEMS,VOL.7,NO.1,MARCH1999Fig.3.Effect of restricted coarsening .(a)Example hypergraph with a given partitioning with the required balance of 40/60.(b)Possible condensed version of (a).(c)Another condensed version of a hypergraph.out of a local minima and reach to a better cut.However,in the context of a multilevel scheme,a long sequence of cut-increasing moves rarely leads to a better local minima.For this reason,we stop each pass of the FM algorithm as soon as we haveperformedto be equal to 1%of the number ofvertices in the graph we are refining.This modification to FM,called early-exit FM (FM-EE),does not significantly affect the quality of the final partitioning,but it dramatically improves the run time (see Section IV).2)HER:One of the drawbacks of FM (and other similar vertex-based refinement schemes)is that it is often unable to refine hyperedges that have many nodes on both sides of the partitioning boundary.However,a refinement scheme that moves all the vertices that belong to a hyperedge can potentially solve this problem.Our HER works as follows.It randomly visits all the hyperedges and,for each one that straddles the bisection,it determines if it can move a subset of the vertices incident on it,so that this hyperedge will become completely interior to a partition.In particular,consider ahyperedgebe the verticesofto partition 0.Now,depending on these gains and subject to balance constraints,it may move one of the twosets .In particular,if.III.M ULTIPHASE R EFINEMENT WITHR ESTRICTED C OARSENINGAlthough the multilevel paradigm is quite robust,random-ization is inherent in all three phases of the algorithm.In particular,the random choice of vertices to be matched in the coarsening phase can disallow certain hyperedge cuts,reducing refinement in the uncoarsening phase.For example,consider the example hypergraph in Fig.3(a)and its two possible con-densed versions [Fig.3(b)and (c)]with the same partitioning.The version in Fig.3(b)is obtained by selectinghyperedgesto be compressed in the HEC phase and then selecting pairs ofnodesto be compressed inthe HEC phase and then selecting pairs ofnodesand apartitioningfor ,be the sequence of hypergraphsand partitionings.Given ahypergraphandorpartition,,are collapsedtogether to formvertexof,thenvertex belong。

Dyn Games Appl(2011)1:74–114DOI10.1007/s13235-010-0005-0Some Recent Aspects of Differential Game TheoryR.Buckdahn·P.Cardaliaguet·M.QuincampoixPublished online:5October2010©Springer-Verlag2010Abstract This survey paper presents some new advances in theoretical aspects of dif-ferential game theory.We particular focus on three topics:differential games with state constraints;backward stochastic differential equations approach to stochastic differential games;differential games with incomplete information.We also address some recent devel-opment in nonzero-sum differential games(analysis of systems of Hamilton–Jacobi equa-tions by conservation laws methods;differential games with a large number of players,i.e., mean-field games)and long-time average of zero-sum differential games.Keywords Differential game·Viscosity solution·System of Hamilton–Jacobi equations·Mean-field games·State-constraints·Backward stochastic differential equations·Incomplete information1IntroductionThis survey paper presents some recent results in differential game theory.In order to keep the presentation at a reasonable size,we have chosen to describe in full details three topics with which we are particularly familiar,and to give a brief summary of some other research directions.Although this choice does not claim to represent all the recent literature on the R.Buckdahn·M.QuincampoixUniversitéde Brest,Laboratoire de Mathématiques,UMR6205,6Av.Le Gorgeu,BP809,29285Brest, FranceR.Buckdahne-mail:Rainer.Buckdahn@univ-brest.frM.Quincampoixe-mail:Marc.Quincampoix@univ-brest.frP.Cardaliaguet( )Ceremade,UniversitéParis-Dauphine,Place du Maréchal de Lattre de Tassigny,75775Paris Cedex16, Francee-mail:cardaliaguet@ceremade.dauphine.frmore theoretic aspects of differential game theory,we are pretty much confident that it cov-ers a large part of what has recently been written on the subject.It is clear however that the respective part dedicated to each topic is just proportional to our own interest in it,and not to its importance in the literature.The three main topics we have chosen to present in detail are:–Differential games with state constraints,–Backward stochastic differential equation approach to differential games,–Differential games with incomplete information.Before this,we also present more briefly two domains which have been the object of very active research in recent years:–nonzero-sum differential games,–long-time average of differential games.Thefirst section of this survey is dedicated to nonzero-sum differential games.Although zero-sum differential games have attracted a lot of attention in the80–90’s(in particular, thanks to the introduction of viscosity solutions for Hamilton–Jacobi equations),the ad-vances on nonzero-sum differential games have been scarcer,and mainly restricted to linear-quadratic games or stochastic differential games with a nondegenerate diffusion.The main reason for this is that there was very little understanding of the system of Hamilton–Jacobi equations naturally attached to these games.In the recent years the analysis of this sys-tem has been the object of several papers by Bressan and his co-authors.At the same time, nonzero-sum differential games with a very large number of players have been investigated in the terminology of mean-field games by Lasry and Lions.In the second section we briefly sum up some advances in the analysis of the large time behavior of zero-sum differential games.Such problems have been the aim of intense re-search activities in the framework of repeated game theory;it has however only been re-cently investigated for differential games.In the third part of this survey(thefirst one to be the object of a longer development) we investigate the problem of state constraints for differential games,and in particular,for pursuit-evasion games.Even if such class of games has been studied since Isaacs’pioneer-ing work[80],the existence of a value was not known up to recently for these games in a rather general framework.This is mostly due to the lack of regularity of the Hamiltonian and of the value function,which prevents the usual viscosity solution approach to work(Evans and Souganidis[63]):Indeed some controllability conditions on the phase space have to be added in order to prove the existence of the value(Bardi,Koike and Soravia[18]).Following Cardaliaguet,Quincampoix and Saint Pierre[50]and Bettiol,Cardaliaguet and Quincam-poix[26]we explain that,even without controllability conditions,the game has a value and that this value can be characterized as the smallest supersolution of some Hamilton–Jacobi equation with discontinuous Hamiltonian.Next we turn to zero-sum stochastic differential games.Since the pioneering work by Fleming and Souginidis[65]it has been known that such games have a value,at least in a framework of games of the type“nonanticipating strategies against controls”.Unfortunately this notion of strategies is not completely satisfactory,since it presupposes that the players have a full knowledge of their opponent’s control in all states of the world:It would be more natural to assume that the players use strategies which give an answer to the control effectively played by their opponent.On the other hand it seems also natural to consider nonlinear cost functionals and to allow the controls of the players to depend on events of the past which happened before the beginning of the game.The last two points have beeninvestigated in a series of papers by Buckdahn and Li[35,36,39],and an approach more direct than that in[65]has been developed.Thefirst point,together with the two others,will be the object of the fourth part of the survey.In the last part we study differential games with incomplete information.In such games, one of the parameters of the game is chosen at random according to some probability mea-sure and the result is told to one of the players and not to the other.Then the game is played as usual,players observing each other’s control.The main difference with the usual case is that at least one of the players does not know which payoff he is actually optimizing.All the difficulty of this game is to understand what kind of information the informed player has interest in to disclose in order to optimize his payoff,taking thus the risk that his opponent learns his missing information.Such games are the natural extension to differential games of the Aumann–Maschler theory for repeated games[11].Their analysis has been developed in a series of papers by Cardaliaguet[41,43–45]and Cardaliaguet and Rainer[51,52].Throughout these notes we assume the reader to be familiar with the basic results of dif-ferential game theory.Many references can be quoted on this subject:A general introduction for the formal relation between differential games and Hamilton–Jacobi equations(or sys-tem)can be found in the monograph Baçar and Olsder[13].We also refer the reader to the classical monographs by Isaacs[80],Friedman[67]and Krasovskii and Subbotin[83]for early presentations of differential game theory.The recent literature on differential games strongly relies on the notion of viscosity solution:Classical monographs on this subject are Bardi and Capuzzo Dolcetta[17],Barles[19],Fleming and Soner[64],Lions[93]and the survey paper by Crandall,Ishii and Lions[56].In particular[17]contains a good introduc-tion to the viscosity solution aspects of deterministic zero-sum differential games:the proof of the existence and the characterization of a value for a large class of differential games can be found there.Section6is mostly based on the notion of backward stochastic differential equation(BSDE):We refer to El Karoui and Mazliak[60],Ma and Yong[96]and Yong and Zhou[116]for a general presentation.The reader is in particular referred to the work by S.Peng on BSDE methods in stochastic control[101].Let usfinally note that,even if this survey tries to cover a large part of the recent literature on the more theoretical aspects of differential games,we have been obliged to omit some topics:linear-quadratic differential games are not covered by this survey despite their usefulness in applications;however,these games have been already the object of several survey ck of place also prevented us from describing advances in the domain of Dynkin games.2Nonzero-sum Differential GamesIn the recent years,the more striking advances in the analysis of nonzero-sum differential games have been directed in two directions:analysis by P.D.E.methods of Nash feedback equilibria for deterministic differential games;differential games with a very large number of small players(mean-field games).These topics appear as the natural extensions of older results:existence of Nash equilibria in memory strategies and of Nash equilibria in feedback strategies for stochastic differential games,which have also been revisited.2.1Nash Equilibria in Memory StrategiesSince the work of Kononenko[82](see also Kleimenov[81],Tolwinski,Haurie and Leit-mann[114],Gaitsgory and Nitzan[68],Coulomb and Gaitsgory[55]),it has been knownthat deterministic nonzero-sum differential games admit Nash equilibrium payoffs in mem-ory strategies:This result is actually the counterpart of the so-called Folk Theorem in re-peated game theory[100].Recall that a memory(or a nonanticipating)strategy for a player is a strategy where this player takes into account the past controls played by the other play-ers.In contrast a feedback strategy is a strategy which only takes into account the present position of the system.Following[82]Nash equilibrium payoffs in memory strategies are characterized as follows:A payoff is a Nash equilibrium payoff if and only if it is reach-able(i.e.,the players can obtain it by playing some control)and individually rational(the expected payoff for a player lies above its min-max level at any point of the resulting trajec-tory).This result has been recently generalized to stochastic differential games by Buckdahn, Cardaliaguet and Rainer[38](see also Rainer[105])and to games in which players can play random strategies by Souquière[111].2.2Nash Equilibria in Feedback FormAlthough the existence and characterization result of Nash equilibrium payoffs in mem-ory strategies is quite general,it has several major drawbacks.Firstly,there are,in general, infinitely many such Nash equilibria,but there exists—at least up to now—no completely satisfactory way to select one.Secondly,such equilibria are usually based on threatening strategies which are often non credible.Thirdly,the corresponding strategies are,in general, not“time-consistent”and in particular cannot be computed by any kind of“backward in-duction”.For this reason it is desirable tofind more robust notions of Nash equilibria.The best concept at hand is the notion of subgame perfect Nash equilibria.Since the works of Case[54]and Friedman[67],it is known that subgame perfect Nash equilibria are(at least heuristically)given by feedback strategies and that their corresponding payoffs should be the solution of a system of Hamilton–Jacobi equations.Up to now these ideas have been successfully applied to linear-quadratic differential games(Case[54],Starr and Ho[113], ...)and to stochastic differential games with non degenerate viscosity term:In thefirst case,one seeks solutions which are quadratic with respect to the state variable;this leads to the resolution of Riccati equations.In the latter case,the regularizing effect of the non-degenerate diffusion allows us to usefixed point arguments to get either Nash equilibrium payoffs or Nash equilibrium feedbacks.Several approaches have been developed:Borkar and Ghosh[27]consider infinite horizon problems and use the smoothness of the invari-ant measure associated to the S.D.E;Bensoussan and Frehse[21,22]and Mannucci[97] build“regular”Nash equilibrium payoffs satisfying a system of Hamilton–Jacobi equations thanks to elliptic or parabolic P.D.E techniques;Nash equilibrium feedbacks can also be built by backward stochastic differential equations methods like in Hamadène,Lepeltier and Peng[75],Hamadène[74],Lepeltier,Wu and Yu[92].2.3Ill-posedness of the System of HJ EquationsIn a series of articles,Bressan and his co-authors(Bressan and Chen[33,34],Bressan and Priuli[32],Bressan[30,31])have analyzed with the help of P.D.E methods the system of Hamilton–Jacobi equations arising in the construction of feedback Nash equilibria for deter-ministic nonzero-sum games.In state-space dimension1and for thefinite horizon problem, this system takes the form∂V i+H i(x,D V1,...,D V n)=0in R×(0,T),i=1,...,n,coupled with a terminal condition at time T(here n is the number of players and H i is the Hamiltonian of player i,V i(t,x)is the payoff obtained by player i for the initial condition (t,x)).Setting p i=(V i)x and deriving the above system with respect to x one obtains the system of conservation laws:∂t p i+H i(x,p1,...,p n)x=0in R×(0,T).This system turns out to be,in general,ill-posed.Typically,in the case of two players(n= 2),the system is ill-posed if the terminal payoff of the players have an opposite monotonicity. If,on the contrary,these payoffs have the same monotony and are close to some linear payoff (which is a kind of cooperative case),then the above system has a unique solution,and one can build Nash equilibria in feedback form from the solution of the P.D.E[33].Still in space dimension1,the case of infinite horizon seems more promising:The sys-tem of P.D.E then reduces to an ordinary differential equation.The existence of suitable solutions for this equation then leads to Nash equilibria.Such a construction is carried out in Bressan and Priuli[32],Bressan[30,31]through several classes of examples and by various methods.In a similar spirit,the papers Cardaliaguet and Plaskacz[47],Cardaliaguet[42]study a very simple class of nonzero-sum differential games in dimension1and with a terminal payoff:In this case it is possible to select a unique Nash equilibrium payoff in feedback form by just imposing that it is Pareto whenever there is a unique Pareto one.However,this equilibrium payoff turns out to be highly unstable with respect to the terminal data.Some other examples of nonlinear-quadratic differential games are also analyzed in Olsder[99] and in Ramasubramanian[106].2.4Mean-field GamesSince the system of P.D.Es arising in nonzero-sum differential games is,in general,ill-posed,it is natural to investigate situations where the problem simplifies.It turns out that this is the case for differential games with a very large number of identical players.This problem has been recently developed in a series of papers by Lasry and Lions[87–90,94] under the terminology of mean-field games(see also Huang,Caines and Malhame[76–79] for a related approach).The main achievement of Lasry and Lions is the identification of the limit when the number of players tends to infinity.The typical resulting model takes the form⎧⎪⎨⎪⎩(i)−∂t u−Δu+H(x,m,Du)=0in R d×(0,T),(ii)∂t m−Δm−divD p H(x,m,Du)m=0in R d×(0,T),(iii)m(0)=m0,u(x,T)=Gx,m(T).(1)In the above system,thefirst equation has to be understood backward in time while the second one is forward in time.Thefirst equation(a Hamilton–Jacobi one)is associated with an optimal control problem and its solution can be regarded as the value function for a typical small player(in particular the Hamiltonian H=H(x,m,p)is convex with respect to the last variable).As for the second equation,it describes the evolution of the density m(t)of the population.More precisely,let usfirst consider the behavior of a typical player.He controls through his control(αs)the stochastic differential equationdX t=αt dt+√2B t(where(B t)is a standard Brownian motion)and he aims at minimizing the quantityET12LX s,m(s),αsds+GX T,m(T),where L is the Fenchel conjugate of H with respect to the p variable.Note that in this cost the evolving measure m(s)enters as a parameter.The value function of our average player is then given by(1-(i)).His optimal control is—at least heuristically—given in feedback form byα∗(x,t)=−D p H(x,m,Du).Now,if all agents argue in this way,their repartition will move with a velocity which is due,on the one hand,to the diffusion,and,one the other hand,to the drift term−D p H(x,m,Du).This leads to the Kolmogorov equation(1-(ii)).The mean-field game theory developed so far has been focused on two main issues:firstly,investigate equations of the form(1)and give an interpretation(in economics,for instance)of such systems.Secondly,analyze differential games with afinite but large num-ber of players and interpret(1)as their limiting behavior as the number of players goes to infinity.Up to now thefirst issue is well understood and well documented.The original works by Lasry and Lions give a certain number of conditions under which(1)has a solution,discuss its uniqueness and its stability.Several papers also study the numerical approximation of this solution:see Achdou and Capuzzo Dolcetta[1],Achdou,Camilli and Capuzzo Dolcetta[2], Gomes,Mohr and Souza[71],Lachapelle,Salomon and Turinici[85].The mean-field games theory has been used in the analysis of wireless communication systems in Huang,Caines and Malhamé[76],or Yin,Mehta,Meyn and Shanbhag[115].It seems also particularly adapted to modeling problems in economics:see Guéant[72,73],Lachapelle[84],Lasry, Lions,Guéant[91],and the references therein.As for the second part of the program,the limiting behavior of differential games when the number of players tend to infinity has been understood for ergodic differential games[88].The general case remains mostly open.3Long-time Average of Differential GamesAnother way to reduce the complexity of differential games is to look at their long-time be-havior.Among the numerous applications of this topic let us quote homogenization,singular perturbations and dimension reduction of multiscale systems.In order to explain the basic ideas,let us consider a two-player stochastic zero-sum dif-ferential game with dynamics given bydX t,ζ;u,vs =bX t,ζ;u,vs,u s,v sds+σX t,ζ;u,v,u s,v sdB s,s∈[t,+∞),X t=ζ,where B is a d-dimensional standard Brownian motion on a given probability space (Ω,F,P),b:R N×U×V→R N andσ:R N×U×V→R N×d,U and V being some metric compact sets.We assume that thefirst player,playing with u,aims at minimizing a running payoff :R N×U×V→R(while the second players,playing with v,maximizes). Then it is known that,under some Isaacs’assumption,the game has a value V T which is the viscosity solution of a second order Hamilton–Jacobi equation of the form−∂t V T(t,x)+Hx,D V T(t,x),D2V T(t,x)=0in[0,T]×R N,V T(T,x)=0in R N.A natural question is the behavior of V T as T→+∞.Actually,since V T is typically of linear growth,the natural quantity to consider is the long-time average,i.e.,lim T→+∞V T/T.Interesting phenomena can be observed under some compactness assumption on the un-derlying state-space.Let us assume,for instance,that the maps b(·,u,v),σ(·,u,v)and (·,u,v)are periodic in all space variables:this actually means that the game takes place in the torus R N/Z N.In this framework,the long-time average is well understood in two cases:either the dif-fusion is strongly nondegenerate:∃ν>0,(σσ∗)(x,u,v)≥νI N∀x,u,v,(where the inequality is understood in the sense of quadratic matrices);orσ≡0and H= H(x,ξ)is coercive:lim|ξ|→+∞H(x,ξ)=+∞uniformly with respect to x.(2) In both cases the quantity V T(x,0)/T uniformly converges to the unique constant¯c forwhich the problem¯c+Hx,Dχ(x),D2χ(x)=0in R Nhas a continuous,periodic solutionχ.In particular,the limit is independent of the initial condition.Such kind of results has been proved by Lions,Papanicoulaou and Varadhan[95] forfirst order equations(i.e.,deterministic differential games).For second order equations, the result has been obtained by Alvarez and Bardi in[3],where the authors combine funda-mental contributions of Evans[61,62]and of Arisawa and Lions[7](see also Alvarez and Bardi[4,5],Bettiol[24],Ghosh and Rao[70]).For deterministic differential games(i.e.,σ≡0),the coercivity condition(2)is not very natural:Indeed,it means that one of the players is much more powerful than the other one. However,very little is known without such a condition.Existing results rely on a specific structure of the game:see for instance Bardi[16],Cardaliaguet[46].The difficulty comes from the fact that,in these cases,the limit may depend upon the initial condition(see also Arisawa and Lions[7],Quincampoix and Renault[104]for related issues in a control set-ting).The existence of a limit for large time differential games is certainly one of the main challenges in differential games theory.4Existence of a Value for Zero-sum Differential Games with State Constraints Differential games with state constraints have been considered since the early theory of differential games:we refer to[23,28,66,69,80]for the computation of the solution for several examples of pursuit.We present here recent trends for obtaining the existence of a value for a rather general class of differential games with constraints.This question had been unsolved during a rather long period due to problems we discuss now.The main conceptual difficulty for considering such zero-sum games lies in the fact that players have to achieve their own goal and to satisfy the state constraint.Indeed,it is not clear to decide which players has to be penalized if the state constraint is violated.For this reason,we only consider a specific class of decoupled games where each player controls independently a part of the dynamics.A second mathematical difficulty comes from the fact that players have to use admissible controls i.e.,controls ensuring the trajectory to fulfilthe state constraint.A byproduct of this problem is the fact that starting from two close initial points it is not obvious tofind two close constrained trajectories.This also affects the regularity of value functions associated with admissible controls:The value functions are,in general,not Lipschitz continuous anymore and,consequently,classical viscosity solutions methods for Hamilton–Jacobi equations may fail.4.1Statement of the ProblemWe consider a differential game where thefirst player playing with u,controls afirst systemy (t)=gy(t),u(t),u(t)∈U,y(t0)=y0∈K U,(3) while the second player,playing with v,controls a second systemz (t)=hz(t),v(t),v(t)∈V,z(t0)=z0∈K V.(4)For every time t,thefirst player has to ensure the state constraint y(t)∈K U while the second player has to respect the state constraint z(t)∈K V for any t∈[t0,T].We denote by x(t)= x[t0,x0;u(·),v(·)](t)=(y[t0,y0;u(·)](t),z[t0,z0;v(·)](t))the solution of the systems(3) and(4)associated with an initial data(t0,x0):=(t0,y0,z0)and with a couple of controls (u(·),v(·)).In the following lines we summarize all the assumptions concerning with the vectorfields of the dynamics:⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎩(i)U and V are compact subsets of somefinitedimensional spaces(ii)f:R n×U×V→R n is continuous andLipschitz continuous(with Lipschitz constant M)with respect to x∈R n(iii)uf(x,u,v)andvf(x,u,v)are convex for any x(iv)K U={y∈R l,φU(y)≤0}withφU∈C2(R l;R),∇φU(y)=0ifφU(y)=0(v)K V={z∈R m,φV(z)≤0}withφV∈C2(R m;R),∇φV(z)=0ifφV(z)=0(vi)∀y∈∂K U,∃u∈U such that ∇φU(y),g(y,u) <0(vii)∀z∈∂K V,∃v∈V such that ∇φV(z),h(z,v) <0(5)We need to introduce the notion of admissible controls:∀y0∈K U,∀z0∈K V and∀t0∈[0,T]we defineU(t0,y0):=u(·):[t0,+∞)→U measurable|y[t0,y0;u(·)](t)∈K U∀t≥t0V(t0,z0):=v(·):[t0,+∞)→V measurable|z[t0,z0;v(·)](t)∈K V∀t≥t0.Under assumptions(5),the Viability Theorem(see[9,10])ensures that for all x0= (y0,z0)∈K U×K VU(t0,y0)=∅and V(t0,z0)=∅.Throughout the paper we omit t0in the notations U(t0,y0)and U(t0,y0)whenever t0=0.We now describe two quantitative differential games.Let us start with a game with an integral cost:Bolza Type Differential Game Given a running cost L:[0,T]×R N×U×V→R and afinal costΨ:R N→R,we define the payoff associated to an initial position(t0,x0)= (t0,y0,z0)and to a pair of controls(u,v)∈U(t0,y0)×V(t0,z0)byJt0,x0;u(·),v(·)=Tt0Lt,x(t),u(·),v(·)dt+Ψx(T),(6)where x(t)=x[t0,x0;u(·),v(·)](t)=(y[t0,y0;u(·)](t),z[t0,z0;v(·)](t))denotes the solu-tion of the systems(3)and(4).Thefirst player wants to maximize the functional J,while the second player’s goal is to minimize J.Definition1A mapα:V(t0,z0)→U(t0,y0)is a nonanticipating strategy(for thefirst player and for the point(t0,x0):=(t0,y0,z0)∈R+×K U×K V)if,for anyτ>0,for all controls v1(·)and v2(·)belonging to V(t0,z0),which coincide a.e.on[t0,t0+τ],α(v1(·)) andα(v2(·))coincide almost everywhere on[t0,t0+τ].Nonanticipating strategiesβfor the second player are symmetrically defined.For any point x0∈K U×K V and∀t0∈[0,T]we denote by A(t0,x0)and by B(t0,x0)the sets of the nonanticipating strategies for thefirst and the second player respectively.We are now ready to define the value functions of the game.The lower value V−is defined by:V−(t0,x0):=infβ∈B(t0,x0)supu(·)∈U(t0,y0)Jt0,x0;u(·),βu(·),(7)where J is defined by(6).On the other hand we define the upper value function as follows:V+(t0,x0):=limε→0+supα∈A(t0,x0)infv(·)∈V(t0,z0)Jεt0,x0;αv(·),v(·)(8)withJεt0,x0;u(·),v(·):=Tt0Lt,x(t),u(t),v(t)dt+Ψεx(T),where x(t)=x[t0,x0;u(·),v(·)](t)andΨεis the lower semicontinuous function defined byΨε(x):=infρ∈R|∃y∈R n with(y,ρ)−x,Ψ(x)=ε.The asymmetry between the definition of the value functions is due to the fact that one assumes that the terminal payoffΨis lower semicontinuous.WhenΨis continuous,one can check that V+can equivalently be defined in a more natural way asV+(t0,x0):=supα∈A(t0,x0)infv(·)∈V(t0,z0)Jt0,x0;αv(·),v(·).We now describe the second differential game which is a pursuit game with closed target C⊂K U×K V.Pursuit Type Differential Game The hitting time of C for a trajectory x(·):=(y(·),z(·)) is:θCx(·):=inft≥0|x(t)∈C.If x(t)/∈C for every t≥0,then we setθC(x(·)):=+∞.In the pursuit game,thefirst player wants to maximizeθC while the second player wants to minimize it.The value functions aredefined as follows:The lower optimal hitting-time function is the mapϑ−C :K U×K V→R+∪{+∞}defined,for any x0:=(y0,z0),byϑ−C (x0):=infβ(·)∈B(x0)supu(·)∈U(y0)θCxx0,u(·),βu(·).The upper optimal hitting-time function is the mapϑ+C :K U×K V→R+∪{+∞}de-fined,for any x0:=(y0,z0),byϑ+ C (x0):=limε→0+supα(·)∈A(x0)infv(·)∈V(z0)θC+εBxx0,αv(·),v(·).By convention,we setϑ−C (x)=ϑ+C(x)=0on C.Remarks–Note that here again the definition of the upper and lower value functions are not sym-metric:this is related to the fact that the target assumed to be closed,so that the game is intrinsically asymmetric.–The typical pursuit game is the case when the target coincides with the diagonal:C= {(y,z),|y=z}.We refer the reader to[6,29]for various types of pursuit games.The formalism of the present survey is adapted from[50].4.2Main ResultThe main difficulty for the analysis of state-constraint problems lies in the fact that two trajectories of a control system starting from two—close—different initial conditions could be estimated by classical arguments on the continuity of theflow of the differential equation. For constrained systems,it is easy to imagine cases where the constrained trajectories starting from two close initial conditions are rather far from each other.So,an important problem in order to get suitable estimates on constrained trajectories,is to obtain a kind of Filippov Theorem with ly a result which allows one to approach—in a suitable sense—a given trajectory of the dynamics by a constrained trajectory.Note that similar results exist in the literature.However,we need here to construct a constrained trajectory in a nonanticipating way[26](cf.also[25]),which is not the case in the previous constructions.Proposition1Assume that conditions(5)are satisfied.For any R>0there exist C0= C0(R)>0such that for any initial time t0∈[0,T],for any y0,y1∈K U with|y0|,|y1|≤R,。

A Survey of Clustering Data Mining TechniquesPavel BerkhinYahoo!,Inc.pberkhin@Summary.Clustering is the division of data into groups of similar objects.It dis-regards some details in exchange for data simplifirmally,clustering can be viewed as data modeling concisely summarizing the data,and,therefore,it re-lates to many disciplines from statistics to numerical analysis.Clustering plays an important role in a broad range of applications,from information retrieval to CRM. Such applications usually deal with large datasets and many attributes.Exploration of such data is a subject of data mining.This survey concentrates on clustering algorithms from a data mining perspective.1IntroductionThe goal of this survey is to provide a comprehensive review of different clus-tering techniques in data mining.Clustering is a division of data into groups of similar objects.Each group,called a cluster,consists of objects that are similar to one another and dissimilar to objects of other groups.When repre-senting data with fewer clusters necessarily loses certainfine details(akin to lossy data compression),but achieves simplification.It represents many data objects by few clusters,and hence,it models data by its clusters.Data mod-eling puts clustering in a historical perspective rooted in mathematics,sta-tistics,and numerical analysis.From a machine learning perspective clusters correspond to hidden patterns,the search for clusters is unsupervised learn-ing,and the resulting system represents a data concept.Therefore,clustering is unsupervised learning of a hidden data concept.Data mining applications add to a general picture three complications:(a)large databases,(b)many attributes,(c)attributes of different types.This imposes on a data analysis se-vere computational requirements.Data mining applications include scientific data exploration,information retrieval,text mining,spatial databases,Web analysis,CRM,marketing,medical diagnostics,computational biology,and many others.They present real challenges to classic clustering algorithms. These challenges led to the emergence of powerful broadly applicable data2Pavel Berkhinmining clustering methods developed on the foundation of classic techniques.They are subject of this survey.1.1NotationsTo fix the context and clarify terminology,consider a dataset X consisting of data points (i.e.,objects ,instances ,cases ,patterns ,tuples ,transactions )x i =(x i 1,···,x id ),i =1:N ,in attribute space A ,where each component x il ∈A l ,l =1:d ,is a numerical or nominal categorical attribute (i.e.,feature ,variable ,dimension ,component ,field ).For a discussion of attribute data types see [106].Such point-by-attribute data format conceptually corresponds to a N ×d matrix and is used by a majority of algorithms reviewed below.However,data of other formats,such as variable length sequences and heterogeneous data,are not uncommon.The simplest subset in an attribute space is a direct Cartesian product of sub-ranges C = C l ⊂A ,C l ⊂A l ,called a segment (i.e.,cube ,cell ,region ).A unit is an elementary segment whose sub-ranges consist of a single category value,or of a small numerical bin.Describing the numbers of data points per every unit represents an extreme case of clustering,a histogram .This is a very expensive representation,and not a very revealing er driven segmentation is another commonly used practice in data exploration that utilizes expert knowledge regarding the importance of certain sub-domains.Unlike segmentation,clustering is assumed to be automatic,and so it is a machine learning technique.The ultimate goal of clustering is to assign points to a finite system of k subsets (clusters).Usually (but not always)subsets do not intersect,and their union is equal to a full dataset with the possible exception of outliersX =C 1 ··· C k C outliers ,C i C j =0,i =j.1.2Clustering Bibliography at GlanceGeneral references regarding clustering include [110],[205],[116],[131],[63],[72],[165],[119],[75],[141],[107],[91].A very good introduction to contem-porary data mining clustering techniques can be found in the textbook [106].There is a close relationship between clustering and many other fields.Clustering has always been used in statistics [10]and science [158].The clas-sic introduction into pattern recognition framework is given in [64].Typical applications include speech and character recognition.Machine learning clus-tering algorithms were applied to image segmentation and computer vision[117].For statistical approaches to pattern recognition see [56]and [85].Clus-tering can be viewed as a density estimation problem.This is the subject of traditional multivariate statistical estimation [197].Clustering is also widelyA Survey of Clustering Data Mining Techniques3 used for data compression in image processing,which is also known as vec-tor quantization[89].Datafitting in numerical analysis provides still another venue in data modeling[53].This survey’s emphasis is on clustering in data mining.Such clustering is characterized by large datasets with many attributes of different types. Though we do not even try to review particular applications,many important ideas are related to the specificfields.Clustering in data mining was brought to life by intense developments in information retrieval and text mining[52], [206],[58],spatial database applications,for example,GIS or astronomical data,[223],[189],[68],sequence and heterogeneous data analysis[43],Web applications[48],[111],[81],DNA analysis in computational biology[23],and many others.They resulted in a large amount of application-specific devel-opments,but also in some general techniques.These techniques and classic clustering algorithms that relate to them are surveyed below.1.3Plan of Further PresentationClassification of clustering algorithms is neither straightforward,nor canoni-cal.In reality,different classes of algorithms overlap.Traditionally clustering techniques are broadly divided in hierarchical and partitioning.Hierarchical clustering is further subdivided into agglomerative and divisive.The basics of hierarchical clustering include Lance-Williams formula,idea of conceptual clustering,now classic algorithms SLINK,COBWEB,as well as newer algo-rithms CURE and CHAMELEON.We survey these algorithms in the section Hierarchical Clustering.While hierarchical algorithms gradually(dis)assemble points into clusters (as crystals grow),partitioning algorithms learn clusters directly.In doing so they try to discover clusters either by iteratively relocating points between subsets,or by identifying areas heavily populated with data.Algorithms of thefirst kind are called Partitioning Relocation Clustering. They are further classified into probabilistic clustering(EM framework,al-gorithms SNOB,AUTOCLASS,MCLUST),k-medoids methods(algorithms PAM,CLARA,CLARANS,and its extension),and k-means methods(differ-ent schemes,initialization,optimization,harmonic means,extensions).Such methods concentrate on how well pointsfit into their clusters and tend to build clusters of proper convex shapes.Partitioning algorithms of the second type are surveyed in the section Density-Based Partitioning.They attempt to discover dense connected com-ponents of data,which areflexible in terms of their shape.Density-based connectivity is used in the algorithms DBSCAN,OPTICS,DBCLASD,while the algorithm DENCLUE exploits space density functions.These algorithms are less sensitive to outliers and can discover clusters of irregular shape.They usually work with low-dimensional numerical data,known as spatial data. Spatial objects could include not only points,but also geometrically extended objects(algorithm GDBSCAN).4Pavel BerkhinSome algorithms work with data indirectly by constructing summaries of data over the attribute space subsets.They perform space segmentation and then aggregate appropriate segments.We discuss them in the section Grid-Based Methods.They frequently use hierarchical agglomeration as one phase of processing.Algorithms BANG,STING,WaveCluster,and FC are discussed in this section.Grid-based methods are fast and handle outliers well.Grid-based methodology is also used as an intermediate step in many other algorithms (for example,CLIQUE,MAFIA).Categorical data is intimately connected with transactional databases.The concept of a similarity alone is not sufficient for clustering such data.The idea of categorical data co-occurrence comes to the rescue.The algorithms ROCK,SNN,and CACTUS are surveyed in the section Co-Occurrence of Categorical Data.The situation gets even more aggravated with the growth of the number of items involved.To help with this problem the effort is shifted from data clustering to pre-clustering of items or categorical attribute values. Development based on hyper-graph partitioning and the algorithm STIRR exemplify this approach.Many other clustering techniques are developed,primarily in machine learning,that either have theoretical significance,are used traditionally out-side the data mining community,or do notfit in previously outlined categories. The boundary is blurred.In the section Other Developments we discuss the emerging direction of constraint-based clustering,the important researchfield of graph partitioning,and the relationship of clustering to supervised learning, gradient descent,artificial neural networks,and evolutionary methods.Data Mining primarily works with large databases.Clustering large datasets presents scalability problems reviewed in the section Scalability and VLDB Extensions.Here we talk about algorithms like DIGNET,about BIRCH and other data squashing techniques,and about Hoffding or Chernoffbounds.Another trait of real-life data is high dimensionality.Corresponding de-velopments are surveyed in the section Clustering High Dimensional Data. The trouble comes from a decrease in metric separation when the dimension grows.One approach to dimensionality reduction uses attributes transforma-tions(DFT,PCA,wavelets).Another way to address the problem is through subspace clustering(algorithms CLIQUE,MAFIA,ENCLUS,OPTIGRID, PROCLUS,ORCLUS).Still another approach clusters attributes in groups and uses their derived proxies to cluster objects.This double clustering is known as co-clustering.Issues common to different clustering methods are overviewed in the sec-tion General Algorithmic Issues.We talk about assessment of results,de-termination of appropriate number of clusters to build,data preprocessing, proximity measures,and handling of outliers.For reader’s convenience we provide a classification of clustering algorithms closely followed by this survey:•Hierarchical MethodsA Survey of Clustering Data Mining Techniques5Agglomerative AlgorithmsDivisive Algorithms•Partitioning Relocation MethodsProbabilistic ClusteringK-medoids MethodsK-means Methods•Density-Based Partitioning MethodsDensity-Based Connectivity ClusteringDensity Functions Clustering•Grid-Based Methods•Methods Based on Co-Occurrence of Categorical Data•Other Clustering TechniquesConstraint-Based ClusteringGraph PartitioningClustering Algorithms and Supervised LearningClustering Algorithms in Machine Learning•Scalable Clustering Algorithms•Algorithms For High Dimensional DataSubspace ClusteringCo-Clustering Techniques1.4Important IssuesThe properties of clustering algorithms we are primarily concerned with in data mining include:•Type of attributes algorithm can handle•Scalability to large datasets•Ability to work with high dimensional data•Ability tofind clusters of irregular shape•Handling outliers•Time complexity(we frequently simply use the term complexity)•Data order dependency•Labeling or assignment(hard or strict vs.soft or fuzzy)•Reliance on a priori knowledge and user defined parameters •Interpretability of resultsRealistically,with every algorithm we discuss only some of these properties. The list is in no way exhaustive.For example,as appropriate,we also discuss algorithms ability to work in pre-defined memory buffer,to restart,and to provide an intermediate solution.6Pavel Berkhin2Hierarchical ClusteringHierarchical clustering builds a cluster hierarchy or a tree of clusters,also known as a dendrogram.Every cluster node contains child clusters;sibling clusters partition the points covered by their common parent.Such an ap-proach allows exploring data on different levels of granularity.Hierarchical clustering methods are categorized into agglomerative(bottom-up)and divi-sive(top-down)[116],[131].An agglomerative clustering starts with one-point (singleton)clusters and recursively merges two or more of the most similar clusters.A divisive clustering starts with a single cluster containing all data points and recursively splits the most appropriate cluster.The process contin-ues until a stopping criterion(frequently,the requested number k of clusters) is achieved.Advantages of hierarchical clustering include:•Flexibility regarding the level of granularity•Ease of handling any form of similarity or distance•Applicability to any attribute typesDisadvantages of hierarchical clustering are related to:•Vagueness of termination criteria•Most hierarchical algorithms do not revisit(intermediate)clusters once constructed.The classic approaches to hierarchical clustering are presented in the sub-section Linkage Metrics.Hierarchical clustering based on linkage metrics re-sults in clusters of proper(convex)shapes.Active contemporary efforts to build cluster systems that incorporate our intuitive concept of clusters as con-nected components of arbitrary shape,including the algorithms CURE and CHAMELEON,are surveyed in the subsection Hierarchical Clusters of Arbi-trary Shapes.Divisive techniques based on binary taxonomies are presented in the subsection Binary Divisive Partitioning.The subsection Other Devel-opments contains information related to incremental learning,model-based clustering,and cluster refinement.In hierarchical clustering our regular point-by-attribute data representa-tion frequently is of secondary importance.Instead,hierarchical clustering frequently deals with the N×N matrix of distances(dissimilarities)or sim-ilarities between training points sometimes called a connectivity matrix.So-called linkage metrics are constructed from elements of this matrix.The re-quirement of keeping a connectivity matrix in memory is unrealistic.To relax this limitation different techniques are used to sparsify(introduce zeros into) the connectivity matrix.This can be done by omitting entries smaller than a certain threshold,by using only a certain subset of data representatives,or by keeping with each point only a certain number of its nearest neighbors(for nearest neighbor chains see[177]).Notice that the way we process the original (dis)similarity matrix and construct a linkage metric reflects our a priori ideas about the data model.A Survey of Clustering Data Mining Techniques7With the(sparsified)connectivity matrix we can associate the weighted connectivity graph G(X,E)whose vertices X are data points,and edges E and their weights are defined by the connectivity matrix.This establishes a connection between hierarchical clustering and graph partitioning.One of the most striking developments in hierarchical clustering is the algorithm BIRCH.It is discussed in the section Scalable VLDB Extensions.Hierarchical clustering initializes a cluster system as a set of singleton clusters(agglomerative case)or a single cluster of all points(divisive case) and proceeds iteratively merging or splitting the most appropriate cluster(s) until the stopping criterion is achieved.The appropriateness of a cluster(s) for merging or splitting depends on the(dis)similarity of cluster(s)elements. This reflects a general presumption that clusters consist of similar points.An important example of dissimilarity between two points is the distance between them.To merge or split subsets of points rather than individual points,the dis-tance between individual points has to be generalized to the distance between subsets.Such a derived proximity measure is called a linkage metric.The type of a linkage metric significantly affects hierarchical algorithms,because it re-flects a particular concept of closeness and connectivity.Major inter-cluster linkage metrics[171],[177]include single link,average link,and complete link. The underlying dissimilarity measure(usually,distance)is computed for every pair of nodes with one node in thefirst set and another node in the second set.A specific operation such as minimum(single link),average(average link),or maximum(complete link)is applied to pair-wise dissimilarity measures:d(C1,C2)=Op{d(x,y),x∈C1,y∈C2}Early examples include the algorithm SLINK[199],which implements single link(Op=min),Voorhees’method[215],which implements average link (Op=Avr),and the algorithm CLINK[55],which implements complete link (Op=max).It is related to the problem offinding the Euclidean minimal spanning tree[224]and has O(N2)complexity.The methods using inter-cluster distances defined in terms of pairs of nodes(one in each respective cluster)are called graph methods.They do not use any cluster representation other than a set of points.This name naturally relates to the connectivity graph G(X,E)introduced above,because every data partition corresponds to a graph partition.Such methods can be augmented by so-called geometric methods in which a cluster is represented by its central point.Under the assumption of numerical attributes,the center point is defined as a centroid or an average of two cluster centroids subject to agglomeration.It results in centroid,median,and minimum variance linkage metrics.All of the above linkage metrics can be derived from the Lance-Williams updating formula[145],d(C iC j,C k)=a(i)d(C i,C k)+a(j)d(C j,C k)+b·d(C i,C j)+c|d(C i,C k)−d(C j,C k)|.8Pavel BerkhinHere a,b,c are coefficients corresponding to a particular linkage.This formula expresses a linkage metric between a union of the two clusters and the third cluster in terms of underlying nodes.The Lance-Williams formula is crucial to making the dis(similarity)computations feasible.Surveys of linkage metrics can be found in [170][54].When distance is used as a base measure,linkage metrics capture inter-cluster proximity.However,a similarity-based view that results in intra-cluster connectivity considerations is also used,for example,in the original average link agglomeration (Group-Average Method)[116].Under reasonable assumptions,such as reducibility condition (graph meth-ods satisfy this condition),linkage metrics methods suffer from O N 2 time complexity [177].Despite the unfavorable time complexity,these algorithms are widely used.As an example,the algorithm AGNES (AGlomerative NESt-ing)[131]is used in S-Plus.When the connectivity N ×N matrix is sparsified,graph methods directly dealing with the connectivity graph G can be used.In particular,hierarchical divisive MST (Minimum Spanning Tree)algorithm is based on graph parti-tioning [116].2.1Hierarchical Clusters of Arbitrary ShapesFor spatial data,linkage metrics based on Euclidean distance naturally gener-ate clusters of convex shapes.Meanwhile,visual inspection of spatial images frequently discovers clusters with curvy appearance.Guha et al.[99]introduced the hierarchical agglomerative clustering algo-rithm CURE (Clustering Using REpresentatives).This algorithm has a num-ber of novel features of general importance.It takes special steps to handle outliers and to provide labeling in assignment stage.It also uses two techniques to achieve scalability:data sampling (section 8),and data partitioning.CURE creates p partitions,so that fine granularity clusters are constructed in parti-tions first.A major feature of CURE is that it represents a cluster by a fixed number,c ,of points scattered around it.The distance between two clusters used in the agglomerative process is the minimum of distances between two scattered representatives.Therefore,CURE takes a middle approach between the graph (all-points)methods and the geometric (one centroid)methods.Single and average link closeness are replaced by representatives’aggregate closeness.Selecting representatives scattered around a cluster makes it pos-sible to cover non-spherical shapes.As before,agglomeration continues until the requested number k of clusters is achieved.CURE employs one additional trick:originally selected scattered points are shrunk to the geometric centroid of the cluster by a user-specified factor α.Shrinkage suppresses the affect of outliers;outliers happen to be located further from the cluster centroid than the other scattered representatives.CURE is capable of finding clusters of different shapes and sizes,and it is insensitive to outliers.Because CURE uses sampling,estimation of its complexity is not straightforward.For low-dimensional data authors provide a complexity estimate of O (N 2sample )definedA Survey of Clustering Data Mining Techniques9 in terms of a sample size.More exact bounds depend on input parameters: shrink factorα,number of representative points c,number of partitions p,and a sample size.Figure1(a)illustrates agglomeration in CURE.Three clusters, each with three representatives,are shown before and after the merge and shrinkage.Two closest representatives are connected.While the algorithm CURE works with numerical attributes(particularly low dimensional spatial data),the algorithm ROCK developed by the same researchers[100]targets hierarchical agglomerative clustering for categorical attributes.It is reviewed in the section Co-Occurrence of Categorical Data.The hierarchical agglomerative algorithm CHAMELEON[127]uses the connectivity graph G corresponding to the K-nearest neighbor model spar-sification of the connectivity matrix:the edges of K most similar points to any given point are preserved,the rest are pruned.CHAMELEON has two stages.In thefirst stage small tight clusters are built to ignite the second stage.This involves a graph partitioning[129].In the second stage agglomer-ative process is performed.It utilizes measures of relative inter-connectivity RI(C i,C j)and relative closeness RC(C i,C j);both are locally normalized by internal interconnectivity and closeness of clusters C i and C j.In this sense the modeling is dynamic:it depends on data locally.Normalization involves certain non-obvious graph operations[129].CHAMELEON relies heavily on graph partitioning implemented in the library HMETIS(see the section6). Agglomerative process depends on user provided thresholds.A decision to merge is made based on the combinationRI(C i,C j)·RC(C i,C j)αof local measures.The algorithm does not depend on assumptions about the data model.It has been proven tofind clusters of different shapes,densities, and sizes in2D(two-dimensional)space.It has a complexity of O(Nm+ Nlog(N)+m2log(m),where m is the number of sub-clusters built during the first initialization phase.Figure1(b)(analogous to the one in[127])clarifies the difference with CURE.It presents a choice of four clusters(a)-(d)for a merge.While CURE would merge clusters(a)and(b),CHAMELEON makes intuitively better choice of merging(c)and(d).2.2Binary Divisive PartitioningIn linguistics,information retrieval,and document clustering applications bi-nary taxonomies are very useful.Linear algebra methods,based on singular value decomposition(SVD)are used for this purpose in collaborativefilter-ing and information retrieval[26].Application of SVD to hierarchical divisive clustering of document collections resulted in the PDDP(Principal Direction Divisive Partitioning)algorithm[31].In our notations,object x is a docu-ment,l th attribute corresponds to a word(index term),and a matrix X entry x il is a measure(e.g.TF-IDF)of l-term frequency in a document x.PDDP constructs SVD decomposition of the matrix10Pavel Berkhin(a)Algorithm CURE (b)Algorithm CHAMELEONFig.1.Agglomeration in Clusters of Arbitrary Shapes(X −e ¯x ),¯x =1Ni =1:N x i ,e =(1,...,1)T .This algorithm bisects data in Euclidean space by a hyperplane that passes through data centroid orthogonal to the eigenvector with the largest singular value.A k -way split is also possible if the k largest singular values are consid-ered.Bisecting is a good way to categorize documents and it yields a binary tree.When k -means (2-means)is used for bisecting,the dividing hyperplane is orthogonal to the line connecting the two centroids.The comparative study of SVD vs.k -means approaches [191]can be used for further references.Hier-archical divisive bisecting k -means was proven [206]to be preferable to PDDP for document clustering.While PDDP or 2-means are concerned with how to split a cluster,the problem of which cluster to split is also important.Simple strategies are:(1)split each node at a given level,(2)split the cluster with highest cardinality,and,(3)split the cluster with the largest intra-cluster variance.All three strategies have problems.For a more detailed analysis of this subject and better strategies,see [192].2.3Other DevelopmentsOne of early agglomerative clustering algorithms,Ward’s method [222],is based not on linkage metric,but on an objective function used in k -means.The merger decision is viewed in terms of its effect on the objective function.The popular hierarchical clustering algorithm for categorical data COB-WEB [77]has two very important qualities.First,it utilizes incremental learn-ing.Instead of following divisive or agglomerative approaches,it dynamically builds a dendrogram by processing one data point at a time.Second,COB-WEB is an example of conceptual or model-based learning.This means that each cluster is considered as a model that can be described intrinsically,rather than as a collection of points assigned to it.COBWEB’s dendrogram is calleda classification tree.Each tree node(cluster)C is associated with the condi-tional probabilities for categorical attribute-values pairs,P r(x l=νlp|C),l=1:d,p=1:|A l|.This easily can be recognized as a C-specific Na¨ıve Bayes classifier.During the classification tree construction,every new point is descended along the tree and the tree is potentially updated(by an insert/split/merge/create op-eration).Decisions are based on the category utility[49]CU{C1,...,C k}=1j=1:kCU(C j)CU(C j)=l,p(P r(x l=νlp|C j)2−(P r(x l=νlp)2.Category utility is similar to the GINI index.It rewards clusters C j for in-creases in predictability of the categorical attribute valuesνlp.Being incre-mental,COBWEB is fast with a complexity of O(tN),though it depends non-linearly on tree characteristics packed into a constant t.There is a similar incremental hierarchical algorithm for all numerical attributes called CLAS-SIT[88].CLASSIT associates normal distributions with cluster nodes.Both algorithms can result in highly unbalanced trees.Chiu et al.[47]proposed another conceptual or model-based approach to hierarchical clustering.This development contains several different use-ful features,such as the extension of scalability preprocessing to categori-cal attributes,outliers handling,and a two-step strategy for monitoring the number of clusters including BIC(defined below).A model associated with a cluster covers both numerical and categorical attributes and constitutes a blend of Gaussian and multinomial models.Denote corresponding multivari-ate parameters byθ.With every cluster C we associate a logarithm of its (classification)likelihoodl C=x i∈Clog(p(x i|θ))The algorithm uses maximum likelihood estimates for parameterθ.The dis-tance between two clusters is defined(instead of linkage metric)as a decrease in log-likelihoodd(C1,C2)=l C1+l C2−l C1∪C2caused by merging of the two clusters under consideration.The agglomerative process continues until the stopping criterion is satisfied.As such,determina-tion of the best k is automatic.This algorithm has the commercial implemen-tation(in SPSS Clementine).The complexity of the algorithm is linear in N for the summarization phase.Traditional hierarchical clustering does not change points membership in once assigned clusters due to its greedy approach:after a merge or a split is selected it is not refined.Though COBWEB does reconsider its decisions,its。

/ Business & Society/content/38/3/268The online version of this article can be found at: DOI: 10.1177/000765039903800303 1999 38: 268Business Society Archie B. Carroll Corporate Social Responsibility : Evolution of a Definitional Construct Published by: On behalf of:International Association for Business and Society can be found at:Business & Society Additional services and information for/cgi/alerts Email Alerts:/subscriptions Subscriptions:/journalsReprints.nav Reprints:/journalsPermissions.nav Permissions: /content/38/3/268.refs.html Citations:1999Corporate Social ResponsibilityEvolution of a Definitional ConstructARCHIE B.CARROLLUniversity of GeorgiaThere is an impressive history associated with the evolution of the concept and definition of corporate social responsibility (CSR).In this article,the author traces the evolution of the CSR construct beginning in the 1950s,which marks the mod-ern era of CSR.Definitions expanded during the 1960s and proliferated during the 1970s.In the 1980s,there were fewer new definitions,more empirical research,and alternative themes began to mature.These alternative themes included corpo-rate social performance (CSP),stakeholder theory,and business ethics theory.In the 1990s,CSR continues to serve as a core construct but yields to or is trans-formed into alternative thematic frameworks.The concept of corporate social responsibility (CSR)has a long and varied history.It is possible to trace evidences of the business community’s concern for society for centuries.Formal writing on social responsi-bility,however,is largely a product of the 20th century,especially the past 50years.Furthermore,although it is possible to see footprints of CSR thought throughout the world (mostly in developed countries),formal writings have been most evident in the United States,where a sizable body of literature has accumulated.With this in mind,my review of CSR’s defi-nitional evolution will focus on this body of literature.At the same time,however,it must be acknowledged that related notions may have devel-oped both in theory and practice in other countries and at different times.A significant challenge is to decide how far back into the literature to delve to begin discussing the concept of CSR.A good case could be made for about 50years because so much has occurred since that time that has shaped our theory,research,and ing this as a general guideline for this article,I note that references to a concern for social responsibility268BUSINESS &SOCIETY ,V ol.38No.3,September 1999268-295©1999Sage Publications,Inc.Carroll/CORPORATE SOCIAL RESPONSIBILITY269 appeared earlier than this,and especially during the1930s and1940s.Ref-erences from this period worth noting include Chester Barnard’s(1938) The Functions of the Executive,J.M.Clark’s(1939)Social Control of Business,and Theodore Kreps’(1940)Measurement of the Social Perfor-mance of Business.From a more practical vantage point,it should be noted that as far back as1946business executives(the literature called them“businessmen”in those days)were polled by Fortune magazine ask-ing them about their social responsibilities(Fortune,1946,cited in Bowen,1953,p.44).For purposes of this definitional review,however,it makes sense to center our attention on more recent concepts of CSR.Therefore,I start with the literature of the1950s and1960s and then move on toward the 1970s and more recently,when the topic became widely discussed among academics and business practitioners.In this discussion,I organize my review of literature on a historical basis and treat the concept on the basis of decade-by-decade categories.The goal is to trace the evolution of CSR as a concept,or definitional construct,and come to appreciate what it has meant in the past and still means today.Such a quest is essential to provide a solid foundation for further research on the topic.Space does not permit an exhaustive review,so my goal is to identify the major contributors to the evolution of the CSR definition,rather than to review all that has been said by anyone on the subject.THE MODERN ERA OF SOCIALRESPONSIBILITY BEGINS:THE1950SIn the early writings on CSR,it was referred to more often as social responsibility(SR)than as CSR.Perhaps this was because the age of the modern corporation’s prominence and dominance in the business sector had not yet occurred or been noted.The publication by Howard R.Bowen (1953)of his landmark book Social Responsibilities of the Businessman is argued to mark the beginnings of the modern period of literature on this subject.As the title of Bowen’s book suggests,there apparently were no businesswomen during this period,or at least they were not acknowledged in formal writings.Bowen’s(1953)work proceeded from the belief that the several hun-dred largest businesses were vital centers of power and decision making and that the actions of these firms touched the lives of citizens at many points.Among the many questions raised by Bowen,one is of special note270BUSINESS&SOCIETY/September1999here.He queried,“What responsibilities to society may businessmen rea-sonably be expected to assume?”(p.xi).Bowen(1953)set forth an initial definition of the social responsibili-ties of businessmen:“It refers to the obligations of businessmen to pursue those policies,to make those decisions,or to follow those lines of action which are desirable in terms of the objectives and values of our society”(p.6).Bowen quoted Fortune magazine’s survey(1946,as cited in Bowen, 1953,p.44),wherein the magazine’s editors thought that CSR,or the “social consciousness,”of managers meant that businessmen were responsible for the consequences of their actions in a sphere somewhat wider than that covered by their profit-and-loss statements(cited in Bowen,1953,p.44).It is fascinating to note that93.5%of the business-men responding agreed with the statement.Because Bowen’s(1953)book was specifically concerned with the doc-trine of social responsibility,it is easy to see how it marks the modern,seri-ous discussion of the topic.Bowen argued that social responsibility is no panacea,but that it contains an important truth that must guide business in the future.Because of his early and seminal work,I would submit that How-ard Bowen should be called the“Father of Corporate Social Responsibility.”Bowen’s(1953)book and definition represented the most notable lit-erature from the1950s.For further evidence of the extent to which busi-nesspeople were adopting and practicing CSR during this time and earlier, I cite Morrell Heald’s(1970)The Social Responsibilities of Business: Company and Community,1900-1960.Although Heald did not succinctly state definitions of social responsibility,he provided an interesting and provocative discussion of the theory and practice of CSR during the first half of the twentieth century.It is clear from Heald’s(1970)discussions that CSR is defined consis-tently with the Bowen(1953)definition.Other important literature from the1950s includes Selekman’s(1959)Moral Philosophy for Manage-ment;Heald’s(1957)Management’s Responsibility to Society:The Growth of an Idea;and Eells’(1956)Corporate Giving in a Free Society. CSR LITERATURE EXPANDS:THE1960SIf there was scant evidence of CSR definitions in the literature in the 1950s and before,the decade of the1960s marked a significant growth in attempts to formalize or,more accurately,state what CSR means.One of the first and most prominent writers in that period to define CSR was Keith Davis,who later wrote extensively about the topic in his business andCarroll/CORPORATE SOCIAL RESPONSIBILITY271 society textbook,later revisions,and articles.Davis set forth his definition of social responsibility in an article by arguing that it refers to“business-men’s decisions and actions taken for reasons at least partially beyond the firm’s direct economic or technical interest”(Davis,1960,p.70).Davis(1960)argued that social responsibility is a nebulous idea but should be seen in a managerial context.Furthermore,he asserted that some socially responsible business decisions can be justified by a long, complicated process of reasoning as having a good chance of bringing long-run economic gain to the firm,thus paying it back for its socially responsible outlook(p.70).This is rather interesting inasmuch as this view became commonly accepted in the late1970s and1980s.Davis became well known for his views on the relation between social responsi-bility and business power.He set forth his now-famous“Iron Law of Responsibility,”which held that“social responsibilities of businessmen need to be commensurate with their social power”(p.71).He further took the position that if social responsibility and power were to be relatively equal,“then the avoidance of social responsibility leads to gradual erosion of social power”(p.73)on the part of businesses.Davis’s contributions to early definitions of CSR were so significant that I would consider him to be the runner-up to Bowen for the Father of CSR designation.William C.Frederick was also an influential contributor to the early definitions of social responsibility as he wrote,[Social responsibilities]mean that businessmen should oversee the opera-tion of an economic system that fulfills the expectations of the public.And this means in turn that the economy’s means of production should be em-ployed in such a way that production and distribution should enhance total socio-economic welfare.Social responsibility in the final analysis implies a public posture to-ward society’s economic and human resources and a willingness to see that those resources are used for broad social ends and not simply for the nar-rowly circumscribed interests of private persons and firms.(Frederick, 1960,p.60)Another major contributor to the definition of social responsibility dur-ing the1960s was Joseph W.McGuire.In his book Business and Society (1963),he stated,“The idea of social responsibilities supposes that the corporation has not only economic and legal obligations but also certain responsibilities to society which extend beyond these obligations”(p.144).McGuire’s(1963)definition is somewhat more precise than previous ones in that he defined it as extending beyond economic and legal obliga-tions.Although he did not clarify what,exactly,these obligations were in272BUSINESS&SOCIETY/September1999his definition,he later elaborated by saying that the corporation must take an interest in politics,in the welfare of the community,in education,in the “happiness”of its employees,and,in fact,in the whole social world about it.Therefore,business must act“justly,”as a proper citizen should(p.144). This latter statement hints at the notions of business ethics and corporate citizenship.In the first edition of their Business and its Environment textbook, Keith Davis and Robert Blomstrom(1966)defined social responsibility: Social responsibility,therefore,refers to a person’s obligation to consider the effects of his decisions and actions on the whole social system.Busi-nessmen apply social responsibility when they consider the needs and inter-est of others who may be affected by business actions.In so doing,they look beyond their firm’s narrow economic and technical interests.(p.12)It is interesting to note that the phrase“businessmen”was still being used even in the mid-1960s.Keith Davis revisited the concept of CSR in1967,when he sought to understand the social responsibility puzzle.In an article addressing the question of what businessmen owed society,he added to his earlier defini-tion.He asserted,“The substance of social responsibility arises from con-cern for the ethical consequences of one’s acts as they might affect the interests of others”(Davis,1967,p.46).He suggests how social responsi-bility gets one beyond the limited application of person-to-person con-tacts:“Social responsibility moves one large step further by emphasizing institutional actions and their effect on the whole social system.Social responsibility,therefore,broadens a person’s view to the total social sys-tem”(p.46).In a book titled Corporate Social Responsibilities,Clarence C.Walton (1967),a foremost thinker on this subject,addressed many facets of CSR in a book series concerned with the role of the business firm and the busi-nessperson in modern society.In this significant book,he presented a number of different varieties,or models,of social responsibility,includ-ing his fundamental definition of social responsibility:In short,the new concept of social responsibility recognizes the intimacy of the relationships between the corporation and society and realizes that such relationships must be kept in mind by top managers as the corporation and the related groups pursue their respective goals.(Walton,1967,p.18) Walton elaborated to emphasize that the essential ingredient of the corpo-ration’s social responsibilities include a degree of voluntarism,as opposedCarroll/CORPORATE SOCIAL RESPONSIBILITY273 to coercion,an indirect linkage of certain other voluntary organizations to the corporation,and the acceptance that costs are involved for which it may not be possible to gauge any direct measurable economic returns(p.18).DEFINITIONS OF CSRPROLIFERATE:THE1970SThe1970s were ushered in with an interesting book written by Morrell Heald.The book was titled The Social Responsibilities of Business:Com-pany and Community,1900-1960(Heald,1970).Although Heald did not provide a succinct definition of the social responsibility construct,it is clear that his understanding of the term was in the same vein as the defini-tions presented during the1960s and earlier.In the preface to his book,he asserted that he was concerned with the idea of social responsibility“as businessmen themselves have defined and experienced it”(p.xi).He added that the“meaning of the concept of social responsibility for busi-nessmen must finally be sought in the actual policies with which they were associated”(p.xi).He then described,in a historical fashion, community-oriented programs,policies,and views of business execu-tives.His descriptions suggest that business people during that period were significantly preoccupied with corporate philanthropy and commu-nity relations.In Harold Johnson’s(1971)Business in Contemporary Society: Framework and Issues,the author presented a variety of definitions or views of CSR and then proceeded to critique and analyze them.Johnson first presented what he termed“conventional wisdom,”which he defined as the following:“A socially responsible firm is one whose managerial staff balances a multiplicity of interests.Instead of striving only for larger profits for its stockholders,a responsible enterprise also takes into account employees,suppliers,dealers,local communities,and the nation”(p.50). It is worth noting that Johnson is hinting at the possibility of a stakeholder approach as he references a“multiplicity of interests”and actually names several of these specific interests(groups).Johnson(1971)then said,In this approach,social responsibility in business is the pursuit of socioeco-nomic goals through the elaboration of social norms in prescribed business roles;or,to put it more simply,business takes place within a socio-cultural system that outlines through norms and business roles particular ways of re-sponding to particular situations and sets out in some detail the prescribed ways of conducting business affairs.(p.51)274BUSINESS&SOCIETY/September1999Johnson(1971)presented a second view of CSR:“Social responsibility states that businesses carry out social programs to add profits to their organization”(p.54).In this view,social responsibility is perceived as long-run profit maximization.Johnson(1971)presented a third view of social responsibility,which he calls“utility maximization.”In this view,he asserted,“The third approach of social responsibility assumes that the prime motivation of the business firm is utility maximization;the enterprise seeks multiple goals rather than only maximum profits”(p.59).He then postulated the follow-ing definition:A socially responsible entrepreneur or manager is one who has a utilityfunction of the second type,such that he is interested not only in his own well-being but also in that of the other members of the enterprise and that of his fellow citizens.(p.68)Finally,Johnson(1971)explained a fourth view,which he called the “lexicographic view of social responsibility.”In this definition, The goals of the enterprise,like those of the consumer,are ranked in order of importance and that targets are assessed for each goal.These target levels are shaped by a variety of factors,but the most important are the firm’s past experience with these goals and the past performance of similar business enterprises;individuals and organizations generally want to do at least as well as others in similar circumstances.(p.73)Johnson said that“lexicographic utility theory suggests that strongly profit-motivated firms may engage in socially responsible behavior.Once they attain their profit targets,they act as if social responsibility were an important goal—even though it isn’t”(p.75).Johnson concluded about the four definitions that although they may appear contradictory at times, they are essentially complementary ways of viewing the same reality(p.77).A landmark contribution to the concept of CSR came from the Com-mittee for Economic Development(CED)in its1971publication Social Responsibilities of Business Corporations.The CED got into this topic by observing that“business functions by public consent and its basic purpose is to serve constructively the needs of society—to the satisfaction of soci-ety”(p.11).The CED noted that the social contract between business and society was changing in substantial and important ways:Business is being asked to assume broader responsibilities to society than ever before and to serve a wider range of human values.Business enter-prises,in effect,are being asked to contribute more to the quality of Ameri-Carroll/CORPORATE SOCIAL RESPONSIBILITY275 can life than just supplying quantities of goods and services.Inasmuch as business exists to serve society,its future will depend on the quality of man-agement’s response to the changing expectations of the public.(p.16)In response to a public opinion survey conducted by Opinion Research Corporation in1970in which two thirds of the respondents believed busi-ness had a moral obligation to help other major institutions to achieve social progress,even at the expense of profitability,the CED articulated a three concentric circles definition of social responsibility: The inner circle includes the clear-cut basic responsibilities for the efficient execution of the economic function—products,jobs and economic growth.The intermediate circle encompasses responsibility to exercise this eco-nomic function with a sensitive awareness of changing social values and priorities:for example,with respect to environmental conservation;hiring and relations with employees;and more rigorous expectations of customers for information,fair treatment,and protection from injury.The outer circle outlines newly emerging and still amorphous responsi-bilities that business should assume to become more broadly involved in ac-tively improving the social environment.(For example,poverty and urban blight).(p.15)What is particularly noteworthy about the CED’s construction of CSR is that the CED is composed of business people and educators and thus reflects an important practitioner view of the changing social contract between business and society and businesses’newly emerging social responsibilities.It is useful to note that the CED may have been respond-ing to the times in that the late1960s and early1970s was a period during which social movements with respect to the environment,worker safety, consumers,and employees were poised to transition from special interest status to government regulation.Another significant writer on CSR in the1970s was George Steiner.In the first edition of his textbook Business and Society(1971),Steiner wrote extensively on the subject.Steiner tended to defer to Davis’s and Freder-ick’s definitions of CSR,but he did state his views on the subject: Business is and must remain fundamentally an economic institution, but...it does have responsibilities to help society achieve its basic goals and does,therefore,have social responsibilities.The larger a company be-comes,the greater are these responsibilities,but all companies can assume some share of them at no cost and often at a short-run as well as a long-run profit.The assumption of social responsibilities is more of an attitude,of the way a manager approaches his decision-making task,than a great shift in276BUSINESS&SOCIETY/September1999the economics of decision making.It is a philosophy that looks at the social interest and the enlightened self-interest of business over the long run as compared with the old,narrow,unrestrained short-run self-interest.(Steiner, 1971,p.164)Although Steiner(1971)did not dwell on definitions,he extended the meaning and circumstances under which CSR might be interpreted and applied.For example,he discussed specific spheres in which CSR might be applied,and he presented models for determining the social responsi-bilities of business(p.157).He also presented criteria for determining the social responsibilities of business(pp.159-163).A major debate over the meaning of CSR took place in1972.This debate,sponsored by the American Enterprise Institute,involved eco-nomics professors Henry G.Manne and Henry C.Wallich.The debate was summarized in their volume The Modern Corporation and Social Responsibility(Manne&Wallich,1972).In the debates,Manne set forth his definition of CSR by arguing that any working definition requires three elements:To qualify as socially responsible corporate action,a business expenditure or activity must be one for which the marginal returns to the corporation are less than the returns available from some alternative expenditure,must be purely voluntary,and must be an actual corporate expenditure rather than a conduit for individual largesse.(pp.4-6)Manne added that even with such a definition in mind,“in practice it is often extremely difficult if not impossible to distinguish a purely business expenditure only alleged to have been made for the public’s good from one actually made with real charitable intent”(p.8).With this latter quote,he emphasized a point that more contemporary writers have noted,that busi-ness expenditures may have multiple rather than single motives and, therefore,this is not a fruitful criterion for judging social responsibility. His element of volunteerism has been carried forward into many modern definitions of CSR,but this,too,is difficult to judge.It is impossible to distinguish between that which is“purely voluntary”and that which is in response to social norms.Professor Wallich(Manne&Wallich,1972)defined CSR in broad terms:I take responsibility to mean a condition in which the corporation is at leastin some measure a free agent.To the extent that any of the foregoing social objectives are imposed on the corporation by law,the corporation exercises no responsibility when it implements them.(p.40)Carroll/CORPORATE SOCIAL RESPONSIBILITY277 He wrote that the exercise of CSR involves three basic elements.“Three basic activities seem to be involved in the exercise of corporate responsi-bility:(1)the setting of objectives,(2)the decision whether to pursue given objectives,and(3)the financing of these objectives”(p.41).Wallich identified circumstances in which CSR might be defensible,but he favored stockholder instructions to the corporation...to make corpora-tions properly responsible to stockholder interest(pp.56-62).In1973,Keith Davis again entered the discussion in his landmark arti-cle surveying the case for and against business assumption of social responsibilities(Davis,1973).In the introduction to the article,he quoted two well-known economists and their diverse views on the subject.First, he quoted Milton Friedman,whose famous objection is familiar to most. Friedman(1962)contended that“few trends could so thoroughly under-mine the very foundations of our free society as the acceptance by corpo-rate officials of a social responsibility other than to make as much money for their stockholders as possible”(p.133).However,Davis(1973)coun-tered this view with a quote by Paul Samuelson,another distinguished economist,who argued that“a large corporation these days not only may engage in social responsibility,it had damn well better try to do so”(Samuelson,1971,p.24).Beyond these observations,Davis(1973) defined CSR:For purposes of this discussion it[CSR]refers to the firm’s consideration of,and response to,issues beyond the narrow economic,technical,and le-gal requirements of the firm.(p.312)It is the firm’s obligation to evaluate in its decision-making process the effects of its decisions on the external social system in a manner that will ac-complish social benefits along with the traditional economic gains which the firm seeks.(p.313)It means that social responsibility begins where the law ends.A firm is not being socially responsible if it merely complies with the minimum require-ments of the law,because this is what any good citizen would do.(p.313) Davis(1973)then presented and discussed the arguments to date both for and against business being socially responsible(pp.313-321).It is appar-ent that Davis employed a restricted definition of CSR,because in his lat-ter statement he seemed to be excluding legal obedience,as a part of cor-porate citizenship,from social responsibility.Two other writers on CSR during this period were Henry Eilbert and I.Robert Parket(1973),who discussed the“current status of corporate social responsibility.”Eilbert and Parket were less interested in providing a rigorous definition of CSR than gathering data from the business278BUSINESS&SOCIETY/September1999community on the extent to which CSR has moved from the level of verbal discussions to its implementation in practice.For purposes of their research,the authors defined CSR:Perhaps the best way to understand social responsibility is to think of it as ‘good neighborliness.’The concept involves two phases.On one hand,it means not doing things that spoil the neighborhood.On the other,it may be expressed as the voluntary assumption of the obligation to help solve neigh-borhood problems.Those who find neighborliness an awkward or coy concept may substi-tute the idea that social responsibility means the commitment of a business or Business,in general,to an active role in the solution of broad social prob-lems,such as racial discrimination,pollution,transportation,or urban de-cay.(Eilbert&Parket,1973,p.7)Their research reported survey results of the extent to which CSR had affected organizational structure and budget,the type of CSR activities in which firms engaged,the activities believed to be most important,and other organizational issues.These are mentioned here because they repre-sent one of the early attempts to associate CSR with organizational vari-ables and to suggest that CSR is composed of a variety of different activities.Although Richard Eells and Clarence Walton addressed the CSR con-cept in the1961first edition of their volume Conceptual Foundations of Business,they elaborated on the concept at length in their third edition (Eells&Walton,1974).Their favorite topics were business history,the concept of the corporation,ownership,and governance.However,they dedicated a chapter to“recent trends”in corporate social responsibilities. Like Steiner(1971),they did not focus on definitions per se but rather took a broader perspective on what CSR means and how it evolved.They observed,In its broadest sense,corporate social responsibility represents a concern with the needs and goals of society which goes beyond the merely eco-nomic.Insofar as the business system as it exists today can only survive in an effectively functioning free society,the corporate social responsibility movement represents a broad concern with business’s role in supporting and improving that social order.(Eells&Walton,1974,p.247)Eells and Walton(1974)provided an extensive discussion of the CSR movement and the various ways in which academics and practitioners were coming to regard the topic at that time.。

War to Resist U.S. Aggression and Aid Korea (1950-1953).In the early years of the People’s Republic of China (PRC), founded in 1949, China faceddomestic turmoil and foreign aggression. After a civil war broke out on the Korean Peninsula in June 1950, the U.S.-led “UN forces” made repeated provocations on the borderbetween China and Korea, and civilians were bombed. From October 1950, the ChinesePeople’s Volunteers (CPV) army fought alongside the army of the Democratic People’sRepublic of Korea to bring about long-term peace and stability. On the battlefield, eventhough there was a great disparity in military strength, the CPV army achieved victorythrough heroic sacrifices. On the diplomatic stage, the delegation of the PRC made itsdebut at the United Nations, garnering international respect with the new voices of China.The film uses dynamic montages to combine events in different timelines and spaces tocreate a compelling artistic effect. It depicts the origin of the war and the intensity of fighting in various battles across mountains, villages, rivers, and snow fields, but also weavesit with the picture of Chinese representative Wu Xiuquan’s speech at the meeting of theUnited Nations Security Council, presenting a profoundly insightful exploration and understanding of the relationship between national dignity and individual lives.Moscow MissionGenres: Drama, Crime, ActionDirector: Herman Yau Lai-ToLength: 128 MinutesThe film is based on the real-life events of the China-Russia train robbery in 1993. Inthe early 1990s, after the collapse of the former Soviet Union, the Russian economy wason the brink of collapse and the supply of goods was extremely strained. A large numberof Chinese merchants took the K3 international train from Beijing to Moscow, transportingChinese goods such as clothing, food, and cosmetics to earn high profits. On this train, awell-trained gang carried out a series of incidents of looting and violence, causing a stiraround the world. After the incident, the Chinese police promptly engaged in a cross-borderdetection. Through their investigation, the police tracked down a mysterious person with thepseudonym Vasily and a woman named Zhenzhen — gradually uncovering another largerconspiracy in the case.8080CHINA TODAY。