The Counting Bloom Filter （CBF） is a kind of space-efficient data structure that extends a Bloom filter so as to allow approximate multiplicity queries on a dynamic multi-set. This paper evaluates the performance of...The Counting Bloom Filter （CBF） is a kind of space-efficient data structure that extends a Bloom filter so as to allow approximate multiplicity queries on a dynamic multi-set. This paper evaluates the performance of multiplicity queries of three simple CBF schemes-the Naive Counting Bloom Filter （NCBF）, the Space-Code Bloom Filter （SCBF） and the d-left Counting Bloom Filter （dlCBF）-using metrics of space complexity and counting error under both uniform and zipfian multiplicity distributions. We compare their counting error under same space complexity, and their space complexity when similar counting errors are achieved respectively. Our results show that dICBF is the best while SCBF is the worst in terms of both space-efficiency and accuracy. Furthermore, the performance gap between dlCBF and the others has a trend of being enlarged with the increment of space occupation or counting accuracy.展开更多
An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover＇s original quantum search algorithm is for finding single marked state with ...An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover＇s original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long＇s algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ＂duality computer＂ and show its advantage over other algorithms.展开更多
To solve the problem of strong nonlinear and motion model switching of maneuvering target tracking system in clutter environment, a novel maneuvering multi-target tracking algorithm based on multiple model particle fi...To solve the problem of strong nonlinear and motion model switching of maneuvering target tracking system in clutter environment, a novel maneuvering multi-target tracking algorithm based on multiple model particle filter is presented in this paper. The algorithm realizes dynamic combination of multiple model particle filter and joint probabilistic data association algorithm. The rapid expan- sion of computational complexity, caused by the simple combination of the interacting multiple model algorithm and particle filter is solved by introducing model information into the sampling process of particle state, and the effective validation and utilization of echo is accomplished by the joint proba- bilistic data association algorithm. The concrete steps of the algorithm are given, and the theory analysis and simulation results show the validity of the method.展开更多
On the basis of software testing tools we developed for programming languages, we firstly present a new control flowgraph model based on block. In view of the notion of block, we extend the traditional program\|based ...On the basis of software testing tools we developed for programming languages, we firstly present a new control flowgraph model based on block. In view of the notion of block, we extend the traditional program\|based software test data adequacy measurement criteria, and empirically analyze the subsume relation between these measurement criteria. Then, we define four test complexity metrics based on block. They are J\|complexity 0; J\|complexity 1; J\|complexity \{1+\}; J\|complexity 2. Finally, we show the Kiviat diagram that makes software quality visible.展开更多
The main purpose of this paper is to analyze the necessity of a Geographical Observatory of Atmospheric Pollution （GEOAP） in the Greek territory. The analysis performed is mainly focused on the benefits of the futur...The main purpose of this paper is to analyze the necessity of a Geographical Observatory of Atmospheric Pollution （GEOAP） in the Greek territory. The analysis performed is mainly focused on the benefits of the future function of the GEOAP to the environmental planning of the country and it could also provide an environmental management tool for the whole region. Measuring and mapping the pollution data and at the same time performing the geographical analysis of the complexity and the characteristics of natural and human environment can be useful tool in observation, management, and planning of the environmental policy of the country.展开更多
基金Supported by the National Grand Fundamental Research 973 Program of China (No.2007CB307100, No.2007CB 307102)
文摘The Counting Bloom Filter （CBF） is a kind of space-efficient data structure that extends a Bloom filter so as to allow approximate multiplicity queries on a dynamic multi-set. This paper evaluates the performance of multiplicity queries of three simple CBF schemes-the Naive Counting Bloom Filter （NCBF）, the Space-Code Bloom Filter （SCBF） and the d-left Counting Bloom Filter （dlCBF）-using metrics of space complexity and counting error under both uniform and zipfian multiplicity distributions. We compare their counting error under same space complexity, and their space complexity when similar counting errors are achieved respectively. Our results show that dICBF is the best while SCBF is the worst in terms of both space-efficiency and accuracy. Furthermore, the performance gap between dlCBF and the others has a trend of being enlarged with the increment of space occupation or counting accuracy.
基金4 Acknowledgements The author would like to thank G.L. Long for very helpful discussion, and thank J.Q. Yi for his generous help in plotting the function figures.
文摘An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover＇s original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long＇s algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ＂duality computer＂ and show its advantage over other algorithms.
基金Supported by the National Natural Science Foundation of China （60634030）, the National Natural Science Foundation of China （60702066, 6097219） and the Natural Science Foundation of Henan Province （092300410158）.
文摘To solve the problem of strong nonlinear and motion model switching of maneuvering target tracking system in clutter environment, a novel maneuvering multi-target tracking algorithm based on multiple model particle filter is presented in this paper. The algorithm realizes dynamic combination of multiple model particle filter and joint probabilistic data association algorithm. The rapid expan- sion of computational complexity, caused by the simple combination of the interacting multiple model algorithm and particle filter is solved by introducing model information into the sampling process of particle state, and the effective validation and utilization of echo is accomplished by the joint proba- bilistic data association algorithm. The concrete steps of the algorithm are given, and the theory analysis and simulation results show the validity of the method.
文摘On the basis of software testing tools we developed for programming languages, we firstly present a new control flowgraph model based on block. In view of the notion of block, we extend the traditional program\|based software test data adequacy measurement criteria, and empirically analyze the subsume relation between these measurement criteria. Then, we define four test complexity metrics based on block. They are J\|complexity 0; J\|complexity 1; J\|complexity \{1+\}; J\|complexity 2. Finally, we show the Kiviat diagram that makes software quality visible.
文摘The main purpose of this paper is to analyze the necessity of a Geographical Observatory of Atmospheric Pollution （GEOAP） in the Greek territory. The analysis performed is mainly focused on the benefits of the future function of the GEOAP to the environmental planning of the country and it could also provide an environmental management tool for the whole region. Measuring and mapping the pollution data and at the same time performing the geographical analysis of the complexity and the characteristics of natural and human environment can be useful tool in observation, management, and planning of the environmental policy of the country.
