ABSTRACT Concurrency control protocols play a vital role in ensuring the correctness of databases when transactions are processed in parallel. Plor is a non‐real‐time concurrency control protocol based on the 2‐phase locking protocol. Plor utilizes the Wound‐Wait scheme, a timestamp‐based scheme for deadlock prevention, as it provides lower tail latency. One problem of Plor with that it requires transactions to fetch timestamps from a single centralized atomic counter. This paper evaluates the implementation of the Fair Thread ID method (FairTID), a decentralized approach where transactions use the thread IDs as their timestamps instead. The FairTID method shows up to 1.5 times throughput improvement while reducing latency by 1.6 times and the deadline‐miss ratio by 1.67 times over the baseline protocol. The application of the method is formally verified for fairness reasoning.

This paper proposes Oze, a concurrency control protocol that handles heterogeneous workloads, including long-running update transactions. Oze explores a large scheduling space using a multi-version serialization graph to reduce false positives. Oze manages the graph in a decentralized manner to exploit many cores in modern servers. We further propose an OLTP benchmark, BoMB (Bill of Materials Benchmark), based on a use case in an actual manufacturing company. BoMB consists of one long-running update transaction and five short transactions that conflict with each other. Experiments using BoMB show that Oze can handle the long-running update transaction while achieving four orders of magnitude higher throughput than state-of-the-art optimistic and multi-version protocols and up to five times higher throughput than pessimistic protocols. We also show Oze performs comparably with existing techniques even in a typical OLTP workload, TPC-C, thanks to a protocol switching mechanism.

Index access is one of the dominant performance factors in transactional database systems. Many systems use a B+tree or one of its variants to handle point and range operations. This access pattern has room for performance improvement. Firstly, point operations can potentially be processed in O(1) with a hash table. Secondly, to ensure serializability of transactions, range operations incur overhead from phantom avoidance techniques that involve additional processing or synchronization, such as an extra traversal of the B+-tree. To address these issues, we propose a hybrid index architecture, Griffin. For point operations, Griffin has a hash table that provides access paths in O(1) time, along with a B+-tree. For phantom avoidance, Griffin employs a precision locking method, which does not involve additional traversal of the B+-tree. Despite its hybrid architecture, Griffin transparently provides linearizable operations and an interface of a single database index. We built a Griffin index combining a hash table and BwTree. Compared to a baseline index that is composed of a BwTree only, it achieves up to 3.1x higher throughput in a point operation dominant workload, and up to 5.4x higher throughput in a range operation dominant workload.

Summary This article proposes EPO‐R, which is an efficient garbage collection scheme designed for multi‐version concurrency control (MVCC) protocols. MVCC generates a version for each update operation, and it can exhaust physical memory for dynamically changing environments such as IoT payments. Eager pruning of obsolete versions (EPO) is a novel garbage collection technique for long‐term transactions. We found room for improvement in EPO, which triggers reclamation invocation. EPO is triggered for each write operation, and it wastes CPU resources. The proposed method EPO‐R is triggered on a read operation to address this issue. The result of experiments with 64 CPU cores and workloads with the combination of short‐term and long‐term transactions demonstrated that EPO‐R exhibited 6.3 times higher throughput than that of EPO. The reason for this can be explained by analyzing the number of unreclaimable versions.

Serializability is a standard to guarantee the correct execution of database operations. Since cloud databases do not always guarantee serializability, users must check for serializability on their own. However, the internal of cloud databases is a black box for users, making it difficult for them to make a judgment. This is a combinatorial optimization problem called the “black-box serializability problem which is a satisfiability problem” known to be NP-complete. Previous research has proposed an architecture that solves this problem using the SMT solver, a general-purpose solver for the satisfiability problem. Still, as the number of transactions increases, the search space will expand exponentially, so it becomes challenging to determine serializability. On the other hand, quantum annealing is excellent for fast-solving combinatorial optimization problems and can be applied to this satisfiability problem. This paper proposes a fast solver for the black-box serializability problem using quantum annealing. The evaluation results show that the proposed method is 751-890 times faster than state of the art method.

Transaction processing is widely used for many applications, such as credit card payments or social data analysis. To deal with these applications, scalable concurrency control protocols have been proposed. Modern techniques mainly target SEARCH and UPDATE operations. Unfortunately, the issues of improving the performance of SCAN, which is used for large size of data analysis, and avoiding phantom anomalies have not been addressed. In this paper, we propose a novel protocol for the efficient execution of transactional wide-range SCAN. The proposed protocol, node-locking, acquires locks of the leaf nodes in the tree index during SCAN to prevent phantoms. The proposed protocol avoids deadlocks due to locking by applying the WaitDie protocol to index nodes. On a workload containing SCAN transactions reading 10,000 records, Silo with the proposed protocol shows up to 743 times performance improvement over the original Silo protocol.

Plor is a hybrid concurrency control protocol between optimistic concurrency control and pessimistic 2-phase locking protocol. Plor utilizes the wound-wait scheme, a timestamps-based scheme for deadlock prevention, as it provides lower tail latency. One problem of Plor is that it requires transactions to fetch timestamps from a single centralized atomic counter. This paper evaluates Plor and its implementation of the Fair Thread ID method (FairTID), in which transactions use the thread IDs as their timestamps instead, in a real-time environment. The FairTID method shows up to 2 times performance improvement while reducing latency by 1.73 times and deadline-miss rate by 1.97 times over the baseline protocol.

TF is a core library in ROS that manages positional relationships between objects. TF has fundamental problems in that accesses are sequentially executed due to the giant locking and its interfaces' limited functionality. TF is designed for managing only a few objects, and it has two problems supporting such use cases as pedestrian prediction or traffic congestion avoidance. The first problem is poor operators, and the second problem is the generation of phantom anomalies. We address the first problem by designing a SQL-based interface with various powerful operators and the second problem by designing a phantom anomaly protocol based on ghost record protocols.

Bamboo is a state-of-the-art concurrency control protocol based on the 2-phase locking protocol. One problem of Bamboo is that it requires transactions to fetch timestamps from a single centralized atomic counter. To replace the concentrated access to it, each transaction should generate timestamps independently. This paper proposes thread-ID method (TID), which dismisses the process of fetching timestamps entirely by assigning an ID to each thread, and transactions use the thread IDs as their timestamps. In high-contention settings, the performance of TID plummets, but proposed optimization FairTID sustains the performance. The experiments measured an improvement of up to 60% from Bamboo with the proposed method.

In the Robot Operating System (ROS), a major middleware for robots, the Transform Library (TF) is a mandatory package that manages transformation information between coordinate systems by using a single-rooted directed tree and providing methods for registering and computing the information. However, the tree has two fundamental problems. The first is its poor scalability: since it accepts only a single thread at a time due to using a single giant lock for mutual exclusion, the access to the tree is sequential. Second, there is a lack of data freshness: it retrieves non-latest synthetic data when computing coordinate transformations because it prioritizes temporal consistency over data freshness. In this paper, we propose methods to solve these problems. First, we decentralize the giant lock to provide performance scalability and show that this results in a throughput 243 times higher than conventional TF on a read-only workload. Second, we design transactional methods based on serializable protocols that prevent anomalies, thus retrieving the freshest data. These transactional methods show a freshness up to 1276 times higher than the conventional one on a read-write combined workload.

Inclusion dependencies (IND) is an important problem in relational database, relevant to data integration, query optimization and various data management tasks. The discovery of IND has been addressed by many studies following different strategies, while IND detection still needs improvement as the complexity and diversity of real-life data increase. Conventional IND is only for column-to-column dimension, which is not applicable to lots of data processing tasks. The concept of dependency can be expanded. Based on the understanding of the conventional IND and approximate approach FAIDA, we present our algorithm for detecting tuple IND, converting column-to-column detection to row-to-row dimension, more in line with real-world data retrieval tasks in distributed system. Through probabilistic and accurate detection and the use of multi-threading, both accuracy and performance are guaranteed and IND detection performance is taken to a new level.

We herein propose three novel optimization methods to accelerate distributed transaction processing into a geographically distributed database. The first optimization involves the parallelization of the write-ahead logging protocol. It allows multiple worker threads to synchronize log entries to the storage device simultaneously without any dependencies. The second optimization involves the grouped transfer of log entries from the leader to followers. This reduces the number of transmissions and effectively uses the network bandwidth. The third optimization involves the separation of the worker thread logic. By breaking the logic into the prepare phase and the commit phase, the worker threads at the leader node run asynchronously in parallel without waiting for responses from the follower nodes. The experimental results demonstrated that the proposed method achieved more than 10 million tps and less than 100 ms with client interactions through the network. The CPU utilization was almost 100%, which implied a dramatic reduction in synchronization in worker threads.

This paper presents yet another concurrency control analysis platform, CCBench. CCBench supports seven protocols (Silo, TicToc, MOCC, Cicada, SI, SI with latch-free SSN, 2PL) and seven versatile optimization methods and enables the configuration of seven workload parameters. We analyzed the protocols and optimization methods using various workload parameters and a thread count of 224. Previous studies focused on thread scalability and did not explore the space analyzed here. We classified the optimization methods on the basis of three performance factors: CPU cache, delay on conflict, and version lifetime. Analyses using CCBench and 224 threads, produced six insights. The performance of optimistic concurrency control protocol for a read-only workload rapidly degrades as cardinality increases even without L3 cache misses. (I2) Silo can outperform TicToc for some write-intensive workloads by using invisible reads optimization. (I3) The effectiveness of two approaches to coping with conflict (wait and no-wait) depends on the situation. (I4) OCC reads the same record two or more times if a concurrent transaction interruption occurs, which can improve performance. (I5) Mixing different implementations is inappropriate for deep analysis. (I6) Even a state-of-the-art garbage collection method cannot improve the performance of multi-version protocols if there is a single long transaction mixed into the workload. On the basis of I4, we defined the read phase extension optimization in which an artificial delay is added to the read phase. On the basis of I6, we defined the aggressive garbage collection optimization in which even visible versions are collected. The code for CCBench and all the data in this paper are available online at GitHub.

Sequence operators are effective for efficiently combining multiple events when state recognition is performed by combining time series events. Since sensor data are inherently noisy, one can take a strict attitude to deal with them: it is conceivable that all of time series events are regarded as false positives. Then, all complex events should be constructed carefully. Such an attitude is called the skip-till-any-match model in the sequence operator. When using this model, huge amounts of potential complex events are generated. A sequence operator usually supports both Kleene closure and non-Kleene closure. While efficient methods have been studied for Kleene closure so far, that for non-Kleene closure have been still explored. In this paper, we propose the reduced expression method to improve the efficiency of sequence operator processing for the skip-till-any-match model. Experimental results showed that the processing time and memory size were more efficient compared with SASE, which is the conventional method, and that degree is up to several thousand times.

This paper proposes and examines the three in-memory shuffling methods designed to address problems in MapReduce shuffling caused by skewed data. Coupled Shuffle Architecture (CSA) employs a single pairwise all-to-all exchange to shuffle both blocks, units of shuffle transfer, and meta-blocks, which contain the metadata of corresponding blocks. Decoupled Shuffle Architecture (DSA) separates the shuffling of meta-blocks and blocks, and applies different all-to-all exchange algorithms to each shuffling process, attempting to mitigate the impact of stragglers in strongly skewed distributions. Decoupled Shuffle Architecture with Skew-Aware Meta-Shuffle (DSA w/ SMS) autonomously determines the proper placement of blocks based on the memory consumption of each worker process. This approach targets extremely skewed situations where some worker processes could exceed their node memory limitation. This study evaluates implementations of the three shuffling methods in our prototype in-memory MapReduce engine, which employs high performance interconnects such as InfiniBand and Intel Omni-Path. Our results suggest that DSA w/ SMS is the only viable solution for extremely skewed data distributions, but this solution is only valid on systems equipped with high performance interconnects. We also present a detailed investigation of the performance of CSA and DSA in various skew situations.

In this paper, we describe a use case applying a scientific workflow system and a distributed file system to improve the performance of telescope data processing. The application is pipeline processing of data generated by Hyper Suprime-Cam (HSC) which is a focal plane camera mounted on the Subaru telescope. In this paper, we focus on the scalability of parallel I/O and core utilization. The IBM Spectrum Scale (GPFS) used for actual operation has a limit on scalability due to the configuration using storage servers. Therefore, we introduce the Gfarm file system which uses the storage of the worker node for parallel I/O performance. To improve core utilization, we introduce the Pwrake workflow system instead of the parallel processing framework developed for the HSC pipeline. Descriptions of task dependencies are necessary to further improve core utilization by overlapping different types of tasks. We discuss the usefulness of the workflow description language with the function of scripting language for defining complex task dependency. In the experiment, the performance of the pipeline is evaluated using a quarter of the observation data per night (input files: 80 GB, output files: 1.2 TB). Measurements on strong scaling from 48 to 576 cores show that the processing with Gfarm file system is more scalable than that with GPFS. Measurement using 576 cores shows that our method improves the processing speed of the pipeline by 2.2 times compared with the method used in actual operation.

With the development of sensing devices, the size of data managed by human being has been rapidly increasing. To manage such huge data, relational database management system (RDBMS) plays a key role. RDBMS models the real world data as n-ary relational tables. Join operator is one of the most important relational operators, and its acceleration has been studied widely and deeply. How can an RDBMS provide such an efficient join operator? The performance improvement of join operator has been deeply studied for a decade, and many techniques are proposed already. The problem that we face is how to actually use such excellent techniques in real RDBMSs. We propose to implement an efficient join technique by the data transfer approach. The approach makes a hook point inside an RDBMS internal, and pulls data streams from the operator pipeline in the RDBMS, and applies our original join operator to the data, and finally returns the result to the operator pipeline in the RDBMS. The result of the experiment showed that our proposed method achieved 1.42x speedup compared with PostgreSQL. Our code is available on GitHub.

We proposed the idea of combining the Cicada concurrency control mechanism with P-WAL (parallel write-ahead logging) and experimentally evaluated the proposed control mechanism. Our results show that P-WAL can be combined suitably with Cicada without decreasing Cicada's performance. We then experimentally evaluated the most optimal parallel write-ahead logging parameter among (1) conservative lock release; (2) early lock release, the early release of locks on database objects; and (3) group commit, which writes the transaction log to storage all at once. The results show that early lock release and group commit were the most optimal parameters for the combination of Cicada and P-WAL.

The problem of scaling out relational join performance for large data sets in the database management system (DBMS) has been studied for years. Although in-memory DBMS engines can reduce load times by storing data in the main memory, join queries still remain computationally expensive. Modern graphics processing units (GPUs) provide massively parallel computing and may enhance the performance of such join queries; however, it is not clearyet in what condition relational joins perform well on GPUs. In this paper, we identify the performance characteristics of GPU computing for relational joins by implementing several well-known GPU-based join algorithms under various configurations. Experimental results indicate that the speedup ratio of GPU-based relational joins to CPU-based counterparts depends on the number of compute cores, the size of data sets, join conditions, and join algorithms. In the best case, the speedup ratios are up to 6.67 times for non-index joins, 9.41 times for sort index joins, and 2.55 times for hash joins. The execution time of GPU-based implementation for index joins, on the other hand, is only about 0.696 times less than the execution time of the CPU's counterparts.

In this study, we attempt to address the issue regarding the spatial join count, where in the number of particles around a halo is counted only once for a given simulation result. An efficient spatial index is necessary for accelerated counting; therefore, we propose a CPU optimized sort-tile-recursive R-tree that employs a parallel radix sort and node packing with thread pool and single instruction multiple data instructions. In an experiment conducted with astronomical data, the proposed method demonstrates an improvement in performance by 26.8 times compared with that using a conventional CPU optimized R-tree. We also propose a partial materialization approach to handle large amount of data that exceeds the capacity of main memory. To accelerate the approach, we propose a construct-search-destruct pipeline that exploits a thread pool to conceal the latency of the construction and destruction of the index. The pipelining method achieves an improvement in performance by 27.5 times compared with that of a conventional CPU optimized R-tree. All our codes are available on GitHub.

An array database is effective for managing and analyzing multidimensional scientific big data, and the window aggregate is an important operator in array databases. This paper proposes a method that exploits the scheme of incremental computation to accelerate the execution of window aggregates considerably. Six types of aggregate are improved using different designs of buffer tools to eliminate redundant computation. Our proposed recursive incremental computation method completely eliminates all redundant computation and achieves an improvement factor of the total window size compared with the naive method. This proposed method is fully implemented in SciDB. It improved performance by a factor of 10 on an earth science benchmark and by a factor of 64 on synthetic workloads with a certain data setting when compared with SciDB's built-in window operator.

We propose an efficient window aggregation method over multi-dimensional array data based on incremental computation. We improve several aggregations with different data structures exploited to achieve efficient computation: list for sum and avg, heap for max and min, and balanced binary search tree for percentile. We present time complexity analysis for the methods, and then evaluate performance with experiments in SciDB array database system with both synthetic and JRA55 meteorological dataset. Our analysis shows that performance improvement is proportional to the window size in the last dimension in theory, and the result of experiment is consistent with the analysis. In certain cases, it shows an acceleration factor more than 13 by the proposed method with percentile, while a factor over 28 with maximum.

This paper describes a prototype system of remote music therapy for elderly people with dementia using the latest communication technology in Japan. The system uses the latest high-speed optical network, called NGN (Next Generation Network) and the latest terminal especially for audio data communication called Hikari DUETTO NY1, which was released at the end of the last year. We did an experiment of the system using the real communication environment in this January between Tokyo and Osaka. The communication time of the system between Tokyo and Osaka was about 25.5 msec. Thus, we confirmed that the system was able to provide almost real-time audio data communication. Based on the result, the feasibility of music therapy activities, such as singing and exercises with music, using the system was examined. We confirmed that the singing activity which is the most important one in the music therapy was feasible.

One of a critical design issues for implementing handshake-join hardware is result collection performed by a merging network. To address the issue, we introduce an adaptive merging network. Our implementation achieves over 3 million tuples per second when the selectivity is 0.1. The proposed implementation attains up to 5.2x higher throughput than original handshake-join hardware. In this demonstration, we apply the proposed technique to filter out malicious packets from packet streams. To the best of our knowledge, our system is the fastest handshake join implementation on FPGA.

This paper proposes a processor architecture for DR-SPE, a dynamic reconfigurable stream processing engine. DR-SPE is special-purpose hardware for stream data processing, which achieves high processing performance by exploiting parallelism in the target query. It also handles query registration and execution order of operations at runtime. Available operations in DR-SPE are the same as those in Streams on Wires. In this paper, DR-SPE is implemented on a FPGA XC6VLX240T-1, and its performance is evaluated. The results of the evaluation show that DR-SPE achieves register modification within 506 μsec when the configuration path is driven at 1 Mbps, which is not achieved by Streams on Wires. DR-SPE also achieves flexibility and can support complicated queries by providing 10 × 10 operation units tiled onto an FPGA. DR-SPE achieves comparable operation throughput with Streams on Wires at the expense of requiring more LUTs.

Distributed stream processing engines (DSPEs) have recently been studied to meet the needs of continuous query processing. Because they are built on the cooperation of several stream processing engines (SPEs), node failures cause the whole system to fail. This paper proposes a new high-availability scheme called Adaptive Semi-Active Standby (A-SAS). A-SAS enables adaptive tradeoff between bandwidth usage and recovery time. This paper presents the properties of A-SAS and experimental results that suggest A-SAS effectiveness.

This paper proposes to share gesture contents among heterogeneous robots. In this paper, we classify gestures in two types; pointing gesture and track gesture. Criteria of classification is factors which are essential for each gesture. Pointing gestures are used for pointing somewhere around a robot. Trajectory of a gesture is important for track gesture. Track gestures can keep its essential factors by moving track horizontally or vertically. We made gesture translation algorithms for each classification and achieved sharing semantic information of gesture contents. We carried out quantitative evaluation with simulations, and qualitative evaluation with questionnaire.

This paper proposes a novel window operator, pattern-based window, for data stream processing. By using pattern-based windows, user-specified complex events can be extracted from data streams under the framework of continuous query language (CQL), which integrates the current data stream processing and event stream processing. In this paper, the pattern-based window is formally defined and the query language of pattern-based windows is designed. A simple pattern matching algorithm is introduced to show logical expression of the query language. We also give simple examples to show the usage of the query language by using pattern-based windows.

The paper proposes a new middleware named semantic sensor network which connects the variety of physically grounded applications to the information of the real world. Semantic sensor network infers and describes the state of an environment using logical expressions. The target which semantic sensor network describes is an environment where wireless sensor nodes are attached to daily items. The remarkable achievement of semantic sensor network is to employ explicitly the concept of a class and an instance on the sensor network so as to construct efficiently an interpretation model for sensor data and queries. We have developed two physically grounded applications on semantic sensor network; one is a GUI and the other is a robotic system. They use semantic sensor network to obtain information about the environment

For frequently data arriving data environment, this paper tackles the following three problems. (1) Maximizing throughput. (2) Minimizing logging time. (3) Minimizing blocking time. To solve these problems, this paper proposes Two Level Asynchronous Checkpointing technique. Furthermore this paper designs and implements the technique within DBMS and experiments are conducted by using the DBMS to evaluate the technique. The result of experiments show that remote logging provides better performance than disk logging, 10 times for (1), 17 times for (2). Furthermore, average blocking time is shown as 4.38 micro seconds.

Sensor database systems need to provide both freshness of data and persistence to the incoming sensor streams. To provide persistence, a disk based logging method has been widely used, however it is not applicable for sensor streams because of its tardiness. In this paper, we propose the light neighbor write ahead logging protocol(L-WAL) for sensor streams. The L-WAL is a refinement of the neighbor-WAL (N-WAL). The L-WAL needs two network interfaces and applies a relaxed protocol rather than a two phase commit protocol. Since the relaxed protocol weakens the guarantee of logging successes, we have incorporated a repair system and checker system to enhance the guarantee. The result of experiments shows that the L-WAL is about 2.13 times faster than the N-WAL when the number of concurrent sensor streams is 250 and the L-WAL can enhance the persistence of data almost for free, while the N-WAL needs to pay high cost.