Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
Publications

Publications by CRACS

2010

Reusable and Inter-Operable Web-Based Intelligent Tutoring Systems Using SCORM 2004

Authors
Santos, G; Figueira, A;

Publication
PROCEEDINGS OF THE 9TH EUROPEAN CONFERENCE ON E-LEARNING, VOL 1

Abstract
For several years Intelligent Tutoring Systems (ITSs) have been developed and shown to lead to impressive improvement in student learning in a range of domains. Some of the most important limitations of ITSs are that their development is very time consuming, and they cannot be reused or imported to different platforms. The main benefits of the Sharable Content Object Reference Model (SCORM) are interoperability and reusability. Based on the SCORM Sequencing and Navigation (SN) specification we have developed an approach for implementing Web-Based SCORM compliant ITSs that are therefore reusable and interoperable. The main objective of this paper is to describe our approach and explain how to implement SCORM compliant ITSs using as an example, a prototype that we built.

2010

PARALLEL CALCULATION OF SUBGRAPH CENSUS IN BIOLOGICAL NETWORKS

Authors
Ribeiro, P; Silva, F; Lopes, L;

Publication
BIONFORMATICS 2010: PROCEEDINGS OF THE FIRST INTERNATIONAL CONFERENCE ON BIOINFORMATICS

Abstract
Mining meaningful data from complex biological networks is a critical task in many areas of research. One important example is calculating the frequency of all subgraphs of a certain size, also known as the sub graph census problem. This can provide a very comprehensive structural characterization of a network and is also used as an intermediate step in the computation of network motifs, an important basic building block of networks, that try to bridge the gap between structure and function. The subgraph census problem is com-putationally hard and here we present several parallel strategies to solve this problem. Our initial strategies were refined towards achieving an efficient and scalable adaptive parallel algorithm. This algorithm achieves almost linear speedups up to 128 cores when applied to a representative set of biological networks from different domains and makes the calculation of census for larger subgraph sizes feasible.

2010

g-tries: an efficient data structure for discovering network motifs

Authors
Pinto Ribeiro, PM; Silva, FMA;

Publication
Proceedings of the 2010 ACM Symposium on Applied Computing (SAC), Sierre, Switzerland, March 22-26, 2010

Abstract
In this paper we propose a novel specialized data structure that we call g-trie, designed to deal with collections of subgraphs. The main conceptual idea is akin to a prefix tree in the sense that we take advantage of common topology by constructing a multiway tree where the descendants of a node share a common substructure. We give algorithms to construct a g-trie, to list all stored subgraphs, and to find occurrences on another graph of the subgraphs stored in the g-trie. We evaluate the implementation of this structure and its associated algorithms on a set of representative benchmark biological networks in order to find network motifs. To assess the efficiency of our algorithms we compare their performance with other known network motif algorithms also implemented in the same common platform. Our results show that indeed, g-tries are a feasible, adequate and very efficient data structure for network motifs discovery, clearly outperforming previous algorithms and data structures. © 2010 ACM.

2010

Efficient Parallel Subgraph Counting Using G-Tries

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

Lightweight Fault-Tolerance for Peer-to-Peer Middleware

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

Efficient Subgraph Frequency Estimation with G-Tries

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.

  • 152
  • 201