Volume 17,Issue 5,2006 Table of Contents
2006, 17(5):951-958.
Abstract:
Since SVM is very sensitive to outliers and noises in the training set, a fuzzy support vector machine algorithm based on affinity among samples is proposed in this paper. The fuzzy membership is defined by not only the relation between a sample and its cluster center, but also those among samples, which is described by the affinity among samples. A method defining the affinity among samples is considered using a sphere with minimum volume while containing the maximum of the samples. Then, the fuzzy membership is defined according to the position of samples in sphere space. Compared with the fuzzy support vector machine algorithm based on the relation between a sample and its cluster center, this method effectively distinguishes between the valid samples and the outliers or noises. Experimental results show that the fuzzy support vector machine based on the affinity among samples is more robust than the traditional support vector machine, and the fuzzy support vector machines based on the distance of a sample and its cluster center.
Since SVM is very sensitive to outliers and noises in the training set, a fuzzy support vector machine algorithm based on affinity among samples is proposed in this paper. The fuzzy membership is defined by not only the relation between a sample and its cluster center, but also those among samples, which is described by the affinity among samples. A method defining the affinity among samples is considered using a sphere with minimum volume while containing the maximum of the samples. Then, the fuzzy membership is defined according to the position of samples in sphere space. Compared with the fuzzy support vector machine algorithm based on the relation between a sample and its cluster center, this method effectively distinguishes between the valid samples and the outliers or noises. Experimental results show that the fuzzy support vector machine based on the affinity among samples is more robust than the traditional support vector machine, and the fuzzy support vector machines based on the distance of a sample and its cluster center.
2006, 17(5):959-967.
Abstract:
An algorithm for estimating aircraft approach angle using computer vision is proposed in this paper. During the landing of an aircraft, the descent of the aircraft may be approximately considered as a pure translation motion. In this case the epipole has the same coordinates in all images and is called the Focus-of-Expansion (FOE), and the vanishing line of the ground plane is termed the Horizon. Furthermore, how the Focus-of-Expansion and the Horizon are extracted from a few calibrated sequential images is first introduced, then the aircraft approach angle is derived from these parameters. Simulated and real experiments validate this algorithm.
An algorithm for estimating aircraft approach angle using computer vision is proposed in this paper. During the landing of an aircraft, the descent of the aircraft may be approximately considered as a pure translation motion. In this case the epipole has the same coordinates in all images and is called the Focus-of-Expansion (FOE), and the vanishing line of the ground plane is termed the Horizon. Furthermore, how the Focus-of-Expansion and the Horizon are extracted from a few calibrated sequential images is first introduced, then the aircraft approach angle is derived from these parameters. Simulated and real experiments validate this algorithm.
2006, 17(5):968-975.
Abstract:
Extended fuzzy description logic EFALCN (extended fuzzy attributive concept description language with complements and unqualified number restriction) is the fuzzy extension of the description logic with numerical restriction ALCN (attributive concept description language with complements and unqualified number restriction), but it lacks of reasoning algorithms and complexity analysis for reasoning tasks. In this paper, a constraint-propagation based tableau algorithm is proposed, and it is proved that this algorithm can be executed in PSPACE (polynomial space). For there is a polynomial time reduction that can reduce ALCN reasoning tasks into EFALCN reasoning tasks and ALCN reasoning tasks are PSPACE-complete, EFALCN reasoning tasks are PSPACE-hard. Thus, it can be proved that the EFALCN reasoning tasks are PSPACE-complete.
Extended fuzzy description logic EFALCN (extended fuzzy attributive concept description language with complements and unqualified number restriction) is the fuzzy extension of the description logic with numerical restriction ALCN (attributive concept description language with complements and unqualified number restriction), but it lacks of reasoning algorithms and complexity analysis for reasoning tasks. In this paper, a constraint-propagation based tableau algorithm is proposed, and it is proved that this algorithm can be executed in PSPACE (polynomial space). For there is a polynomial time reduction that can reduce ALCN reasoning tasks into EFALCN reasoning tasks and ALCN reasoning tasks are PSPACE-complete, EFALCN reasoning tasks are PSPACE-hard. Thus, it can be proved that the EFALCN reasoning tasks are PSPACE-complete.
2006, 17(5):976-982.
Abstract:
Qualitative spatial reasoning has received a lot of attention in the areas of Geographic Information Systems, Artificial Intelligence, Databases and Multimedia. The basic theory and algorithm of spatial reasoning are developing and innovating continually. Direction relation reasoning is an important branch in the field of spatial reasoning. Applying the theory of interval algebra and rectangle algebra, a new reasoning method combining cardinal direction relations with rectangle algebra relations is presented based on the model of MBR (minimum bounding rectangle). By this means, the good calculating property of rectangle algebra is applied to spatial direction relation reasoning, and the following methods are realized such as transform method between MBR-based cardinal direction relations and rectangle algebra relations, composition and inversion operation of cardinal directions, judging method of convex relations in cardinal direction relations and the consistency check algorithm of direction relations.
Qualitative spatial reasoning has received a lot of attention in the areas of Geographic Information Systems, Artificial Intelligence, Databases and Multimedia. The basic theory and algorithm of spatial reasoning are developing and innovating continually. Direction relation reasoning is an important branch in the field of spatial reasoning. Applying the theory of interval algebra and rectangle algebra, a new reasoning method combining cardinal direction relations with rectangle algebra relations is presented based on the model of MBR (minimum bounding rectangle). By this means, the good calculating property of rectangle algebra is applied to spatial direction relation reasoning, and the following methods are realized such as transform method between MBR-based cardinal direction relations and rectangle algebra relations, composition and inversion operation of cardinal directions, judging method of convex relations in cardinal direction relations and the consistency check algorithm of direction relations.
2006, 17(5):983-990.
Abstract:
Tailoring voice font, or pruning redundant synthesis instances, is an important issue of scalable Corpus-based Text To Speech (TTS) system. However, pruning redundant synthesis instances, usually results in the loss of non-uniform. In order to solve this problem, the concept of virtual non-uniform is proposed. According to this concept and the synthesis frequency of each instance, an algorithm named StaRp-VPA is constructed to make TTS scalable to hardware. In experiments, the naturalness scored by Mean Opinion Score (MOS) remains almost unchanged when less than 50% instances are pruned off, and the MOS does not severely degrade when the reduction rate is above 50%.
Tailoring voice font, or pruning redundant synthesis instances, is an important issue of scalable Corpus-based Text To Speech (TTS) system. However, pruning redundant synthesis instances, usually results in the loss of non-uniform. In order to solve this problem, the concept of virtual non-uniform is proposed. According to this concept and the synthesis frequency of each instance, an algorithm named StaRp-VPA is constructed to make TTS scalable to hardware. In experiments, the naturalness scored by Mean Opinion Score (MOS) remains almost unchanged when less than 50% instances are pruned off, and the MOS does not severely degrade when the reduction rate is above 50%.
2006, 17(5):991-1000.
Abstract:
XML document as a new data model has been a hot research area. Similarity measure is a basic of analyses, management and text mining for XML documents. Structured Link Vector Model (SLVM) is a document model for the XML documents’ similarity measure based on both the content and structure. The kernel matrix, which describes the relations between the structure units, plays an important role in the SLVM. In the paper, two algorithms are derived to learn the kernel matrix for capturing the relations between the structure units: one is based on the support vector machine and the other is based on matrix iterative analysis. For the performance evaluation, the proposed similarity measure is applied to similarity search. The experimental results show that the similarity measure based on kernel matrix learning outperform significantly the traditional measures. Furthermore, comparing with the kernel matrix leaning algorithm based on the support vector machine (SVM)’s regression, the kernel matrix leaning algorithms based on matrix iterative analysis not only acquires higher precision but also needs less training documents and cost.
XML document as a new data model has been a hot research area. Similarity measure is a basic of analyses, management and text mining for XML documents. Structured Link Vector Model (SLVM) is a document model for the XML documents’ similarity measure based on both the content and structure. The kernel matrix, which describes the relations between the structure units, plays an important role in the SLVM. In the paper, two algorithms are derived to learn the kernel matrix for capturing the relations between the structure units: one is based on the support vector machine and the other is based on matrix iterative analysis. For the performance evaluation, the proposed similarity measure is applied to similarity search. The experimental results show that the similarity measure based on kernel matrix learning outperform significantly the traditional measures. Furthermore, comparing with the kernel matrix leaning algorithm based on the support vector machine (SVM)’s regression, the kernel matrix leaning algorithms based on matrix iterative analysis not only acquires higher precision but also needs less training documents and cost.
2006, 17(5):1001-1008.
Abstract:
A novel method of dynamic object modeling for visual tracking is presented. The Haar transformation is first applied on the incoming image of the video to get features, which are over-complete description of the image. Then, the Fisher criteria are employed for ranking features based on their contributions to the discrimination between the tracked objects and the background. After that, the objects are modeled by the subset of top-ranked features. During tracking, a Kalman filter is used to predict the upcoming destinations of the tracked objects and the features are re-ranked by the discrimination between the objects and predicted locations. Thereafter, objects models will be updated and only discriminative features are kept in it. This proposed strategy aims to maximally maintain the basic discrimination and reduce computational cost simultaneously. To evaluate the performance of the proposed method, several experiments have been conducted on long video sequences. The experimental results show that the proposed method can handle various uncertain factors under the real world conditions and successfully track the objects in real-time.
A novel method of dynamic object modeling for visual tracking is presented. The Haar transformation is first applied on the incoming image of the video to get features, which are over-complete description of the image. Then, the Fisher criteria are employed for ranking features based on their contributions to the discrimination between the tracked objects and the background. After that, the objects are modeled by the subset of top-ranked features. During tracking, a Kalman filter is used to predict the upcoming destinations of the tracked objects and the features are re-ranked by the discrimination between the objects and predicted locations. Thereafter, objects models will be updated and only discriminative features are kept in it. This proposed strategy aims to maximally maintain the basic discrimination and reduce computational cost simultaneously. To evaluate the performance of the proposed method, several experiments have been conducted on long video sequences. The experimental results show that the proposed method can handle various uncertain factors under the real world conditions and successfully track the objects in real-time.
2006, 17(5):1009-1016.
Abstract:
Outliers are objects that do not comply with the general behavior of the data. The method of partition divides data space into a set of non-overlapping rectangular cells by partitioning every dimension into equal length. Statistical information of cells is used to find knowledge in datasets. There exists very large data skew in real-life datasets, so partition will produce many empty cells, which affects the efficiency of the algorithms. An efficient index structure called CD-Tree (cell dimension tree) is designed for indexing cells. Moreover, to guide partition and to optimize the structure of CD-Tree, the concept of SOD (skew of data) is proposed to measure the degree of data skew. Finally, the CD-Tree-based algorithm is designed for outlier detection based on CD-Tree and SOD. The experimental results show that the efficiency of CD-Tree-based algorithm and the maximum number of dimensions processed increase obviously comparing with the Cell-based algorithm on real-life datasets.
Outliers are objects that do not comply with the general behavior of the data. The method of partition divides data space into a set of non-overlapping rectangular cells by partitioning every dimension into equal length. Statistical information of cells is used to find knowledge in datasets. There exists very large data skew in real-life datasets, so partition will produce many empty cells, which affects the efficiency of the algorithms. An efficient index structure called CD-Tree (cell dimension tree) is designed for indexing cells. Moreover, to guide partition and to optimize the structure of CD-Tree, the concept of SOD (skew of data) is proposed to measure the degree of data skew. Finally, the CD-Tree-based algorithm is designed for outlier detection based on CD-Tree and SOD. The experimental results show that the efficiency of CD-Tree-based algorithm and the maximum number of dimensions processed increase obviously comparing with the Cell-based algorithm on real-life datasets.
2006, 17(5):1017-1025.
Abstract:
Association categorization approach based on frequent patterns has been recently presented, which builds the classification rules according to frequent patterns in various categories and classifies the new text employing these rules. But there are two shortages when the method is applied to classify text data: one is that the method ignores the information about word’s frequency in a text; another is that the rule pruning to improve the classification efficiency will lead to obvious descending of accuracy when mass rules are generated. Therefore, a text categorization algorithm based on frequent patterns with term frequency is presented. This study illuminates that the word frequency is helpful for improving the accuracy of the association categorization and the classification rule tree can improve the efficiency of the association classification. The result of experiments shows the performance of association classification is better than three typical text classification methods Bayes, kNN (k nearest neighbor) and SVM (support vector machines), so it is a promising text classification method.
Association categorization approach based on frequent patterns has been recently presented, which builds the classification rules according to frequent patterns in various categories and classifies the new text employing these rules. But there are two shortages when the method is applied to classify text data: one is that the method ignores the information about word’s frequency in a text; another is that the rule pruning to improve the classification efficiency will lead to obvious descending of accuracy when mass rules are generated. Therefore, a text categorization algorithm based on frequent patterns with term frequency is presented. This study illuminates that the word frequency is helpful for improving the accuracy of the association categorization and the classification rule tree can improve the efficiency of the association classification. The result of experiments shows the performance of association classification is better than three typical text classification methods Bayes, kNN (k nearest neighbor) and SVM (support vector machines), so it is a promising text classification method.
2006, 17(5):1026-1033.
Abstract:
Computational efficiency is an important concern for machine learning algorithms, especially for applications on large test sets or in real-time scenarios. In this paper, a novel data structure and the corresponding algorithms for the execution system of the maximum entropy model are described. This data structure, called sparse feature tree, is used to represent the feature set to speed up the process of feature search (or feature matching), so that speed up the process of probability calculation and execution system. Experiments on chunking recognition and Part-of-Speech tagging are conducted to show that the new data structure greatly speeds up the feature matching process while keeping the same space complexity.
Computational efficiency is an important concern for machine learning algorithms, especially for applications on large test sets or in real-time scenarios. In this paper, a novel data structure and the corresponding algorithms for the execution system of the maximum entropy model are described. This data structure, called sparse feature tree, is used to represent the feature set to speed up the process of feature search (or feature matching), so that speed up the process of probability calculation and execution system. Experiments on chunking recognition and Part-of-Speech tagging are conducted to show that the new data structure greatly speeds up the feature matching process while keeping the same space complexity.
2006, 17(5):1034-1041.
Abstract:
It is a hot research topic to eliminate irrelevant variables from counterexample, to make it easier to be understood. BFL (brute force lifting) algorithm is the most effective one among all the existing approaches, but its time overhead is very large due to one call to SAT (boolean satisfiability problem) solver per candidate variable to be eliminated. So a faster algorithm based on refutation analysis and incremental SAT is proposed. The counterexample minimization problem is first translated into a set of SAT instances for each free variable v, to determine if v can prevent the counterexample. Then refutation analysis on those UNSAT (unsatisfiable) instances is performed, to extract the set of variables that lead to refutation. All variables that don’t belong to this set can be eliminated directly as irrelevant variables. At the same time, the incremental SAT approach is employed to share conflict clauses between similar instances, such that the overlapped state space can be prevented from being searched repeatedly. Theoretical analysis and experimental result show that this approach run much faster than BFL algorithm, and with minor lost in reduction rate.
It is a hot research topic to eliminate irrelevant variables from counterexample, to make it easier to be understood. BFL (brute force lifting) algorithm is the most effective one among all the existing approaches, but its time overhead is very large due to one call to SAT (boolean satisfiability problem) solver per candidate variable to be eliminated. So a faster algorithm based on refutation analysis and incremental SAT is proposed. The counterexample minimization problem is first translated into a set of SAT instances for each free variable v, to determine if v can prevent the counterexample. Then refutation analysis on those UNSAT (unsatisfiable) instances is performed, to extract the set of variables that lead to refutation. All variables that don’t belong to this set can be eliminated directly as irrelevant variables. At the same time, the incremental SAT approach is employed to share conflict clauses between similar instances, such that the overlapped state space can be prevented from being searched repeatedly. Theoretical analysis and experimental result show that this approach run much faster than BFL algorithm, and with minor lost in reduction rate.
2006, 17(5):1042-1050.
Abstract:
Time series prediction is a very important problem in many applications and the current prediction techniques are nearly all based on the Takens' embedding theorem. Many realistic systems are parameter-varying systems, and the embedding theorems are invalid, predicting the behavior of parameter-varying systems is more difficult. This paper proposes the novel prediction techniques for parameter-varying systems reconstruction, which are based on wavelet neural network (WNN) and multiwavelets neural network (MWNN). These techniques absorb the advantages of high resolution of wavelet and learning of neural networks. The significant improvement is that the error's functions of both networks are convex, and the problem of poor convergence and undesired local minimum can be solved remarkably. Ikeda time series generated by the parameter-varying systems is adopted to check the prediction performance of the proposed models. The numerical experiments show that the three proposed models are feasible, MWNN has the top performance, and WNN could lead the better results than NN in the prediction of the parameter-varying systems.
Time series prediction is a very important problem in many applications and the current prediction techniques are nearly all based on the Takens' embedding theorem. Many realistic systems are parameter-varying systems, and the embedding theorems are invalid, predicting the behavior of parameter-varying systems is more difficult. This paper proposes the novel prediction techniques for parameter-varying systems reconstruction, which are based on wavelet neural network (WNN) and multiwavelets neural network (MWNN). These techniques absorb the advantages of high resolution of wavelet and learning of neural networks. The significant improvement is that the error's functions of both networks are convex, and the problem of poor convergence and undesired local minimum can be solved remarkably. Ikeda time series generated by the parameter-varying systems is adopted to check the prediction performance of the proposed models. The numerical experiments show that the three proposed models are feasible, MWNN has the top performance, and WNN could lead the better results than NN in the prediction of the parameter-varying systems.
2006, 17(5):1051-1067.
Abstract:
With the massive and ever increasing pages in the Web, incremental crawling has become a promising method to achieve on-line information. Its main advantage is the resource economization, which comes from the avoidance of downloading unchanged pages. For the precision of change prediction, the evolution of Web is generally studied to find out how pages change. In sum, incremental crawlers often integrate change frequency, change extent, and document quality for each page to determine its relative order as well as its download frequency. In this paper, the researches on Web evolution and incremental crawling in recent years are summarized: First, the change of page is modeled as a Poisson process, and the solutions are given to estimate its parameters, especially the change frequency, and then experimental results are shown. Second, based on the change of pages, three public large-scale incremental crawling systems are introduced, with emphasis on their scheduling policies and strategies to enhance page qualities. Third, theoretical analysis and exploration are performed to find the optimal scheduling policy, three approaches from different points of views are utilized to achieve this object, and a heuristic approximate solution is supplied for the feasibility in practice. Finally, research trends in this area are predicted, and three main issues are listed.
With the massive and ever increasing pages in the Web, incremental crawling has become a promising method to achieve on-line information. Its main advantage is the resource economization, which comes from the avoidance of downloading unchanged pages. For the precision of change prediction, the evolution of Web is generally studied to find out how pages change. In sum, incremental crawlers often integrate change frequency, change extent, and document quality for each page to determine its relative order as well as its download frequency. In this paper, the researches on Web evolution and incremental crawling in recent years are summarized: First, the change of page is modeled as a Poisson process, and the solutions are given to estimate its parameters, especially the change frequency, and then experimental results are shown. Second, based on the change of pages, three public large-scale incremental crawling systems are introduced, with emphasis on their scheduling policies and strategies to enhance page qualities. Third, theoretical analysis and exploration are performed to find the optimal scheduling policy, three approaches from different points of views are utilized to achieve this object, and a heuristic approximate solution is supplied for the feasibility in practice. Finally, research trends in this area are predicted, and three main issues are listed.
2006, 17(5):1068-1077.
Abstract:
Service Composition enables a new way to create new services by assembling independent service components. One of the important goals in service composition is load balancing across service replicas. In this paper, a novel adaptive distributed load capacity based (LCB) algorithm is presented to solve the load balancing problem in service composition. LCB algorithm uses service routing mechanism to search services and transfer the application data. By self-adaptively calculating the load capacity (LC) metric, LCB algorithm can choose a reasonable service path. LC metric reflects the workload of the service node, and is adaptively adjusted according to the variations of the server’s load. Compared with the previous researches, LCB algorithm needn’t the global topology information and load information. It is much suitable for dynamic service composition in distributed systems. Simulations show that LCB algorithm performs well in terms of load balancing across the service replicas.
Service Composition enables a new way to create new services by assembling independent service components. One of the important goals in service composition is load balancing across service replicas. In this paper, a novel adaptive distributed load capacity based (LCB) algorithm is presented to solve the load balancing problem in service composition. LCB algorithm uses service routing mechanism to search services and transfer the application data. By self-adaptively calculating the load capacity (LC) metric, LCB algorithm can choose a reasonable service path. LC metric reflects the workload of the service node, and is adaptively adjusted according to the variations of the server’s load. Compared with the previous researches, LCB algorithm needn’t the global topology information and load information. It is much suitable for dynamic service composition in distributed systems. Simulations show that LCB algorithm performs well in terms of load balancing across the service replicas.
2006, 17(5):1078-1088.
Abstract:
The TCP(transmission control protocol) flow fairness problem in wireless multi-hop ad hoc networks is investigated. It is identified that the IEEE 802.11 DCF protocol can lead to severe unfairness, i.e., some nodes seize the whole channel capacity while others are starved. The TCP flow unfairness problem is first analyzed by simulation and it is found that the main reason lies in the unfairness of MAC(media access and control) protocol, while the TCP timeout mechanism makes the unfairness more severe. Then a probability model is used to quantitatively analyze the relation between the TCP unfairness and MAC parameters, which shows that the TCP flow fairness heavily correlates with the TCP packet length, and increasing the initial contention window of the MAC protocol can improve the fairness effectively. Based on these observations, a novel adaptive backoff algorithm is proposed, which dynamically adjusts the initial contention window according to the TCP packet length. Both theoretic analysis and simulation results show that the proposed algorithm can relieve the fairness problem to a large extent without significantly impairing aggregate throughput in wireless ad hoc networks.
The TCP(transmission control protocol) flow fairness problem in wireless multi-hop ad hoc networks is investigated. It is identified that the IEEE 802.11 DCF protocol can lead to severe unfairness, i.e., some nodes seize the whole channel capacity while others are starved. The TCP flow unfairness problem is first analyzed by simulation and it is found that the main reason lies in the unfairness of MAC(media access and control) protocol, while the TCP timeout mechanism makes the unfairness more severe. Then a probability model is used to quantitatively analyze the relation between the TCP unfairness and MAC parameters, which shows that the TCP flow fairness heavily correlates with the TCP packet length, and increasing the initial contention window of the MAC protocol can improve the fairness effectively. Based on these observations, a novel adaptive backoff algorithm is proposed, which dynamically adjusts the initial contention window according to the TCP packet length. Both theoretic analysis and simulation results show that the proposed algorithm can relieve the fairness problem to a large extent without significantly impairing aggregate throughput in wireless ad hoc networks.
2006, 17(5):1089-1097.
Abstract:
The problem that XML formally governs syntax only but not semantics has been recognized as a serious barrier for XML-Based data integration and the extension of current Web to the semantic Web. To address this problem, the XML Semantics Definition Language (XSDL) is proposed to explicitly express the XML author’s intended meaning and a model-theoretic semantics for XML. In this way, the XML becomes a sub-language of RDF (resource description framework) in expressivity and the XML data can be semantics-preserving transformed to the RDF data. The semantic validity and entailment problem of XML documents are further provided and they are reduced to the knowledge base unsatisfiability problem in description logic language ΣΗΟΙΝ(?).
The problem that XML formally governs syntax only but not semantics has been recognized as a serious barrier for XML-Based data integration and the extension of current Web to the semantic Web. To address this problem, the XML Semantics Definition Language (XSDL) is proposed to explicitly express the XML author’s intended meaning and a model-theoretic semantics for XML. In this way, the XML becomes a sub-language of RDF (resource description framework) in expressivity and the XML data can be semantics-preserving transformed to the RDF data. The semantic validity and entailment problem of XML documents are further provided and they are reduced to the knowledge base unsatisfiability problem in description logic language ΣΗΟΙΝ(?).
2006, 17(5):1098-1106.
Abstract:
One of the essential problems in P2P is the strategy for resource discovery. Related methods in unstructured P2P either depend on the flooding and its variations or utilize various indices, which results in too much overhead to forward messages or too expensive cost to maintain the indices. An adaptive, bandwidth-efficient and easily maintained search algorithm for unstructured P2P systems, PeerRank, is presented. The scheme utilizes the feedback from previous searches to probabilistically guide future ones. In addition, an effective caching and indexing mechanism is introduced, which remarkably enforces the search performance. The final simulation experiment shows that the strategy can remarkably improve the search efficiency with the small average path length, high success rates, very low bandwidth consumption, and the eminent adaptability to the change of hot resources.
One of the essential problems in P2P is the strategy for resource discovery. Related methods in unstructured P2P either depend on the flooding and its variations or utilize various indices, which results in too much overhead to forward messages or too expensive cost to maintain the indices. An adaptive, bandwidth-efficient and easily maintained search algorithm for unstructured P2P systems, PeerRank, is presented. The scheme utilizes the feedback from previous searches to probabilistically guide future ones. In addition, an effective caching and indexing mechanism is introduced, which remarkably enforces the search performance. The final simulation experiment shows that the strategy can remarkably improve the search efficiency with the small average path length, high success rates, very low bandwidth consumption, and the eminent adaptability to the change of hot resources.
2006, 17(5):1107-1114.
Abstract:
Much work has been done on building content-based publish/subscribe systems over structured P2P networks, so that the two technologies can be combined together to better support large-scale and highly dynamic systems. However, existing content-based routing protocols can only provide weak reliability guarantees over P2P networks. Based on the routing protocols of structured P2P networks, a new type of content-based routing protocol for pub/sub systems is designed, which is called Identifier Range Based Routing (IRBR) protocol. The IRBR protocol guarantees that the subscribing nodes always receive the interested events exactly once as long as the message from publishing nodes to subscribing nodes is arrivable in the P2P network. At the same time, it can also disseminate an event to all interested subscribers with less network traffic. A prototype pub/sub system has been developed on Pastry, and the experimental results demonstrate the fault-tolerance and routing efficiency of the protocol.
Much work has been done on building content-based publish/subscribe systems over structured P2P networks, so that the two technologies can be combined together to better support large-scale and highly dynamic systems. However, existing content-based routing protocols can only provide weak reliability guarantees over P2P networks. Based on the routing protocols of structured P2P networks, a new type of content-based routing protocol for pub/sub systems is designed, which is called Identifier Range Based Routing (IRBR) protocol. The IRBR protocol guarantees that the subscribing nodes always receive the interested events exactly once as long as the message from publishing nodes to subscribing nodes is arrivable in the P2P network. At the same time, it can also disseminate an event to all interested subscribers with less network traffic. A prototype pub/sub system has been developed on Pastry, and the experimental results demonstrate the fault-tolerance and routing efficiency of the protocol.
2006, 17(5):1115-1123.
Abstract:
Petersen graph has good performance in parallel and distributed computation because of its characteristics such as short diameter and regularity. On the basis of topology of double-loops, a new double-loops connected Petersen graph network DLCPG(k) is constructed. In addition, unicasting, broadcasting and a kind of fault-tolerant routing algorithms are designed respectively. It is proved that DLCPG(k) not only has good extensibility, short diameter and simple topology, but also has the following good characteristics for the networks with 10k nodes: The diameter of DLCPG(k) is shorter than that of 2-dimensional Torus and RP(k) networks, and the grouping ability of DLCPG(k) overmatches that of 2-dimensional Torus and RP(k) networks at the same time. It is also proved that the communication efficiency of both the unicasting and broadcasting algorithms are better than the unicasting and broadcasting algorithms of RP(k) network conspicuously. Simulation results conclude that the new fault-tolerant routing algorithm is of good fault-tolerant ability.
Petersen graph has good performance in parallel and distributed computation because of its characteristics such as short diameter and regularity. On the basis of topology of double-loops, a new double-loops connected Petersen graph network DLCPG(k) is constructed. In addition, unicasting, broadcasting and a kind of fault-tolerant routing algorithms are designed respectively. It is proved that DLCPG(k) not only has good extensibility, short diameter and simple topology, but also has the following good characteristics for the networks with 10k nodes: The diameter of DLCPG(k) is shorter than that of 2-dimensional Torus and RP(k) networks, and the grouping ability of DLCPG(k) overmatches that of 2-dimensional Torus and RP(k) networks at the same time. It is also proved that the communication efficiency of both the unicasting and broadcasting algorithms are better than the unicasting and broadcasting algorithms of RP(k) network conspicuously. Simulation results conclude that the new fault-tolerant routing algorithm is of good fault-tolerant ability.
2006, 17(5):1124-1132.
Abstract:
In this paper, a robust algorithm with large data payload and high computational efficiency is proposed, which is suitable for real-time watermarking of JPEG or MPEG streams because it operates directly on DCT (discrete cosine transform) blocks. The proposed method is based on modifying the low-mid frequency DCT coefficients imperceptibly to modulate block energy. During the modulation, a theorem deduced from the Watson’s perceptual model is employed to restrict the modified magnitude of coefficients. This system is capable of embedding 2048 bits of information in images with dimensions 512×512 pixels. Experimental results indicate that the presented scheme is transparent and robust to significant valumetric distortions (including additive noise, low-pass filtering, lossy compression and valumetric scaling) and a part of geometric distortions.
In this paper, a robust algorithm with large data payload and high computational efficiency is proposed, which is suitable for real-time watermarking of JPEG or MPEG streams because it operates directly on DCT (discrete cosine transform) blocks. The proposed method is based on modifying the low-mid frequency DCT coefficients imperceptibly to modulate block energy. During the modulation, a theorem deduced from the Watson’s perceptual model is employed to restrict the modified magnitude of coefficients. This system is capable of embedding 2048 bits of information in images with dimensions 512×512 pixels. Experimental results indicate that the presented scheme is transparent and robust to significant valumetric distortions (including additive noise, low-pass filtering, lossy compression and valumetric scaling) and a part of geometric distortions.
2006, 17(5):1133-1139.
Abstract:
A special quantum error correction scheme is proposed to protect the flow of transmitted quantum information in complex channels. Based on the derived syndrome, an algorithm is devised for the construction of the called quantum event-error correction code, which can correct simultaneously random and burst quantum errors.Moreover, the constructed code can detect the length, the number and even the exact location of the occurring errors in the listed error event.
A special quantum error correction scheme is proposed to protect the flow of transmitted quantum information in complex channels. Based on the derived syndrome, an algorithm is devised for the construction of the called quantum event-error correction code, which can correct simultaneously random and burst quantum errors.Moreover, the constructed code can detect the length, the number and even the exact location of the occurring errors in the listed error event.
2006, 17(5):1140-1148.
Abstract:
Random Early Detection (RED) is the active queue management (AQM) algorithm recommended by IETF. Unfortunately, it is identified that RED is difficult to configure its parameters and the average queue length of RED is closely related to the load level. ARED (adaptive RED) is the adaptive version of RED. ARED dynamically adjust maximum packet marking probability according to the average queue length to make average queue length stable, but it still suffers from unstable instantaneous queue length and performance degradation under dynamic traffic conditions. In this paper, the cause of such problems of ARED is analyzed and a load adaptive active queue management scheme called LARED (load adaptive RED) is proposed. LARED features in adapting the load level of bottleneck link as well as quick response to queue length dynamics. Analysis and simulation results show that, compared with ARED and other AQM algorithms, LARED brings more stable queue dynamics; while keeping high link utilization and low queuing delay, it presents good responsiveness and robustness in various traffic conditions.
Random Early Detection (RED) is the active queue management (AQM) algorithm recommended by IETF. Unfortunately, it is identified that RED is difficult to configure its parameters and the average queue length of RED is closely related to the load level. ARED (adaptive RED) is the adaptive version of RED. ARED dynamically adjust maximum packet marking probability according to the average queue length to make average queue length stable, but it still suffers from unstable instantaneous queue length and performance degradation under dynamic traffic conditions. In this paper, the cause of such problems of ARED is analyzed and a load adaptive active queue management scheme called LARED (load adaptive RED) is proposed. LARED features in adapting the load level of bottleneck link as well as quick response to queue length dynamics. Analysis and simulation results show that, compared with ARED and other AQM algorithms, LARED brings more stable queue dynamics; while keeping high link utilization and low queuing delay, it presents good responsiveness and robustness in various traffic conditions.
2006, 17(5):1149-1156.
Abstract:
Delaunay triangulation has been widely used in many fields such as computational fluid dynamics, statistics, meteorology, solid state physics, computational geometry and so on. With the development of Ad Hoc networks, some researchers proposed geometric routing protocols to guarantee the delivery of the packet between any pair of nodes in the network, and the underlying network topology is also constructed by the ways of Delaunay triangulation. In this paper, a novel online routing algorithm GLNFR (greedy and local neighbor face routing) for finding communication paths between the mobile nodes is proposed. The localized manner is used to form the local Delaunay triangulation as the underlying topology of a wireless network on which the GLNFR routing algorithm could guarantee the delivery of the packets. It has better scalability and adaptability for the change of networks. Experiment on NS (network simulator) has been conducted. The results show that the delivery success rate of packets and routing protocol overhead under such novel routing protocols performs better than others proposed previously.
Delaunay triangulation has been widely used in many fields such as computational fluid dynamics, statistics, meteorology, solid state physics, computational geometry and so on. With the development of Ad Hoc networks, some researchers proposed geometric routing protocols to guarantee the delivery of the packet between any pair of nodes in the network, and the underlying network topology is also constructed by the ways of Delaunay triangulation. In this paper, a novel online routing algorithm GLNFR (greedy and local neighbor face routing) for finding communication paths between the mobile nodes is proposed. The localized manner is used to form the local Delaunay triangulation as the underlying topology of a wireless network on which the GLNFR routing algorithm could guarantee the delivery of the packets. It has better scalability and adaptability for the change of networks. Experiment on NS (network simulator) has been conducted. The results show that the delivery success rate of packets and routing protocol overhead under such novel routing protocols performs better than others proposed previously.
2006, 17(5):1157-1167.
Abstract:
Wireless sensor network combines sensing, computation and communication. Due to limited energy,energy efficiency of sensors is a main concern and a most challenging task for the design of wireless sensor networks. This paper proposes a novel algorithm for network topology, namely Dynamic Energy-Efficient Hierarchical clustering algorithm (DEEH). Different from others, DEEH need to know any local information of sensors. The algorithm can be applied to real large-scale sensor networks in which the sensors have different energy levels and different transmission radius. Compared with the classical clustering algorithm LEACH (Low-Energy Adaptive Clustering Hierarchy), the algorithm is better when the nodes are densely distributed. This paper also considers the selfishness of nodes and analyzes its impact, and introduces a trustful mechanism design that is applied to the algorithm. Under this mechanism, the dominant strategy of selfish nodes is to report their energy truthfully. This strategy can prolong the network lifetime and improve the stability of the network topology.
Wireless sensor network combines sensing, computation and communication. Due to limited energy,energy efficiency of sensors is a main concern and a most challenging task for the design of wireless sensor networks. This paper proposes a novel algorithm for network topology, namely Dynamic Energy-Efficient Hierarchical clustering algorithm (DEEH). Different from others, DEEH need to know any local information of sensors. The algorithm can be applied to real large-scale sensor networks in which the sensors have different energy levels and different transmission radius. Compared with the classical clustering algorithm LEACH (Low-Energy Adaptive Clustering Hierarchy), the algorithm is better when the nodes are densely distributed. This paper also considers the selfishness of nodes and analyzes its impact, and introduces a trustful mechanism design that is applied to the algorithm. Under this mechanism, the dominant strategy of selfish nodes is to report their energy truthfully. This strategy can prolong the network lifetime and improve the stability of the network topology.
2006, 17(5):1170-1181.
Abstract:
The decentralized structure together with the self-organization and fault-tolerant features makes P2P network an effective model for information sharing, however, the content location remains a serious challenge of large scale P2P networks. In this paper, the SemreX is introduced, which is a P2P system for literature retrieval. Semantic-similarity-based P2P overlay and routing algorithms are proposed for SemreX. Experimental results show that searching in semantic overlay greatly improves the efficiency of search.
The decentralized structure together with the self-organization and fault-tolerant features makes P2P network an effective model for information sharing, however, the content location remains a serious challenge of large scale P2P networks. In this paper, the SemreX is introduced, which is a P2P system for literature retrieval. Semantic-similarity-based P2P overlay and routing algorithms are proposed for SemreX. Experimental results show that searching in semantic overlay greatly improves the efficiency of search.
2006, 17(5):1182-1194.
Abstract:
Web services composition is the hotspot research in the field of Web services. Many methods are proposed, however, composition starting from architecture is a new perspective. BPEL4WS is a de facto standard description language for Web services composition. An architecture style of Web services composition system based on BPEL4WS is presented. Then, an architecture description language, WSC/ADL (Web services composition/architecture description language), is designed according to the architecture style. WSC/ADL consists of service components describing Web services, connectors describing the interaction between Web services and configures setting up the relations between instances of service components and connectors, providing the support for top-down development of Web services composition based on architecture. WSC/ADL is discussed in detail with an example and is compared with related work.
Web services composition is the hotspot research in the field of Web services. Many methods are proposed, however, composition starting from architecture is a new perspective. BPEL4WS is a de facto standard description language for Web services composition. An architecture style of Web services composition system based on BPEL4WS is presented. Then, an architecture description language, WSC/ADL (Web services composition/architecture description language), is designed according to the architecture style. WSC/ADL consists of service components describing Web services, connectors describing the interaction between Web services and configures setting up the relations between instances of service components and connectors, providing the support for top-down development of Web services composition based on architecture. WSC/ADL is discussed in detail with an example and is compared with related work.
2006, 17(5):1195-1203.
Abstract:
Regarding the shortcomings found with the traditional method of integrating a J2EE (Java 2 platform enterprise edition) Web Container, a two-layered Web container integration framework is proposed: the outer layer is independent of the Web container implementation and is the interface between the Web container and management tools, deployment tools and other modules; the inner layer is an extension to the Web container. The framework has been implemented on the J2EE application server PKUAS (Peking University Application Server). Test results have shown that this framework can satisfy the design goals of a pluggable, unified configurable Web container, and its performance is satisfactory.
Regarding the shortcomings found with the traditional method of integrating a J2EE (Java 2 platform enterprise edition) Web Container, a two-layered Web container integration framework is proposed: the outer layer is independent of the Web container implementation and is the interface between the Web container and management tools, deployment tools and other modules; the inner layer is an extension to the Web container. The framework has been implemented on the J2EE application server PKUAS (Peking University Application Server). Test results have shown that this framework can satisfy the design goals of a pluggable, unified configurable Web container, and its performance is satisfactory.
2006, 17(5):1204-1212.
Abstract:
A conjunctive normal form (CNF) formula F is minimal unsatisfiable if F is unsatisfiable and the resulting formula removing any clause from F is satisfiable. (r,s)-CNF is a subclass of CNF in which each clause of formula has exactly r distinct literals and every variable occurs at most s times. The corresponding satisfiable problem (r,s)-SAT means that the instances are restricted in (r,s)-CNF. For positive integer r≥3, there exists a critical function f(r) such that all formulas in (r,f(r))-CNF are satisfiable, but (r,f(r)+1)-SAT is already NP-Complete. It is open whether or not the function f is computable. One can only estimate some bounds of f(r) except for f(3)=3 and f(4)=4. In this paper, the applications of minimal unsatisfiable formulas are described for transformations between CNF formulas. A new algorithm is presented to introduce less new variables in transformation from CNF to 3-CNF, which for clauses with length l(>3) only ??????2l new variables are introduced. The principle and method for transforming CNF to (r,s)-CNF and constructing unsatisfiable formulas in (r,s)-CNF are presented.
A conjunctive normal form (CNF) formula F is minimal unsatisfiable if F is unsatisfiable and the resulting formula removing any clause from F is satisfiable. (r,s)-CNF is a subclass of CNF in which each clause of formula has exactly r distinct literals and every variable occurs at most s times. The corresponding satisfiable problem (r,s)-SAT means that the instances are restricted in (r,s)-CNF. For positive integer r≥3, there exists a critical function f(r) such that all formulas in (r,f(r))-CNF are satisfiable, but (r,f(r)+1)-SAT is already NP-Complete. It is open whether or not the function f is computable. One can only estimate some bounds of f(r) except for f(3)=3 and f(4)=4. In this paper, the applications of minimal unsatisfiable formulas are described for transformations between CNF formulas. A new algorithm is presented to introduce less new variables in transformation from CNF to 3-CNF, which for clauses with length l(>3) only ??????2l new variables are introduced. The principle and method for transforming CNF to (r,s)-CNF and constructing unsatisfiable formulas in (r,s)-CNF are presented.
2006, 17(5):1213-1221.
Abstract:
Because the static materialized views lack of better response performance for dynamic query, an optimized algorithm DCO (dynamic cache optimization) is proposed, which generates a dynamic materialized views set to cooperate with the existing static materialized view set by cache. With the assistance of the additional materialized views, the dynamic adaptability and response capability to query increase greatly. Meanwhile, a novel method of allocating the space is presented to provide the alternative for realizing the dynamic cache, and then the free space of system can be used efficiently to store more materialized views for improving the response capability. Experimental results indicate the efficiency and feasibility of DCO, and also show that DCO can overcome the SPSE (space-performance saturation effect) of materialized views in some degree.
Because the static materialized views lack of better response performance for dynamic query, an optimized algorithm DCO (dynamic cache optimization) is proposed, which generates a dynamic materialized views set to cooperate with the existing static materialized view set by cache. With the assistance of the additional materialized views, the dynamic adaptability and response capability to query increase greatly. Meanwhile, a novel method of allocating the space is presented to provide the alternative for realizing the dynamic cache, and then the free space of system can be used efficiently to store more materialized views for improving the response capability. Experimental results indicate the efficiency and feasibility of DCO, and also show that DCO can overcome the SPSE (space-performance saturation effect) of materialized views in some degree.
2006, 17(5):1222-1231.
Abstract:
K-Anonymization is an important approach to protect data privacy in data publishing scenario. Existing approaches mainly consider data processing with single constraint. There exist multiple constraints cases in the real applications, which makes the K-anonymization more complex. Simply applying the approaches with single constraint to the problem of multiple constraints may cause high information loss and low efficiency. Based on the idea of Classfly, a family of multiple constraints supported K-anonymization approaches named Classfly+ are proposed according to the features of mutiple constraints. Three K-anonymization approaches are proposed, which are naive approach, complete IndepCSet, and partial IndepCSet Classfly+ approaches. Experimental results show that Classfly+ can decrease the information loss and improve efficiency of k-anonymization.
K-Anonymization is an important approach to protect data privacy in data publishing scenario. Existing approaches mainly consider data processing with single constraint. There exist multiple constraints cases in the real applications, which makes the K-anonymization more complex. Simply applying the approaches with single constraint to the problem of multiple constraints may cause high information loss and low efficiency. Based on the idea of Classfly, a family of multiple constraints supported K-anonymization approaches named Classfly+ are proposed according to the features of mutiple constraints. Three K-anonymization approaches are proposed, which are naive approach, complete IndepCSet, and partial IndepCSet Classfly+ approaches. Experimental results show that Classfly+ can decrease the information loss and improve efficiency of k-anonymization.
2006, 17(5):1232-1240.
Abstract:
Timing behaviors are crucial for real-time systems. In order to weaken or even remove the timing impact of the inserted assertions during testing, a new monitoring schema is proposed, which has little time intrusiveness than the software monitoring and supports to test the system completely. Furthermore, a WCET (worst-case execution time) analysis based on time compensation method is presented, which corrects the recorded time of events based on the accurate execution time analysis of assertions.
Timing behaviors are crucial for real-time systems. In order to weaken or even remove the timing impact of the inserted assertions during testing, a new monitoring schema is proposed, which has little time intrusiveness than the software monitoring and supports to test the system completely. Furthermore, a WCET (worst-case execution time) analysis based on time compensation method is presented, which corrects the recorded time of events based on the accurate execution time analysis of assertions.
2006, 17(5):1241-1250.
Abstract:
Walsh functions are widely used in many areas such as signal and image processing, digital communication etc. Walsh function system is orthogonal and completed. Among many methods to generate Walsh functions, Swick’s copy theory is famous. This method takes Walsh function’s order numbers as the copy information and can generate an arbitrary function given certain order number, which in fact is the vector processing method and is not applicable for such 2D signal processing applications as fast transforms. Walsh function system can be expressed by Walsh matrix Wk. In this paper, row copy and block copy methods are put forward based on Wk. Copy operators are designed based on symmetries and a new ordering is discovered (named Walsh-Like ordering). After the iterative formulas of 6 ordering Walsh matrices are deduced by Kronecker product, the computer images of these matrices are illustrated. It is proved that the proposed method is more advanced than the former. The later can achieve higher performance and is applicable to the fast transforms designing. The fourth symmetric ordering of Walsh function system is discovered (Walsh-Like ordering), and the conjecture that the new ordering is likely to be the reverse form of Walsh ordering is made by analyzing and comparing with these images.
Walsh functions are widely used in many areas such as signal and image processing, digital communication etc. Walsh function system is orthogonal and completed. Among many methods to generate Walsh functions, Swick’s copy theory is famous. This method takes Walsh function’s order numbers as the copy information and can generate an arbitrary function given certain order number, which in fact is the vector processing method and is not applicable for such 2D signal processing applications as fast transforms. Walsh function system can be expressed by Walsh matrix Wk. In this paper, row copy and block copy methods are put forward based on Wk. Copy operators are designed based on symmetries and a new ordering is discovered (named Walsh-Like ordering). After the iterative formulas of 6 ordering Walsh matrices are deduced by Kronecker product, the computer images of these matrices are illustrated. It is proved that the proposed method is more advanced than the former. The later can achieve higher performance and is applicable to the fast transforms designing. The fourth symmetric ordering of Walsh function system is discovered (Walsh-Like ordering), and the conjecture that the new ordering is likely to be the reverse form of Walsh ordering is made by analyzing and comparing with these images.
联系方式
- 《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.
