Monografias em Ciência da Computação

2013

ABSTRACTS

Departmento de Informática 
Pontifícia Universidade Católica do Rio de Janeiro - PUC-Rio
Rio de Janeiro - Brazil


This file contains a list of the technical reports of the Departmento de Informática, Pontifícia Universidade Católica do Janeiro - PUC-Rio, Brazil, which are published in our series Monografias em Ciência da Computação (ISSN 0103-9741), edited by Prof. Carlos Lucena. Please note that the reports not available for download are available in their print format and can be obtained via the e-mail below.
For any questions, requests or suggestions, please contact:
Rosane Castilho bib-di@inf.puc-rio.br

Last update: 12/NOVEMBER/2013

INDEX

[MCC01/13]
MONTEIRO, I.T.; LEITÃO, C.F.; DE SOUZA, C.S. Interacting with the Web Navigation Helper: first lessons about mediated metacommunication for increased accessibility. 28 p. Eng. E-mail: clarisse@inf.puc-rio.br

Abstract: Semiotic Engineering is a semiotic theory of HCI in which human-computer interaction is viewed as a particular kind of computer-mediated human communication. In it, designers of interactive software are communicating their design vision to users. The designers' message tells the users about how, when, where and why to communicate with software in order to achieve various kinds of goals and effects, thus a case of metacommunication. In this document, we report and discuss findings of research on mediated metacommunication, as a strategy to address accessibility problems. We carried out a qualitative study with the Web Navigation Helper (WNH), a user agent designed to help users perform scripted activities on the Web. WNH assistance is given through mediation dialogs created by savvy end-users who act as helpers of users in need. We investigated how a small group of elderly users received different instances of mediated metacommunication created by helpers. The results of the study point at the promises and challenges of mediated metacommunication as a strategy for increasing accessibility on the Web.

 
[MCC02/13]
JENA, S.J.; POGGI, M. Harvest planning in the Brazilian sugar cane industry via mixed integer programming. 19 p. Eng. E-mail: poggi@inf.puc-rio.br

Abstract: This work addresses harvest planning problems that arise in the production of sugar and alcohol from sugar cane in Brazil. The planning is performed for two planning horizons, tactical and operational planning, such that the total sugar content in the harvested cane is maximized. The tactical planning comprises the entire harvest season that averages seven months. The operational planning considers a horizon from seven to thirty days. Both problems are solved by Mixed Integer Programming. The tactical planning is well handled. The model for the operational planning extends the one for the tactical planning and is presented in detail. Valid inequalities are introduced and three techniques are proposed to speed up finding quality solutions. These include preprocessing by grouping and filtering the distance matrix between fields, hot starting with construction heuristic solutions, and dividing and sequentially solving the resulting MIP program. Experiments are run over a set of real world and artificial instances. A case study illustrates the benefits of the proposed planning.

 
[MCC03/13]
VASCONCELOS, I.O.; VASCONCELOS, R.O.; BAPTISTA, G.L.B.; SEGUIN, C.P.; ENDLER, M. Desenvolvendo aplicações de rastreamento e comunicação móvel usando o middleware SDDL. 8 p. Eng. E-mail: endler@inf.puc-rio.br

Abstract: This article explains, and gives some details, of how an application prototye for mobile tracking and communication among roadside inspectors and vehicles called Acompanhamento Remoto de Fiscais e Frotas (ARFF) was developed using the Scalable Data Distribution Layer(SDDL) middleware.

 
[MCC04/13]
BRANCO, A.F; RODRIGUEZ, N.L.R.; ROSSETO, S. Determining the boundary cost and flexibility in wireless sensor networks. 20 p. Eng. E-mail: noemi@inf.puc-rio.br

Abstract: Several authors have proposed solutions for remotely updating wireless sensor network applications. These proposals usually make a trade-off in flexibility versus update cost. At one extreme, full-scale binary upgrades provide full flexibility at unacceptable communication cost, while at the other end parameter tuning typically provides the least expendable but also the least flexible form of updates. In this work, we describe WDvm, a platform that allows the programmer to experiment with different combinations of flexibility and cost, choosing the best fit for each application. WDvm provides a virtual machine which runs over TinyOS and which can be installed with different sets of ready-made components, facilitating tuning of the abstraction boundary that can be used for reconfiguration. A simple intermediate language runs over this virtual machine. Parameter-based configuration receives special attention in WDvm. Parameters are directly integrated into the intermediate language, allowing scripts to act both as simple parameter redefinitions and to determine new parameter values as a result of arbitrary operations. In this report, we describe the structure of WDvm and describe some experiments, in which we evaluate the overhead imposed by the virtual machine by comparing the execution of simple scripts with a TinyOS similar application. We also illustrate, through an example, the possibility of defining different abstraction boundaries for the virtual machine.

 
[MCC05/13]
ABREU NETTO, M.T.; LUCENA, C.J.P.; SANTOS NETO, B.F.; REIOLI, E.J.C.; FREIRE, F. A self-organizing and normative piloting system. 19 p. Eng. E-mail: lucena@inf.puc-rio.br

Abstract: The services and technologies inherent to computer networks have become part of society. However, its management by human administrators came at high cost and it is prone to failure, and the simple automation of management through software components may worsen the situation due to the wide variety of systems and unexpected behaviors. Autonomic networks were proposed to deal with this management problem by enabling systems to self-manage. But, in order to perform a self-management in an optimal, robust and secure way it is necessary to have a piloting system. The main goal of a piloting system is to regulate and adapt the virtual net-work in response to changing context in accordance with applicable high-level goals and policies. In this context, this report presents a self-organizing and normative piloting system that aims to govern the entities of the network in a decentralized way. Moreover, we provide a simulation environment that enable users to experiment and observe the network behavior in face of the application of different normative and organizational configurations of the piloting plane

 
[MCC06/13]
SILVA, L.D.N.; ENDLER, M.; RORIZ, M. MR-UDP: yet another reliable user datagram protocol, now for mobile nodes. 7 p. Eng. E-mail: endler@inf.puc-rio.br

Abstract: This paper describes the main characteristics and functioning of the Mobile Reliable UDP (MR-UDP). It extends Reliable UDP and provides reliable connectivity with mobile clients which execute behind Firewalls with NAT, and which may change their IP address and port dynamically.

 
[MCC07/13]
VALENTE, L.; FEIJÓ, B. A survey on pervasive mobile games. 23 p. Eng. E-mail: bruno@inf.puc-rio.br

Abstract: Pervasive games in a recent research field that proposes a new form of entertainment. The literature on pervasive games presents viewpoints from game studies, storytelling, design, social studies, pervasive computing, mobile computing, and ubiquitous computing. Such broad scope makes it difficult to define what a pervasive game is. This work presents a survey on selected projects considered as “pervasive games” in the literature. More specifically, we are interested in a subset we defined as “pervasive mobile games” - context-aware games that necessarily use mobile devices. We believe this collection can work as a starting point for researchers interested in exploring the world of pervasive gaming.

 
[MCC08/13]
 LOPES, G.R.; PAES LEME, L.A.P.; NUNES, B.P.; CASANOVA, M.A.; DIETZE, S. Comparing recommendation approaches for dataset interlinking. 17 p. Eng. E-mail: casanova@inf.puc-rio.br

Abstract: Whenever a dataset t is published on the Web of Data, an exploratory search over existing datasets must be performed to identify those datasets that are potential candidates to be interlinked with t. This technical report introduces and compares two approaches to address the dataset interlinking recommendation problem, respectively based on Bayesian classifiers and on Social Network Analysis techniques. Both approaches define rank score functions that explore the vocabularies, classes and properties that the datasets use, in addition to the known dataset links. After extensive experiments using real-world datasets, the results show that the rank score functions achieve a mean average precision of around 60%. Intuitively, this means that the exploratory search for datasets to be interlinked with t might be limited to just the top-ranked datasets, reducing the cost of the dataset interlinking process.

 
[MCC09/13]
PAMPANELLI, P.C.P.; SILVA, P.M.C.; GATTASS, M. A. New volumetric fault attribute based on first order directional derivatives. 9 p. Eng. E-mail: mgattass@inf.puc-rio.br

Abstract: In this work we present an edge-detection-based method for fault enhancement.The proposed method is simple to implement and has a strong mathematical background.As is well known, faults can be viewed as discontinuities along horizons. Thus, in order to enhance these discontinuities we apply a rst-order directional derivative. Here, we use the vector perpendicular to the instantaneous phase gradient as orientation vector. This orientation vector is calculated analytically. In addition, we describe an approach to combine the attributes in order to capture discontinuities in inline and crossline directions.To assess the proposed method, we use the volume of the Netherlands oshore F3 block downloaded from the Opendtect website and compare the obtained results with variance attribute. We concluded that our method is su-ciently accurate and do not enhance acquisition footprint.

 
[MCC10/13]
LIMA, E.S.; FEIJÓ, B; BARBOSA, S.D.J.; FURTADO, A.L. A keyword-based guide to Poirot stories.  p. Eng. E-mail: furtado@inf.puc-rio.br

Abstract: A system (named KW-GPS) to assist users intent on enjoying Web resources related to a domain-restricted collection of stories is described. Each story is referenced in a virtual library in terms of: (1) the URLs of resources associated with the story, which include but are not limited to plot-summaries, narrative texts and videos; and in terms of (2) keywords of different classes, which serve as a multi-aspect index mechanism. The system was initially applied to Agatha Christie's Poirot detective-stories. Its main feature is a rank-and-show process, that first prompts the end-users to indicate their preferences by choosing from class-organized keyword lists displayed on the screen, after which they are in a position to order the system to activate the desired Web resources. Keywords structured as logical terms, admitting variables as parameters, allow to perform other more laborious processes, involving complex selections and the use of story templates to explore structural similarities. It is shown how story templates, as a representation of narrative motifs, offer a major help towards the composition of new stories. A logic-programming tool was developed to implement the system. A reduced version of the tool runs the basic rank-and-show process in mobile devices, such as tablets and cell-phones. An authoring module is provided to help extending the system to other domains, mainly for entertainment applications.

 
[MCC11/13]
PECIN, D.; POGGI, M.; MARTINELLI, R. Efficient elementary and restricted non-elementary route pricing. 23 p. Eng. E-mail: poggi@inf.puc-rio.br

Abstract: Column generation is present in the current most efficient approaches to routing problems. Set partitioning formulations model routing problems by considering all possible routes and selecting a subset of them that visits all customers. These formulations often produce tight linear relaxation lower bounds and require column generation for their pricing step. The lower bounds in the resulting branch-and-price algorithm are tighter when only elementary routes are considered, but this leads to a harder pricing problem. Balancing the pricing problem with route relaxations has become crucial for the efficiency of the branch-and-price approach for routing problems. Recently, Baldacci,Mingozzi and Roberti proposed the ng-routes as a compromise between elementary and non-elementary routes, known as q-routes. The ng-routes are non-elementary routes with the restriction that following a customer it is not allowed to visit another customer that was visited before only if it belongs to a dynamically computed set. This dynamic set is obtained from ng-sets of given size, associated to each customer, which is usually composed by the closest ones. The larger the size of the ng-sets, the closer the ng-route is to an elementary route. This work presents an efficient pricing algorithm for ng-routes and extends this algorithm to pricing elementary routes. Therefore we address the SPPRC and the ESPPRC problems. The proposed algorithm combines Decremental State-Space Relaxation (DSSR) technique with completion bounds. This allows strengthening the domination rule, drastically reducing the total number of labels. We apply this algorithm for the Generalized Vehicle Routing Problem (GVRP). Experimental results are also presented for the Capacitated Vehicle Routing Problem (CVRP). We report for the first time experiments with ng-set sizes up to sixty-four, obtaining several new best lower bounds for the GVRP, specially for large instances. The proposed algorithm is capable to price elementary routes even for CVRP instances with 200 customers.

 
[MCC12/13]
SOARES, L.F.G.; BATISTA, C.E.F.  FSMDA instantiation to support NCL 3.1 applications in Ginga reference Implementation. 39 p. Eng. E-mail: lfgs@inf.puc-rio.br

Abstract: Applications that are somehow related to the content presented on the main screen have been introduced to collective spaces, such as rooms with Digital TV, theaters with Digital Cinema, conferences with interactive presentations, etc. In this technical report we introduce a framework to support the execution of distributed multi-device applications aiming at these collective spaces. The main contribution is an interoperable software platform that offers high-level abstractions that hide or minimize the complexity of dealing with this distributed and heterogeneous execution environment, unlike existing solutions that have limited functionality or are constrained to device brands. The proposed architecture is presented by means of its instantiation, part of middleware Ginga, and the support offered by the NCL language. However, the framework is not constrained to NCL and Ginga. The instantiated platform has been tested against different scenarios, which are also presented..

 
[MCC13/13]
SILVA, T.; POGGI, M.; PINHEIRO, P.R.  A more human-like portfolio optimization approach. 13 p. Eng. E-mail: poggi@inf.puc-rio.br.

Abstract: In Black-Litterman model the construction of views can be confusing and depends largely on the investor ability in quantifying something extremely subjective. In this article we propose a new way to evaluate these views using Verbal Decision Analysis. Surveys were created with the intent to make it easier for investors to express their vision about stocks. Following ZAPROS methodology the investor answers surveys and using Formal Index of Quality (FIQ) we create views for Black-Litterman. Further, to test our approach in practical situations we implemented a test case for our methodology using the Brazilian stocks.

 
[MCC14/13]
COLCHER, S. Programa integrado para gestão e regulação social de competências profissionais. 10 p. Port. E-mail: colcher@inf.puc-rio.br.

Abstract: Management of professional skills has been recognized as one of the abilities that may leverage competitive advantages on different levels. The aim of this work is to propose an environment in which the information that allows the management of professional skills is permanently accessible to whoever needs, provides or consumes it. This environment creates facilities for an adequate evaluation of intellectual and professional assets, either on an individual or in a collective basis, in corporations, or even to those responsible for the establishment of public policies.

 
[MCC15/13]
VALENTE, L.; FEIJÓ, B.; ENDLER, M.  Location-based games in smartphones: uncertainty handling policy examples. 17 p. Eng. E-mail: bfeijo@inf.puc-rio.br.

Abstract: Location-based applications suffer from many drawbacks related to the underlying infrastructure necessary to support this functionality. This work analyzes location-based games for cellphones, in order to investigate possible approaches to handle technology limitations in this kind of application.

 
[MCC16/13]
VALADARES, C.; COWAN,D.D.; LUCENA, C.J.P.  A Multiagent based context-aware and self-adaptive model for virtual network provisionng. 16 p. Eng. E-mail: lucena@inf.puc-rio.br.

Abstract: Recent research in Network Virtualization has focused on the Internet ossification problem whereby multiple independent virtual networks (VN) that exhibit a high degree of autonomy share physical resources and can provide services with varying degrees of quality. Thus, the Network field has taken evolutionary steps on re-thinking the design and architectural principles of VN. However, to the best of our knowledge, there has been little investigation into the autonomic behavior of such architectures. This paper describes an attempt to use Multiagent System (MAS) principles to design an autonomic and self-adaptive model for virtual network provisioning (VNP) that fills a gap in the current Internet architecture. In addition, we provide an analysis of the requirements of self-adaptive provisioning for designing a reliable autonomic model that is able to self-organize its own resources, with no external control, in order to cope with environment changes. Such behavior will be required as the next generation Internet evolves. Through our evaluation, we demonstrate that the model achieves its main purpose of efficiently self-organizing the VN, since it is able to anticipate critical scenarios and trigger corresponding adaptive plans.

 
[MCC17/13]
BAPTISTA, G.L.B.; RORIZ, M.; VASCONCELOS, R.; OLIVIERI, B.; VASCONCELOS, I.; ENDLER, M. On-line detection of collective mobility patterns through distributed complex event processing. 19 p. Eng. E-mail: endler@inf.puc-rio.br.

Abstract: Applications such as fleet management, mobile task force coordination, logistics or traffic control can largely benefit from the on-line detection of collective mobility patterns of vehicles, goods or persons. However, collective mobility pattern analysis is exponential by nature, requires the high-throughput processing of large volumes of mobile sensor data, and thus generates huge communication and processing load to a monitoring system. Considering the benefits of the event-based asynchronous processing model for on-line monitoring applications, in this paper we argue that several collective mobility patterns can be elegantly described as a composition of reusable Complex Event Processing (CEP) rules, and specifically focus on the detection of the cluster mobility pattern. We also present a DDS-based mobile middleware that supports a distributed deployment of these CEP rules for such collective mobility pattern detection. As means of evaluating our approach we show that using our middleware it is possible to detect this mobility pattern for thousands of mobile nodes, with a latency that is adequate for most monitoring applications.