Slicing the metric space to provide quick indexing of complex data in the main memory

Searching in a dataset for elements that are similar to a given query element is a core problem in applications that manage complex data, and has been aided by metric access methods (MAMs). A growing number of applications require indices that must be built faster and repeatedly, also providing faster response for similarity queries. The increase in the main memory capacity and its lowering costs also motivate using memory-based MAMs. In this paper. we propose the Onion-tree, a new and robust dynamic memory-based MAM that slices the metric space into disjoint subspaces to provide quick indexing of complex data. It introduces three major characteristics: (i) a partitioning method that controls the number of disjoint subspaces generated at each node; (ii) a replacement technique that can change the leaf node pivots in insertion operations; and (iii) range and k-NN extended query algorithms to support the new partitioning method, including a new visit order of the subspaces in k-NN queries. Performance tests with both real-world and synthetic datasets showed that the Onion-tree is very compact. Comparisons of the Onion-tree with the MM-tree and a memory-based version of the Slim-tree showed that the Onion-tree was always faster to build the index. The experiments also showed that the Onion-tree significantly improved range and k-NN query processing performance and was the most efficient MAM, followed by the MM-tree, which in turn outperformed the Slim-tree in almost all the tests. (C) 2010 Elsevier B.V. All rights reserved.

Outer Trust-Region Method for Constrained Optimization

Given an algorithm A for solving some mathematical problem based on the iterative solution of simpler subproblems, an outer trust-region (OTR) modification of A is the result of adding a trust-region constraint to each subproblem. The trust-region size is adaptively updated according to the behavior of crucial variables. The new subproblems should not be more complex than the original ones, and the convergence properties of the OTR algorithm should be the same as those of Algorithm A. In the present work, the OTR approach is exploited in connection with the ""greediness phenomenon"" of nonlinear programming. Convergence results for an OTR version of an augmented Lagrangian method for nonconvex constrained optimization are proved, and numerical experiments are presented.

U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time. (C) 2009 Elsevier Ltd. All rights reserved.

Retail competition and shelf space allocation

We develop a model to study shelf space allocation in retail. Retailers compete for consumers not only choosing prices but also by the space allocated to each product on shelves. Our approach depart from the existing literature on shelf allocation, as we model the problem of price setting and shelf allocation in an oligopolistic retail market. We present a simple model of retail competition in which prices are dispersed in the crosssection of stores but shelf allocation is not.

Object-Space Road Extraction in Rural Areas Using Stereoscopic Aerial Images

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Confinement of spinless particles by Coulomb potentials in two-dimensional space-time

The problem of confinement of spinless particles in 1 + 1 dimensions is approached with a linear potential by considering a mixing of Lorentz vector and scalar couplings. Analytical bound-states solutions are obtained when the scalar coupling is of sufficient intensity compared to the vector coupling. (c) 2005 Elsevier B.V. All rights reserved.

Confinement of fermions by mixed vector-scalar linear potentials in two-dimensional space-time

The problem of confinement of fermions in 1 + 1 dimensions is approached with a linear potential in the Dirac equation by considering a mixing of Lorentz vector and scalar couplings. Analytical bound-states solutions are obtained when the scalar coupling is of sufficient intensity compared to the vector coupling. (C) 2002 Elsevier B.V. B.V. All rights reserved.

Hybrid evolutionary algorithm for the Capacitated Centered Clustering Problem

The Capacitated Centered Clustering Problem (CCCP) consists of defining a set of p groups with minimum dissimilarity on a network with n points. Demand values are associated with each point and each group has a demand capacity. The problem is well known to be NP-hard and has many practical applications. In this paper, the hybrid method Clustering Search (CS) is implemented to solve the CCCP. This method identifies promising regions of the search space by generating solutions with a metaheuristic, such as Genetic Algorithm, and clustering them into clusters that are then explored further with local search heuristics. Computational results considering instances available in the literature are presented to demonstrate the efficacy of CS. (C) 2010 Elsevier Ltd. All rights reserved.

A Strategy to Solve the Multistage Transmission Expansion Planning Problem

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Supersymmetry flows, semi-symmetric space sine-Gordon models and the Pohlmeyer reduction

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Finding invariant tori in the problem of a periodically corrugated waveguide

Some dynamic properties for a light ray suffering specular reflections inside a periodically corrugated waveguide are studied. The dynamics of the model is described in terms of a two dimensional nonlinear area preserving map. We show that the phase space is mixed in the sense that there are KAM islands surrounded by a large chaotic sea that is confined by two invariant spanning curves. We have used a connection with the Standard Mapping near a transition from local to global chaos and found the position of these two invariant spanning curves limiting the size of the chaotic sea as function of the control parameter.

Dynamical properties for the problem of a particle in an electric field of wave packet: Low velocity and relativistic approach

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

The symmetry group of Z(q)(n) in the Lee space and the Z(qn)-linear codes

The Z(4)-linearity is a construction technique of good binary codes. Motivated by this property, we address the problem of extending the Z(4)-linearity to Z(q)n-linearity. In this direction, we consider the n-dimensional Lee space of order q, that is, (Z(q)(n), d(L)), as one of the most interesting spaces for coding applications. We establish the symmetry group of Z(q)(n) for any n and q by determining its isometries. We also show that there is no cyclic subgroup of order q(n) in Gamma(Z(q)(n)) acting transitively in Z(q)(n). Therefore, there exists no Z(q)n-linear code with respect to the cyclic subgroup.

Optimal space manoeuvres in a non-Keplerian force field

In this work the problem of a spacecraft bi-impulsive transfer between two given non coplanar elliptical orbits, with minimum fuel consumption, is solved considering a non-Keplerian force field (the perturbing forces include Earth gravity harmonics and atmospheric drag). The problem is transformed in the Two Point Boundary Value Problem. It is developed and implemented a new algorithm, that uses the analytical expressions developed here. A dynamics that considered a Keplerian force field was used to produce an initial guess to solve the Two Point Boundary Value Problem. Several simulations were performed to observe the spacecraft orbital behaviour by different kind of perturbations and constraints, on a fuel consumption optimization point of view. (C) 2002 COSPAR. Published by Elsevier B.V. Ltd. All rights reserved.

The Liapunov exponent as a tool for exploring phase space

We have used the Liapunov exponent to explore the phase space of a dynamical system. Considering the planar, circular restricted three-body problem for a mass ratio mu = 10(-3) (close to the Jupiter/Sun case), we have integrated similar to 16,000 starting conditions for orbits started interior to that of the perturber and we have estimated the maximum Liapunov characteristic exponent for each starting condition. Despite the fact that the integrations, in general, are for only a few thousand orbital periods of the secondary, a comparative analysis of the Liapunov exponents for various values of the 'cut-off' gives a good overview of the structure of the phase space. It provides information about the diffusion rates of the various chaotic regions, the location of the regular regions associated with primary resonances and even details such as the location of secondary resonances that produce chaotic regions inside the regular regions of primary resonances.