An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters

Bloom filters are a data structure for storing data in a compressed form. They offer excellent space and time efficiency at the cost of some loss of accuracy (so-called lossy compression). This work presents a yes-no Bloom filter, which as a data structure consisting of two parts: the yes-filter which is a standard Bloom filter and the no-filter which is another Bloom filter whose purpose is to represent those objects that were recognised incorrectly by the yes-filter (that is, to recognise the false positives of the yes-filter). By querying the no-filter after an object has been recognised by the yes-filter, we get a chance of rejecting it, which improves the accuracy of data recognition in comparison with the standard Bloom filter of the same total length. A further increase in accuracy is possible if one chooses objects to include in the no-filter so that the no-filter recognises as many as possible false positives but no true positives, thus producing the most accurate yes-no Bloom filter among all yes-no Bloom filters. This paper studies how optimization techniques can be used to maximize the number of false positives recognised by the no-filter, with the constraint being that it should recognise no true positives. To achieve this aim, an Integer Linear Program (ILP) is proposed for the optimal selection of false positives. In practice the problem size is normally large leading to intractable optimal solution. Considering the similarity of the ILP with the Multidimensional Knapsack Problem, an Approximate Dynamic Programming (ADP) model is developed making use of a reduced ILP for the value function approximation. Numerical results show the ADP model works best comparing with a number of heuristics as well as the CPLEX built-in solver (B&B), and this is what can be recommended for use in yes-no Bloom filters. In a wider context of the study of lossy compression algorithms, our researchis an example showing how the arsenal of optimization methods can be applied to improving the accuracy of compressed data.

Least square projection: A fast high-precision multidimensional projection technique and its application to document mapping

The problem of projecting multidimensional data into lower dimensions has been pursued by many researchers due to its potential application to data analyses of various kinds. This paper presents a novel multidimensional projection technique based on least square approximations. The approximations compute the coordinates of a set of projected points based on the coordinates of a reduced number of control points with defined geometry. We name the technique Least Square Projections ( LSP). From an initial projection of the control points, LSP defines the positioning of their neighboring points through a numerical solution that aims at preserving a similarity relationship between the points given by a metric in mD. In order to perform the projection, a small number of distance calculations are necessary, and no repositioning of the points is required to obtain a final solution with satisfactory precision. The results show the capability of the technique to form groups of points by degree of similarity in 2D. We illustrate that capability through its application to mapping collections of textual documents from varied sources, a strategic yet difficult application. LSP is faster and more accurate than other existing high-quality methods, particularly where it was mostly tested, that is, for mapping text sets.

Turning math attractive to computer science students: an application-to-model approach

This paper describes an innovative approach to develop the understanding about the relevance of mathematics to computer science. The mathematical subjects are introduced through an application-to-model scheme that lead computer science students to a better understanding of why they have to learn math and learn it effectively. Our approach consists of a single one semester course, taught at the first semester of the program, where the students are initially exposed to some typical computer applications. When they recognize the applications' complexity, the instructor gives the mathematical models supporting such applications, even before a formal introduction to the model in a math course. We applied this approach at Unesp (Brazil) and the results include a large reduction in the rate of students that abandon the college and better students in the final years of our program.

A flexible curriculum for computer science undergraduate major

This paper describes an innovative approach to establish a CS curriculum, aiming flexibility and minimization of the time spent in the classrooms. This approach has been developed at the Paulista State University - Unesp - at São José do Rio Preto, and is producing very interesting results. The load reduction is achieved through a series of fundamental core and breadth courses that precede depth courses in specific areas. The flexibility comes as a side effect of the depth courses, which can be adapted without any changes in the core courses. In the following pages we fully describe our motivations, actions and results.

A proposal for a virtual museum of computer science

A proposal for a virtual museum of computer science

Software tools and efficient algorithms for the feature detection, feature tracking, event localization, and visualization of large sets of atmospheric data

Data sets describing the state of the earth's atmosphere are of great importance in the atmospheric sciences. Over the last decades, the quality and sheer amount of the available data increased significantly, resulting in a rising demand for new tools capable of handling and analysing these large, multidimensional sets of atmospheric data. The interdisciplinary work presented in this thesis covers the development and the application of practical software tools and efficient algorithms from the field of computer science, aiming at the goal of enabling atmospheric scientists to analyse and to gain new insights from these large data sets. For this purpose, our tools combine novel techniques with well-established methods from different areas such as scientific visualization and data segmentation. In this thesis, three practical tools are presented. Two of these tools are software systems (Insight and IWAL) for different types of processing and interactive visualization of data, the third tool is an efficient algorithm for data segmentation implemented as part of Insight.Insight is a toolkit for the interactive, three-dimensional visualization and processing of large sets of atmospheric data, originally developed as a testing environment for the novel segmentation algorithm. It provides a dynamic system for combining at runtime data from different sources, a variety of different data processing algorithms, and several visualization techniques. Its modular architecture and flexible scripting support led to additional applications of the software, from which two examples are presented: the usage of Insight as a WMS (web map service) server, and the automatic production of a sequence of images for the visualization of cyclone simulations. The core application of Insight is the provision of the novel segmentation algorithm for the efficient detection and tracking of 3D features in large sets of atmospheric data, as well as for the precise localization of the occurring genesis, lysis, merging and splitting events. Data segmentation usually leads to a significant reduction of the size of the considered data. This enables a practical visualization of the data, statistical analyses of the features and their events, and the manual or automatic detection of interesting situations for subsequent detailed investigation. The concepts of the novel algorithm, its technical realization, and several extensions for avoiding under- and over-segmentation are discussed. As example applications, this thesis covers the setup and the results of the segmentation of upper-tropospheric jet streams and cyclones as full 3D objects. Finally, IWAL is presented, which is a web application for providing an easy interactive access to meteorological data visualizations, primarily aimed at students. As a web application, the needs to retrieve all input data sets and to install and handle complex visualization tools on a local machine are avoided. The main challenge in the provision of customizable visualizations to large numbers of simultaneous users was to find an acceptable trade-off between the available visualization options and the performance of the application. Besides the implementational details, benchmarks and the results of a user survey are presented.

An Experience-Driven Pedagogy for the Instruction of Software Testing in Computer Science

In the realm of computer programming, the experience of writing a program is used to reinforce concepts and evaluate ability. This research uses three case studies to evaluate the introduction of testing through Kolb's Experiential Learning Model (ELM). We then analyze the impact of those testing experiences to determine methods for improving future courses. The first testing experience that students encounter are unit test reports in their early courses. This course demonstrates that automating and improving feedback can provide more ELM iterations. The JUnit Generation (JUG) tool also provided a positive experience for the instructor by reducing the overall workload. Later, undergraduate and graduate students have the opportunity to work together in a multi-role Human-Computer Interaction (HCI) course. The interactions use usability analysis techniques with graduate students as usability experts and undergraduate students as design engineers. Students get experience testing the user experience of their product prototypes using methods varying from heuristic analysis to user testing. From this course, we learned the importance of the instructors role in the ELM. As more roles were added to the HCI course, a desire arose to provide more complete, quality assured software. This inspired the addition of unit testing experiences to the course. However, we learned that significant preparations must be made to apply the ELM when students are resistant. The research presented through these courses was driven by the recognition of a need for testing in a Computer Science curriculum. Our understanding of the ELM suggests the need for student experience when being introduced to testing concepts. We learned that experiential learning, when appropriately implemented, can provide benefits to the Computer Science classroom. When examined together, these course-based research projects provided insight into building strong testing practices into a curriculum.

Relationship among research collaboration, number of documents and number of citations. A case study in Spanish computer science production in 2000-2009.

This paper analyzes the relationship among research collaboration, number of documents and number of citations of computer science research activity. It analyzes the number of documents and citations and how they vary by number of authors. They are also analyzed (according to author set cardinality) under different circumstances, that is, when documents are written in different types of collaboration, when documents are published in different document types, when documents are published in different computer science subdisciplines, and, finally, when documents are published by journals with different impact factor quartiles. To investigate the above relationships, this paper analyzes the publications listed in the Web of Science and produced by active Spanish university professors between 2000 and 2009, working in the computer science field. Analyzing all documents, we show that the highest percentage of documents are published by three authors, whereas single-authored documents account for the lowest percentage. By number of citations, there is no positive association between the author cardinality and citation impact. Statistical tests show that documents written by two authors receive more citations per document and year than documents published by more authors. In contrast, results do not show statistically significant differences between documents published by two authors and one author. The research findings suggest that international collaboration results on average in publications with higher citation rates than national and institutional collaborations. We also find differences regarding citation rates between journals and conferences, across different computer science subdisciplines and journal quartiles as expected. Finally, our impression is that the collaborative level (number of authors per document) will increase in the coming years, and documents published by three or four authors will be the trend in computer science literature.

Teamwork competence and academic motivation in computer science engineering studies.

The present work is focused on studying two issues: the “teamwork” generic competence and the “academic motivation”. Currently the professional profile of engineers has a strong component of teamwork. On the other hand, motivational profile of students determines their tendencies when they come to work in team, as well as their performance at work. In this context we suggest four hypotheses: (H1) students improve their teamwork capacity by specific training and carrying out a set of activities integrated into an active learning process; (H2) students with higher mastery motivation have better attitude towards team working; (H3) students with higher mastery motivation obtain better results in academic performance; and (H4) students show different motivation profiles in different circumstances: type of courses, teaching methodologies, different times of the learning process. This study was carried out with computer science engineering students from two Spanish universities. The first results point to an improvement in teamwork competence of students if they have previously received specific training in facets of that competence. Other results indicate that there is a correlation between the motivational profiles of students and their perception about teamwork competence. Finally, and contrary to the initial hypothesis, these profiles appear to not influence significantly the academic performance of students.

Teamwork, motivational profiles and academic performance in computer science engineering

The present work is aimed at discussing several issues related to the teamwork generic competence, motivational profiles and academic performance. In particular, we study the improvement of teamwork attitude, the predominant types of motivation in different contexts and some correlations among these three components of the learning process. The above-mentioned aspects are of great importance. Currently, the professional profile of engineers has a strong teamwork component and the motivational profile of students determines both their tendencies when they come to work as part of a team, as well as their performance at work. Taking these issues into consideration, we suggest four hypotheses: (H1) students improve their teamwork capacity through specific training and carrying out of a set of activities integrated into an active learning process; (H2) students with higher mastery motivation have a better attitude towards teamwork; (H3) students with different types of motivations reach different levels of academic performance; and (H4) students show different motivation profiles in different circumstances: type of courses, teaching methodologies, different times of the learning process. This study was carried out with Computer Science Engineering students from two Spanish universities. The first results point to an improvement in teamwork competence of students if they have previously received specific training in facets of that competence. Other results indicate that there is a correlation between the motivational profiles of students and their perception of teamwork competence. Finally, results point to a clear relationship between some kind of motivation and academic performance. In particular, four kinds of motivation are analyzed and students are classified into two groups according to them. After analyzing several marks obtained in compulsory courses, we perceive that those students that show higher motivation for avoiding failure obtain, in general, worse academic performance.