Aggregated Multicast — A Comparative Study

Though IP multicast is resource ef£cient in delivering data to a group of members simultaneously, it suffers from scalability problem with the number of concurrently active multicast groups because it requires a router to keep forwarding state for every multicast tree passing through it. To solve this state scalability problem, we proposed a scheme, called aggregated multicast. The key idea is that multiple groups are forced to share a single delivery tree. In our earlier work, we introduced the basic concept of aggregated multicast and presented some initial results to show that multicast state can be reduced. In this paper, we develop a more quantitative assessment of the cost/bene£t trade-offs. We propose an algorithm to assign multicast groups to delivery trees with controllable cost and introduce metrics to measure multicast state and tree management overhead for multicast schemes. We then compare aggregated multicast with conventional multicast schemes, such as source speci£c tree scheme and shared tree scheme. Our extensive simulations show that aggregated multicast can achieve signi£cant routing state and tree management overhead reduction while containing the expense of extra resources (bandwidth waste and tunnelling overhead). We conclude that aggregated multicast is a very cost-effective and promising direction for scalable transit domain multicast provisioning.

Extração de dados de produtos em páginas de comércio eletrônico

Pós-graduação em Ciência da Computação - IBILCE

Implementazione ed analisi di un framework basato su Cloud per la valutazione di algoritmi di data Distribution Management

Il Data Distribution Management (DDM) è un componente dello standard High Level Architecture. Il suo compito è quello di rilevare le sovrapposizioni tra update e subscription extent in modo efficiente. All'interno di questa tesi si discute la necessità di avere un framework e per quali motivi è stato implementato. Il testing di algoritmi per un confronto equo, librerie per facilitare la realizzazione di algoritmi, automatizzazione della fase di compilazione, sono motivi che sono stati fondamentali per iniziare la realizzazione framework. Il motivo portante è stato che esplorando articoli scientifici sul DDM e sui vari algoritmi si è notato che in ogni articolo si creavano dei dati appositi per fare dei test. L'obiettivo di questo framework è anche quello di riuscire a confrontare gli algoritmi con un insieme di dati coerente. Si è deciso di testare il framework sul Cloud per avere un confronto più affidabile tra esecuzioni di utenti diversi. Si sono presi in considerazione due dei servizi più utilizzati: Amazon AWS EC2 e Google App Engine. Sono stati mostrati i vantaggi e gli svantaggi dell'uno e dell'altro e il motivo per cui si è scelto di utilizzare Google App Engine. Si sono sviluppati quattro algoritmi: Brute Force, Binary Partition, Improved Sort, Interval Tree Matching. Sono stati svolti dei test sul tempo di esecuzione e sulla memoria di picco utilizzata. Dai risultati si evince che l'Interval Tree Matching e l'Improved Sort sono i più efficienti. Tutti i test sono stati svolti sulle versioni sequenziali degli algoritmi e che quindi ci può essere un riduzione nel tempo di esecuzione per l'algoritmo Interval Tree Matching.

Probabilidades de daño por viento Zonda en la floración de frutales, vid y olivos

La agricultura de Mendoza está expuesta a daños producidos por viento Zonda, cuya frecuencia y magnitud no han sido suficientemente estudiadas. Por ello se ha procurado determinar las características de los vientos Zonda y la probabilidad de que sean afectados cultivos de vid, olivo y frutales. Se tuvieron en cuenta los Zondas registrados durante 44 años (1958-2002) por la estación agrometeorológica Chacras de Coria de la Facultad de Ciencias Agrarias de la UNCuyo, en el período de floración de las principales variedades de los cultivos mencionados. El análisis se realizó cada diez días mediante los parámetros que se consignan a continuación: Salto térmico: diferencia entre las temperaturas máximas del día anterior y del día con Zonda, subdividido en las siguientes categorías: leve: 1 a 5 °C; fuerte: 6 a 10 °C; severo: mayor de 10 °C. Poder secante: evaporación del día del evento subdividido en las siguientes categorías: pequeño: 1 a 6 mm/día; grande: 7 a 12mm/día; muy grande: superior a 12 mm/día. Duración del evento, subdividido en las siguientes categorías: corta: 1a 8 hs; larga: 9 a 16 hs; muy larga: superior a 16 hs. La interacción y combinación de estos parámetros en sus diversas magnitudes determina el efecto dañino del Zonda representado a través del Índice Climático de Peligrosidad (ICP) de los vientos, que demues tra que todo el período estudiado tiene algún grado de riesgo. Se concluye que: El 47 % del total de casos de viento Zonda corresponde a agosto y la primera semana de septiembre. Las probabilidades de ocurrencia de un salto térmico severo están circunscriptas a agosto y primeros días de septiembre. En todo el período existen probabilidades superiores al 2 % de que ocurra un Zonda con poder secante muy grande. Eventos de muy larga duración tienen relativamente alta probabilidad de ocurrencia en agosto y primeros días de septiembre. Se puede determinar la probabilidad de daño para un cultivo confrontado los valores del ICP con la fenodata de plena floración correspondiente, lo cual constituye una herramienta para la defensa pasiva. Se suministran las fenodatas de las principales variedades de vid, olivo, duraznero y ciruelo, que son las especies cultivadas más importantes en el área de influencia de la estación agrometeorológica de Chacras de Coria.

Auditory-visual speech integration by prelinguistic infants: Perception of an emergent consonant in the McGurk effect

The McGurk effect, in which auditory [ba] dubbed onto [go] lip movements is perceived as da or tha, was employed in a real-time task to investigate auditory-visual speech perception in prelingual infants. Experiments 1A and 1B established the validity of real-time dubbing for producing the effect. In Experiment 2, 4(1)/(2)-month-olds were tested in a habituation-test paradigm, in which 2 an auditory-visual stimulus was presented contingent upon visual fixation of a live face. The experimental group was habituated to a McGurk stimulus (auditory [ba] visual [ga]), and the control group to matching auditory-visual [ba]. Each group was then presented with three auditory-only test trials, [ba], [da], and [deltaa] (as in then). Visual-fixation durations in test trials showed that the experimental group treated the emergent percept in the McGurk effect, [da] or [deltaa], as familiar (even though they had not heard these sounds previously) and [ba] as novel. For control group infants [da] and [deltaa] were no more familiar than [ba]. These results are consistent with infants'perception of the McGurk effect, and support the conclusion that prelinguistic infants integrate auditory and visual speech information. (C) 2004 Wiley Periodicals, Inc.

LNT: a logical neighbor tree secure group communication scheme for wireless sensor networks

Secure group communication is a paradigm that primarily designates one-to-many communication security. The proposed works relevant to secure group communication have predominantly considered the whole network as being a single group managed by a central powerful node capable of supporting heavy communication, computation and storage cost. However, a typical Wireless Sensor Network (WSN) may contain several groups, and each one is maintained by a sensor node (the group controller) with constrained resources. Moreover, the previously proposed schemes require a multicast routing support to deliver the rekeying messages. Nevertheless, multicast routing can incur heavy storage and communication overheads in the case of a wireless sensor network. Due to these two major limitations, we have reckoned it necessary to propose a new secure group communication with a lightweight rekeying process. Our proposal overcomes the two limitations mentioned above, and can be applied to a homogeneous WSN with resource-constrained nodes with no need for a multicast routing support. Actually, the analysis and simulation results have clearly demonstrated that our scheme outperforms the previous well-known solutions.

On group strategy-proof mechanisms for a many-to-one matching model

For the many-to-one matching model in which firms have substitutable and quota q-separable preferences over subsets of workers we show that the workers-optimal stable mechanism is group strategy-proof for the workers. In order to prove this result, we also show that under this domain of preferences (which contains the domain of responsive preferences of the college admissions problem) the workers-optimal stable matching is weakly Pareto optimal for the workers and the Blocking Lemma holds as well. We exhibit an example showing that none of these three results remain true if the preferences of firms are substitutable but not quota q-separable.

Tree automorphisms and quasi-isometries of Thompson's group F

We prove that automorphisms of the infinite binary rooted tree T2 do not yield quasi-isometries of Thompson's group F, except for the map which reverses orientation on the unit interval, a natural outer automorphism of F. This map, together with the identity map, forms a subgroup of Aut(T2) consisting of 2-adic automorphisms, following standard terminology used in the study of branch groups. However, for more general p, we show that the analgous groups of p-adic tree automorphisms do not give rise to quasiisometries of F(p).

Cryptic diversity among Western Palearctic tree frogs: postglacial range expansion, range limits, and secondary contacts of three European tree frog lineages (Hyla arborea group).

We characterize divergence times, intraspecific diversity and distributions for recently recognized lineages within the Hyla arborea species group, based on mitochondrial and nuclear sequences from 160 localities spanning its whole distribution. Lineages of H. arborea, H. orientalis, H. molleri have at least Pliocene age, supporting species level divergence. The genetically uniform Iberian H. molleri, although largely isolated by the Pyrenees, is parapatric to H. arborea, with evidence for successful hybridization in a small Aquitanian corridor (southwestern France), where the distribution also overlaps with H. meridionalis. The genetically uniform H. arborea, spread from Crete to Brittany, exhibits molecular signatures of a postglacial range expansion. It meets different mtDNA clades of H. orientalis in NE-Greece, along the Carpathians, and in Poland along the Vistula River (there including hybridization). The East-European H. orientalis is strongly structured genetically. Five geographic mitochondrial clades are recognized, with a molecular signature of postglacial range expansions for the clade that reached the most northern latitudes. Hybridization with H. savignyi is suggested in southwestern Turkey. Thus, cryptic diversity in these Pliocene Hyla lineages covers three extremes: a genetically poor, quasi-Iberian endemic (H. molleri), a more uniform species distributed from the Balkans to Western Europe (H. arborea), and a well-structured Asia Minor-Eastern European species (H. orientalis).

Timeframe of speciation inferred from secondary contact zones in the European tree frog radiation (Hyla arborea group).

BACKGROUND: Hybridization between incipient species is expected to become progressively limited as their genetic divergence increases and reproductive isolation proceeds. Amphibian radiations and their secondary contact zones are useful models to infer the timeframes of speciation, but empirical data from natural systems remains extremely scarce. Here we follow this approach in the European radiation of tree frogs (Hyla arborea group). We investigated a natural hybrid zone between two lineages (Hyla arborea and Hyla orientalis) of Mio-Pliocene divergence (~5 My) for comparison with other hybrid systems from this group. RESULTS: We found concordant geographic distributions of nuclear and mitochondrial gene pools, and replicated narrow transitions (~30 km) across two independent transects, indicating an advanced state of reproductive isolation and potential local barriers to dispersal. This result parallels the situation between H. arborea and H. intermedia, which share the same amount of divergence with H. orientalis. In contrast, younger lineages show much stronger admixture at secondary contacts. CONCLUSIONS: Our findings corroborate the negative relationship between hybridizability and divergence time in European tree frogs, where 5 My are necessary to achieve almost complete reproductive isolation. Speciation seems to progress homogeneously in this radiation, and might thus be driven by gradual genome-wide changes rather than single speciation genes. However, the timescale differs greatly from that of other well-studied amphibians. General assumptions on the time necessary for speciation based on evidence from unrelated taxa may thus be unreliable. In contrast, comparative hybrid zone analyses within single radiations such as our case study are useful to appreciate the advance of speciation in space and time.

Mirror neurons in the tree of life, development and evolution of sensorimotor matching responses

Mirror neurons in the tree of life rappresenta lo sviluppo e l' evoluzione del sistema dei neuroni specchio nei primati umani, non - umani e di alcune specie di uccelli, utilizzando metodi cooptati dalla filosofia della biologia e la biologia teorica, per integrare dati relativi al sistema nervoso e al comportamento delle specie in esame.

DECISION TREE CLASSIFIERS FOR STAR/GALAXY SEPARATION

We study the star/galaxy classification efficiency of 13 different decision tree algorithms applied to photometric objects in the Sloan Digital Sky Survey Data Release Seven (SDSS-DR7). Each algorithm is defined by a set of parameters which, when varied, produce different final classification trees. We extensively explore the parameter space of each algorithm, using the set of 884,126 SDSS objects with spectroscopic data as the training set. The efficiency of star-galaxy separation is measured using the completeness function. We find that the Functional Tree algorithm (FT) yields the best results as measured by the mean completeness in two magnitude intervals: 14 <= r <= 21 (85.2%) and r >= 19 (82.1%). We compare the performance of the tree generated with the optimal FT configuration to the classifications provided by the SDSS parametric classifier, 2DPHOT, and Ball et al. We find that our FT classifier is comparable to or better in completeness over the full magnitude range 15 <= r <= 21, with much lower contamination than all but the Ball et al. classifier. At the faintest magnitudes (r > 19), our classifier is the only one that maintains high completeness (> 80%) while simultaneously achieving low contamination (similar to 2.5%). We also examine the SDSS parametric classifier (psfMag - modelMag) to see if the dividing line between stars and galaxies can be adjusted to improve the classifier. We find that currently stars in close pairs are often misclassified as galaxies, and suggest a new cut to improve the classifier. Finally, we apply our FT classifier to separate stars from galaxies in the full set of 69,545,326 SDSS photometric objects in the magnitude range 14 <= r <= 21.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).