3 resultados para tag data structure
em Biblioteca Digital da Produção Intelectual da Universidade de São Paulo
Resumo:
The design of a network is a solution to several engineering and science problems. Several network design problems are known to be NP-hard, and population-based metaheuristics like evolutionary algorithms (EAs) have been largely investigated for such problems. Such optimization methods simultaneously generate a large number of potential solutions to investigate the search space in breadth and, consequently, to avoid local optima. Obtaining a potential solution usually involves the construction and maintenance of several spanning trees, or more generally, spanning forests. To efficiently explore the search space, special data structures have been developed to provide operations that manipulate a set of spanning trees (population). For a tree with n nodes, the most efficient data structures available in the literature require time O(n) to generate a new spanning tree that modifies an existing one and to store the new solution. We propose a new data structure, called node-depth-degree representation (NDDR), and we demonstrate that using this encoding, generating a new spanning forest requires average time O(root n). Experiments with an EA based on NDDR applied to large-scale instances of the degree-constrained minimum spanning tree problem have shown that the implementation adds small constants and lower order terms to the theoretical bound.
Resumo:
Spatial data warehouses (SDWs) allow for spatial analysis together with analytical multidimensional queries over huge volumes of data. The challenge is to retrieve data related to ad hoc spatial query windows according to spatial predicates, avoiding the high cost of joining large tables. Therefore, mechanisms to provide efficient query processing over SDWs are essential. In this paper, we propose two efficient indices for SDW: the SB-index and the HSB-index. The proposed indices share the following characteristics. They enable multidimensional queries with spatial predicate for SDW and also support predefined spatial hierarchies. Furthermore, they compute the spatial predicate and transform it into a conventional one, which can be evaluated together with other conventional predicates by accessing a star-join Bitmap index. While the SB-index has a sequential data structure, the HSB-index uses a hierarchical data structure to enable spatial objects clustering and a specialized buffer-pool to decrease the number of disk accesses. The advantages of the SB-index and the HSB-index over the DBMS resources for SDW indexing (i.e. star-join computation and materialized views) were investigated through performance tests, which issued roll-up operations extended with containment and intersection range queries. The performance results showed that improvements ranged from 68% up to 99% over both the star-join computation and the materialized view. Furthermore, the proposed indices proved to be very compact, adding only less than 1% to the storage requirements. Therefore, both the SB-index and the HSB-index are excellent choices for SDW indexing. Choosing between the SB-index and the HSB-index mainly depends on the query selectivity of spatial predicates. While low query selectivity benefits the HSB-index, the SB-index provides better performance for higher query selectivity.
Resumo:
Aedes aegypti is the most important vector of dengue viruses in tropical and subtropical regions. Because vaccines are still under development, dengue prevention depends primarily on vector control. Population genetics is a common approach in research involving Ae. aegypti. In the context of medical entomology, wing morphometric analysis has been proposed as a strong and low-cost complementary tool for investigating population structure. Therefore, we comparatively evaluated the genetic and phenotypic variability of population samples of Ae. aegypti from four sampling sites in the metropolitan area of Sao Paulo city, Brazil. The distances between the sites ranged from 7.1 to 50 km. This area, where knowledge on the population genetics of this mosquito is incipient, was chosen due to the thousands of dengue cases registered yearly. The analysed loci were polymorphic, and they revealed population structure (global F-ST = 0.062; p < 0.05) and low levels of gene flow (Nm = 0.47) between the four locations. Principal component and discriminant analyses of wing shape variables (18 landmarks) demonstrated that wing polymorphisms were only slightly more common between populations than within populations. Whereas microsatellites allowed for geographic differentiation, wing geometry failed to distinguish the samples. These data suggest that microevolution in this species may affect genetic and morphological characters to different degrees. In this case, wing shape was not validated as a marker for assessing population structure. According to the interpretation of a previous report, the wing shape of Ae. aegypti does not vary significantly because it is stabilised by selective pressure. (C) 2011 Elsevier B.V. All rights reserved.