Volume 11,Issue 2,2000 Table of Contents
2000, 11(2):143-158.
Abstract:
This paper presents linguistic cloud models for knowledge representation and uncertainty handling in KDD.Multi-dimensional cloud models are introduced as the extension of one-dimensional ones.The digital characteristics of linguistic clouds well integrate the fuzziness and randomness of linguistic terms in a unified way.Conceptual hierarchies based on the models can bridge the gap between quantitative knowledge and qualitative knowledge.In order to discover strong association rules,attribute values are generalized at higher concept levels,allowing overlapping between neighbor attribute values or linguistic terms.And this kind of soft partitioning can mimic human being's thinking,while making the discovered knowledge robust.Combining the cloud model based generalization method with Apriori algorithm for mining association rules from a spatial database shows the benefits in effectiveness,efficiency and flexibility.
This paper presents linguistic cloud models for knowledge representation and uncertainty handling in KDD.Multi-dimensional cloud models are introduced as the extension of one-dimensional ones.The digital characteristics of linguistic clouds well integrate the fuzziness and randomness of linguistic terms in a unified way.Conceptual hierarchies based on the models can bridge the gap between quantitative knowledge and qualitative knowledge.In order to discover strong association rules,attribute values are generalized at higher concept levels,allowing overlapping between neighbor attribute values or linguistic terms.And this kind of soft partitioning can mimic human being's thinking,while making the discovered knowledge robust.Combining the cloud model based generalization method with Apriori algorithm for mining association rules from a spatial database shows the benefits in effectiveness,efficiency and flexibility.
2000, 11(2):159-172.
Abstract:
All proposed parallel algorithms for mining association rules follow the conventional level-wise approach.It imposes a synchronization in every iteration in the computation which degrades greatly their performance if they are used to compute the rules on a shared-memory multi-processor parallel machine.The deficiency comes from the contention on the shared I/O channel when all processors are accessing the channel synchronously in every iteration.An asynchronous algorithm APM has been proposed for mining association rules on shared-memory multi-processor machine.All participating processors in APM generate candidates and count their supports independently without synchronization.Furthermore,it can finish the computation with fewer passes of database scanning than required in the level-wise approach.An optimization technique has been developed to enhance APM so that its performance would be insensitive to the data distribution.Two variants of APM and the synchronous algorithm Count Distribution,which is a parallel version of the popular serial mining algorithm Apriori,have been implemented on an SGI Power Challenge SMP parallel machine.The results show that the asynchronous algorithm APM performs much better,and is more scalable than the synchronous algorithm.
All proposed parallel algorithms for mining association rules follow the conventional level-wise approach.It imposes a synchronization in every iteration in the computation which degrades greatly their performance if they are used to compute the rules on a shared-memory multi-processor parallel machine.The deficiency comes from the contention on the shared I/O channel when all processors are accessing the channel synchronously in every iteration.An asynchronous algorithm APM has been proposed for mining association rules on shared-memory multi-processor machine.All participating processors in APM generate candidates and count their supports independently without synchronization.Furthermore,it can finish the computation with fewer passes of database scanning than required in the level-wise approach.An optimization technique has been developed to enhance APM so that its performance would be insensitive to the data distribution.Two variants of APM and the synchronous algorithm Count Distribution,which is a parallel version of the popular serial mining algorithm Apriori,have been implemented on an SGI Power Challenge SMP parallel machine.The results show that the asynchronous algorithm APM performs much better,and is more scalable than the synchronous algorithm.
2000, 11(2):173-178.
Abstract:
This paper summarizes Java's compiler technology,and sorts all kinds of Java compilers into five categories:compilers with interpreter technology,compilers with JIT compiler technology,compilers with adaptive optimization technology,native compilers and translators.Their architectures and working principles are described and analyzed in detail.The authors also analyze the effect that compiler technology has on Java performance.
This paper summarizes Java's compiler technology,and sorts all kinds of Java compilers into five categories:compilers with interpreter technology,compilers with JIT compiler technology,compilers with adaptive optimization technology,native compilers and translators.Their architectures and working principles are described and analyzed in detail.The authors also analyze the effect that compiler technology has on Java performance.
2000, 11(2):179-186.
Abstract:
With the increasing development of broadband technology,the speed of packets forwarding needs to be over gigabits per second for the backbone routers.Traditional routers have some insuperable barriers and can not solve the problem based on shared-bus and central processing unit.It is a great challenge for the future router architecture.In this article,the authors survey the recent advances in the research of broadband IP router,and analyze the architecture design of the fourth generation backbone router in detail.Finally,some challenging open problems are identified.
With the increasing development of broadband technology,the speed of packets forwarding needs to be over gigabits per second for the backbone routers.Traditional routers have some insuperable barriers and can not solve the problem based on shared-bus and central processing unit.It is a great challenge for the future router architecture.In this article,the authors survey the recent advances in the research of broadband IP router,and analyze the architecture design of the fourth generation backbone router in detail.Finally,some challenging open problems are identified.
2000, 11(2):187-194.
Abstract:
A precise dataflow analysis should effectively exploit the semantic information presented by conditional branch statements.Most traditional systems,however,either ignore the logical conditions,or try hard to handle logical conditions with logical reasoning which is rather difficult and infeasible for paralleling systems.With the aim to solve this problem efficiently and effectively,the authors introduce the computation function model and then successfully convert the logical reasoning problems into problems of deciding the coverage relationship of Omega regions which are substantially more feasible to be solved by contemporary paralleling compilers.
A precise dataflow analysis should effectively exploit the semantic information presented by conditional branch statements.Most traditional systems,however,either ignore the logical conditions,or try hard to handle logical conditions with logical reasoning which is rather difficult and infeasible for paralleling systems.With the aim to solve this problem efficiently and effectively,the authors introduce the computation function model and then successfully convert the logical reasoning problems into problems of deciding the coverage relationship of Omega regions which are substantially more feasible to be solved by contemporary paralleling compilers.
2000, 11(2):195-201.
Abstract:
Based on the statistical characteristics of Chinese maximal noun phrases (MNPs) in a Chinese corpus with 5 573 sentences,two efficient identifying algorithms for Chinese MNPs:(1) To identify MNPs by using boundary distribution probabilities; (2) To identify MNPs by using internal structure rules,are proposed in this paper.Experimental results show better performances:precision 85.4% and recall 82.3%,by using identifying algorithm (2).
Based on the statistical characteristics of Chinese maximal noun phrases (MNPs) in a Chinese corpus with 5 573 sentences,two efficient identifying algorithms for Chinese MNPs:(1) To identify MNPs by using boundary distribution probabilities; (2) To identify MNPs by using internal structure rules,are proposed in this paper.Experimental results show better performances:precision 85.4% and recall 82.3%,by using identifying algorithm (2).
2000, 11(2):202-206.
Abstract:
In this paper,LOKI97 is analyzed using linear cryptanalysis.The results show that LOKI97 does not meet the needs of AES (advanced encryption standard).Using algorithm 1 of linear cryptanalysis,the authors can get the 92－bit subkey with 250 known-plaintexts and the success rate is 0.977; using algorithm 2 of linear cryptanalysis,it is possible to break LOKI97 with 245 known-plaintexts and the success rate is 0.967.
In this paper,LOKI97 is analyzed using linear cryptanalysis.The results show that LOKI97 does not meet the needs of AES (advanced encryption standard).Using algorithm 1 of linear cryptanalysis,the authors can get the 92－bit subkey with 250 known-plaintexts and the success rate is 0.977; using algorithm 2 of linear cryptanalysis,it is possible to break LOKI97 with 245 known-plaintexts and the success rate is 0.967.
2000, 11(2):207-212.
Abstract:
Conformance testing of TCP/IP protocol is the first step for interoperability among Internet network products.The conformance testing of the Internet protocol with a PITS (protocol integrated test system) is presented in this paper.The authors use the distributed test method and remote traverse test method to test IP (Internet protocol) end system and IP relay system in Internet,respectively.IP test suite in TTCN (tree and table combined notation) is derived according to IP test purposes.Furthermore,the IP conformance testing has been applied for developing routers.
Conformance testing of TCP/IP protocol is the first step for interoperability among Internet network products.The conformance testing of the Internet protocol with a PITS (protocol integrated test system) is presented in this paper.The authors use the distributed test method and remote traverse test method to test IP (Internet protocol) end system and IP relay system in Internet,respectively.IP test suite in TTCN (tree and table combined notation) is derived according to IP test purposes.Furthermore,the IP conformance testing has been applied for developing routers.
2000, 11(2):213-221.
Abstract:
In this paper,a non-monotonic dynamic logic that verifies properties of security protocols is introduced.In accordance with the specific requirement of information security,it provides axioms and inference rules about various cryptographic operations such as encryption,decryption,signature,authentication and key assignment.Several instances are given to illustrate its applications in security protocol verification.Open problems for further study are also discussed.
In this paper,a non-monotonic dynamic logic that verifies properties of security protocols is introduced.In accordance with the specific requirement of information security,it provides axioms and inference rules about various cryptographic operations such as encryption,decryption,signature,authentication and key assignment.Several instances are given to illustrate its applications in security protocol verification.Open problems for further study are also discussed.
2000, 11(2):222-228.
Abstract:
A heterogeneous data integration system can integrate a broad range of data sources including WWW.Decomposition and optimization for query are very difficult because some data sources have neither regular schemata nor strong query capabilities.To help query decomposition and optimization,a dynamic dictionary is proposed as unified schemata for various heterogeneous data sources,and the way for the construction of a global dynamic dictionary by operating on dynamic dictionaries of local data sources is given.Furthermore,to simplify the design of wrappers for data sources with limited capabilities and reduce responding time for query,an approach,which can take advantage of all powers of various data sources and results of prior queries,is proposed for query decomposition and optimization.
A heterogeneous data integration system can integrate a broad range of data sources including WWW.Decomposition and optimization for query are very difficult because some data sources have neither regular schemata nor strong query capabilities.To help query decomposition and optimization,a dynamic dictionary is proposed as unified schemata for various heterogeneous data sources,and the way for the construction of a global dynamic dictionary by operating on dynamic dictionaries of local data sources is given.Furthermore,to simplify the design of wrappers for data sources with limited capabilities and reduce responding time for query,an approach,which can take advantage of all powers of various data sources and results of prior queries,is proposed for query decomposition and optimization.
2000, 11(2):229-234.
Abstract:
A widely used method for checking real-time systems is,according to the real-time property to be checked,to use a proper bi-simulation equivalence relation to convert the infinite-timed state space to a finite equivalence class space.The algorithm needs only to explore the finite space to get a correct answer.In most cases,exhaustive exploration is very difficult because the equivalence class space increases explosively when the scale of the system increases.In this paper,an equivalence relation is introduced to check whether a concurrent system,which is composed of a finite set of real-time automata,satisfies a linear duration property.To avoid exhaustive exploration,this paper also introduces a compatibility relation between timed states (configurations).Based on these two relations,an algorithm is proposed to check whether a real-time automaton network satisfies a linear duration property.The cases study shows that under some conditions this algorithm has better efficiency than the tools in the literature.
A widely used method for checking real-time systems is,according to the real-time property to be checked,to use a proper bi-simulation equivalence relation to convert the infinite-timed state space to a finite equivalence class space.The algorithm needs only to explore the finite space to get a correct answer.In most cases,exhaustive exploration is very difficult because the equivalence class space increases explosively when the scale of the system increases.In this paper,an equivalence relation is introduced to check whether a concurrent system,which is composed of a finite set of real-time automata,satisfies a linear duration property.To avoid exhaustive exploration,this paper also introduces a compatibility relation between timed states (configurations).Based on these two relations,an algorithm is proposed to check whether a real-time automaton network satisfies a linear duration property.The cases study shows that under some conditions this algorithm has better efficiency than the tools in the literature.
2000, 11(2):235-239.
Abstract:
Extended graph-oriented distributed programming model (ExGOM) provides a system architecture to support dynamic configuration.Dynamic configuration involves system expansion and shrink during execution,upgrading while running,and reconfiguration after a fault occurs.One problem in reconfiguration is how to recover the system to the consistent states that exist just before the occurrence of faults.This paper is focused on this problem and proposes an asynchronous rollback algorithm and a crash recovery mechanism based on fault-sensitive graphs.The issue of multiple faulty processes on a single transient faulty host is addressed.Compared with other asynchronous rollback and recovery algorithms,the algorithm presented in this paper localizes the region of faults.Only fault-sensitive nodes are rolled back.This results in a minimized system overhead.
Extended graph-oriented distributed programming model (ExGOM) provides a system architecture to support dynamic configuration.Dynamic configuration involves system expansion and shrink during execution,upgrading while running,and reconfiguration after a fault occurs.One problem in reconfiguration is how to recover the system to the consistent states that exist just before the occurrence of faults.This paper is focused on this problem and proposes an asynchronous rollback algorithm and a crash recovery mechanism based on fault-sensitive graphs.The issue of multiple faulty processes on a single transient faulty host is addressed.Compared with other asynchronous rollback and recovery algorithms,the algorithm presented in this paper localizes the region of faults.Only fault-sensitive nodes are rolled back.This results in a minimized system overhead.
2000, 11(2):240-250.
Abstract:
This paper introduces the payment process of SET(secure electronic transactions)protocol,and extends the logical framework of NDL to fit the purpose of logical verification of SET.This means to add some new axioms about SET protocols and redefine some given inference rules.Based on these,the logical verification for key fragments of SET protocol is given to show the importance of NDL and its extensions in E-commerce.Topics for further research on the “Rule of Accumulation” are also proposed.
This paper introduces the payment process of SET(secure electronic transactions)protocol,and extends the logical framework of NDL to fit the purpose of logical verification of SET.This means to add some new axioms about SET protocols and redefine some given inference rules.Based on these,the logical verification for key fragments of SET protocol is given to show the importance of NDL and its extensions in E-commerce.Topics for further research on the “Rule of Accumulation” are also proposed.
2000, 11(2):251-255.
Abstract:
To improve network reliability and management level in today's high-speed telecommunication networks,a performance and dependability analysis model used for network management is proposed in this paper,which computes in real-time and forecasts performance-reliability,performance-availability for the overall network performance parameter (e.g.bandwidth,throughput and latency) and the MTTF (mean time to failure).Due to the arising complexity of exact model solution,for highly reliable network's management an approximation of the model and its implementation are also presented.
To improve network reliability and management level in today's high-speed telecommunication networks,a performance and dependability analysis model used for network management is proposed in this paper,which computes in real-time and forecasts performance-reliability,performance-availability for the overall network performance parameter (e.g.bandwidth,throughput and latency) and the MTTF (mean time to failure).Due to the arising complexity of exact model solution,for highly reliable network's management an approximation of the model and its implementation are also presented.
2000, 11(2):256-259.
Abstract:
The mean field annealing approach is a new neural network model,which improves the simulated annealing approach greatly.In the paper,the via minimization problem in multi-layer routing with adjacent constraints is translated to a k-colorable problem which has more general meanings,and a mean field annealing algorithm for the k-colorable problem is proposed.On the basis of the segment-crossing graph model,the adjacent matrix and the crossing matrix are introduced.A permute matrix of binary variables is used to map the problem to the neural network,and then the energy function is presented.The object item,crossing constrained item and adjacency constrained item in the energy function,and the normalization of neurons prove that the effective result can be gotten.The experimental results show that it is an effective method.
The mean field annealing approach is a new neural network model,which improves the simulated annealing approach greatly.In the paper,the via minimization problem in multi-layer routing with adjacent constraints is translated to a k-colorable problem which has more general meanings,and a mean field annealing algorithm for the k-colorable problem is proposed.On the basis of the segment-crossing graph model,the adjacent matrix and the crossing matrix are introduced.A permute matrix of binary variables is used to map the problem to the neural network,and then the energy function is presented.The object item,crossing constrained item and adjacency constrained item in the energy function,and the normalization of neurons prove that the effective result can be gotten.The experimental results show that it is an effective method.
2000, 11(2):260-264.
Abstract:
The minimum rectilinear Steiner tree (MRST) problem is an NP-complete problem which arises in VLSI wiring,network routing and many combinatorial optimization problems.In this paper,an O(n2) time complexity approximation algorithm for MRST is proposed.The approximation ratio of the algorithm is strictly less than 3/2.The computer verification of the algorithm shows that the costs of the produced spanning trees are only 0.8% away from the optimal.In addition,this algorithm can be revised for multidimensional Manhattan space and implemented in parallel/distributed environments easily.
The minimum rectilinear Steiner tree (MRST) problem is an NP-complete problem which arises in VLSI wiring,network routing and many combinatorial optimization problems.In this paper,an O(n2) time complexity approximation algorithm for MRST is proposed.The approximation ratio of the algorithm is strictly less than 3/2.The computer verification of the algorithm shows that the costs of the produced spanning trees are only 0.8% away from the optimal.In addition,this algorithm can be revised for multidimensional Manhattan space and implemented in parallel/distributed environments easily.
2000, 11(2):265-270.
Abstract:
Path search and spatial query are considered as two independent topics in database research.The processing of path query with spatial constraint needs both path computation and spatial query.To provide path computation with spatial constraint,two processing strategies are considered:(1) whether pre-processing spatial operation before path computation,and (2) whether pre-filtering spatial objects before path computation.Based on these two strategies,four integrated spatial path query processing approaches are proposed in this paper.
Path search and spatial query are considered as two independent topics in database research.The processing of path query with spatial constraint needs both path computation and spatial query.To provide path computation with spatial constraint,two processing strategies are considered:(1) whether pre-processing spatial operation before path computation,and (2) whether pre-filtering spatial objects before path computation.Based on these two strategies,four integrated spatial path query processing approaches are proposed in this paper.
2000, 11(2):271-276.
Abstract:
In speech recognition,the selection of training corpus for robust acoustic modeling which can cover almost all phone phenomena is very important.Traditionally,corpus is selected manually first,and then tested and supplemented,which can't provide sufficient coverage of samples for various statistical modeling methods.An algorithm for automatically selecting the training samples from large-scale text corpus is developed in this paper.This algorithm can not only cover almost all phone phenomena but also ensure to include ideal samples of triphones or class-triphones and ensure enough data for training,which makes it possible to train acoustic model reliably.
In speech recognition,the selection of training corpus for robust acoustic modeling which can cover almost all phone phenomena is very important.Traditionally,corpus is selected manually first,and then tested and supplemented,which can't provide sufficient coverage of samples for various statistical modeling methods.An algorithm for automatically selecting the training samples from large-scale text corpus is developed in this paper.This algorithm can not only cover almost all phone phenomena but also ensure to include ideal samples of triphones or class-triphones and ensure enough data for training,which makes it possible to train acoustic model reliably.
2000, 11(2):277-284.
Abstract:
The improvement on the shift rules of global and immediate focuses is presented.The improved rules can be used for more extensive domain.Based on Mckeown's focus algorithm,a new algorithm that adopts tree as a controlling structure instead of stack is proposed.It can control the shift of both global and immediate focuses simultaneously.The new algorithm improves the ATN representation of Schema by adding repeat property and priority information to the edge and incorporates the control of the recursion of Schema and backtrack mechanism.The filling and recursion of Schema are determined by the knowledge base.Moreover,the new algorithm can also handle the interchangeable symbols in the Schema.The design of an experimental system based on the proposed algorithm is introduced and the effectiveness of the algorithm is discussed.
The improvement on the shift rules of global and immediate focuses is presented.The improved rules can be used for more extensive domain.Based on Mckeown's focus algorithm,a new algorithm that adopts tree as a controlling structure instead of stack is proposed.It can control the shift of both global and immediate focuses simultaneously.The new algorithm improves the ATN representation of Schema by adding repeat property and priority information to the edge and incorporates the control of the recursion of Schema and backtrack mechanism.The filling and recursion of Schema are determined by the knowledge base.Moreover,the new algorithm can also handle the interchangeable symbols in the Schema.The design of an experimental system based on the proposed algorithm is introduced and the effectiveness of the algorithm is discussed.
联系方式
- 《Journal of Software 》
- 主办单位：Institute of Software, CAS, China
- 邮编：100190
- 电话：010-62562563
- 电子邮箱：jos@iscas.ac.cn
- 网址：https://www.jos.org.cn
- 刊号：ISSN 1000-9825
- CN 11-2560/TP
- 国内定价：70元
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.
