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

2021

Derzis: A Path Aware Linked Data Crawler

Authors
dos Santos, AF; Leal, JP;

Publication
10th Symposium on Languages, Applications and Technologies, SLATE 2021, July 1-2, 2021, Vila do Conde/Póvoa de Varzim, Portugal.

Abstract
Consuming Semantic Web data presents several challenges, from the number of datasets it is composed of, to the (very) large size of some of those datasets and the uncertain availability of querying endpoints. According to its core principles, accessing linked data can be done simply by dereferencing the IRIs of RDF resources. This is a light alternative both for clients and servers when compared to dataset dumps or SPARQL endpoints. The linked data interface does not support complex querying, but using it recursively may suffice to gather information about RDF resources, or to extract the relevant sub-graph which can then be processed and queried using other methods. We present Derzis1, an open source semantic web crawler capable of traversing the linked data cloud starting from a set of seed resources. Derzis maintains information about the paths followed while crawling, which allows to define property path-based restrictions to the crawling frontier.

2021

Open source collection of gamified programming exercises

Authors
Swacha, J; Naprawski, T; Queirós, R; Paiva, JC; Leal, JP; de Vita, CG; Mellone, G; Montella, R; Ljubenkov, D; Kosta, S;

Publication
Proceedings of the Information Systems Education Conference, ISECON

Abstract
Computer programming courses are considered difficult. They can be made more engaging for students by incorporating game elements in a process known as gamification. In order to make it easier to facilitate this process in practice, several European universities collaborated in a joint project aimed at developing a framework for application of gamification to programming education. The framework includes the specification of the gamification scheme and the exercise definition format, an open source toolkit for preparing the gamified exercises and an interactive learning environment to present them to the students, and, last but not least, an open source collection of gamified programming exercises. In this paper, we present a work-in-progress on the last element, describing the current contents of the collection and planned directions for its extension.

2021

Refactoring the Whitby Intelligent Tutoring System for Clean Architecture

Authors
Brown, PS; Dimitrova, V; Hart, G; Cohn, AG; Moura, P;

Publication
THEORY AND PRACTICE OF LOGIC PROGRAMMING

Abstract
Whitby is the server-side of an Intelligent Tutoring System application for learning SystemTheoretic Process Analysis (STPA), a methodology used to ensure the safety of anything that can be represented with a systems model. The underlying logic driving the reasoning behind Whitby is Situation Calculus, which is a many-sorted logic with situation, action, and object sorts. The Situation Calculus is applied to Ontology Authoring and Contingent Scaffolding: the primary activities within Whitby. Thus many fluents and actions are aggregated in Whitby from these two sub-applications and from Whitby itself, but all are available through a common situation query interface that does not depend upon any of the fluents or actions. Each STPA project in Whitby is a single situation term, which is queried for fluents that include the ontology, and to determine what pedagogical interventions to offer. Initially Whitby was written in Prolog using a module system. In the interest of a cleaner architecture and implementation with improved code reuse and extensibility, the initial application was refactored into Logtalk. This refactoring includes decoupling the Situation Calculus reasoner, Ontology Authoring framework, and Contingent Scaffolding framework into third-party libraries that can be reused in other applications. This extraction was achieved by inverting dependencies via Logtalk protocols and categories, which are reusable interfaces and components that provide functionally cohesive sets of predicate declarations and predicate definitions. In this paper the architectures of two iterations of Whitby are evaluated with respect to the motivations behind the refactor: clean architecture enabling code reuse and extensibility.

2021

On the correctness and efficiency of a novel lock-free hash trie map design

Authors
Areias, M; Rocha, R;

Publication
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING

Abstract
Hash tries are a trie-based data structure with nearly ideal characteristics for the implementation of hash maps. In this paper, we present a novel, simple and scalable hash trie map design that fully supports the concurrent search, insert and remove operations on hash maps. To the best of our knowledge, our proposal is the first that puts together the following characteristics: (i) be lock free; (ii) use fixed size data structures; and (iii) maintain the access to all internal data structures as persistent memory references. Our design is modular enough to allow different types of configurations aimed for different performances in memory usage and execution time and can be easily implemented in any type of language, library or within other complex data structures. We discuss in detail the key algorithms required to easily reproduce our implementation by others and we present a proof of correctness showing that our proposal is linearizable and lock-free for the search, insert and remove operations. Experimental results show that our proposal is quite competitive when compared against other state-of-the-art proposals implemented in Java.

2021

On the implementation of memory reclamation methods in a lock-free hash trie design

Authors
Moreno, P; Areias, M; Rocha, R;

Publication
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING

Abstract
Hash tries are a trie-based data structure with nearly ideal characteristics for the implementation of hash maps. Starting from a particular lock-free hash map data structure, named Lock-Free Hash Tries, we focus on solving the problem of memory reclamation without losing the lock-freedom property. To the best of our knowledge, outside garbage collected environments, there is no current implementation of hash maps that is able to reclaim memory in a lock-free manner. To achieve this goal, we propose an approach for memory reclamation specific to Lock-Free Hash Tries that explores the characteristics of its structure in order to achieve efficient memory reclamation with low and well-defined memory bounds. We present and discuss in detail the key algorithms required to easily reproduce our implementation by others. Experimental results show that our approach obtains better results when compared with other state-of-the-art memory reclamation methods and provides a competitive and scalable hash map implementation, if compared to lock-based implementations.

2021

Towards an Elastic Lock-Free Hash Trie Design

Authors
Areias, M; Rocha, R;

Publication
2021 20TH INTERNATIONAL SYMPOSIUM ON PARALLEL AND DISTRIBUTED COMPUTING (ISPDC)

Abstract
A key aspect of any hash map design is the problem of dynamically resizing it in order to deal with hash collisions. In this context, elasticity refers to the ability to automatically resize the internal data structures that support the hash map operations in order to meet varying workloads, thus optimizing the overall memory consumption of the hash map. This work extends a previous lock-free hash trie design to support elastic hashing, i.e., expand saturated hash levels and compress unused hash levels, such that, at each point in time, the number of levels in a path matches the current demand as closely as possible. Experimental results show that elasticity effectively improves the search operation and, in doing so, our design becomes very competitive when compared to other state-of-the-art designs implemented in Java.

  • 40
  • 208