Database cracking has been an area of active research in recent years. The core idea of database cracking is to create indexes adaptively and incrementally as a side product of query processing. Several works have pro...
详细信息
Database cracking has been an area of active research in recent years. The core idea of database cracking is to create indexes adaptively and incrementally as a side product of query processing. Several works have proposed different cracking techniques for different aspects including updates, tuple reconstruction, convergence, concurrency control, and robustness. Our 2014 VLDB paper "The Uncracked Pieces in Database Cracking" (PVLDB 7:97-108, 2013/VLDB 2014) was the first comparative study of these different methods by an independent group. In this article, we extend our published experimental study on database cracking and bring it to an up-to-date state. Our goal is to critically review several aspects, identify the potential, and propose promising directions in database cracking. With this study, we hope to expand the scope of database cracking and possibly leverage cracking in database engines other than MonetDB. We repeat several prior database cracking works including the core cracking algorithms as well as three other works on convergence (hybrid cracking), tuple reconstruction (sideways cracking), and robustness (stochastic cracking), respectively. Additionally to our conference paper, we now also look at a recently published study about CPU efficiency (predication cracking). We evaluate these works and show possible directions to do even better. As a further extension, we evaluate the whole class of parallel cracking algorithms that were proposed in three recent works. Altogether, in this work we revisit 8 papers on database cracking and evaluate in total 18 cracking methods, 6 sorting algorithms, and 3 full index structures. Additionally, we test cracking under a variety of experimental settings, including high selectivity (Low selectivity means that many entries qualify. Consequently, a high selectivity means, that only few entries qualify) queries, low selectivity queries, varying selectivity, and multiple query access patterns. Finally, we compare crack
In this paper, the authors present a new algorithm efficient solution to the packing problem in two dimensions. The authors propose a new heuristic using the value of the electromagnetic field to determine the best po...
详细信息
In this paper, the authors present a new algorithm efficient solution to the packing problem in two dimensions. The authors propose a new heuristic using the value of the electromagnetic field to determine the best position to place a circular object in a configuration of other circular objects previously packed. Also, this algorithm simulates two processes to compact objects already placed, inspired by gravitational forces, to minimize the empty space in the container and maximizing the number of objects in the container. To determine the efficacy of this algorithm, the authors carried out experiments with twenty-four instances. Parallel computing can contribute to making decision processes such as optimization and prediction more agile and faster. Real-time decision making involves the use of solution methodologies and algorithms. For this reason the present manuscript shows an alternative for the solution of a classic industry problem that must be solved quickly. Packaging optimization can help reduce waste of container material. The material used to transport the products can reduce its environmental impact due to an efficient packaging process. Light-weighting can also be accomplished by reducing the amount of packaging material used.
Efficient hill climbers are at the heart of the latest gray-box optimization techniques, where some structural information about the optimization problem is available. Focusing on NK-landscapes as a challenging class ...
详细信息
ISBN:
(纸本)9781450383509
Efficient hill climbers are at the heart of the latest gray-box optimization techniques, where some structural information about the optimization problem is available. Focusing on NK-landscapes as a challenging class of k-bounded pseudo-boolean functions, we propose a quality-enhanced and a time-accelerated hill climber. Our investigations are based on the idea of performing several simultaneous moves at each iteration of the search process. This is enabled using graph coloring to structure the interacting variables of an NK-landscape, and to identify subsets of possibly improving independent moves in the Hamming distance 1 neighborhood. Besides being extremely competitive with respect to the state-of-the-art first- and best- ascent serial variants, our initial design exposes a natural degree of parallelism allowing us to convert our serial algorithm into a parallel hill climber without further design efforts. As such, we also provide a multi-threaded implementation using up to 10 shared-memory CPU-cores. Using a range of large-scale random NK-landscapes with up to 10(6) variables, we provide evidence on the efficiency and effectiveness of the proposed hill climber and we highlight the strength of our parallel design in attaining substantial acceleration factors for the largest experimented functions.
This paper presents a multi-threaded version of the Spotted Hyena Optimizer algorithm with thread-crossing techniques (MT-SHO) to improve the ability of the algorithm to explore the search space. The original algorith...
详细信息
This paper presents a multi-threaded version of the Spotted Hyena Optimizer algorithm with thread-crossing techniques (MT-SHO) to improve the ability of the algorithm to explore the search space. The original algorithm is inspired by the hunting behavior of the spotted hyena. Along the different sections of the work, we explain in detail how the original algorithm simulates the spotted hyenas behavior to optimize highly complex mathematical functions and how we handle the procedures and results of the multi-threaded version, with thread-crossing techniques that improve the ability to explore and exploit the search space by letting threads learn between them. We present the experiments used to determine the best value of the parameters used in the parallel version of the algorithm and to prove that our proposal obtains significantly good results we compare the results obtained by evaluating 24 benchmark functions with the results published for the original algorithm as well as other metaheuristic algorithms. (c) 2021 The Authors. Published by Elsevier B.V.
With the rapid increase in the scale of Very Large Scale Integration (VLSI), the runtime of fault simulation becomes a crucial issue during the test development phase of the VLSI design process. Various acceleration t...
详细信息
ISBN:
(纸本)9798350352047;9798350352030
With the rapid increase in the scale of Very Large Scale Integration (VLSI), the runtime of fault simulation becomes a crucial issue during the test development phase of the VLSI design process. Various acceleration techniques have been proposed across different dimensions. However, a single technique may struggle to comprehensively address the multiple challenges in the fault simulation domain. This paper optimizes existing multi-threaded fault simulation algorithms on ARM multi-core processors. Firstly, the baseline single-threaded fault simulation algorithm was implemented with various optimization techniques such as event-driven, fault collapsing, and ARM NEON. Secondly, based on the analysis of uneven workloads in a previous multi-threaded algorithm, we present a fault-block allocation strategy to balance workloads among threads, which adopts parallel pattern single fault propagation and FFR-based fault sorting as well, to effectively reduce simulation path disparities among different threads. Experimental results conducted on the Kunpeng 920 processor demonstrate the effectiveness of the implemented algorithm with integrated multiple optimization techniques.
This paper presents a multi-threaded version of the Spotted Hyena Optimizer algorithm with thread-crossing techniques (MT-SHO) to improve the ability of the algorithm to explore the search space. The original algorith...
详细信息
This paper presents a multi-threaded version of the Spotted Hyena Optimizer algorithm with thread-crossing techniques (MT-SHO) to improve the ability of the algorithm to explore the search space. The original algorithm is inspired by the hunting behavior of the spotted hyena. Along the different sections of the work, we explain in detail how the original algorithm simulates the spotted hyena’s behavior to optimize highly complex mathematical functions and how we handle the procedures and results of the multi-threaded version, with thread-crossing techniques that improve the ability to explore and exploit the search space by letting threads learn between them. We present the experiments used to determine the best value of the parameters used in the parallel version of the algorithm and to prove that our proposal obtains significantly good results we compare the results obtained by evaluating 24 benchmark functions with the results published for the original algorithm as well as other metaheuristic algorithms.
暂无评论