Over the forty-year history of interactive computer graphics, there have been continuous advances, but at some stage this progression must terminate with images being sufficiently realistic for all practical purposes. How much detail do we really need? Polygon counts over a few million imply that on average each polygon paints less than a single pixel, making use of polygon shading hardware wasteful. We consider the problem of determining how much realism is required for a variety of applications. We discuss how current trends in computer graphics hardware, and in particular of graphics cards targeted at the computer games industry, will help or hinder achievement of these requirements. With images now being so convincingly realistic in many cases, critical faculties are often suspended and the images are accepted as correct and truthful although they may well be incorrect and sometimes misleading or untruthful. Display resolution has remained largely constant in spatial terms for the last twenty years and in terms of the number of pixels has increased by less than an order of magnitude. If the long-promised breakthroughs in display technology are finally realised, how should we use the increased resolution?

Ramamritham gives three common types of constraints for the execution history of concurrent transactions. This paper extends the constraints and gives the fourth type of constraint. Then the weak commit dependency and abort dependency between transactions, because of data access conflicts, are analyzed. Based on the analysis, an optimistic commit protocol 2LC (two-Level Commit) is proposed, which is specially designed for the distributed real-time domain. It allows transactions to optimistically access the locked data in a controlled manner, which reduces the data inaccessibility and priority inversion inherent and undesirable in distributed real-time database systems. Furthermore, if the prepared transaction is aborted, the transactions in its weak commit dependency set will execute as normal according to 2LC. Extensive simulation experiments have been performed to compare the performance of 2LC with that of the base protocol, the permits reading of modified prepared-data for timeliness (PROMPT) and the deadline-driven conflict resolution (DDCR). The simulation results show that 2LC is effective in reducing the number of missed transaction deadlines. Furthermore, it is easy to be incorporated with the existing concurrency control protocols.

In this paper, a novel global routing algorithm is presented for congestion optimization based on efficient local search, named SSTT (search space traversing technology). This method manages to traverse the whole search space. A hybrid optimization strategy is adopted, consisting of three optimization sub-strategies: stochastic optimization, deterministic optimization and local enumeration optimization, to dynamically reconstruct the problem structure. Thus, "transition" can be made from a local minimum point to reach other parts of the search space, traverse the whole search space, and obtain the global (approximate) optimal routing solution. Since any arbitrary initial routing solution can be used as the start point of the search, the initialization in SSTT algorithm is greatly simplified. SSTT algorithm has been tested on both MCNC benchmark circuits and industrial circuits, and the experimental results were compared with those of typical existing algorithms. The experimental results show that SSTT algorithm can obtain the global (approximate) optimal routing solution easily and quickly. Moreover, it can meet the needs of practical applications. The SSTT global routing algorithm gives a general-purpose routing solution.

This paper discusses the classification problems of text documents. Based on the concept of the proximity degree, the set of words is partitioned into some equivalence classes. Particularly, the concepts of the semantic field and association degree are given in this paper. Based on the above concepts, this paper presents a fuzzy classification approach for document categorization. Furthermore, applying the concept of the entropy of information, the approaches to select key words from the set of words covering the classification of documents and to construct the hierarchical structure of key words are obtained.

Mining frequent itemsets from large databases has played an essential role in many data mining tasks. It is also important to maintain the discovered frequent itemsets for these data mining tasks when the database is updated. All algorithms proposed so far for the maintenance of discovered frequent itemsets are only performed with a fixed minimum support, which is the same as that used to obtain the discovered frequent itemsets. That is, users cannot change the minimum support even if the new results are unsatisfactory to the users. In this paper two new complementary algorithms, FMP (First Maintaining Process) and RMP (Repeated Maintaining Process), are proposed to maintain discovered frequent itemsets in the case that new transaction data are added to a transaction database. Both algorithms allow users to change the minimum support for the maintenance processes. FMP is used for the first maintaining process, and when the result derived from the FMP is unsatisfactory, RMP will be performed repeatedly until satisfactory results are obtained. The proposed algorithms re-use the previous results to cut down the cost of maintenance. Extensive experiments have been conducted to assess the performance of the algorithms. The experimental results show that the proposed algorithms are very resultful compared with the previous mining and maintenance algorithms for maintenance of discovered frequent itemsets.

Multiresolution-based magnetic resonance (MR) image segmentation has attracted attention for its ability to capture rich information across scales compared with the conventional segmentation methods. In this paper, a new scale-space-based segmentation model is presented, where both the intra-scale and inter-scale properties are considered and formulated as two fuzzy energy functions. Meanwhile, a control parameter is introduced to adjust the contribution of the similarity character across scales and the clustering character within the scale. By minimizing the combined inter/intra energy function, the multiresolution fuzzy segmentation algorithm is derived. Then the coarse to fine leading segmentation is performed automatically and iteratively on a set of multiresolution images. The validity of the proposed algorithm is demonstrated by the test image and pathological MR images. Experiments show that by this approach the segmentation results, especially in the tumor area delineation, are more precise than those of the conventional fuzzy segmentation methods.

The majority of researches on content-based retrieval focused on visual media. However audio is also an important medium and information carrier from the viewpoint of human auditory perception, so it is needed to retrieve for audio collection. Audio is handled by conventional methods as an opaque stream medium, which is not suitable for information retrieval by its content. In fact, audio carries rich aural information with the form of speech, musical, and sound effects, so it could be retrieved based on its aural content, such as acoustic features, musical melodies and associated semantics. In this paper, a concept framework (ARF) for content-based audio retrieval is proposed from systematic perspectives, which describes audio content model, audio retrieval architecture and audio query schemes. Audio contents are represented by a hierarchical model and a set of formal descriptions from physical to acoustic to semantic level, which depict acoustic features, logical structure and semantics of audio and audio objects. The architecture consisting of audio meta-database, populating and accessing modules presents a system structure view of audio information retrieval. The query schemes give generalized approaches and modes concerning how users deliver audio information needs to audio collections. Finally, an audio retrieval example implemented is used to explain and specify the application of the components in the proposed ARF.

The study on database technologies, or more generally, the technologies of data and information management, is an important and active research field. Recently, many exciting results have been reported. In this fast growing field, Chinese researchers play more and more active roles. Research papers from Chinese scholars, both in China and abroad, appear in prestigious academic forums. In this paper, we, nine young Chinese researchers working in the United States, present concise surveys and report our recent progress on the selected fields that we are working on. Although the paper covers only a small number of topics and the selection of the topics is far from balanced, we hope that such an effort would attract more and more researchers, especially those in China, to enter the frontiers of database research and promote collaborations. For the obvious reason, the authors are listed alphabetically, while the sections are arranged in the order of the author list.

The growing interest in the application of formal methods of cryptographic protocol analysis has led to the development of a number of different ways for analyzing protocol. In this paper, it is strictly proved that if for any strand, there exists at least one bundle containing it, then an entity authentication protocol is secure in strand space model (SSM) with some small extensions. Unfortunately, the results of attack scenario demonstrate that this protocol and the Yahalom protocol and its modification are de facto insecure. By analyzing the reasons of failure of formal inference in strand space model, some deficiencies in original SSM are pointed out. In order to break through these limitations of analytic capability of SSM, the generalized strand space model (GSSM) induced by some protocol is proposed. In this model, some new classes of strands, oracle strands, high order oracle strands etc., are developed, and some notions are formalized strictly in GSSM, such as protocol attacks, valid protocol run and successful protocol run. GSSM can then be used to further analyze the entity authentication protocol. This analysis sheds light on why this protocol would be vulnerable while it illustrates that GSSM not only can prove security protocol correct, but also can be efficiently used to construct protocol attacks. It is also pointed out that using other protocol to attack some given protocol is essentially the same as the case of using the most of protocol itself.

In this paper, we present a logic system for probabilistic belief named PBL, which expands the language of belief logic by introducing probabilistic belief. Furthermore, we give the probabilistic Aumann semantics of PBL. We also list some valid properties of belief and probabilistic belief, which form the deduction system of PBL. Finally, we prove the soundness and completeness of these properties with respect to probabilistic Aumann semantics.

This paper introduces some improvements on the intelligent backtracking strategy for forward chaining theorem proving. How to decide a minimal useful consequent atom set for a refutation derived at a node in a proof tree is discussed. In most cases, an unnecessary non-Horn clause used for forward chaining will be split only once. The increase of the search space by invoking unnecessary forward chaining clauses will be nearly linear, not exponential anymore. In this paper, the principle of the proposed method and its correctness are introduced. Moreover, some examples are provided to show that the proposed approach is powerful for forward chaining theorem proving.

The construction of a GC^1 cubic interpolating curve that lies on the same side of a given straight line as the data points is studied. The main task is to choose appropriate approaches to modify tangent vectors at the data points for the desired curve. Three types of approaches for changing the magnitudes of the tangent vectors are presented. The first-type approach modifies the tangent vectors by applying a constraint to the curve segment. The second one does the work by optimization techniques. The third one is a modification of the existing method. Three criteria are presented to compare the three types of approaches with the existing method. The experiments that test the effectiveness of the approaches are included.

Broadcasting operations are of great importance in Mobile Ad Hoc Networks (MANETs) since they are frequently executed. A straightforward broadcasting by flooding will produce serious redundancy, contention and collision, and furthermore it will result in the performance degradation of the networks. PCBA, a Priority-based Competitive Broadcasting Algorithm, is proposed in this paper to solve the above problem. In this algorithm, hosts with larger Priority Index (PI) have higher probability to rebroadcast relevant messages while some other hosts will be prevented from rebroadcasting according to the competing policy. PCBA is a distributed algorithm and will not increase communication overhead. Through the analyses and extensive simulations, the authors demonstrate that PCBA has advantages in availability and scalability. It can significantly reduce the rebroadcast redundancy. In addition, PCBA can also be further used in other applications such as routing discovery schemes, enhancing the performance.

IEEE 802.11 Medium Access Control (MAC) is proposed to support asynchronous and time bounded delivery of radio packets. Distributed Coordination Function (DCF), which uses Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) and binary slotted exponential backoff, is the basis of the 802.11 MAC. This paper proposes a throughput enhancement for DCF by adjusting the Contention Window (CW) setting scheme. Moreover, an analytical model based on Markov chain is introduced to compute the enhanced throughput. The accuracy of the model and the enhancement of the proposed scheme are verified by elaborate simulations.

This paper proposes an algorithm named WLFVC, which is a fully distributed wireless packet scheduling algorithm based on LFVC (Leap Forward Virtual Clock), to provide streams with fairness, especially in the short time scale. This algorithm is able to allocate bandwidth to streams proportional to their weights. Thus, better delay and jitter performance can be achieved. Since collisions and wireless link error degrade the performance of MAC protocols in the WLAN environment, WLFVC also takes them into consideration. Finally, this algorithm works in a fully distributed way and it can coexist with other stations that only support DCF (Distributed Coordination Function).