BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2020 >
Volume 14, Number 3-4 >

Please use this identifier to cite or link to this item:

Title: Theoretical Properties of a Neighborhood-based Approach for Widening
Authors: Ivanova-Rohling, Violeta
Keywords: Parallel Neighborhood-Based Search
Lattice Traversal
Parallel Data Mining
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.
ISSN: 1312-6555
Appears in Collections:Volume 14, Number 3-4

Files in This Item:

File Description SizeFormat
sjc-vol14-num3-4-2020-p65-p91.pdf882.94 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License