Search

Data security has become crucial to most enterprise and government applications due to the increasing amount of data generated, collected, and analyzed. Many algorithms have been developed to secure data storage and transmission. However, most existing solutions require multi-round functions to prevent differential and linear attacks. This results in longer execution times and greater memory consumption, which are not suitable for large datasets or delay-sensitive systems. To address these issues, this work proposes a novel algorithm that uses, on one hand, the reflection property of a balanced binary search tree data structure to minimize the overhead, and on the other hand, a dynamic offset to achieve a high security level. The performance and security of the proposed algorithm were compared to Advanced Encryption Standard and Data Encryption Standard symmetric encryption algorithms. The proposed algorithm achieved the lowest running time with comparable memory usage and satisfied the avalanche effect criterion with 50.1%. Furthermore, the randomness of the dynamic offset passed a series of National Institute of Standards and Technology (NIST) statistical tests.

The storage structure on the data block of the current blockchain systems is still a linked list. This traditional structure is one-way and is not efficient for query operation. In view of this, we proposed a novel searching structure based on a height balanced Binary Search Tree (BST). The data structure we proposed not only retains the characteristics of the traditional ledgers but also adds the function of quick query. Through the new data structure, we can quickly find the starting position of the search and start searching for all transaction records within a specified range of time from this position. We also made an analysis and comparisons in the final.

Pathfinding is the problem of finding the shortest path between a pair of nodes in a graph. In the context of uniform-cost undirected grid maps, heuristic search algorithms, such as A ☆ and weighted A ☆ ( W A ☆ ), have been dominantly used for pathfinding. However, the lack of knowledge about obstacle shapes in a gird map often leads heuristic search algorithms to unnecessarily explore areas where a viable path is not available. We refer to such areas in a grid map as blocked areas (BAs). This paper introduces a preprocessing algorithm that analyzes the geometry of obstacles in a grid map and stores knowledge about blocked areas in a memory-efficient balanced binary search tree data structure. During actual pathfinding, a search algorithm accesses the binary search tree to identify blocked areas in a grid map and therefore avoid exploring them. As a result, the search time is significantly reduced. The scope of the paper covers maps in which obstacles are represented as horizontal and vertical line-segments. The impact of using the blocked area knowledge during pathfinding in A ☆ and W A ☆ is evaluated using publicly available benchmark set, consisting of sixty grid maps of mazes and rooms. In mazes, the search time for both A ☆ and W A ☆ is reduced by 28 % , on average. In rooms, the search time for both A ☆ and W A ☆ is reduced by 30 % , on average. This is achieved while preserving the search optimality of A ☆ and the search sub-optimality of W A ☆ .

Multiclass decomposition algorithms are the means by which binary classification algorithms like support vector machine are used for multiclass classification problems. The popular multiclass decomposition algorithms like one against one (OAO), one against all (OAA), etc., perform the decomposition in a naive manner. This paper presents a novel heuristic-based decomposition algorithm that takes the Hausdorff distance between two classes to decide the decomposition. During the decomposition, rules are made to ensure a balanced binary search tree structure. To model the uncertainty and class noise present in the data, an unsupervised outlier detection technique has been used so that only possible non-outliers take part in the decomposition process. The presented algorithm has been evaluated and compared against OAO and OAA methods across 6 datasets. While evaluating the decomposition algorithms, fuzzy support vector machine has been used to model the class noise during each binary classification. The comparison shows that presented method not only provides comparable performance, but also in all cases, can classify the test samples with fewer average number of support vectors, thus leading to faster test performance. The paper further observes that the proposed approach can provide statistically better performance when the decomposition structure is learned only using the possible non-outliers, as compared to the scenario where the decomposition structure is learned using all samples.

In the binary space of large dimension we analyze the nearest neighbor search problem where the required point is a distorted version of one of the patterns. Previously it was shown that the only algorithms able to solve the set problem are the exhaustive search and the neural network search tree. For the given problem the speed of operation of the last algorithm is dozens of times larger comparing with the exhaustive search. Moreover, in the case of large dimensions the neural network tree can be regarded as an accurate algorithm since the probability of its error is so small that cannot be measured. In the present publication, we propose a modification of the scalar neural network tree allowing the speeding of the algorithm's operation up to hundred times without losses in its reliability.

In this paper, a novel approach which can map high-dimensional, real-valued data into low-dimensional, binary vectors is proposed to achieve fast approximate nearest neighbor (ANN) search. In our paper, the binary codes are required to preserve the relative similarity, which makes the Hamming distances of data pairs approximate their Euclidean distances in ANN search. Under such constraint, the distribution adaptive binary labels are obtained through a lookup-based mechanism. The perpendicular bisector planes located between two kinds of data whose binary labels are different on only one specific bit are considered as weak hash functions. As just two kinds of data are taken into consideration during generation of the weak hash functions, the final strong hash functions are formed by combining the weak ones through boosting scheme to map all kinds of data into binary codes effectively. Experimental results show that our algorithm can encode the out of samples efficiently, and the performances of our method are superior to many state-of-the-art methods.

This paper introduces the problem of communication pattern adaption for a distributed self-adjusting binary search tree. We propose a simple local algorithm that is closely related to the over thirty-year-old idea of splay trees and evaluate its adaption performance in the distributed scenario if different communication patterns are provided. To do so, the process of self-adjustment is modeled similarly to a basic network creation game in which the nodes want to communicate with only a certain subset of all nodes. We show that, in general, the game (i.e., the process of local adjustments) does not converge, and that convergence is related to certain structures of the communication interests, which we call conflicts. We classify conflicts and show that for two communication scenarios in which convergence is guaranteed, the self-adjusting tree performs well. Furthermore, we investigate the different classes of conflicts separately and show that, for a certain class of conflicts, the performance of the tree network is asymptotically as good as the performance for converging instances. However, for the other conflict classes, a distributed self-adjusting binary search tree adapts poorly.

Test data generation is a process of creating program inputs that satisfy specific testing criteria. Many works have been focused on test generation with respect to numeric and string data. Dynamic data structures, such as trees and linked lists, have been widely used in modern programming, but on which there are few studies presented. In general, generating a dynamic data structure is associated with a proper shape and valid values generation. It would be difficult to generate such dynamic data structures, as both shapes and values are necessary to be valid simultaneously. This paper focuses on binary tree structures and proposes a novel test generation approach that combines search based testing with constraint solving techniques. The approach creates the shapes of binary tree structures by using GA, and generates the values in their data fields by using constraint solving techniques. The experimental results show that the presented approach is promising and effective. Moreover, the studies investigate factors affecting the performance of the approach, and arrive at a conclusion that the test generation cost is cubic growing as the number of pointer constraints increases.

With the increasing resolution of digital elevation models (DEMs), computational efficiency problems have been encountered when extracting the drainage network of a large river basin at billion-pixel scales. The efficiency of the most time-consuming depression-filling pretreatment has been improved by using the O ( N log N ) complexity least-cost path search method, but the complete extraction steps following this method have not been proposed and tested. In this paper, an improved O ( N log N ) algorithm was proposed by introducing a size-balanced binary search tree (BST) to improve the efficiency of the depression-filling pretreatment further. The following extraction steps, including the flow direction determination and the upslope area accumulation, were also redesigned to benefit from this improvement. Therefore, an efficient and comprehensive method was developed. The method was tested to extract drainage networks of 31 river basins with areas greater than 500,000 km 2 from the 30-m-resolution ASTER GDEM and two sub-basins with areas of approximately 1000 km 2 from the 1-m-resolution airborne LiDAR DEM. Complete drainage networks with both vector features and topographic parameters were obtained with time consumptions in O ( N log N ) complexity. The results indicate that the developed method can be used to extract entire drainage networks from DEMs with billions of pixels with high efficiency.

A novel method is proposed to design an optimal binary tree using genetic algorithm.Our method is the first one for the global optimization of a binary tree.The results demonstrated that the classification accuracy of our method was improved. Support vector machine (SVM) with a binary tree architecture is popular since it requires the minimum number of binary SVM to be trained and tested. Many efforts have been made to design the optimal binary tree architecture. However, these methods usually construct a binary tree by a greedy search. They sequentially decompose classes into two groups so that they consider only local optimum at each node. Although genetic algorithm (GA) has been recently introduced in multiclass SVM for the local partitioning of the binary tree structure, the global optimization of a binary tree structure has not been tried yet. In this paper, we propose a global optimization method of a binary tree structure using GA to improve the classification accuracy of multiclass problem for SVM. Unlike previous researches on multiclass SVM using binary tree structures, our approach globally finds the optimal binary tree structure. For the efficient utilization of GA, we propose an enhanced crossover strategy to include the determination method of crossover points and the generation method of offsprings to preserve the maximum information of a parent tree structure. Experimental results showed that the proposed method provided higher accuracy than any other competing methods in 11 out of 18 datasets used as benchmark, within an appropriate time. The performance of our method for small size problems is comparable with other competing methods while more sensible improvements of the classification accuracy are obtained for the medium and large size problems.

The deployments of RFID system are seriously affected by collision caused by multiple tags responding simultaneously. To facilitate the resolution of collisions caused by densely distributed memoryless passive tags in successive cycles, based on the binary query tree protocol, this paper proposes a new Successive Scheme. In this scheme, the binary query tree constructed by the protocol will be reused. In the subsequent cycle, only the successful or idle binary query strings in the tree are adopted directly as the initial binary query strings, and these collision query strings in the tree are skipped. Due to the dynamic entrance and departure of tags, new nodes will be added to and abundant nodes will be removed from the tree. The performance of this Successive Scheme will be analyzed theoretically and examined with numeric simulations. Results indicate that in almost all cases, the Successive Scheme outperforms the commonly used binary query tree protocols in terms of system efficiency, message complexity, time, and time system efficiency. Especially when the tags stay stable, the system efficiency of the scheme is improved to 69.2%. Besides, simulation results also reveal that the scheme can deal efficiently with the case that the binary tag identifiers are in biased distribution.

CB tree represents the binary trie by a compact binary sequence. However, retrieval time grows fast since the more keys stored in the trie, longer the binary sequences are. In addition it is inefficient for frequent key insertion/deletion. HCB tree is a hierarchical CB tree consisting of small binary tries. However it can not avoid shift operations and have to scan an additional table to refer child or parent trie. In order to improve retrieval performance and avoid shift operations when keys are inserted or deleted, we in this paper represent each separated trie by a full binary trie and then assign the unique identifier to it. Finally the theoretical evaluations show that both the proposed approach and HCB tree provides better than CB tree for key retrieval. The proposed approach shows the highest performance in case of key insertion/deletion and moreover requires only 71%~89% of storage as compared with CB tree.

The K-nearest neighbor ( KNN ) rule is one of the most useful supervised classification methods, and is widely used in many pattern classification applications due to its simplicity. However, it faces prohibitive computational and storage requirements when dealing with large datasets. A reasonable way of alleviating this problem is to extract a small representative subset from the original dataset without reducing the classification accuracy. This means the most internal patterns are removed and the boundary patterns that can contribute to better classification accuracy are retained. To achieve this purpose, a new algorithm based on binary tree technique and some reduction operations is presented. The key issues of the proposed algorithm are how to build binary nearest neighbor search tree and design reduction strategies to keep the high classification accuracy patterns. In particular, firstly, we utilize several tree control rules and KNN rule to build a binary nearest neighbor tree of each random pattern. Secondly, according to the node locations in each binary nearest neighbor tree and the strategies of selection and replacement, different kinds of patterns as prototypes are obtained, which are close to class boundary regions or locate in the interior regions, and some internal patterns are generated. Finally, experimental results show that the proposed algorithm effectively reduces the number of prototypes while maintaining the same level of classification accuracy as the traditional KNN algorithm and other prototype algorithms. Moreover, it is a simple and fast hybrid algorithm for prototype reduction.

The feature extraction based on machine learning is significant in the detection system. The boundary information, the circumference and the area are the essential features in the identification and the classification of flaws. In order to get those information, this paper proposed a novel algorithm to get the boundary information using the boundary tracking, and to make each flaw independent by establishing a balanced binary search tree for data storage. By scanning the image and the image boundaries based on binarization transformation, there is no need to fill the region, nor need to use the chain code to count the number of regions and the boundary information. According to the established balanced binary search tree, we can calculate the number of the pixel of the area of each fault, the edge information of the boundary, and the circumference. The algorithm has the advantages of fast speed, less computation, better noise suppression and accurate results.

The paper describes new algorithm based on binary search tree using, which have average case time complexity O(N∗log(H)) where N is the size of the input set of points and H is the number of vertices found to be on the convex hull. The algorithm calculates the approximate center and stores all convex hull points in balanced binary search tree by the angle from it. Implementation of the new algorithm is written in C++ and tested against well-known algorithms. We show that our approach works better on low percentage of points in hull which is common case in convex hull calculation.

A non-blocking chromatic tree is a type of balanced binary search tree where multiple processes can concurrently perform search and update operations. We prove that a certain implementation has amortized cost $O(\dot{c} + \log n)$ for each operation, where $\dot{c}$ is the maximum number of concurrent operations during the execution and $n$ is the maximum number of keys in the tree during the operation. This amortized analysis presents new challenges compared to existing analyses of other non-blocking data structures., Comment: arXiv admin note: text overlap with arXiv:1712.05406 by other authors

Let G = ( V , E ) be a connected graph. The locating-chromatic number of G , denoted by χ L ( G ), is the cardinality of a minimum locating coloring of the vertex set V ( G ) such that all vertices have distinct coordinates. The results on locating-chromatic number of graphs are still limited. In particular, the locating-chromatic number of trees is not completely solved. Therefore, in this paper, we study the locating-chromatic number of any binary tree.

Memory reclamation for lock-based data structures is typically easy. However, it is a significant challenge for lock-free data structures. Automatic techniques such as garbage collection are inefficient or use locks, and non-automatic techniques either have high overhead, or do not work for many data structures. For example, subtle problems can arise when hazard pointers, one of the most common non-automatic techniques, are applied to many lock-free data structures. Epoch based reclamation (EBR), which is by far the most efficient non-automatic technique, allows the number of unreclaimed objects to grow without bound, because one crashed process can prevent all other processes from reclaiming memory. We develop a more efficient, distributed variant of EBR that solves this problem. It is based on signaling, which is provided by many operating systems, such as Linux and UNIX. Our new scheme takes $O(1)$ amortized steps per high-level operation on the data structure and $O(1)$ steps in the worst case each time an object is removed from the data structure. At any point, $O(mn^2)$ objects are waiting to be freed, where $n$ is the number of processes and $m$ is a small constant for most data structures. Experiments show that our scheme has very low overhead: on average 10\%, and at worst 28\%, for a balanced binary search tree over many thread counts, operation mixes and contention levels. Our scheme also outperforms a highly tuned implementation of hazard pointers by an average of 75\%. Typically, memory reclamation is tightly woven into lock-free data structure code. To improve modularity and facilitate the comparison of different memory reclamation schemes, we also introduce a highly flexible abstraction. It allows a programmer to easily interchange schemes for reclamation, object pooling, allocation and deallocation with virtually no overhead, by changing a single line of code., 27 pages, full version of paper published at PODC 2015

There are many storage structure available to store data in memory of many forms. These structures can be array, class, linked list with its various forms, Tree, Binary Tree, Binary Search Tree (BST), etc. These can be differentiated in two major forms. First one uses continuous memory allocation and the second one can occupy any free memory block by pointed by the other memory locations. An array occupies continuous memory space for storage purpose and the size should also be known before allocating the space. Perhaps we can use dynamic memory allocation methods for arrays but a Linked List provides better options. There is a disadvantage in Linked List, it does not allow to perform binary search operation on it. The Binary Search Tree is more efficient than the other mentioned data structures. BST provides the two way traversal direction but sometimes the structure of the BST can become unbalanced due to unprocessed ordering of inserted data. In this presented paper, the BST is considered as unbalanced if the number of levels is more than the levels which is required to hold the nodes. The unbalanced BST can lead to a straight tree structure with only one intermediate node at each and every level in the worst case scenario. The structure of BST depends on the insertion order of key elements. By changing the insertion order, BST can be made balanced. The proposed Estimated Level Based Balanced BST provides a solution for finding an insertion order of key elements which will not lead to unbalanced Balanced BST.

Traversing binary tree is an important algorithm in data structure. This paper analyses and discusses the recursive algorithm implementation of preorder-traversing binary tree through instance. It would contribute beginners to understand more deeply the process of preorder-traversing and enhance their programming.

Network tomography is a promising inference technique for network topology from end-to-end measurements. In this letter, we propose a novel binary tree pruning algorithm based on t-test to infer the network topology. A binary tree topology is first inferred using the existing Agglomerative Likelihood Tree (ALT) method, and then two samples t-test is applied to prune the binary tree, thus a general tree corresponding to the real topology is obtained. A lower bound on the correctly identified probability of the proposed method is derived. Simulation results show that the pruning method based on t-test outperforms the method which prunes the binary tree using a fixed threshold.

We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.

We show that for every $k$, the probability that a randomly selected vertex of a random binary search tree on $n$ nodes is at distance $k-1$ from the closest leaf converges to a rational constant $c_k$ as $n$ goes to infinity., 12 pages 1 figure

Binary codes play an important role in many computer vision applications. They require less storage space while allowing efficient computations. However, a linear search to find the best matches among binary data creates a bottleneck for large-scale datasets. Among the approximation methods used to solve this problem, the hierarchical clustering tree (HCT) method is a state-of the-art method. However, the HCT performs a hard assignment of each data point to only one cluster, which leads to a quantisation error and degrades the search performance. As a solution to this problem, an algorithm to create hierarchical soft clustering tree (HSCT) by assigning a data point to multiple nearby clusters in the Hamming space is proposed. Through experiments, the HSCT is shown to outperform other existing methods.

According to the issue of tag collision in the radio frequency identification technology, this paper proposes a binary tree search anti-collision algorithm, which takes different processing methods according to how many continuous collision. Compared with the dynamic binary tree search algorithm, the improved algorithm reduces the query information send by the reader. At the same time,the algorithm in the process of identifying tags reduces the query information, the query number and tag response times, so as to shorten the recognition time, further improve the search performance.

A improved binary tree SVM multi-class classification algorithm is proposed. Firstly, constructing the minimum hyper ellipsoid for each class sample in the feather space, and then generating optimal binary tree according to the hyper ellipsoid volume, training sub-classifier for every non-leaf node in the binary tree at the same time. For the sample to be classified, the sub-classifiers are used from the root node until one leaf node, and the corresponding class of the leaf node is the class of the sample. The experiments are done on the Statlog database, and the experimental results show that the algorithm improves classification precision and classification speed, especially in the situation that the number of class are more and their distribution area are equal approximately, the algorithm can greatly improve the classification precision and classification speed.

One of the classic data structures for storing point sets in R^2 is the priority search tree, introduced by McCreight in 1985. We show that this data structure can be made in-place, i.e., it can be stored in an array such that each entry stores only one point of the point set and no entry is stored in more than one location of that array. It combines a binary search tree with a heap. We show that all the standard query operations can be performed within the same time bounds as for the original priority search tree, while using only O(1) extra space. We introduce the min-max priority search tree which is a combination of a binary search tree and a min-max heap. We show that all the standard queries which can be done in two separate versions of a priority search tree can be done with a single min-max priority search tree. As an application, we present an in-place algorithm to enumerate all maximal empty axis-parallel rectangles amongst points in a rectangular region R in R^2 in O(mlogn) time with O(1) extra space, where m is the total number of maximal empty rectangles.

An anti-collision scheme in RFID systems is required to identify all the tags in the reader field. Deterministic tree search algorithms are mostly used to guarantee that all the tags in the field are identified, and achieve the best performance. Such tree search algorithms are based on the binary tree, and single bit arbitration is made at a time. In this letter, a novel tag anti-collision algorithm called M-ary query tree scheme (MQT) is proposed. An analytic model is developed for the response time to complete identifying all tags and then derive optimal M-ary tree for the minimum average response time. Our theoretical analysis and simulation results verify that MQT outperforms other tree-based protocols in terms of time complexity and communication overhead.

In this paper, we revisit a method to produce binary sequences using the most significant bit map from Z4 to the binary field. This method is useful for the construction of binary sequences with low correlation and large family size. There may be more cases where starting with Z4 could help researchers design new low correlation sequences for code-division multiple access application.

The paper presents the first concurrency-optimal implementation of a binary search tree (BST). The implementation, based on a standard sequential implementation of a partially-external tree, ensures that every schedule, i.e., interleaving of steps of the sequential code, is accepted unless linearizability is violated. To ensure this property, we use a novel read-write locking protocol that protects tree edges in addition to its nodes.

The general area of the paper is methods and data structures to efficiently avoid data duplication. In telecommunication networks operation support systems (OSS) process time series of counters related to the behaviour of network elements, such as failed location updates over the last 5 min. In general we may assume time series of key-value pairs with the key encoding the ordered sequence number of the particular counter.

We describe a general technique for obtaining provably correct, non-blocking implementations of a large class of tree data structures where pointers are directed from parents to children. Updates are permitted to modify any contiguous portion of the tree atomically. Our non-blocking algorithms make use of the LLX, SCX and VLX primitives, which are multi-word generalizations of the standard LL, SC and VL primitives and have been implemented from single-word CAS. To illustrate our technique, we describe how it can be used in a fairly straightforward way to obtain a non-blocking implementation of a chromatic tree, which is a relaxed variant of a red-black tree. The height of the tree at any time is O(c + log n), where n is the number of keys and c is the number of updates in progress. We provide an experimental performance analysis which demonstrates that our Java implementation of a chromatic tree rivals, and often significantly outperforms, other leading concurrent dictionaries.

Positive selection is one of artificial immune approaches, which finds application in network security. It relies on building detectors for protecting self cells, i.e. positive class objects. Random selection used to find candidates for detectors gives good results if the data is represented in a non-multidimensional space. For a higher dimension many attempts may be needed to find a detector. In an extreme case, the approach may fail due to not building any detector. This paper proposes an improved version of the positive selection approach. Detectors are constructed based on self cells in a deterministic way and they are stored in a binary tree structure. Thanks to this, each cell is protected by at least one detector regardless of the data dimension and size. Results of experiments conducted on network intrusion data (KDD Cup 1999 Data) and other datasets show that the proposed approach produces detectors of similar or better quality in a considerably shorter time compared with the probabilistic version. Furthermore, the number of detectors needed to cover the whole self space can be clearly smaller.

Constructing robust binary local feature descriptors are receiving increasing interest due to their binary nature, which can enable fast processing while requiring significantly less memory than their floating-point competitors. To bridge the performance gap between the binary and floating-point descriptors without increasing the computational cost of computing and matching, optimal binary weights are learning to assign to binary descriptor for considering each bit might contribute differently to the distinctiveness and robustness. Technically, a large-scale regularized optimization method is applied to learn float weights for each bit of the binary descriptor. Furthermore, binary approximation for the float weights is performed by utilizing an efficient alternatively greedy strategy, which can significantly improve the discriminative power while preserve fast matching advantage. Extensive experimental results on two challenging datasets (Brown dataset and Oxford dataset) demonstrate the effectiveness and efficiency of the proposed method.

P-sets consists of an internal P-set XF and an outer P-set XF and has dynamic characteristics, which result from the internal dynamic characteristics on XF and the outer dynamic characteristics on XF. In order to extend the application of the P-sets, the paper proposes an F-recursive binary tree through applying the dynamic characteristics for the P-set XF. Meanwhile, the paper provides the structures and characteristics for the F-recursive binary tree, including some properties and theorems about the F-recursive binary tree. The paper also gives the method of constructing F-recursive binary tree. The F-recursive binary tree has inward contraction characteristics and recursive characteristics. It can be used many research fields, such as information science and technology, artificial intelligence, knowledge discovery, as well as control theory and control engineering.

The method of carrier acquisition which we have used in this paper is a modified form of binary search algorithm. This modified search algorithm is a hybrid of two search algorithms which are "Binary search tree" and "Modified search tree". Firstly the modulated signal is received by the receiver where it is analyzed to acquire carrier. The receiver consists of two sections. One section uses the binary search tree process while the other section uses the modified search tree. Firstly binary search tree is used for carrier acquisition method and secondly the modified search tree is used. The overall tree diagram is a real-time tree diagram and it is formed during the process of carrier acquisition. This hybrid tree structure proves more helpful for carrier acquisition process as it is more accurate, low cost, less complex and less time consuming.

Ordered sets (and maps when data is associated with each key) are one of the most important and useful data types. The set-set functions union, intersection and difference are particularly useful in certain applications. Brown and Tarjan first described an algorithm for these functions, based on 2-3 trees, that meet the optimal Θ(m log (n/m+1)) time bounds in the comparison model (n and m ≤ n are the input sizes). Later Adams showed very elegant algorithms for the functions, and others, based on weight-balanced trees. They only require a single function that is specific to the balancing scheme---a function that joins two balanced trees---and hence can be applied to other balancing schemes. Furthermore the algorithms are naturally parallel. However, in the twenty-four years since, no one has shown that the algorithms, sequential or parallel are asymptotically work optimal. In this paper we show that Adams' algorithms are both work efficient and highly parallel (polylog span) across four different balancing schemes---AVL trees, red-black trees, weight balanced trees and treaps. To do this we use careful, but simple, algorithms for Join that maintain certain invariants, and our proof is (mostly) generic across the schemes.To understand how the algorithms perform in practice we have also implemented them (all code except Join is generic across the balancing schemes). Interestingly the implementations on all four balancing schemes and three set functions perform similarly in time and speedup (more than 45x on 64 cores). We also compare the performance of our implementation to other existing libraries and algorithms.

Fast Image Retrieval is required for many applications like Image Search and Shopping, especially for large datasets. Hashing addresses this problem by learning compact binary codes for images and using them as direct addresses into hash tables. In practice, using binary codes as addresses does not guarantee fast retrieval, as similar images are not mapped to the same binary code(address). We address this problem by presenting an efficient supervised hashing method that aims to explicitly map all images from the same class to a unique binary code to obtain fast retrieval. We refer to the binary codes of the images as 'Semantic Binary Codes' and the unique code for all same class images as 'Class Binary Code'. We formulate this intuitive objective 'directly' by minimizing the squared error criterion between the semantic binary codes and the corresponding class binary codes. We further propose a Deep Semantic Binary Code model that utilizes the class binary codes and show that we significantly outperform the state-of-the-art. We also propose a new class-based Hamming metric that dramatically reduces the retrieval times for larger databases and also improves the performance of the method by large margins.

Recent years have witnessed the increasing popularity of binary hashing for efficient similarity search in large-scale vision problems. This paper presents a novel Supervised Ranking-Based Hashing (SRH) method for efficient binary code learning to better capture the semantic nearest neighbors and improve the search performance. In particular, a family of hash functions is designed to preserve the semantic data structure in the original high-dimensional space by utilizing the semantic ranking order information induced by any specific query. The proposed hashing framework is obtained by jointly minimizing the empirical error over the ranking violation in the binary code space together with the quantization loss between the original data and the binary codes. Furthermore, an effective regularizer for maximizing the even binary code distribution is also taken into account in the optimization to generate more efficient and compact binary codes. Experimental results have demonstrated the proposed method outperforms the state-of-the-art.

Binary Search Tree (BST) is an important data structure for managing ordered data. Many algorithms---blocking as well as non-blocking---have been proposed for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations based on both external and internal representations of a search tree. An important step in executing an operation on a tree is to traverse the tree from top-to-down in order to locate the operation's window. A process may need to perform this traversal several times to handle any failures occurring due to other processes performing conflicting actions on the tree. Most concurrent algorithms that have proposed so far use a naïve approach and simply restart the traversal from the root of the tree. In this work, we present a new approach to recover from such failures more efficiently in a concurrent binary search tree based on internal representation using local recovery by restarting the traversal from the "middle" of the tree in order to locate an operation's window. Our approach is sufficiently general in the sense that it can be applied to a variety of concurrent binary search trees based on both blocking and non-blocking approaches. Using experimental evaluation, we demonstrate that our local recovery approach can yield significant speed-ups of up to 69% for many concurrent algorithms.

In this paper, a novel algorithm for shape matching based on the Hausdorff distance and a binary search tree data structure is proposed. The shapes are stored in a binary search tree that can be traversed according to a Hausdorff-like similarity measure that allows us to make routing decisions at any given internal node. Each node functions as a classifier that can be trained using supervised learning. These node classifiers are very similar to perceptrons, and can be trained by formulating a probabilistic criterion for the expected performance of the classifier, then maximizing that criterion. Methods for node insertion and deletion are also available, so that a tree can be dynamically updated. While offline training is time consuming, all online training and both online and offline testing operations can be performed in O(logn) time. Experimental results on pedestrian detection indicate the efficiency of the proposed method in shape matching.