Zoneamento agroecológico do Município de Anastácio - MS.

A Embrapa Solos, em parceria com a Secretaria de Estado de Desenvolvimento Agrário, da Produção, da Indústria, do Comércio e do Turismo - SEPROTUR, realizou o Zoneamento Agroecológico do Estado do Mato Grosso do Sul - Fase II - com objetivo de contribuir na indicação de áreas passíveis de exploração agrícola sustentável. No desenvolvimento desse trabalho foram considerados aspectos legais, restrições ambientais, potencial das culturas, aspectos do clima, de geomorfologia e dos solos, todos integrados em ambiente de sistema de informação geográfica com apoio de algebra de mapas, no intuito de avaliar a adequabilidade de uso das terras e apresentar uma proposição de planejamento de uso e ocupação das terras. Os resultados foram consolidados por município e dão origem a esse boletim de pesquisa. No município de Anastácio, as terras indicadas para o uso com lavouras somam 1.425 km², o que equivale a aproximadamente 50% da área total do município, enquanto que as recomendadas para pastagem equivalem a 26,5% e as áreas recomendadas para pastagem especial ou cultivo de arroz correspondem a cerca de 20% da área do município que corresponde a algo como 578 km². Nestas unidades é fundamental avaliar criteriosamente a utilização de pastagens nestas terras quando essas ainda se encontram sob cobertura vegetal, visto que, praticamente 20% destas terras ainda permanecem com vegetação natural em seus diversos graus de conservação. As terras recomendadas para conservação dos recursos naturais equivalem a menos de 80 km², as quais constituem áreas de alta fragilidade ambiental e/ ou apresentam restrições legais de uso como áreas de preservação permanente. As áreas identificadas como zonas recomendadas para recuperação ambiental equivalem a 80 km² e constituem áreas de moderada a alta fragilidade ambiental e/ou que apresentam restrições legais de uso e que já foram desmatadas para o uso com pastagens/agricultura. A área do município de Anastácio apresenta alto grau de ação antrópica das terras, onde mais de 75% das terras sendo utilizadas com pastagens e/ou com agricultura, enquanto que apenas 25% ainda apresentam certo grau de preservação.

Zoneamento agroecológico do Município de Coxim - MS.

A Embrapa Solos, em parceria com a Secretaria de Estado de Desenvolvimento Agrário, da Produção, da Indústria, do Comércio e do Turismo - SEPROTUR, realizou o Zoneamento Agroecológico do Estado do Mato Grosso do Sul - Fase II - com objetivo de contribuir na indicação de áreas passíveis de exploração agrícola sustentável. No desenvolvimento desse trabalho foram considerados aspectos legais, restrições ambientais, potencial das culturas, aspectos do clima, de geomorfologia e dos solos, todos integrados em ambiente de sistema de informação geográfica com apoio de algebra de mapas, no intuito de avaliar a adequabilidade de uso das terras e apresentar uma proposição de planejamento de uso e ocupação das terras. As terras indicadas para o uso com lavouras somam cerca de 1.040 km², o que equivale a aproximadamente 16% da área total zoneada. As áreas recomendadas para pastagem equivalem a 47% e as áreas recomendadas para pastagem especial a menos de 1,5% da área do município que corresponde a algo como 80 km². Nestas unidades é fundamental avaliar criteriosamente a utilização de pastagens nestas terras quando essas ainda se encontram sob cobertura vegetal, visto que, praticamente 82% destas terras ainda permanecem com vegetação natural em seus diversos graus de conservação. As terras recomendadas para conservação dos recursos naturais e/ou recuperação ambiental equivalem a 210 km², as quais constituem áreas de alta fragilidade ambiental e/ou apresentam restrições legais de uso como áreas de preservação permanente. As áreas identificadas como zonas recomendadas para recuperação ambiental equivalem a 123 km² e constituem áreas de moderada a alta fragilidade ambiental e/ou que apresentam restrições legais de uso e que já foram desmatadas para o uso com pastagens/agricultura. O do município de Coxim apresenta um alto grau de ação antrópica das terras, onde cerca de 60% das terras são utilizadas com pastagens e/ou com agricultura, enquanto que apenas 40% ainda apresentam certo grau de preservação. O município de Coxim apresenta um bom potencial para o desenvolvimento da agropecuária, porém, devidos às características edafoclimáticas e de topografia, a recomendação preferencial é a utilização com pastagens.

Application of metabolomics to plant genotype discrimination using statistics and machine learning

Janet Taylor, Ross D King, Thomas Altmann and Oliver Fiehn (2002). Application of metabolomics to plant genotype discrimination using statistics and machine learning. 1st European Conference on Computational Biology (ECCB). (published as a journal supplement in Bioinformatics 18: S241-S248).

Newton's aerodynamic problem in media of chaotically moving particles

Plakhov, A.Y.; Torres, D., (2005) 'Newton's aerodynamic problem in media of chaotically moving particles', Sbornik: Mathematics 196(6) pp.885-933 RAE2008

A probabilistic index for completely positive maps and an application

Gohm, Rolf, (2003) 'A probabilistic index for completely positive maps and an application', Journal of Operator Theory 54(2) pp.339-361 RAE2008

Rozproszone algorytmy aproksymacyjne dla grafów dyskowych

Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej

Wizualizacja kartograficzna dostępności przestrzennej w modelu monocentrycznym

Wydział Nauk Geograficznych i Geologicznych

Geometric Generalizations of the Power of Two Choices

A well-known paradigm for load balancing in distributed systems is the``power of two choices,''whereby an item is stored at the less loaded of two (or more) random alternative servers. We investigate the power of two choices in natural settings for distributed computing where items and servers reside in a geometric space and each item is associated with the server that is its nearest neighbor. This is in fact the backdrop for distributed hash tables such as Chord, where the geometric space is determined by clockwise distance on a one-dimensional ring. Theoretically, we consider the following load balancing problem. Suppose that servers are initially hashed uniformly at random to points in the space. Sequentially, each item then considers d candidate insertion points also chosen uniformly at random from the space,and selects the insertion point whose associated server has the least load. For the one-dimensional ring, and for Euclidean distance on the two-dimensional torus, we demonstrate that when n data items are hashed to n servers,the maximum load at any server is log log n / log d + O(1) with high probability. While our results match the well-known bounds in the standard setting in which each server is selected equiprobably, our applications do not have this feature, since the sizes of the nearest-neighbor regions around servers are non-uniform. Therefore, the novelty in our methods lies in developing appropriate tail bounds on the distribution of nearest-neighbor region sizes and in adapting previous arguments to this more general setting. In addition, we provide simulation results demonstrating the load balance that results as the system size scales into the millions.

Database Indexing Methods for 3D Hand Pose Estimation

Estimation of 3D hand pose is useful in many gesture recognition applications, ranging from human-computer interaction to automated recognition of sign languages. In this paper, 3D hand pose estimation is treated as a database indexing problem. Given an input image of a hand, the most similar images in a large database of hand images are retrieved. The hand pose parameters of the retrieved images are used as estimates for the hand pose in the input image. Lipschitz embeddings of edge images into a Euclidean space are used to improve the efficiency of database retrieval. In order to achieve interactive retrieval times, similarity queries are initially performed in this Euclidean space. The paper describes ongoing work that focuses on how to best choose reference images, in order to improve retrieval accuracy.

Systematic Verification of Safety Properties of Arbitrary Network Protocol Compositions Using CHAIN

Formal correctness of complex multi-party network protocols can be difficult to verify. While models of specific fixed compositions of agents can be checked against design constraints, protocols which lend themselves to arbitrarily many compositions of agents-such as the chaining of proxies or the peering of routers-are more difficult to verify because they represent potentially infinite state spaces and may exhibit emergent behaviors which may not materialize under particular fixed compositions. We address this challenge by developing an algebraic approach that enables us to reduce arbitrary compositions of network agents into a behaviorally-equivalent (with respect to some correctness property) compact, canonical representation, which is amenable to mechanical verification. Our approach consists of an algebra and a set of property-preserving rewrite rules for the Canonical Homomorphic Abstraction of Infinite Network protocol compositions (CHAIN). Using CHAIN, an expression over our algebra (i.e., a set of configurations of network protocol agents) can be reduced to another behaviorally-equivalent expression (i.e., a smaller set of configurations). Repeated applications of such rewrite rules produces a canonical expression which can be checked mechanically. We demonstrate our approach by characterizing deadlock-prone configurations of HTTP agents, as well as establishing useful properties of an overlay protocol for scheduling MPEG frames, and of a protocol for Web intra-cache consistency.

BoostMap: A Method for Efficient Approximate Similarity Rankings

This paper introduces BoostMap, a method that can significantly reduce retrieval time in image and video database systems that employ computationally expensive distance measures, metric or non-metric. Database and query objects are embedded into a Euclidean space, in which similarities can be rapidly measured using a weighted Manhattan distance. Embedding construction is formulated as a machine learning task, where AdaBoost is used to combine many simple, 1D embeddings into a multidimensional embedding that preserves a significant amount of the proximity structure in the original space. Performance is evaluated in a hand pose estimation system, and a dynamic gesture recognition system, where the proposed method is used to retrieve approximate nearest neighbors under expensive image and video similarity measures. In both systems, BoostMap significantly increases efficiency, with minimal losses in accuracy. Moreover, the experiments indicate that BoostMap compares favorably with existing embedding methods that have been employed in computer vision and database applications, i.e., FastMap and Bourgain embeddings.

On trip planning queries in spatial databases

In this paper we discuss a new type of query in Spatial Databases, called Trip Planning Query (TPQ). Given a set of points P in space, where each point belongs to a category, and given two points s and e, TPQ asks for the best trip that starts at s, passes through exactly one point from each category, and ends at e. An example of a TPQ is when a user wants to visit a set of different places and at the same time minimize the total travelling cost, e.g. what is the shortest travelling plan for me to visit an automobile shop, a CVS pharmacy outlet, and a Best Buy shop along my trip from A to B? The trip planning query is an extension of the well-known TSP problem and therefore is NP-hard. The difficulty of this query lies in the existence of multiple choices for each category. In this paper, we first study fast approximation algorithms for the trip planning query in a metric space, assuming that the data set fits in main memory, and give the theory analysis of their approximation bounds. Then, the trip planning query is examined for data sets that do not fit in main memory and must be stored on disk. For the disk-resident data, we consider two cases. In one case, we assume that the points are located in Euclidean space and indexed with an Rtree. In the other case, we consider the problem of points that lie on the edges of a spatial network (e.g. road network) and the distance between two points is defined using the shortest distance over the network. Finally, we give an experimental evaluation of the proposed algorithms using synthetic data sets generated on real road networks.

Type Inference for Variant Object Types

Existing type systems for object calculi are based on invariant subtyping. Subtyping invariance is required for soundness of static typing in the presence of method overrides, but it is often in the way of the expressive power of the type system. Flexibility of static typing can be recovered in different ways: in first-order systems, by the adoption of object types with variance annotations, in second-order systems by resorting to Self types. Type inference is known to be P-complete for first-order systems of finite and recursive object types, and NP-complete for a restricted version of Self types. The complexity of type inference for systems with variance annotations is yet unknown. This paper presents a new object type system based on the notion of Split types, a form of object types where every method is assigned two types, namely, an update type and a select type. The subtyping relation that arises for Split types is variant and, as a result, subtyping can be performed both in width and in depth. The new type system generalizes all the existing first-order type systems for objects, including systems based on variance annotations. Interestingly, the additional expressive power does not affect the complexity of the type inference problem, as we show by presenting an O(n^3) inference algorithm.

Efficient Nearest Neighbor Classification Using a Cascade of Approximate Similarity Measures

Nearest neighbor classification using shape context can yield highly accurate results in a number of recognition problems. Unfortunately, the approach can be too slow for practical applications, and thus approximation strategies are needed to make shape context practical. This paper proposes a method for efficient and accurate nearest neighbor classification in non-Euclidean spaces, such as the space induced by the shape context measure. First, a method is introduced for constructing a Euclidean embedding that is optimized for nearest neighbor classification accuracy. Using that embedding, multiple approximations of the underlying non-Euclidean similarity measure are obtained, at different levels of accuracy and efficiency. The approximations are automatically combined to form a cascade classifier, which applies the slower approximations only to the hardest cases. Unlike typical cascade-of-classifiers approaches, that are applied to binary classification problems, our method constructs a cascade for a multiclass problem. Experiments with a standard shape data set indicate that a two-to-three order of magnitude speed up is gained over the standard shape context classifier, with minimal losses in classification accuracy.

Learning Embeddings for Indexing, Retrieval, and Classification, with Applications to Object and Shape Recognition in Image Databases

Nearest neighbor retrieval is the task of identifying, given a database of objects and a query object, the objects in the database that are the most similar to the query. Retrieving nearest neighbors is a necessary component of many practical applications, in fields as diverse as computer vision, pattern recognition, multimedia databases, bioinformatics, and computer networks. At the same time, finding nearest neighbors accurately and efficiently can be challenging, especially when the database contains a large number of objects, and when the underlying distance measure is computationally expensive. This thesis proposes new methods for improving the efficiency and accuracy of nearest neighbor retrieval and classification in spaces with computationally expensive distance measures. The proposed methods are domain-independent, and can be applied in arbitrary spaces, including non-Euclidean and non-metric spaces. In this thesis particular emphasis is given to computer vision applications related to object and shape recognition, where expensive non-Euclidean distance measures are often needed to achieve high accuracy. The first contribution of this thesis is the BoostMap algorithm for embedding arbitrary spaces into a vector space with a computationally efficient distance measure. Using this approach, an approximate set of nearest neighbors can be retrieved efficiently - often orders of magnitude faster than retrieval using the exact distance measure in the original space. The BoostMap algorithm has two key distinguishing features with respect to existing embedding methods. First, embedding construction explicitly maximizes the amount of nearest neighbor information preserved by the embedding. Second, embedding construction is treated as a machine learning problem, in contrast to existing methods that are based on geometric considerations. The second contribution is a method for constructing query-sensitive distance measures for the purposes of nearest neighbor retrieval and classification. In high-dimensional spaces, query-sensitive distance measures allow for automatic selection of the dimensions that are the most informative for each specific query object. It is shown theoretically and experimentally that query-sensitivity increases the modeling power of embeddings, allowing embeddings to capture a larger amount of the nearest neighbor structure of the original space. The third contribution is a method for speeding up nearest neighbor classification by combining multiple embedding-based nearest neighbor classifiers in a cascade. In a cascade, computationally efficient classifiers are used to quickly classify easy cases, and classifiers that are more computationally expensive and also more accurate are only applied to objects that are harder to classify. An interesting property of the proposed cascade method is that, under certain conditions, classification time actually decreases as the size of the database increases, a behavior that is in stark contrast to the behavior of typical nearest neighbor classification systems. The proposed methods are evaluated experimentally in several different applications: hand shape recognition, off-line character recognition, online character recognition, and efficient retrieval of time series. In all datasets, the proposed methods lead to significant improvements in accuracy and efficiency compared to existing state-of-the-art methods. In some datasets, the general-purpose methods introduced in this thesis even outperform domain-specific methods that have been custom-designed for such datasets.