Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/4037

 Title: Theoretical Properties of a Neighborhood-based Approach for Widening Authors: Ivanova-Rohling, Violeta Keywords: Parallel Neighborhood-Based SearchLattice TraversalParallel Data MiningWidening Issue Date: 2020 Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences Citation: Serdica Journal of Computing, Vol. 14, No 3-4, (2020), 65p-91p Abstract: Most of the research in parallel data mining and machine learning algorithms is focused on improving the efficiency of existing algorithms. However, our focus is the improvement of the solution quality, or model accuracy. We are looking for "smart" strategies to invest parallel compute resources in order to achieve a better exploration of the search space by exploring several solutions in parallel, referred to as Widening. In this paper, we discuss the theoretical properties of a neighborhood-based Widening using a type of neighborhoods, optimality neighborhoods and contrast this communicationless approach to the straightforward beam-like Top-k Widening approach, which requires communication. We show a bound on the number of parallel workers needed for the communicationless approach to guarantee that it has a solution of the same quality as the Top-k approach. In addition to the theoretical comparison, we experimentally compare these two approaches in terms of running time and quality of final solution, using a widened version of the greedy algorithm for set cover problem. URI: http://hdl.handle.net/10525/4037 ISSN: 1312-6555 Appears in Collections: Volume 14, Number 3-4

Files in This Item:

File Description SizeFormat