Studies of efficient data structures to tackle the U-curve optimization problem

• Grant number: 14/23564-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: January 01, 2015
• End date: July 31, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Marcelo da Silva Reis
• Grantee: Gustavo Estrela de Matos
• Host Institution: Instituto Butantan. Secretaria da Saúde (São Paulo - Estado). São Paulo , SP, Brazil
• Associated research grant: 13/07467-1 - CeTICS - Center of Toxins, Immune-Response and Cell Signaling, AP.CEPID

Abstract

The U-curve optimization problem may be used to model problems in several fields; for instance, the feature selection problem in Pattern Recognition. An optimal algorithm to tackle the U-curve problem is the U-Curve-Search (UCS) algorithm. The usage of UCS to solve this problem is promissing, since it computes fewer times the cost function than other algorithms. However, the current implementation of UCS has scalability issues, which is mostly due the usage of doubly linked lists to store the control of the search space that was already explored by the algorithm execution. Therefore, in this project, we propose the investigation of the usage of Reduced Ordered Binary Decision Diagrams (ROBDDs) as data structure to control the search space during an execution of the UCS algorithm. We intend to use ROBDDs to develop a new version of UCS, which will be implemented and tested using the featsel framework. We will carry out tests with artificial instances and also data from real-world problems such as the design of W-operators. We expect that the new version of the UCS algorithm will be also efficient from the required computational time point of view, hence making this algorithm competitive to solve practical problems that can be described as instances of the U-curve problem. (AU)

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

REIS, MARCELO S.; ESTRELA, GUSTAVO; FERREIRA, CARLOS EDUARDO; BARRERA, JUNIOR. Optimal Boolean lattice-based algorithms for the U-curve optimization problem. INFORMATION SCIENCES, v. 471, p. 97-114, JAN 2019. (13/07467-1, 11/50761-2, 14/23564-0)