Recent advances have demonstrated the effectiveness of graph-based machine learning on relational databases (RDBs) for predictive tasks. Such approaches require transforming RDBs into graphs, a process we refer to as RDB-to-graph modeling, where rows of tables are represented as nodes and foreign-key relationships as edges.Yet, effective modeling of RDBs into graphs remains challenging.Specifically, there exist numerous ways to model RDBs into graphs, and performance on predictive tasks varies significantly depending on the chosen graph model of RDBs.In our analysis, we find that the best-performing graph model can yield up to a 10\% higher performance compared to the common heuristic rule for graph modeling, which remains non-trivial to identify.To foster research on intelligent RDB-to-graph modeling, we introduce RDB2G-Bench, the first benchmark framework for evaluating such methods.We construct extensive datasets covering 5 real-world RDBs and 12 predictive tasks, resulting in around 50k graph model–performance pairs for efficient and reproducible evaluations.Thanks to our precomputed datasets, we were able to benchmark 10 automatic RDB-to-graph modeling methods on the $12$ tasks about 380$\times$ faster than on-the-fly evaluation, which requires repeated GNN training.Our analysis of the datasets and benchmark results reveals key structural patterns affecting graph model effectiveness, along with practical implications for effective graph modeling.Our datasets and code are available at https://github.com/chlehdwon/RDB2G-Bench.

The problem of assigning tasks to the processors of a distributed computing system such that the sum of execution and communication costs is minimized is discussed. This problem is known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. H.S. Stone's (1977) network flow approach for a two-processor system is extended to the case for a linear array of any number of processors. The task assignment problem for a linear array network is first transformed into the two-terminal network flow problem, and then solved by applying the Goldberg-Tarjan (1987) network flow algorithm in time no worse than O(n/sup 2/m/sup 3/ log n), where n and m are the number of processors and the number of tasks, respectively.>

A new parallel annealing scheme, stepwise-overlapped parallel annealing, is proposed. This can provide a massive speedup using a multiprocessor system with a large number of processors. It decomposes the annealing process by means of Markov chains. The annealing scheme of the systolic algorithm proposed by Aart et al. is improved. The improved annealing schedule keeps a good temperature profile even when a large number of processors are used. The communication pattern is also enhanced. The new parallel annealing algorithm is applied to floorplan design problems. Experimental results show that the new parallel annealing algorithm is highly effective for a large number of processors. The experimental results of the proposed algorithm are compared with those of other parallel annealing algorithms and the distributed genetic algorithm.

Abstract This paper proposes a parallel annealing algorithm, called step‐wise‐overlapped parallel annealing, that can provide a massive speed‐up utilizing a multiprocessor system with a large number of processors. We improve the parallel annealing scheme of the systolic algorithm that was proposed by Aart et al. Instead of the temperature decrement at each subchain, it decides the decrement ratio at the start of each Markov chain using the standard deviation of the cost distribution in the previous Markov chain of the full length. Thus the improved annealing schedule keeps a good temperature profile even with a large number of processors. We also enhance the communication pattern. The new parallel annealing algorithm has a simple communication pattern and thus less communication overheads. The decomposition strategy of this parallel annealing algorithm is independent of application problems. Experimental results of the step‐wise‐overlapped parallel annealing algorthm for the travelling salesman problems show high efficiencies even when a large number of processors are used; it produces near optimal solutions with a speedup of 70.8 by using 128 processors. It can be implemented efficiently on a message‐passing multiprocessor system with a large number of processors, such as a hypercube computer.

An improved implementation of clock synchronization of multiprocessor systems in the presence of malicious faults is proposed. The proposed hardware implementation for the reference clock selection has a lower gate complexity, smaller time delay, and greater flexibility than the previously published implementation. The improvement is achieved by replacing the sorter with a counting encoder and comparators and by introducing threshold generation logic with programmable registers. The scheme has a gate complexity of O(n) and a delay of O(log n), where n is the total number of inputs to a particular clock, and is programmable for different values of n and m, the maximum number of faults.>

Abstract A selection algorithm to find the Irth smallest element of a elements is presented. The algorithm mainly consists of the partition procedure and an improved method to choose a partitioning element. The algorithm estimates the partitioning element from a small sample so that the icth element is contained in the smaller partition between two partitions resulting from partitioning. The partitioning element is determined by using estimation of the cumulative frequency distribution in the theory of non‐parametric statistics. The expected number of comparisons is found to be n + min(k, n‐k) + O(n2/3) through experimental tests where the sample size is approximately n2/3. The experimental results show that the performance of the algorithm is improved, compared to the two known selection algorithms, particularly when the selection index is near to the median.

The authors focus on the ordering of the columns to minimize the necessary number of tracks in one-dimensional logic array. They use a column-orientation approach to this problem. Each net is converted into a complete graph (or clique). The weighted graph using such topological transformation is unique. The necessary number of tracks can be evaluated by the cut of the two seeds of orderings, the left seed vertex and the right seed vertex. The authors find the minimal track assignments by minimizing the cut of the seed vertex. Additionally, a useful concept called the overriding property is introduced. It determines the local optimal assignments for two or more columns with the above property. The author's algorithm works well with either a uni- or bidirectional approach to select the seed of ordering. Results obtained by the proposed algorithm and the simulated annealing approach are compared.>

The proliferation dynamics of a growing cell population can be represented by a discrete-time state model. An application of recursive least squares algorithms to the estimation of important cell cycle kinetic parameters is considered. Cell kinetic parameters are estimated recursively by the following steps: 1) decomposition of state and output spaces, 2) separation of identification of the unperturbed cell system from that of the perturbed cell system, and 3) application of a recursive least squares algorithm for the identification of each decomposed system. This method is feasible due to the availability of a new technology called flow microfluorometry (FMF) which is capable of providing large amounts of quantitative data within a short time period. Emphasis is placed on the construction of a computationally efficient and stable algorithm. The FMF deoxyribonucleic acid (DNA) data of a Chinese hamster ovary (CHO) cell population is used to demonstrate the potential value of the method developed.