Concurrent queues and stacks are important components of many software systems. They are well-known contended data structures due to intense contention on hotspots, resulting in limited performance and poor scalability. To achieve higher performance, several attempts applied the batching technique, which packs a group of standard operations into a single batch for execution, to lock-free queues and stacks built upon the linked list, but still inherited the contended compare-and-swap (CAS).

B + -trees are prevalent in traditional database systems due to their versatility and balanced structure. While binary search is typically utilized for branch operations, it may lead to inefficient cache utilization in main-memory scenarios. In contrast, trie-based index structures drive branch operations through prefix matching. While these structures generally produce fewer cache misses and are thus increasingly popular, they may underperform in range scans because of frequent pointer chasing. This paper proposes a new high-performance B + -tree variant called Feature B + -tree (FB + -tree ). Similar to employing bit or byte for branch operation in tries, FB + -tree progressively considers several bytes following the common prefix on each level of its inner nodes—referred to as features, which allows FB + -tree to benefit from prefix skewness. FB + -tree blurs the lines between B + -trees and tries, while still retaining balance. In the best case, FB + -tree almost becomes a trie, whereas in the worst case, it continues to function as a B + -tree. Meanwhile, a crafted synchronization protocol that combines the link technique and optimistic lock is designed to support efficient concurrent index access. Distinctively, FB + -tree leverages subtle atomic operations seamlessly coordinated with optimistic lock to facilitate latch-free updates, which can be easily extended to other structures. Intensive experiments on multiple workload-dataset combinations demonstrate that FB + -tree shows comparable lookup performance to state-of-the-art trie-based indexes and outperforms popular B + -trees by 2.3x ~ 3.7x under 96 threads. FB + -tree also exhibits significant potential on other workloads, especially update workloads under contention and scan workloads.

Abstract Concurrent hash tables are one of the fundamental building blocks for cloud computing. In this paper, we introduce lock-free modifications to in-memory bucketized cuckoo hashing. We present a novel concurrent strategy in designing a lock-free hash table, called LFBCH, that paves the way towards scalability and high space efficiency. To the best of our knowledge, this is the first attempt to incorporate lock-free technology into in-memory bucketized cuckoo hashing, while still providing worst-case constant-scale lookup time and extremely high load factor. All of the operations over LFBCH, such as get, put, “kick out” and rehash, are guaranteed to be lock-free, without introducing notorious problems like false miss and duplicated key. The experimental results indicate that under mixed workloads with up to 64 threads, the throughput of LFBCH is 14%–360% higher than other popular concurrent hash tables.

The relatively high cost of record deserialization is increasingly becoming the bottleneck of column-based storage systems in tree-structured applications [58]. Due to record transformation in the storage layer, unnecessary processing costs derived from fields and rows irrelevant to queries may be very heavy in nested schemas, significantly wasting the computational resources in large-scale analytical workloads. This leads to the question of how to reduce both the deserialization and IO costs of queries with highly selective filters following arbitrary paths in a nested schema. We present CORES (Column-Oriented Regeneration Embedding Scheme) to push highly selective filters down into column-based storage engines, where each filter consists of several filtering conditions on a field. By applying highly selective filters in the storage layer, we demonstrate that both the deserialization and IO costs could be significantly reduced. We show how to introduce fine-grained composition on filtering results. We generalize this technique by two pair-wise operations, rollup and drilldown, such that a series of conjunctive filters can effectively deliver their payloads in nested schema. The proposed methods are implemented on an open-source platform. For practical purposes, we highlight how to build a column storage engine and how to drive a query efficiently based on a cost model. We apply this design to the nested relational model especially when hierarchical entities are frequently required by ad hoc queries. The experiments, including a real workload and the modified TPCH benchmark, demonstrate that CORES improves the performance by 0.7×--26.9× compared to state-of-the-art platforms in scan-intensive workloads.

In this paper we study the problem of supporting similarity queries on a large number of records using a vector space model, where each record is a bag of tokens. We consider similarity functions that incorporate non-negative global token weights as well as record-specific token degrees. We develop a family of algorithms based on an inverted index for large data sets, especially for the case of using external storage such as hard disks or flash drives, and present pruning techniques based on various bounds to improve their performance. We formally prove the correctness of these techniques, and show how to achieve better pruning power by iteratively tightening these bounds to exactly filter dissimilar records. We conduct an extensive experimental study using real, large-scale data sets based on different storage platforms, including memory, hard disks, and flash drives. The results show that these algorithms and techniques can efficiently support similarity queries on large data sets.

In this paper, the problem of combined target model estimation and position-based visual servoing is addressed. The target object is assumed to be stationary with at least 3 distinguishable feature points. The midpoint triangulation method and a rough estimation method are developed for initial estimation of the target model and relative pose of target in current end-effector frame. A novel decoupled EKF-based online estimation algorithm is proposed to improve the target model and relative pose estimation simultaneously under continuous robot dynamic motion. This new method is robust to large initial estimation errors and provides consistent and accurate target model estimation for optimal pose estimation as required in position-based visual servoing. Experimental results are given to demonstrate the performance of the proposed method.

In this paper, the dynamic performance of position-based visual servoing methods in the Cartesian and image spaces are investigated. Two major classifications of the position-based method are analyzed. For motion control defined in the stationary desired end-effector frame, the shortest straight line Cartesian trajectory can be achieved, but the corresponding image trajectories are not controlled and may leave the camera field of view. For motion control defined in the moving current end-effector frame, the straight line Cartesian trajectory is not guaranteed, however, the im- age trajectories can be indirectly controlled in this method to move approximately along straight lines when the commanded orientation is small. Simulation results are given to compare the Cartesian and image trajectories of various implementations of the position-based method with those of the image-based and 2 1/2-D methods.

This paper presents a theoretical comparison of the stability and robustness of the two basic visual servoing methods, image-based and position-based visual servoing. A common framework for comparison based on the energy shaping plus damping injection methodology is presented. Previous stability results for the image-based method are extended to show the robustness of stability with respect to camera and target modeling, errors. Similar stability and robustness analyses are extended to the analysis of the position-based method. It is shown that both methods are locally asymptotically stable and robust with respect to camera and target modeling errors. However the stability boundary with respect to above errors has not been established.

In this paper, hybrid motion control and planning strategies for image constraints avoidance in robot visual servoing are presented. The proposed methods consist of a local switching control method and a global hybrid trajectory planning method. In local switching control, image local minima and image singularities can both be resolved by hybrid image-based and position-based visual servoing. The global hybrid trajectory planner is based on the artificial potential field method and various Cartesian and image constraints are incorporated. Based on the proposed methods, motion planning for image boundaries and image local minima avoidance is considered in this paper. Experimental and simulation results are given to demonstrate the efficiency of the proposed methods.