OpenRaiser/Intern-Atlas huggingface dataset:
On Implementation and Evaluation of Inverse Iteration Algorithm with compact WY Orthogonalization
Venue: arXiv cs.NA 2012
Year: 2012

A new inverse iteration algorithm that can be used to compute all the eigenvectors of a real symmetric tri-diagonal matrix on parallel computers is developed. The modified Gram-Schmidt orthogonalization is used in the classical inverse iteration. This algorithm is sequential and causes a bottleneck in parallel computing. In this paper, the use of the compact WY representation is proposed in the orthogonalization process of the inverse iteration with the Householder transformation. This change results in drastically reduced synchronization cost in parallel computing. The new algorithm is evaluated on both an 8-core and a 32-core parallel computer, and it is shown that the new algorithm is greatly faster than the classical inverse iteration algorithm in computing all the eigenvectors of matrices with several thousand dimensions.
On the satisfiability problem for a 4-level quantified syllogistic and some applications to modal logic (extended version)
Venue: arXiv cs.LO 2012
Year: 2012

We introduce a multi-sorted stratified syllogistic, called 4LQSR, admitting variables of four sorts and a restricted form of quantification over variables of the first three sorts, and prove that it has a solvable satisfiability problem by showing that it enjoys a small model property. Then, we consider the fragments (4LQSR)^h of 4LQSR, consisting of 4LQSR-formulae whose quantifier prefixes have length bounded by h > 1 and satisfying certain syntactic constraints, and prove that each of them has an NP-complete satisfiability problem. Finally we show that the modal logic K45 can be expressed in 4LQSR^3.
Toward a New Protocol to Evaluate Recommender Systems
Venue: arXiv cs.IR 2012
Year: 2012

In this paper, we propose an approach to analyze the performance and the added value of automatic recommender systems in an industrial context. We show that recommender systems are multifaceted and can be organized around 4 structuring functions: help users to decide, help users to compare, help users to discover, help users to explore. A global off line protocol is then proposed to evaluate recommender systems. This protocol is based on the definition of appropriate evaluation measures for each aforementioned function. The evaluation protocol is discussed from the perspective of the usefulness and trust of the recommendation. A new measure called Average Measure of Impact is introduced. This measure evaluates the impact of the personalized recommendation. We experiment with two classical methods, K-Nearest Neighbors (KNN) and Matrix Factorization (MF), using the well known dataset: Netflix. A segmentation of both users and items is proposed to finely analyze where the algorithms perform well or badly. We show that the performance is strongly dependent on the segments and that there is no clear correlation between the RMSE and the quality of the recommendation.
Cognitive Radio Networks: Realistic or Not?
Venue: arXiv cs.NI 2012
Year: 2012

A large volume of research has been conducted in the cognitive radio (CR) area the last decade. However, the deployment of a commercial CR network is yet to emerge. A large portion of the existing literature does not build on real world scenarios, hence, neglecting various important interactions of the research with commercial telecommunication networks. For instance, a lot of attention has been paid to spectrum sensing as the front line functionality that needs to be completed in an efficient and accurate manner to enable an opportunistic CR network architecture. This is necessary to detect the existence of spectrum holes without which no other procedure can be fulfilled. However, simply sensing (cooperatively or not) the energy received from a primary transmitter cannot enable correct dynamic spectrum access. For example, the low strength of a primary transmitter's signal does not assure that there will be no interference to a nearby primary receiver. In addition, the presence of a primary transmitter's signal does not mean that CR network users cannot access the spectrum since there might not be any primary receiver in the vicinity. Despite the existing elegant and clever solutions to the DSA problem no robust, implementable scheme has emerged. In this paper, we challenge the basic premises of the proposed schemes. We further argue that addressing the technical challenges we face in deploying robust CR networks can only be achieved if we radically change the way we design their basic functionalities. In support of our argument, we present a set of real-world scenarios, inspired by realistic settings in commercial telecommunications networks, focusing on spectrum sensing as a basic and critical functionality in the deployment of CRs. We use these scenarios to show why existing DSA paradigms are not amenable to realistic deployment in complex wireless environments.
CS Circles: An In-Browser Python Course for Beginners
Venue: arXiv cs.CY 2012
Year: 2012

Computer Science Circles is a free programming website for beginners that is designed to be fun, easy to use, and accessible to the broadest possible audience. We teach Python since it is simple yet powerful, and the course content is well-structured but written in plain language. The website has over one hundred exercises in thirty lesson pages, plus special features to help teachers support their students. It is available in both English and French. We discuss the philosophy behind the course and its design, we describe how it was implemented, and we give statistics on its use.
Statistical Analysis to Extract Effective Parameters on Overall Energy Consumption of Wireless Sensor Network (WSN)
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we use statistical tools to analysis dependency between Wireless Sensor Network (WSN) parameters and overall Energy Consumption (EC). Our approach has two main phases: profiling, and effective parameter extraction. In former, a sensor network simulator is re-run 800 times with different values for eight WSN parameters to profile consumed energy in nodes; then in latter, three statistical analyses (p-value, linear and non-linear correlation) are applied to the outcome of profiling phase to extract the most effective parameters on WSN overall energy consumption.
Online Estimation of Battery Lifetime for Wireless Sensors Network
Venue: arXiv cs.NI 2012
Year: 2012

Battery is a major hardware component of wireless sensor networks. Most of them have no power supply and are generally deployed for a long time. Researches have been done on battery physical model and their adaptation for sensors. We present an implementation on a real sensor operating system and how architectural constraints have been assumed. Experiments have been made in order to test the impact of some parameter, as the application throughput, on the battery lifetime.
Conformance Verification of Normative Specifications using C-O Diagrams
Venue: arXiv cs.FL 2012
Year: 2012

C-O Diagrams have been introduced as a means to have a visual representation of normative texts and electronic contracts, where it is possible to represent the obligations, permissions and prohibitions of the different signatories, as well as what are the penalties in case of not fulfillment of their obligations and prohibitions. In such diagrams we are also able to represent absolute and relative timing constrains. In this paper we consider a formal semantics for C-O Diagrams based on a network of timed automata and we present several relations to check the consistency of a contract in terms of realizability, to analyze whether an implementation satisfies the requirements defined on its contract, and to compare several implementations using the executed permissions as criteria.
Efficient Indicators to Evaluate the Status of Software Development Effort Estimation inside the Organizations
Venue: arXiv cs.SE 2012
Year: 2012

Development effort is an undeniable part of the project management which considerably influences the success of project. Inaccurate and unreliable estimation of effort can easily lead to the failure of project. Due to the special specifications, accurate estimation of effort in the software projects is a vital management activity that must be carefully done to avoid from the unforeseen results. However numerous effort estimation methods have been proposed in this field, the accuracy of estimates is not satisfying and the attempts continue to improve the performance of estimation methods. Prior researches conducted in this area have focused on numerical and quantitative approaches and there are a few research works that investigate the root problems and issues behind the inaccurate effort estimation of software development effort. In this paper, a framework is proposed to evaluate and investigate the situation of an organization in terms of effort estimation. The proposed framework includes various indicators which cover the critical issues in field of software development effort estimation. Since the capabilities and shortages of organizations for effort estimation are not the same, the proposed indicators can lead to have a systematic approach in which the strengths and weaknesses of organizations in field of effort estimation are discovered.
Effect of interaction strength on the evolution of cooperation
Venue: arXiv cs.GT 2012
Year: 2012

Cooperative behaviors are ubiquitous in nature,which is a puzzle to evolutionary biology,because the defector always gains more benefit than the cooperator,thus,the cooperator should decrease and vanish over time.This typical "prisoners' dilemma" phenomenon has been widely researched in recent years.The interaction strength between cooperators and defectors is introduced in this paper(in human society,it can be understood as the tolerance of cooperators).We find that only when the maximum interaction strength is between two critical values,the cooperator and defector can coexist,otherwise, 1) if it is greater than the upper value,the cooperator will vanish, 2) if it is less than the lower value,a bistable state will appear.
Shadow Theory, data model design for data integration
Venue: arXiv cs.DB 2012
Year: 2012

For data integration in information ecosystems, semantic heterogeneity is a known difficulty. In this paper, we propose Shadow Theory as the philosophical foundation to address this issue. It is based on the notion of shadows in Plato's Allegory of the Cave. What we can observe are just shadows, and meanings of shadows are mental entities that only exist in viewers' cognitive structures. With enterprise customer data integration example, we proposed six design principles and algebra to support required operations.
Investigating Streaming Techniques and Energy Efficiency of Mobile Video Services
Venue: arXiv cs.MM 2012
Year: 2012

We report results from a measurement study of three video streaming services, YouTube, Dailymotion and Vimeo on six different smartphones. We measure and analyze the traffic and energy consumption when streaming different quality videos over Wi-Fi and 3G. We identify five different techniques to deliver the video and show that the use of a particular technique depends on the device, player, quality, and service. The energy consumption varies dramatically between devices, services, and video qualities depending on the streaming technique used. As a consequence, we come up with suggestions on how to improve the energy efficiency of mobile video streaming services.
Surveying the Social, Smart and Converged TV Landscape: Where is Television Research Headed?
Venue: arXiv cs.MM 2012
Year: 2012

The TV is dead motto of just a few years ago has been replaced by the prospect of Internet Protocol (IP) television experiences over converged networks to become one of the great technology opportunities in the next few years. As an introduction to the Special Issue on Smart, Social and Converged Television, this extended editorial intends to review the current IP television landscape in its many realizations: operator-based, over-the-top, and user generated. We will address new services like social TV and recommendation engines, dissemination including new paradigms built on peer to peer and content centric networks, as well as the all important quality of experience that challenges services and networks alike. But we intend to go further than just review the existing work by proposing areas for the future of television research. These include strategies to provide services that are more efficient in network and energy usage while being socially engaging, novel services that will provide consumers with a broader choice of content and devices, and metrics that will enable operators and users alike to define the level of service they require or that they are ready to provide. These topics are addressed in this survey paper that attempts to create a unifying framework to link them all together. Not only is television not dead, it is well alive, thriving and fostering innovation and this paper will hopefully prove it.
Technical Report: CSVM Ecosystem
Venue: arXiv cs.CE 2012
Year: 2012

The CSVM format is derived from CSV format and allows the storage of tabular like data with a limited but extensible amount of metadata. This approach could help computer scientists because all information needed to uses subsequently the data is included in the CSVM file and is particularly well suited for handling RAW data in a lot of scientific fields and to be used as a canonical format. The use of CSVM has shown that it greatly facilitates: the data management independently of using databases; the data exchange; the integration of RAW data in dataflows or calculation pipes; the search for best practices in RAW data management. The efficiency of this format is closely related to its plasticity: a generic frame is given for all kind of data and the CSVM parsers don't make any interpretation of data types. This task is done by the application layer, so it is possible to use same format and same parser codes for a lot of purposes. In this document some implementation of CSVM format for ten years and in different laboratories are presented. Some programming examples are also shown: a Python toolkit for using the format, manipulating and querying is available. A first specification of this format (CSVM-1) is now defined, as well as some derivatives such as CSVM dictionaries used for data interchange. CSVM is an Open Format and could be used as a support for Open Data and long term conservation of RAW or unpublished data.
Database Semantics
Venue: arXiv cs.DB 2012
Year: 2012

This paper, the first step to connect relational databases with systems consequence (Kent: "System Consequence" 2009), is concerned with the semantics of relational databases. It aims to to study system consequence in the logical/semantic system of relational databases. The paper, which was inspired by and which extends a recent set of papers on the theory of relational database systems (Spivak: "Functorial Data Migration" 2012), is linked with work on the Information Flow Framework (IFF) [http://suo.ieee.org/IFF/] connected with the ontology standards effort (SUO), since relational databases naturally embed into first order logic. The database semantics discussed here is concerned with the conceptual level of database architecture. We offer both an intuitive and technical discussion. Corresponding to the notions of primary and foreign keys, relational database semantics takes two forms: a distinguished form where entities are distinguished from relations, and a unified form where relations and entities coincide. The distinguished form corresponds to the theory presented in (Spivak: "Simplicial databases" 2009)[arXiv:0904.2012]. The unified form, a special case of the distinguished form, corresponds to the theory presented in (Spivak: "Functorial Data Migration" 2012). A later paper will discuss various formalisms of relational databases, such as relational algebra and first order logic, and will complete the description of the relational database logical environment.
Pattern Detection with Rare Item-set Mining
Venue: arXiv cs.SE 2012
Year: 2012

The discovery of new and interesting patterns in large datasets, known as data mining, draws more and more interest as the quantities of available data are exploding. Data mining techniques may be applied to different domains and fields such as computer science, health sector, insurances, homeland security, banking and finance, etc. In this paper we are interested by the discovery of a specific category of patterns, known as rare and non-present patterns. We present a novel approach towards the discovery of non-present patterns using rare item-set mining.
Graphs: Associated Markov Chains
Venue: arXiv cs.DS 2012
Year: 2012

In this research paper, weighted / unweighted, directed / undirected graphs are associated with interesting Discrete Time Markov Chains (DTMCs) as well as Continuous Time Markov Chains (CTMCs). The equilibrium / transient behaviour of such Markov chains is studied. Also entropy dynamics (Shannon entropy) of certain structured Markov chains is investigated. Finally certain structured graphs and the associated Markov chains are studied.
Mechanisms for Fair Allocation Problems: No-Punishment Payment Rules in Fully Verifiable Settings
Venue: arXiv cs.GT 2012
Year: 2012

Mechanism design is addressed in the context of fair allocations of indivisible goods with monetary compensation. Motivated by a real-world social choice problem, mechanisms with verification are considered in a setting where (i) agents' declarations on allocated goods can be fully verified before payments are performed, and where (ii) verification is not used to punish agents whose declarations resulted in incorrect ones. Within this setting, a mechanism is designed that is shown to be truthful, efficient, and budget-balanced, and where agents' utilities are fairly determined by the Shapley value of suitable coalitional games. The proposed mechanism is however shown to be #P-complete. Thus, to deal with applications with many agents involved, two polynomial-time randomized variants are also proposed: one that is still truthful and efficient, and which is approximately budget-balanced with high probability, and another one that is truthful in expectation, while still budget-balanced and efficient.
Measuring Spreadsheet Formula Understandability
Venue: arXiv cs.SE 2012
Year: 2012

Spreadsheets are widely used in industry, because they are flexible and easy to use. Sometimes they are even used for business-critical applications. It is however difficult for spreadsheet users to correctly assess the quality of spreadsheets, especially with respect to their understandability. Understandability of spreadsheets is important, since spreadsheets often have a long lifespan, during which they are used by several users. In this paper, we establish a set of spreadsheet understandability metrics. We start by studying related work and interviewing 40 spreadsheet professionals to obtain a set of characteristics that might contribute to understandability problems in spreadsheets. Based on those characteristics we subsequently determine a number of understandability metrics. To evaluate the usefulness of our metrics, we conducted a series of experiments in which professional spreadsheet users performed a number of small maintenance tasks on a set of spreadsheets from the EUSES spreadsheet corpus. We subsequently calculate the correlation between the metrics and the performance of subjects on these tasks. The results clearly indicate that the number of ranges, the nesting depth and the presence of conditional operations in formulas significantly increase the difficulty of understanding a spreadsheet.
Nash Equilibria for Stochastic Games with Asymmetric Information-Part 1: Finite Games
Venue: arXiv cs.GT 2012
Year: 2012

A model of stochastic games where multiple controllers jointly control the evolution of the state of a dynamic system but have access to different information about the state and action processes is considered. The asymmetry of information among the controllers makes it difficult to compute or characterize Nash equilibria. Using common information among the controllers, the game with asymmetric information is shown to be equivalent to another game with symmetric information. Further, under certain conditions, a Markov state is identified for the equivalent symmetric information game and its Markov perfect equilibria are characterized. This characterization provides a backward induction algorithm to find Nash equilibria of the original game with asymmetric information in pure or behavioral strategies. Each step of this algorithm involves finding Bayesian Nash equilibria of a one-stage Bayesian game. The class of Nash equilibria of the original game that can be characterized in this backward manner are named common information based Markov perfect equilibria.
Information Retrieval From Internet Applications For Digital Forensic
Venue: arXiv cs.CR 2012
Year: 2012

Advanced internet technologies providing services like e-mail, social networking, online banking, online shopping etc., have made day-to-day activities simple and convenient. Increasing dependency on the internet, convenience, and decreasing cost of electronic devices have resulted in frequent use of online services. However, increased indulgence over the internet has also accelerated the pace of digital crimes. The increase in number and complexity of digital crimes has caught the attention of forensic investigators. The Digital Investigators are faced with the challenge of gathering accurate digital evidence from as many sources as possible. In this paper, an attempt was made to recover digital evidence from a system's RAM in the form of information about the most recent browsing session of the user. Four different applications were chosen and the experiment was conducted across two browsers. It was found that crucial information about the target user such as, user name, passwords, etc., was recoverable.
Linear Precoding Designs for Amplify-and-Forward Multiuser Two-Way Relay Systems
Venue: arXiv cs.IT 2012
Year: 2012

Two-way relaying can improve spectral efficiency in two-user cooperative communications. It also has great potential in multiuser systems. A major problem of designing a multiuser two-way relay system (MU-TWRS) is transceiver or precoding design to suppress co-channel interference. This paper aims to study linear precoding designs for a cellular MU-TWRS where a multi-antenna base station (BS) conducts bi-directional communications with multiple mobile stations (MSs) via a multi-antenna relay station (RS) with amplify-and-forward relay strategy. The design goal is to optimize uplink performance, including total mean-square error (Total-MSE) and sum rate, while maintaining individual signal-to-interference-plus-noise ratio (SINR) requirement for downlink signals. We show that the BS precoding design with the RS precoder fixed can be converted to a standard second order cone programming (SOCP) and the optimal solution is obtained efficiently. The RS precoding design with the BS precoder fixed, on the other hand, is non-convex and we present an iterative algorithm to find a local optimal solution. Then, the joint BS-RS precoding is obtained by solving the BS precoding and the RS precoding alternately. Comprehensive simulation is conducted to demonstrate the effectiveness of the proposed precoding designs.