Advanced search
Start date

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

Grant number: 14/23564-0
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): January 01, 2015
Effective date (End): July 31, 2015
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Marcelo da Silva Reis
Grantee:Gustavo Estrela de Matos
Home 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


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)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

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. Web of Science Citations: 0.

Please report errors in scientific publications list by writing to: