Binary Tree’s Recursion Traversal Algorithm and Its Improvement

Binary tree is a very important data structure in computer science. Some major properties are discussed. Both recursive and non-recursive traversal methods of binary tree are discussed in detail. Some improvements in programming are proposed.

Bi-slotted Binary Tree Algorithm with Stack for Radio Frequency Identification Tag Anti-Collision

A radio frequency identification (RFID) reader will fail to identify tags if a collision occurs. This paper proposes a bi-slotted binary tree algorithm (BSBTA) with stack for RFID tag anti-collision to improve the performance of binary tree algorithm (BTA). In BSBTA, the reader detects collisions by Manchester code and stores colliding prefixes in a stack. The query is composed of a two-bit prefix and an index value. Following every reader query, there are two timeslots for tags whose pointers and identities (IDs) match the query to respond, one for the tag whose next bit is 0 and the other for the tag with 1 as its next bit. Performance analysis and evaluation are also given. The time complexity and the communication complexity of BTA and BSBTA are derived. The simulation results compare the performance of BSBTA with several related anti-collision algorithms. It is shown that BSBTA outperforms BTA in terms of the average number of responded bits and timeslots for one tag identification.

Science Letters:Binary tree of posterior probability support vector machines

Posterior probability support vector machines (PPSVMs) prove robust against noises and outliers and need fewer storage support vectors (SVs). Gonen et al. (2008) extended PPSVMs to a multiclass case by both single-machine and multimachine approaches. However, these extensions suffer from low classification efficiency, high computational burden, and more importantly, unclassifiable regions. To achieve higher classification efficiency and accuracy with fewer SVs, a binary tree of PPSVMs for the multiclass classification problem is proposed in this letter. Moreover, a Fisher ratio separability measure is adopted to determine the tree structure. Several experiments on handwritten recognition datasets are included to illustrate the proposed approach. Specifically, the Fisher ratio separability accelerated binary tree of PPSVMs obtains overall test accuracy, if not higher than, at least comparable to those of other multiclass algorithms, while using significantly fewer SVs and much less test time.

Embedding Binary Tree in VLSI/WSI Processor Array

Many reconfiguration schemes for fault-tolerant binary tree architectures have been proposed in the lite..t.re[1-6]. The VLSI layouts of most previous studies are based on the classical H-tree layout, resulting in low area utilization and likely an unnecessarily high manufacturing cost simply due to the waste of a significaot portion of silicon area. In this paper, we present an area-efficient approach to the reconfigurable binary tree architecture. Area utilization and interconnection complexity of our design compare favorably with the other known approaches. In the reliability analysis, we take ioto arcount the faCt that accepted chips (after fabrication) are with dmereot degrees of redundancy initially, so as to obtain results which better reflect real situations.

Prefix Subsection Matching Binary Algorithm in Passive RFID System

Identifying speed,tag average response times and reliability are the most important capabilities in passive RFID(radio frequency identification) system.QT(query tree) is a famous algorithm for lowest-cost RFID tags,but its shortcoming is high searching delay and high tag average response times.A prefix subsection matching binary(PSMB) algorithm based on QTalgorithm is proposed.The key idea of PSMB anti-collision algorithm is that,during searching phase,a given reader uses the particular tags ID,which has been searched out formerly,to shorten searching delay and depress tag average response times.The idea of PSMB algorithm can be described as follows.Usually,tag ID is composed of several subsections which have different meanings.Based on the tags ID searched out formerly,a given reader builds a prefix database.In subsequent searching phase,the reader uses its prefix database to deduce searching space of tag ID.Simulation results show that identification delay of PSMB algorithm is about 1/3 of QTalgorithm,tag average response times is about 1/4 of QTalgorithm,and system throughput rate is treble QTalgorithm.

An Improved Treed Gaussian Process

Many black box functions and datasets have regions of different variability. Models such as the Gaussian process may fall short in giving the best representation of these complex functions. One successful approach for modeling this type of nonstationarity is the Treed Gaussian process [1], which extended the Gaussian process by dividing the input space into different regions using a binary tree algorithm. Each region became its own Gaussian process. This iterative inference process formed many different trees and thus, many different Gaussian processes. In the end these were combined to get a posterior predictive distribution at each point. The idea was that when the iterations were combined, smoothing would take place for the surface of the predicted points near tree boundaries. We introduce the Improved Treed Gaussian process, which divides the input space into a single main binary tree where the different tree regions have different variability. The parameters for the Gaussian process for each tree region are then determined. These parameters are then smoothed at the region boundaries. This smoothing leads to a set of parameters for each point in the input space that specify the covariance matrix used to predict the point. The advantage is that the prediction and actual errors are estimated better since the standard deviation and range parameters of each point are related to the variation of the region it is in. Further, smoothing between regions is better since each point prediction uses its parameters over the whole input space. Examples are given in this paper which show these advantages for lower-dimensional problems.

Fast,Exact and Robust Set Operations on Polyhedrons Using Localized Constructive Solid Geometry Trees

Regularized Boolean operations have been widely used in 3D modeling systems. However, evaluating Boolean operations may be quite numerically unstable and time consuming, especially for iterated set operations. A novel and unified technique is proposed in this paper for computing single and iterated set operations efficiently, robustly and exactly. An adaptive octree is combined with a nested constructive solid geometry （CSG） tree by this technique. The intersection handling is restricted to the cells in the octree where intersection actually occurs. Within those cells, a CSG tree template is instanced by the surfaces and the tree is converted to planebased binary space partitioning （BSP） for set evaluation; Moreover, the surface classification is restricted to the ceils in the octree where the surfaces only come from a model and are within the bounding-boxes of other polyhedrons. These two ways bring about the efficiency and scalability of the operations, in terms of runtime and memory. As all surfaces in such a cell have the same classification relation, they are classified as a whole. Robustness and exactness are achieved by integrating plane-based geometry representation with adaptive geometry predicate technique in intersection handling, and by applying divide-and-conquer arithmetic on surface classification. Experimental results demonstrate that the proposed approach can guarantee the robustness of Boolean computations and runs faster than other existing approaches.

New multi-pattern matching algorithm

The traditional multiple pattern matching algorithm, deterministic finite state automata, is implemented by tree structure. A new algorithm is proposed by substituting sequential binary tree for traditional tree. It is proved by experiment that the algorithm has three features, its construction process is quick, its cost of memory is small. At the same time, its searching process is as quick as the traditional algorithm. The algorithm is suitable for the application which requires preprocessing the patterns dynamically.

Novel load balancing DHT scheme for the heterogeneous system

The capacities of the nodes in the peer-to-peer system are strongly heterogeneous, hence one can benefit from distributing the load, based on the capacity of the nodes. At first a model is discussed to evaluate the load balancing of the heterogeneous system, and then a novel load balancing scheme is proposed based on the concept of logical servers and the randomized binary tree, and theoretical guarantees are given. Finally, the feasibility of the scheme using extensive simulations is proven.

A Physical Layer Network Coding Based Tag Anti-Collision Algorithm for RFID System

In RFID(Radio Frequency IDentification)system,when multiple tags are in the operating range of one reader and send their information to the reader simultaneously,the signals of these tags are superimposed in the air,which results in a collision and leads to the degrading of tags identifying efficiency.To improve the multiple tags’identifying efficiency due to collision,a physical layer network coding based binary search tree algorithm(PNBA)is proposed in this paper.PNBA pushes the conflicting signal information of multiple tags into a stack,which is discarded by the traditional anti-collision algorithm.In addition,physical layer network coding is exploited by PNBA to obtain unread tag information through the decoding operation of physical layer network coding using the conflicting information in the stack.Therefore,PNBA reduces the number of interactions between reader and tags,and improves the tags identification efficiency.Theoretical analysis and simulation results using MATLAB demonstrate that PNBA reduces the number of readings,and improve RFID identification efficiency.Especially,when the number of tags to be identified is 100,the average needed reading number of PNBA is 83%lower than the basic binary search tree algorithm,43%lower than reverse binary search tree algorithm,and its reading efficiency reaches 0.93.

A novel binary image representation algorithm by using NAM and coordinate encoding procedure and its application to area calculation

We propose a novel binary image representation algorithm using the non-symmetry and anti-packing model and the coordinate encoding procedure （NAMCEP）. By tak- ing some idiomatic standard binary images in the field of image processing as typical test objects, and by comparing our proposed NAMCEP representation with linear quadtree （LQT）, binary tree （Bintree）, non-symmetry and anti-packing model （NAM） with K-lines （NAMK）, and NAM representa- tions, we show that NAMCEP can not only reduce the aver- age node, but also simultaneously improve the average com- pression. We also present a novel NAMCEP-based algorithm for area calculation and show experimentally that our algo- rithm offers significant improvements.

Framed slotted ALOHA with grouping tactic and binary selection for anti-collision in RFID systems

In radio frequency identification （RFID） systems, tag collision arbitration is a significant issue for fast tag identification. This article proposes a novel tag anti-collision algorithm called framed slotted ALOHA with grouping tactic and binary selection （GB-FSA）. The novelty of GB-FSA algorithm is that the reader uses binary tree algorithm to identify the tags according to the collided slot counters information. Furthermore, to save slots, tags are randomly divided into several groups based on the number of collided binary bits in the identification codes （IDs） of tags, and then only the number of the first group of tags is estimated. Performance analysis and simulation results show that the GB-FSA algorithm improves the identification efficiency by 9.9%-16.3% compared to other ALOHA-based tag anti-collision algorithms when the number of tags is 1000.

The General Facility Location Problem with Connectivity on Trees

In this note we study the general facility location problem with connectivity. We present an O（np2）-time algorithm for the general facility location problem with connectivity on trees. Furthermore,we present an O（np）-time algorithm for the general facility location problem with connectivity on equivalent binary trees.

Concurrent Manipulation of Expanded AVL Trees

The concurrent manipulation of an expanded AVL tree (EAVL tree) is considered in this paper. The presented system can support any number of concurrent processes which perform searching, insertion and deletion on the tree. Simulation results indicate the high performance of the system. Elaborate techniques are used to achieve such a system unawilable based on any known algorithms. Methods developed in this paper may provide new insights into other problems in the area of concurrent search structure manipulation.

Multi-class Classification Methods of Enhanced LS-TWSVM for Strip Steel Surface Defects

Considering strip steel surface defect samples, a multi-class classification method was proposed based on enhanced least squares twin support vector machines （ELS-TWSVMs） and binary tree. Firstly, pruning region samples center method with adjustable pruning scale was used to prune data samples. This method could reduce classifierr s training time and testing time. Secondly, ELS-TWSVM was proposed to classify the data samples. By introducing error variable contribution parameter and weight parameter, ELS-TWSVM could restrain the impact of noise sam- ples and have better classification accuracy. Finally, multi-class classification algorithms of ELS-TWSVM were pro- posed by combining ELS-TWSVM and complete binary tree. Some experiments were made on two-dimensional data- sets and strip steel surface defect datasets. The experiments showed that the multi-class classification methods of ELS-TWSVM had higher classification speed and accuracy for the datasets with large-scale, unbalanced and noise samples.

High order modulation format identification based on compressed sensing in optical fiber communication system

We propose a method of modulation format identification based on compressed sensing using a high-order cyclic cumulant combined with a binary tree classifier.Through computing the fourth-order cyclic cumulant of the pretreated band signal,which is obtained by compressed sensing with the sampling rate much less than the Nyquist sampling value,the feature vector for classification is extracted.Simulations are carried out in the optical coherent fiber communication system with different modulation formats of multiple phase-shift keying and multiple quadrature amplitude modulation.The results indicate that this method can identify these modulation formats correctly and efficiently.Meanwhile,the proposed method is insensitive to laser phase noise and signal noise.

Adaptive TDMA slot assignment protocol for vehicular ad-hoc networks

This paper proposes a novel adaptive time division vehicular ad-hoc networks. ATSA divides different sets multiple access （TDMA） slot assignment protocol （ATSA） for of time slots according to vehicles moving in opposite directions. When a node accesses the networks, it choices a frame length and competes a slot based on its direction and location to communication with the other nodes. Based on the binary tree algorithm, the frame length is dynamically doubled or shortened, and the ratio of two slot sets is adjusted to decrease the probability of transmission collisions. The theoretical analysis proves ATSA protocol can reduce the time delay at least 20% than the media access control protocol for vehicular ad-hoc networks （VeMAC） and 30% than the ad-hoc. The simulation experiment shows that ATSA has a good scalability and the collisions would be reduced about 50% than VeMAC, channel utilization is significantly improved than several existing protocols.

Multi-QoS Aware Automatic Service Composition

Almost all current automatic service composition （ASC） algorithms consider only single nonfunctional requirements, namely quality of service （QoS）, which cannot satisfy the real application. This paper proposes MAT （multi-QoS aware top-K ASC） algorithm to realize the high-efficiency exploring and rank- ing of composition scheme by synthesizing more nonfunctional goals. MAT algorithm explores composition schemes by the sky- line technique based on tape model and ranks these schemes by a modified binary tree. Using Web service challenge （WSC） 2009 dataset, we verify the performance of MAT algorithm and the experimental result is even close to the current fastest ASC algo- rithm considering only single QoS.

Extending STL with Efficient Data Structures

The Standard Template Library (STL) is a C++ library that provides a set of wellstructured generic C++ components that work together. Based on its well-structured design, STL can be extended by adding new generic algorithms or new generic containers. In this paper, the work on extending STL by adding several efficient cofitainer classes for threaded binary search trees is discussed. It is shown that the addition of threads signilicantly increases the efficiency of some important access operations on the binary tree containers. In general, significant gain in efficiency can be expected in situations where the data structures are relatively stable, that is, the data structures are looked up often but modified little.

New method in information processing for maintaining an efficient dynamic ordered set

This paper investigates how to maintain an efficient dynamic ordered set of bit strings, which is an important problem in the field of information search and information processing. Generally, a dynamic ordered set is required to support 5 essential operations including search, insertion, deletion, max-value retrieval and next-larger-value retrieval. Based on previous research fruits, we present an advanced data structure named rich binary tree （RBT）, which follows both the binary-search-tree property and the digital-search-tree property. Also, every key K keeps the most significant difference bit （MSDB） between itself and the next larger value among K＇s ancestors, as well as that between itself and the next smaller one among its ancestors. With the new data structure, we can maintain a dynamic ordered set in O（L） time. Since computers represent objects in binary mode, our method has a big potential in application. In fact, RBT can be viewed as a general-purpose data structure for problems concerning order, such as search, sorting and maintaining a priority queue. For example, when RBT is applied in sorting, we get a linear-time algorithm with regard to the key number and its performance is far better than quick-sort. What is more powerful than quick-sort is that RBT supports constant-time dynamic insertion/deletion.