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.

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.

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 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.

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.

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 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.

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.