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.