2010
Authors
Pinto Ribeiro, PM; Silva, FMA; Lopes, LMB;
Publication
Proceedings of the 2010 IEEE International Conference on Cluster Computing, Heraklion, Crete, Greece, 20-24 September, 2010
Abstract
Finding and counting the occurrences of a collection of subgraphs within another larger network is a computationally hard problem, closely related to graph isomorphism. The subgraph count is by itself a very powerful characterization of a network and it is crucial for other important network measurements. G-tries are a specialized data-structure designed to store and search for subgraphs. By taking advantage of subgraph common substructure, g-tries can provide considerable speedups over previously used methods. In this paper we present a parallel algorithm based precisely on gtries that is able to efficiently find and count subgraphs. The algorithm relies on randomized receiver-initiated dynamic load balancing and is able to stop its computation at any given time, efficiently store its search position, divide what is left to compute in two halfs, and resume from where it left. We apply our algorithm to several representative real complex networks from various domains and examine its scalability. We obtain an almost linear speedup up to 128 processors, thus allowing us to reach previously unfeasible limits. We showcase the multidisciplinary potential of the algorithm by also applying it to network motif discovery. © 2010 IEEE.
2010
Authors
Martins, R; Narasimhan, P; Lopes, L; Silva, F;
Publication
2010 29TH IEEE INTERNATIONAL SYMPOSIUM ON RELIABLE DISTRIBUTED SYSTEMS SRDS 2010
Abstract
We address the problem of providing transparent, lightweight, fault-tolerance mechanisms for generic peer-to-peer middleware systems. The main idea is to use the peer-to-peer overlay to provide for fault-tolerance rather than support it higher up in the middleware architecture, e.g. in the form of services. To evaluate our approach we have implemented a fault-tolerant middleware prototype that uses a hierarchical peer-to-peer overlay in which the leaf peers connect to sensors that provide data streams. Clients connect to the root of the overlay and request streams that are routed upwards through intermediate peers in the overlay up to the client. We report encouraging preliminary results for latency, jitter and resource consumption for both the non-faulty and faulty cases.
2010
Authors
Ribeiro, P; Silva, F;
Publication
ALGORITHMS IN BIOINFORMATICS
Abstract
Many biological networks contain recurring overrepresented elements, called network motifs. Finding these substructures is a computationally hard task related to graph isomorphism. G-Tries are an efficient data structure, based on multiway trees, capable of efficiently identifying common substructures in a set of subgraphs. They are highly successful in constraining the search space when finding the occurrences of those subgraphs in a larger original graph. This leads to speedups up to 100 times faster than previous methods that aim for exact and complete results. In this paper we present a new efficient sampling algorithm for subgraph frequency estimation based on g-tries. It is able to uniformly traverse a fraction of the search space, providing an accurate unbiased estimation of subgraph frequencies. Our results show that in the same amount of time our algorithm achieves better precision than previous methods, as it is able to sustain higher sampling speeds.
2010
Authors
Leal, JP; Queiros, R;
Publication
4TH INTERNATIONAL TECHNOLOGY, EDUCATION AND DEVELOPMENT CONFERENCE (INTED 2010)
Abstract
In recent years the concept of eLearning Framework emerged associated with several initiatives promoted by educational organizations. These initiatives share a common goal: to create flexible learning environments by integrating heterogeneous systems already available in many educational institutions. The paper provides an introductory survey on eLearning Frameworks. It gathers information on these initiatives categorizes them and compares their features regarding a set of predefined criteria such as: architecture, business model, primary user groups, technical implementations, adopted standards, maturity and future development.
2010
Authors
Leal, JP; Queiros, R;
Publication
ICEIS 2010: PROCEEDINGS OF THE 12TH INTERNATIONAL CONFERENCE ON ENTERPRISE INFORMATION SYSTEMS, VOL 1: DATABASES AND INFORMATION SYSTEMS INTEGRATION
Abstract
The wide acceptance of digital repositories today in the eLearning field raises several interoperability issues. In this paper we present the interoperability features of a service oriented repository of learning objects called crimsonHex. These features are compliant with the existing standards and we propose extensions to the IMS interoperability recommendation, adding new functions, formalizing message interchange and providing also a REST interface. To validate the proposed extensions and its implementation in crimsonHex we developed a repository plugin for Moodle 2.0 that is expected to be included in the next release of this popular learning management system.
2010
Authors
Leal, JP; Queiros, R; Ferreira, D;
Publication
ADVANCES IN WEB-BASED LEARNING-ICWL 2010
Abstract
The e-Framework is arguably the most prominent e-learning framework currently in use. For this reason it was selected as basis for modelling a programming exercises evaluation service. The purpose of this type of evaluator is to mark and grade exercises in computer programming courses and in programming contests. By exposing its functions as services a programming exercise evaluator is able to participate in business processes integrating different system types, such as Programming Contest Management Systems, Learning Management Systems, Integrated Development Environments and Learning Object Repositories. This paper formalizes the approaches to be used in the implementation of a programming exercise evaluator as a service on the e-Framework.
The access to the final selection minute is only available to applicants.
Please check the confirmation e-mail of your application to obtain the access code.