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.

Nonexistence of global solutions for a class of complex vector fields on two-torus

The goal of this paper is study the global solvability of a class of complex vector fields of the special form L = partial derivative/partial derivative t + (a + ib)(x)partial derivative/partial derivative x, a, b epsilon C(infinity) (S(1) ; R), defined on two-torus T(2) congruent to R(2)/2 pi Z(2). The kernel of transpose operator L is described and the solvability near the characteristic set is also studied. (c) 2008 Elsevier Inc. All rights reserved.

MODELING THE EVOLUTION OF COMPLEX NETWORKS THROUGH THE PATH-STAR TRANSFORMATION AND OPTIMAL MULTIVARIATE METHODS

The topology of real-world complex networks, such as in transportation and communication, is always changing with time. Such changes can arise not only as a natural consequence of their growth, but also due to major modi. cations in their intrinsic organization. For instance, the network of transportation routes between cities and towns ( hence locations) of a given country undergo a major change with the progressive implementation of commercial air transportation. While the locations could be originally interconnected through highways ( paths, giving rise to geographical networks), transportation between those sites progressively shifted or was complemented by air transportation, with scale free characteristics. In the present work we introduce the path-star transformation ( in its uniform and preferential versions) as a means to model such network transformations where paths give rise to stars of connectivity. It is also shown, through optimal multivariate statistical methods (i.e. canonical projections and maximum likelihood classification) that while the US highways network adheres closely to a geographical network model, its path-star transformation yields a network whose topological properties closely resembles those of the respective airport transportation network.

Sensitivity of complex networks measurements

Complex networks obtained from real-world networks are often characterized by incompleteness and noise, consequences of imperfect sampling as well as artifacts in the acquisition process. Because the characterization, analysis and modeling of complex systems underlain by complex networks are critically affected by the quality and completeness of the respective initial structures, it becomes imperative to devise methodologies for identifying and quantifying the effects of the sampling on the network structure. One way to evaluate these effects is through an analysis of the sensitivity of complex network measurements to perturbations in the topology of the network. In this paper, measurement sensibility is quantified in terms of the relative entropy of the respective distributions. Three particularly important kinds of progressive perturbations to the network are considered, namely, edge suppression, addition and rewiring. The measurements allowing the best balance of stability (smaller sensitivity to perturbations) and discriminability (separation between different network topologies) are identified with respect to each type of perturbation. Such an analysis includes eight different measurements applied on six different complex networks models and three real-world networks. This approach allows one to choose the appropriate measurements in order to obtain accurate results for networks where sampling bias cannot be avoided-a very frequent situation in research on complex networks.

On the efficiency of data representation on the modeling and characterization of complex networks

Specific choices about how to represent complex networks can have a substantial impact on the execution time required for the respective construction and analysis of those structures. In this work we report a comparison of the effects of representing complex networks statically by adjacency matrices or dynamically by adjacency lists. Three theoretical models of complex networks are considered: two types of Erdos-Renyi as well as the Barabasi-Albert model. We investigated the effect of the different representations with respect to the construction and measurement of several topological properties (i.e. degree, clustering coefficient, shortest path length, and betweenness centrality). We found that different forms of representation generally have a substantial effect on the execution time, with the sparse representation frequently resulting in remarkably superior performance. (C) 2011 Elsevier B.V. All rights reserved.

Concentric characterization and classification of complex network nodes: Application to an institutional collaboration network

Differently from theoretical scale-free networks, most real networks present multi-scale behavior, with nodes structured in different types of functional groups and communities. While the majority of approaches for classification of nodes in a complex network has relied on local measurements of the topology/connectivity around each node, valuable information about node functionality can be obtained by concentric (or hierarchical) measurements. This paper extends previous methodologies based on concentric measurements, by studying the possibility of using agglomerative clustering methods, in order to obtain a set of functional groups of nodes, considering particular institutional collaboration network nodes, including various known communities (departments of the University of Sao Paulo). Among the interesting obtained findings, we emphasize the scale-free nature of the network obtained, as well as identification of different patterns of authorship emerging from different areas (e.g. human and exact sciences). Another interesting result concerns the relatively uniform distribution of hubs along concentric levels, contrariwise to the non-uniform pattern found in theoretical scale-free networks such as the BA model. (C) 2008 Elsevier B.V. All rights reserved.

Border trees of complex networks

The comprehensive characterization of the structure of complex networks is essential to understand the dynamical processes which guide their evolution. The discovery of the scale-free distribution and the small-world properties of real networks were fundamental to stimulate more realistic models and to understand important dynamical processes related to network growth. However, the properties of the network borders (nodes with degree equal to 1), one of its most fragile parts, remained little investigated and understood. The border nodes may be involved in the evolution of structures such as geographical networks. Here we analyze the border trees of complex networks, which are defined as the subgraphs without cycles connected to the remainder of the network (containing cycles) and terminating into border nodes. In addition to describing an algorithm for identification of such tree subgraphs, we also consider how their topological properties can be quantified in terms of their depth and number of leaves. We investigate the properties of border trees for several theoretical models as well as real-world networks. Among the obtained results, we found that more than half of the nodes of some real-world networks belong to the border trees. A power-law with cut-off was observed for the distribution of the depth and number of leaves of the border trees. An analysis of the local role of the nodes in the border trees was also performed.

Characterizing topological and dynamical properties of complex networks without border effects

The properties of complex networks are highly Influenced by border effects frequently found as a consequence of the finite nature of real-world networks as well as network Sampling Therefore, it becomes critical to devise effective means for sound estimation of net work topological and dynamical properties will le avoiding these types of artifacts. In the current work, an algorithm for minimization of border effects is proposed and discussed, and its potential IS Illustrated with respect to two real-world networks. namely bone canals and air transportation (C) 2009 Elsevier B.V. All rights reserved.

The defensive functions of plant inhibitors are not restricted to insect enzyme inhibition

Three plant proteinase inhibitors BbKI (kallikrein inhibitor) and BbCI (cruzipain inhibitor) from Bauhinia bouhinioides, and a BrTI (trypsin inhibitor) from B. rufa, were examined for other effects in Callosobruchus maculatus development; of these only BrTI affected bruchid emergence. BrTI and BbKI share 81% identities in their primary sequences and the major differences between them are the regions comprising the RGD and RGE motifs in BrTI. These sequences were shown to be essential for BrTI insecticidal activity, since a modified BbKI [that is a recombinant form (BbKIm) with some amino acid residues replaced by those found in BrTI sequence] also strongly inhibited insect development. By using synthetic peptides related to the BrTI sequence, YLEAPVARGDGGLA-NH(2) (RGE) and IVYYPDRGETGL-NH(2) (RGE), it was found that the peptide with an RGE sequence was able to block normal development of C. maculatus larvae (ED(50) 0.16% and LD(50) 0.09%), this being even more effective than the native protein. (C) 2009 Elsevier Ltd. All rights reserved.

A note on a practical relationship between filter coefficients and scaling and wavelet functions of Discrete Wavelet Transforms

In this paper, the relationship between the filter coefficients and the scaling and wavelet functions of the Discrete Wavelet Transform is presented and exemplified from a practical point-of-view. The explanations complement the wavelet theory, that is well documented in the literature, being important for researchers who work with this tool for time-frequency analysis. (c) 2011 Elsevier Ltd. All rights reserved.

Random sums of exchangeable variables and actuarial applications

In this paper we study the accumulated claim in some fixed time period, skipping the classical assumption of mutual independence between the variables involved. Two basic models are considered: Model I assumes that any pair of claims are equally correlated which means that the corresponding square-integrable sequence is exchangeable one. Model 2 states that the correlations between the adjacent claims are the same. Recurrence and explicit expressions for the joint probability generating function are derived and the impact of the dependence parameter (correlation coefficient) in both models is examined. The Markov binomial distribution is obtained as a particular case under assumptions of Model 2. (C) 2007 Elsevier B.V. All rights reserved.

On E-functions of semisimple Lie groups

We develop and describe continuous and discrete transforms of class functions on a compact semisimple, but not simple, Lie group G as their expansions into series of special functions that are invariant under the action of the even subgroup of the Weyl group of G. We distinguish two cases of even Weyl groups-one is the direct product of even Weyl groups of simple components of G and the second is the full even Weyl group of G. The problem is rather simple in two dimensions. It is much richer in dimensions greater than two-we describe in detail E-transforms of semisimple Lie groups of rank 3.

C(k)-solvability near the characteristic set for a class of planar complex vector fields of infinite type

This paper deals with semi-global C(k)-solvability of complex vector fields of the form L = partial derivative/partial derivative t + x(r) (a(x) + ib(x))partial derivative/partial derivative x, r >= 1, defined on Omega(epsilon) = (-epsilon, epsilon) x S(1), epsilon > 0, where a and b are C(infinity) real-valued functions in (-epsilon, epsilon). It is shown that the interplay between the order of vanishing of the functions a and b at x = 0 influences the C(k)-solvability at Sigma = {0} x S(1). When r = 1, it is permitted that the functions a and b of L depend on the x and t variables, that is, L = partial derivative/partial derivative t + x(a(x, t) + ib(x, t))partial derivative/partial derivative x, where (x, t) is an element of Omega(epsilon).

Gevrey solvability near the characteristic set for a class of planar complex vector fields of infinite type

We study the Gevrey solvability of a class of complex vector fields, defined on Omega(epsilon) = (-epsilon, epsilon) x S(1), given by L = partial derivative/partial derivative t + (a(x) + ib(x))partial derivative/partial derivative x, b not equivalent to 0, near the characteristic set Sigma = {0} x S(1). We show that the interplay between the order of vanishing of the functions a and b at x = 0 plays a role in the Gevrey solvability. (C) 2008 Elsevier Inc. All rights reserved.