The dominance scoring problem in a multidimensional dataset is to return the number of points dominated by a given point, which is a common metric for evaluating the quality of a data point. Dominance scoring is an elementary operator for variations of the skyline operator, including top-$k$dominating and$k$-skyband queries. This study proposes query processing for dominance scores that operates primarily on the graphics processing unit (GPU) to fully utilize its massive processing resources and restricted memory space while reducing the transfer overhead between the central processing unit (CPU) and GPU. We introduce a heap-based multidimensional data structure with complete and well-balanced characteristics. Using our preprocessed data, we can construct a complete R-tree with the non-overlapping property, ensuring that the bounding boxes of internal nodes of the same level do not overlap, thereby reducing redundant operations. In addition, we propose two algorithms based on depth-first and breadth-first traversals to accumulate the dominance score on GPUs in parallel. Both take full advantage of the GPU's computing resources and memory space supported by the non-overlapping tree structures. Experiments on synthetic and real-world datasets demonstrate that the proposed algorithms implemented on GPUs dramatically improve the efficiency of dominance scoring.

Maximal clique enumeration (MCE) is a classic problem in graph theory to identify all complete subgraphs in a graph. In prior MCE work, the Bron-Kerbosch algorithm is one of the most popular solutions, and there are several improved algorithms proposed on CPU platforms. However, while few studies have focused on the related issue of parallel implementation, recently, there have been numerous explorations of the acceleration of general purpose applications using a graphics processing unit (GPU) to reduce the computing power consumption. In this article, we develop a GPU-based Bron-Kerbosch algorithm that efficiently solves the MCE problem in parallel by optimizing the process of subproblem decomposition and computing resource usage. To speed up the computations, we use coalesced memory accesses and warp reductions to increase bandwidth and reduce memory latency. Our experimental results show that the proposed algorithm can fully exploit the resources of GPU architectures, allowing for the vast acceleration of operations to solve the MCE problem.

We give a detailed analysis of the optimization time of the [Formula: see text]-Evolutionary Algorithm under two simple fitness functions (OneMax and LeadingOnes). The problem has been approached in the evolutionary algorithm literature in various ways and with different degrees of rigor. Our asymptotic approximations for the mean and the variance represent the strongest of their kind. The approach we develop is based on an asymptotic resolution of the underlying recurrences and can also be extended to characterize the corresponding limiting distributions. While most of our approximations can be derived by simple heuristic calculations based on the idea of matched asymptotics, the rigorous justifications are challenging and require a delicate error analysis.

The skyline query is an efficient data analysis tool for multi-criteria decision making that has received significant attention in the database community. As multi-core architectures have gone mainstream, we present a new parallel skyline query algorithm that can be applied to multi-core and multiprocessor systems, to progressively return skyline points as they are identified efficiently. In this paper, we proposed a parallel skyline algorithm which can eliminate redundant computations and improve parallelism of the skyline query. Experimental results show that our algorithm successfully exploits the features of multiple cores to improve the performance of skyline computation for large high-dimensional datasets.

Skylines emerged as a useful notion in database queries for selecting representative groups in multivariate data samples for further decision making, multiobjective optimization, or data processing, and the $k$-dominant skylines were naturally introduced to resolve the abundance of skylines when the dimensionality grows or when the coordinates are negatively correlated. We prove in this paper that the expected number of $k$-dominant skylines is asymptotically zero for large samples when $1\leq k\leq d-1$ under two reasonable (continuous) probability assumptions of the input points, $d$ being the (finite) dimensionality, in contrast to the asymptotic unboundedness when $k=d$. In addition to such an asymptotic zero-infinity property, we also establish a sharp threshold phenomenon for the expected $(d-1)$-dominant skylines when the dimensionality is allowed to grow with $n$, the sample size. Several related issues, such as the dominant cycle structures, the numerical aspects, and the practical implications, are also briefly studied.

This study explored the issue of power consumption for multi-core systems supporting virtual technology environment and proposed a highly effective dynamic power management mechanism for a virtual machine environment, which regulates the voltage and frequency of core processors to reduce energy consumption during system operations. We analyzed the actual execution state of the threads under the system environment executed by KVM virtualization technology and implemented this power management mechanism in the Linux 2.6 operating system. The experimental results indicated that the proposed mechanism is capable of reducing system energy consumption by an average of nearly 65%, while prolonging the execution time by an average of only 3%. The results suggest that, aside from considering the execution time, this mechanism can achieve the main objective of energy saving.

In this paper, we study the upper bounds of memory storage for two different allocators. In the first case, we consider a general allocator that can allocate memory blocks anywhere in the available heap space. In the second case, a more economical allocator constrained by the address-ordered first-fit allocation policy is considered. We derive the upper bound of memory usage for all allocators and present a systematic approach to search for allocation/deallocation patterns that might lead to the largest fragmentation. These results are beneficial in embedded systems where memory usage must be reduced and predictable because of lack of swapping facility. They are also useful in other types of computing systems.

Wireless sensor networking is a current topic of research areas and widely used in a variety of applications. The localization of sensor nodes is a fundamental problem in wireless sensor networks. Many localization approaches have been presented and can be implemented using some powerful nodes with GPS devices. In this paper, we introduce a distributed localization scheme, called Rectangle Overlapping Approach (ROA), using a moving beacon with a GPS and a directional antenna. The positions can be computed by simple operations according to the current state of the moving beacon, including the rotation angle and the position. Simulation results show that the proposed scheme is very efficient and the node positions can be determined accurately after the beacon operates along straight-line traverse routes.