We propose a method for adaptively selecting merge candidates for the geometric partitioning mode (GPM) in versatile video coding (VVC). The conventional GPM contributes to improved coding efficiency and subjective quality by partitioning the block into two nonrectangular partitions with motion vectors. The motion vector of the GPM is encoded as an index of the merge candidate list, but it does not consider that the GPM partitions are nonrectangular. In this paper, the distribution of merge candidates was evaluated for each GPM mode and partition, and a characteristic bias was revealed. To improve the coding efficiency of VVC, the proposed method allows GPM to select merge candidates that are specific to the partition. This method also introduces adaptive reference frame selection using template matching of adjacent samples. Following common test conditions in the Joint Video Experts Team (JVET), the experimental results showed an improvement in coding efficiency, with a bitrate savings of 0.16%, compared to the reference software for exploration experiments on enhanced compression beyond VVC capability in the JVET.

Memory-efficient Internet Protocol (IP) lookup with high speed is essential to achieve link-speed packet forwarding in IP routers. The rapid growth of Internet traffic and the development of optical link technologies have made IP lookup a major performance bottleneck in core routers. In this paper, we propose a new IP route lookup architecture based on hardware called Prefix-Route Trie (PR-Trie), which supports both IPv4 and IPv6 addresses. In PR-Trie, we develop a novel structure called Overlapping Hybrid Trie (OHT) to perform fast longest-prefix-matching (LPM) based on Multibit-Trie (MT), and a hash-based level matching query used to achieve only one off-chip memory access per lookup. In addition, the proposed PR-Trie also supports fast incremental updates. Since the memory complexity in MT-based IP lookup schemes depends on the level-partitioning solution and the data structure used, we develop an optimization algorithm called Bitmap-based Prefix Partitioning Optimization (BP2O). The proposed BP2O is based on a heuristic search using Ant Colony Optimization (ACO) algorithms to optimize memory efficiency. Experimental results using real-life routing tables prove that our proposal has superior memory efficiency. Theoretical performance analyses show that PR-Trie outperforms the classical Trie-based IP lookup algorithms.

Geometric partitioning mode (GPM) is a new inter prediction tool adopted in versatile video coding (VVC), which is the latest video coding of international standard developed by joint video expert team in 2020. Different from the regular inter prediction performed on rectangular blocks, GPM separates a coding block into two regions by the pre-defined 64 types of straight lines, generates inter predicted samples for each separated region, and then blends them to obtain the final inter predicted samples. With this feature, GPM improves the prediction accuracy at the boundary between the foreground and background with different motions. However, GPM has room to further improve the prediction accuracy if the final predicted samples can be generated using not only inter prediction but also intra prediction. In this paper, we propose a GPM with inter and intra prediction to achieve further enhanced compression capability beyond VVC. To maximize the coding performance of the proposed method, we also propose the restriction of the applicable intra prediction mode number and the prohibition of applying the intra prediction to both GPM-separated regions. The experimental results show that the proposed method improves the coding performance gain by the conventional GPM method of VVC by 1.3 times, and provides an additional coding performance gain of 1% bitrate savings in one of the coding structures for low-latency video transmission where the conventional GPM method cannot be utilized.

Human gait analysis has been widely used in medical and health fields. It is essential to extract spatio-temporal gait features (e.g., single support duration, step length, and toe angle) by partitioning the gait phase and estimating the footprint position/orientation in such fields. Therefore, we propose a method to partition the gait phase given a foot position sequence using mutually constrained piecewise linear approximation with dynamic programming, which not only represents normal gait well but also pathological gait without training data. We also propose a method to detect footprints by accumulating toe edges on the floor plane during stance phases, which enables us to detect footprints more clearly than a conventional method. Finally, we extract four spatial/temporal gait parameters for accuracy evaluation: single support duration, double support duration, toe angle, and step length. We conducted experiments to validate the proposed method using two types of gait patterns, that is, healthy and mimicked hemiplegic gait, from 10 subjects. We confirmed that the proposed method could estimate the spatial/temporal gait parameters more accurately than a conventional skeleton-based method regardless of the gait pattern.

This paper proposes an efficient server selection scheme in successive participation scenario with participating-domain segmentation. The scheme is utilized by distributed processing systems for real-time interactive communication to suppress the communication latency of a wide-area network. In the proposed scheme, users participate for server selection one after another. The proposed scheme determines a recommended server, and a new user selects the recommended server first. Before each user participates, the recommended servers are determined assuming that users exist in the considered regions. A recommended server is determined for each divided region to minimize the latency. The new user selects the recommended available server, where the user is located. We formulate an integer linear programming problem to determine the recommended servers. Numerical results indicate that, at the cost additional computation, the proposed scheme offers smaller latency than the conventional scheme. We investigate different policies to divide the users' participation for the recommended server finding process in the proposed scheme.

Due to most of the existing graph repartitioning methods are known for poor efficiency in distributed environments. In this paper, we introduce a new graph repartitioning method with two phases in distributed environments. In the first phase, a local method is designed to identify all the potential candidate vertices that should be moved to the other partitions at once in each partition locally. In the second phase, a streaming graph processing model is adopted to reassign the candidate vertices to achieve lightweight graph repartitioning. During the reassignment of the vertex, we propose an objective function to balance both the load balance and the number of crossing edges among the distributed partitions. The experimental results with a large set of real word and synthetic graph datasets show that the communication cost can be reduced by nearly 1 to 2 orders of magnitude compared with the existing methods.

The emerging Versatile Video Coding (VVC) standard currently adopts Triangular Partitioning Mode (TPM) to make more flexible inter prediction. Due to the motion search and motion storage for TPM, the complexity of the encoder and decoder is significantly increased. This letter proposes two simplifications of TPM for reducing the complexity of the current design. One simplification is to reduce the number of combinations of motion vectors for both partitions to be checked. The method gives 4% encoding time decrease with negligible BD-rate loss. Another one is to remove the reference picture remapping process in the motion vector storage of TPM. It reduces the complexity of the encoder and decoder without a BD-rate change for the random-access configuration.

In recent years we have witnessed an increasing demand to process queries on large datasets in Non-ordered Discrete Data Spaces (NDDS). In particular, one type of query in an NDDS, called box queries, is used in many emerging applications including error corrections in bioinformatics and network intrusion detection in cybersecurity. Effective indexing methods are necessary for efficiently processing queries on large datasets in disk. However, most existing NDDS indexing methods were not designed for box queries. Several recent indexing methods developed for box queries on a large NDDS dataset in disk are based on the popular data-partitioning approach. Unfortunately, a space-partitioning based indexing scheme, which is more effective for box queries in an NDDS, has not been studied before. In this paper, we propose a novel indexing method based on space-partitioning, called the BINDS-tree, for supporting efficient box queries on a large NDDS dataset in disk. A number of effective strategies such as node split based on minimum span and cross optimal balance, redundancy reduction utilizing a singleton dimension inheritance property, and a space-efficient structure for the split history are incorporated in the constructing algorithm for the BINDS-tree. Experimental results demonstrate that the proposed BINDS-tree significantly improves the box query I/O performance, comparing to that of the state-of-the-artdata-partitioning based NDDS indexing method.

This paper studies a variant of the graph partitioning problem, called the evacuation planning problem, which asks us to partition a target area, represented by a graph, into several regions so that each region contains exactly one shelter. Each region must be convex to reduce intersections of evacuation routes, the distance between each point to a shelter must be bounded so that inhabitants can quickly evacuate from a disaster, and the number of inhabitants assigned to each shelter must not exceed the capacity of the shelter. This paper formulates the convexity of connected components as a spanning shortest path forest for general graphs, and proposes a novel algorithm to tackle this multi-objective optimization problem. The algorithm not only obtains a single partition but also enumerates all partitions simultaneously satisfying the above complex constraints, which is difficult to be treated by existing algorithms, using zero-suppressed binary decision diagrams (ZDDs) as a compressed expression. The efficiency of the proposed algorithm is confirmed by the experiments using real-world map data. The results of the experiments show that the proposed algorithm can obtain hundreds of millions of partitions satisfying all the constraints for input graphs with a hundred of edges in a few minutes.

Recently, the join processing of large-scale datasets in MapReduce environments has become an important issue. However, the existing MapReduce-based join algorithms suffer from too much overhead for constructing and updating the data index. Moreover, the similarity computation cost is high because the existing algorithms partition data without considering the data distribution. In this paper, we propose two grid-based join algorithms for MapReduce. First, we propose a similarity join algorithm that evenly distributes join candidates using a dynamic grid index, which partitions data considering data density and similarity threshold. We use a bottom-up approach by merging initial grid cells into partitions and assigning them to MapReduce jobs. Second, we propose a k-NN join query processing algorithm for MapReduce. To reduce the data transmission cost, we determine an optimal grid cell size by considering the data distribution of randomly selected samples. Then, we perform kNN join by assigning the only related join data to a reducer. From performance analysis, we show that our similarity join query processing algorithm and our k-NN join algorithm outperform existing algorithms by up to 10 times, in terms of query processing time.

With the recent explosion of geographic data generated by smartphones, sensors, and satellites, a data storage that can handle the massive volume of data and support high-computational spatial queries is becoming essential. Although key-value stores efficiently handle large-scale data, they are not equipped with effective functions for supporting geographic data. To solve this problem, in this paper, we present G-HBase, a high-performance geographical database based on HBase, a standard key-value store. To index geographic data, we first use Geohash as the rowkey in HBase. Then, we present a novel partitioning method, namely binary Geohash rectangle partitioning, to support spatial queries. Our extensive experiments on real datasets have demonstrated an improved performance with k nearest neighbors and range query in G-HBase when compared with SpatialHadoop, a state-of-the-art framework with native support for spatial data. We also observed that performance of spatial join in G-HBase is on par with SpatialHadoop and outperforms SJMR algorithm in HBase.

Photo Diode Array (PDA) is the key semiconductor component expected to produce specified output voltage in photo couplers and photo sensors when the light is on. PDA partitioning problem, which is to design PDA, is: Given die area, anode and cathode points, divide the area into N cells, with identical areas, connected in series from anode to cathode. In this paper, we first make restrictions for the problem and reveal the underlying properties of necessary and sufficient conditions for the existence of solutions when the restrictions are satisfied. Then, we propose a method to solve the problem using recursive algorithm, which can be guaranteed to obtain a solution in polynomial time.

Human activity prediction has become a prerequisite for service recommendation and anomaly detection systems in a smart space including ambient assisted living (AAL) and activities of daily living (ADL). In this paper, we present a novel approach to predict the next-activity set in a multi-user smart space. Differing from the majority of the previous studies considering single-user activity patterns, our study considers multi-user activities that occur with a large variety of patterns. Its complexity increases exponentially according to the number of users. In the multi-user smart space, there can be inevitably multiple next-activity candidates after multi-user activities occur. To solve the next-activity problem in a multi-user situation, we propose activity set prediction rather than one activity prediction. We also propose activity sequence partitioning to reduce the complexity of the multi-user activity pattern. This divides an activity sequence into start, ongoing, and finish zones based on the features in the tendency of activity occurrences. The majority of the activities in a multi-user environment occur at the beginning or end, rather than the middle, of an activity sequence. Furthermore, the types of activities typically occurring in each zone can be sufficiently distinguishable. Exploiting these characteristics, we suggest a two-step procedure to predict the next-activity set utilizing a long short-term memory (LSTM) model. The first step identifies the zones to which current activities belong. In the next step, we construct three different LSTM models to predict the next-activity set in each zone. To evaluate the proposed approach, we experimented using a real dataset generated from our campus testbed. Our experiments confirmed the complexity reduction and high accuracy in the next-activity set prediction. Thus, it can be effectively utilized for various applications with context-awareness in a multi-user smart space.

This letter proposes a heuristic algorithm to select check variables, which are points of comparison for error detection, for soft-error tolerant datapaths. Our soft-error tolerance scheme is based on check-and-retry computation and an efficient resource management named speculative resource sharing (SRS). Starting with the smallest set of check variables, the proposed algorithm repeats to add new check variable one by one incrementally and find the minimum latency solution among the series of generated solutions. During the process, each new check variable is selected so that the opportunity of SRS is enlarged. Experimental results show that improvements in latency are achieved compared with the choice of the smallest set of check variables.

As seen in stream data processing, it is necessary to extract a particular data field from bulk data, where we can use a field-data extractor. Particularly, an (M,N)-field-data extractor reads out any consecutive N bytes from an M-byte register by connecting its input/output using multiplexers (MUXs). However, the number of required MUXs increases too much as the input/output byte widths increase. It is known that partitioning a MUX network leads to reducing the number of MUXs. In this paper, we firstly pick up a multi-layered MUX network, which is generated by repeatedly partitioning a MUX network into a collection of single-layered MUX networks. We show that the multi-layered MUX network is equivalent to the barrel shifter from which redundant MUXs and wires are removed, and we prove that the number of required MUXs becomes the smallest among MUX-network-partitioning based field-data extractors. Next, we propose a rotator-based MUX network for a field-data extractor, which is based on reading out a particular data in an input register to a rotator. The byte width of the rotator is the same as its output register and hence we no longer require any extra wires nor MUXs. By rotating the input data appropriately, we can finally have a right-ordered data into an output register. Experimental results show that a multi-layered MUX network reduces the number of required gates to construct a field-data extractor by up to 97.0% compared with the one using a naive approach and its delay becomes 1.8ns-2.3ns. A rotator-based MUX network with a control circuit also reduces the number of required gates to construct a field-data extractor by up to 97.3% compared with the one using a naive approach and its delay becomes 2.1ns-2.9ns.

This letter proposes a Light Space Partitioned Shadow Maps (LSPSMs) algorithm which implements shadow rendering based on a novel partitioning scheme in light space. In stead of splitting the view frustum like traditional Z-partitioning methods, we split partitions from the projection of refined view frustum in light space. The partitioning scheme is performed dual-directionally while limiting the wasted space. Partitions are created in dynamic number corresponding to the light and view directions. Experiments demonstrate that high quality shadows can be rendered in high efficiency with our algorithm.

File system workloads are increasing write-heavy. The growing capacity of RAM in modern nodes allows many reads to be satisfied from memory while writes must be persisted to disk. Today's sophisticated local file systems like Ext4, XFS and Btrfs optimize for reads but suffer from workloads dominated by microdata (including metadata and tiny files). In this paper we present an LSM-tree-based file system, RFS, which aims to take advantages of the write optimization of LSM-tree to provide enhanced microdata performance, while offering matching performance for large files. RFS incrementally partitions the namespace into several metadata columns on a per-directory basis, preserving disk locality for directories and reducing the write amplification of LSM-trees. A write-ordered log-structured layout is used to store small files efficiently, rather than embedding the contents of small files into inodes. We also propose an optimization of global bloom filters for efficient point lookups. Experiments show our library version of RFS can handle microwrite-intensive workloads 2-10 times faster than existing solutions such as Ext4, Btrfs and XFS.

We propose an exponent-based partitioning broadcast protocol (EPBP) to promise the prompt dissemination of emergency message (EM) in vehicular networks. EPBP divides the communication range into segments with different widths iteratively. The width varies corresponding to the exponential curve. The design makes the farther no-empty segment thinner, as a result of which the collision rate of candidates' contention for the relay node decreases and the one-hop message progress increases efficiently. In addition, we adjust the interval of back-off timers to avoid the spurious forwarding problem, and develop more accurate analytical models for the performance. Our simulation verifies these models and show a significant increase of EPBP compared with the state-of-the-art protocols. EM dissemination speed can be improved as 55.94% faster in dense vehicle networks, and packet delivery ratio has risen to higher than 99.99%.

This paper proposes an efficient lossless coding scheme for color video in RGB 4:4:4 format. For the R signal that is encoded before the other signals at each frame, we employ a block-adaptive prediction technique originally developed for monochrome video. The prediction technique used for the remaining G and B signals is extended to exploit inter-color correlations as well as inter- and intra-frame ones. In both cases, multiple predictors are adaptively selected on a block-by-block basis. For the purpose of designing a set of predictors well suited to the local properties of video signals, we also explore an appropriate setting for the spatiotemporal partitioning of a video volume.

An (M,N)-field-data extractor reads out any consecutive N bytes from an M-byte register by connecting its input/output using a multiplexer (MUX) network. It is used in packet analysis and/or stream data processing for video/audio data. In this letter, we propose an efficient MUX network for an (M,N)-field-data extractor. By bi-partitioning a simple MUX network into an upper one and a lower one, we can theoretically reduce the number of required MUXs without increasing the MUX network depth. Experimental results show that we can reduce the gate count by up to 92% compared to a naive approach.