OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Gossip-Based Aggregate Computation
Venue: arXiv cs.DS 2010
Year: 2010

We present the first provably almost-optimal gossip-based algorithms for aggregate computation that are both time optimal and message-optimal. Given a $n$-node network, our algorithms guarantee that all the nodes can compute the common aggregates (such as Min, Max, Count, Sum, Average, Rank etc.) of their values in optimal $O(\log n)$ time and using $O(n \log \log n)$ messages. Our result improves on the algorithm of Kempe et al. \cite{kempe} that is time-optimal, but uses $O(n \log n)$ messages as well as on the algorithm of Kashyap et al. \cite{efficient-gossip} that uses $O(n \log \log n)$ messages, but is not time-optimal (takes $O(\log n \log \log n)$ time). Furthermore, we show that our algorithms can be used to improve gossip-based aggregate computation in sparse communication networks, such as in peer-to-peer networks. The main technical ingredient of our algorithm is a technique called {\em distributed random ranking (DRR)} that can be useful in other applications as well. DRR gives an efficient distributed procedure to partition the network into a forest of (disjoint) trees of small size. Our algorithms are non-address oblivious. In contrast, we show a lower bound of $Ω(n\log n)$ on the message complexity of any address-oblivious algorithm for computing aggregates. This shows that non-address oblivious algorithms are needed to obtain significantly better message complexity. Our lower bound holds regardless of the number of rounds taken or the size of the messages used. Our lower bound is the first non-trivial lower bound for gossip-based aggregate computation and also gives the first formal proof that computing aggregates is strictly harder than rumor spreading in the address-oblivious model.
A Real World Mechanism for Testing Satisfiability in Polynomial Time
Venue: arXiv cs.LO 2010
Year: 2010

Whether the satisfiability of any formula F of propositional calculus can be determined in polynomial time is an open question. I propose a simple procedure based on some real world mechanisms to tackle this problem. The main result is the blueprint for a machine which is able to test any formula in conjunctive normal form (CNF) for satisfiability in linear time. The device uses light and some electrochemical properties to function. It adapts itself to the scope of the problem without growing exponentially in mass with the size of the formula. It requires infinite precision in its components instead.
On Utilization and Importance of Perl Status Reporter (SRr) in Text Mining
Venue: arXiv cs.IR 2010
Year: 2010

In Bioinformatics, text mining and text data mining sometimes interchangeably used is a process to derive high-quality information from text. Perl Status Reporter (SRr) is a data fetching tool from a flat text file and in this research paper we illustrate the use of SRr in text or data mining. SRr needs a flat text input file where the mining process to be performed. SRr reads input file and derives the high quality information from it. Typically text mining tasks are text categorization, text clustering, concept and entity extraction, and document summarization. SRr can be utilized for any of these tasks with little or none customizing efforts. In our implementation we perform text categorization mining operation on input file. The input file has two parameters of interest (firstKey and secondKey). The composition of these two parameters describes the uniqueness of entries in that file in the similar manner as done by composite key in database. SRr reads the input file line by line and extracts the parameters of interest and form a composite key by joining them together. It subsequently generates an output file consisting of the name as firstKey secondKey. SRr reads the input file and tracks the composite key. It further stores all that data lines, having the same composite key, in output file generated by SRr based on that composite key.
Minimum Vertex Cover in Rectangle Graphs
Venue: arXiv cs.DS 2010
Year: 2010

We consider the Vertex Cover problem in intersection graphs of axis-parallel rectangles on the plane. We present two algorithms: The first is an EPTAS for non-crossing rectangle families, rectangle families $\calR$ where $R_1 \setminus R_2$ is connected for every pair of rectangles $R_1,R_2 \in \calR$. This algorithm extends to intersection graphs of pseudo-disks. The second algorithm achieves a factor of $(1.5 + \varepsilon)$ in general rectangle families, for any fixed $\varepsilon > 0$, and works also for the weighted variant of the problem. Both algorithms exploit the plane properties of axis-parallel rectangles in a non-trivial way.
Tuning Message Size in Opportunistic Mobile Networks
Venue: arXiv cs.NI 2010
Year: 2010

We describe a new model for studying intermittently connected mobile networks, based on Markovian random temporal graphs, that captures the influence of message size, maximum tolerated delay and link stability on the delivery ratio.
Execution and Result Integration Scheme in FPU Farms for Co-ordinated Performance
Venue: arXiv cs.IT 2010
Year: 2010

- The main goal of this research is to develop the concept of an innovative processor system called Functional Processor System. The particular work carried out in this paper focuses on the execution of functions in the heterogeneous functional processor units(FPU) and integration of functions to bring net results. As the functional programs are super-level programs, the requirements of execution are only at functional level. The Execution and integration of results of functions in FPUs are a challenge. The methodology of executing the functions in the functional processor farm and the integration of results of functions according to the assigned addresses are investigated here. The concept of feeding the functions into the processor is promoted rather than the processor fetching the instructions/functions and executing in this paradigm. This work is carried out at conceptual levels and it takes a long way to go into the realization of this model in hardware, possibly only with a large industry team and with a realistic time frame.
Formalizing cCSP Synchronous Semantics in PVS
Venue: arXiv cs.LO 2010
Year: 2010

Compensating CSP (cCSP) is a language defined to model long running business transactions within the framework of standard CSP process algebra. In earlier work, we have defined both traces and operational semantics of the language. We have shown the consistency between the two semantic models by defining a relationship between them. Synchronization was missing from the earlier semantic definitions which is an important feature for any process algebra. In this paper, we address this issue by extending the syntax and semantics to support synchronization and define a relationship between the semantic models. Moreover, we improve the scalability of our proof technique by mechanically verifying the semantic relationship using theorem prover PVS. We show how to embed process algebra terms and semantics into PVS and to use these embeddings to prove the semantic relationship.
Software Metrics Evaluation Based on Entropy
Venue: arXiv cs.SE 2010
Year: 2010

Software engineering activities in the Industry has come a long way with various improve- ments brought in various stages of the software development life cycle. The complexity of modern software, the commercial constraints and the expectation for high quality products demand the accurate fault prediction based on OO design metrics in the class level in the early stages of software development. The object oriented class metrics are used as quality predictors in the entire OO software development life cycle even when a highly iterative, incremental model or agile software process is employed. Recent research has shown some of the OO design metrics are useful for predicting fault-proneness of classes. In this paper the empirical validation of a set of metrics proposed by Chidamber and Kemerer is performed to assess their ability in predicting the software quality in terms of fault proneness and degradation. We have also proposed the design complexity of object-oriented software with Weighted Methods per Class metric (WMC-CK metric) expressed in terms of Shannon entropy, and error proneness.
Information criminality - a phenomenon met within the informatics field
Venue: arXiv cs.CY 2010
Year: 2010

The phenomenon described as "information criminality" has taken significant proportions in the last decade, fact that carried out towards an international legislative frame, by implementing judicial forms, which might stop its occurrences. As matter of fact, the information criminality represents an information technology aiming towards fraud and prejudicing the users of informational data, by various means to infringement of the law. In this way, some international organizations have dealt with performing a legislative framework, able to punish the phenomenon of information criminality and implicitly to protect the users of computers. The transnational expansions, extremely fast as concerns the computer networks, and extending the access to these networks, by means of mobile telephony, have brought the increasing of these systems' vulnerability and the creating of opportunities of breaking the law. Considering these aspects, the world legislation is continuously changing, due to a more and more accelerated development of the information technology.
Randomness Testing of Compressed Data
Venue: arXiv cs.CC 2010
Year: 2010

Random Number Generators play a critical role in a number of important applications. In practice, statistical testing is employed to gather evidence that a generator indeed produces numbers that appear to be random. In this paper, we reports on the studies that were conducted on the compressed data using 8 compression algorithms or compressors. The test results suggest that the output of compression algorithms or compressors has bad randomness, the compression algorithms or compressors are not suitable as random number generator. We also found that, for the same compression algorithm, there exists positive correlation relationship between compression ratio and randomness, increasing the compression ratio increases randomness of compressed data. As time permits, additional randomness testing efforts will be conducted.
A Symbolic Dynamical System Approach to Lossy Source Coding with Feedforward
Venue: arXiv cs.IT 2010
Year: 2010

It is known that modeling an information source via a symbolic dynamical system evolving over the unit interval, leads to a natural lossless compression scheme attaining the entropy rate of the source, under general conditions. We extend this notion to the lossy compression regime assuming a feedforward link is available, by modeling a source via a two-dimensional symbolic dynamical system where one component corresponds to the compressed signal, and the other essentially corresponds to the feedforward signal. For memoryless sources and an arbitrary bounded distortion measure, we show this approach leads to a family of simple deterministic compression schemes that attain the rate-distortion function of the source. The construction is dual to a recent optimal scheme for channel coding with feedback.
Applying MVC and PAC patterns in mobile applications
Venue: arXiv cs.SE 2010
Year: 2010

Additional requirements are set for mobile applications in relation to applications for desktop computers. These requirements primarily concern the support to different platforms on which such applications are performed, as well as the requirement for providing more modalities of input/output interaction. These requirements have influence on the user interface and therefore it is needed to consider the usability of MVC (Model-View-Controller) and PAC (Presentation-Abstraction-Control) design patterns for the separation of the user interface tasks from the business logic, specifically in mobile applications. One of the questions is making certain choices of design patterns for certain classes of mobile applications. When using these patterns the possibilities of user interface automatic transformation should be kept in mind. Although the MVC design pattern is widely used in mobile applications, it is not universal, especially in cases where there are requirements for heterogeneous multi-modal input-output interactions.
Particle Swarm Optimization Based Reactive Power Optimization
Venue: arXiv cs.NE 2010
Year: 2010

Reactive power plays an important role in supporting the real power transfer by maintaining voltage stability and system reliability. It is a critical element for a transmission operator to ensure the reliability of an electric system while minimizing the cost associated with it. The traditional objectives of reactive power dispatch are focused on the technical side of reactive support such as minimization of transmission losses. Reactive power cost compensation to a generator is based on the incurred cost of its reactive power contribution less the cost of its obligation to support the active power delivery. In this paper an efficient Particle Swarm Optimization (PSO) based reactive power optimization approach is presented. The optimal reactive power dispatch problem is a nonlinear optimization problem with several constraints. The objective of the proposed PSO is to minimize the total support cost from generators and reactive compensators. It is achieved by maintaining the whole system power loss as minimum thereby reducing cost allocation. The purpose of reactive power dispatch is to determine the proper amount and location of reactive support. Reactive Optimal Power Flow (ROPF) formulation is developed as an analysis tool and the validity of proposed method is examined using an IEEE-14 bus system.
Proposing a New Method for Query Processing Adaption in DataBase
Venue: arXiv cs.DB 2010
Year: 2010

This paper proposes a multi agent system by compiling two technologies, query processing optimization and agents which contains features of personalized queries and adaption with changing of requirements. This system uses a new algorithm based on modeling of users' long-term requirements and also GA to gather users' query data. Experimented Result shows more adaption capability for presented algorithm in comparison with classic algorithms.
Expert System Models in the Companies' Financial and Accounting Domain
Venue: arXiv cs.CE 2010
Year: 2010

The present paper is based on studying, analyzing and implementing the expert systems in the financial and accounting domain of the companies, describing the use method of the informational systems that can be used in the multi-national companies, public interest institutions, and medium and small dimension economical entities, in order to optimize the managerial decisions and render efficient the financial-accounting functionality. The purpose of this paper is aimed to identifying the economical exigencies of the entities, based on the already used accounting instruments and the management software that could consent the control of the economical processes and patrimonial assets.
Hybrid Medical Image Classification Using Association Rule Mining with Decision Tree Algorithm
Venue: arXiv cs.CV 2010
Year: 2010

The main focus of image mining in the proposed method is concerned with the classification of brain tumor in the CT scan brain images. The major steps involved in the system are: pre-processing, feature extraction, association rule mining and hybrid classifier. The pre-processing step has been done using the median filtering process and edge features have been extracted using canny edge detection technique. The two image mining approaches with a hybrid manner have been proposed in this paper. The frequent patterns from the CT scan images are generated by frequent pattern tree (FP-Tree) algorithm that mines the association rules. The decision tree method has been used to classify the medical images for diagnosis. This system enhances the classification process to be more accurate. The hybrid method improves the efficiency of the proposed method than the traditional image mining methods. The experimental result on prediagnosed database of brain images showed 97% sensitivity and 95% accuracy respectively. The physicians can make use of this accurate decision tree classification phase for classifying the brain images into normal, benign and malignant for effective medical diagnosis.
Transformation of Networks through Cognitive Approaches
Venue: arXiv cs.NI 2010
Year: 2010

The growth in data traffic and the increased demand for quality of service had generated a large demand for network systems to be more efficient. The introduction of improved routing systems to meet the increasing demand and varied protocols to accommodate various scales of challenges in network efficiency had further complicated the operations. This means that a better mode of intelligence has to be infused into networking for smoother operations and better autonomic features. Cognitive networks are defined and analyzed in this angle. They are identified to have the potential to deal with the future user related quality and efficiency of service at optimized levels. The cognitive elements of a system like perception, learning, planning, reasoning and decision forming can enable the systems to be more aware of their environment and offer better services. These approaches are expected to transform the mode of operation of future networks.
Deconvolution of linear systems with quantized input: an information theoretic viewpoint
Venue: arXiv cs.IT 2010
Year: 2010

In spite of the huge literature on deconvolution problems, very little is done for hybrid contexts where signals are quantized. In this paper we undertake an information theoretic approach to the deconvolution problem of a simple integrator with quantized binary input and sampled noisy output. We recast it into a decoding problem and we propose and analyze (theoretically and numerically) some low complexity on-line algorithms to achieve deconvolution.
Effective Defect Prevention Approach in Software Process for Achieving Better Quality Levels
Venue: arXiv cs.SE 2010
Year: 2010

Defect prevention is the most vital but habitually neglected facet of software quality assurance in any project. If functional at all stages of software development, it can condense the time, overheads and wherewithal entailed to engineer a high quality product. The key challenge of an IT industry is to engineer a software product with minimum post deployment defects. This effort is an analysis based on data obtained for five selected projects from leading software companies of varying software production competence. The main aim of this paper is to provide information on various methods and practices supporting defect detection and prevention leading to thriving software generation. The defect prevention technique unearths 99% of defects. Inspection is found to be an essential technique in generating ideal software generation in factories through enhanced methodologies of abetted and unaided inspection schedules. On an average 13 % to 15% of inspection and 25% - 30% of testing out of whole project effort time is required for 99% - 99.75% of defect elimination. A comparison of the end results for the five selected projects between the companies is also brought about throwing light on the possibility of a particular company to position itself with an appropriate complementary ratio of inspection testing.
Doped Fountain Coding for Minimum Delay Data Collection in Circular Networks
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies decentralized, Fountain and network-coding based strategies for facilitating data collection in circular wireless sensor networks, which rely on the stochastic diversity of data storage. The goal is to allow for a reduced delay collection by a data collector who accesses the network at a random position and random time. Data dissemination is performed by a set of relays which form a circular route to exchange source packets. The storage nodes within the transmission range of the route's relays linearly combine and store overheard relay transmissions using random decentralized strategies. An intelligent data collector first collects a minimum set of coded packets from a subset of storage nodes in its proximity, which might be sufficient for recovering the original packets and, by using a message-passing decoder, attempts recovering all original source packets from this set. Whenever the decoder stalls, the source packet which restarts decoding is polled/doped from its original source node. The random-walk-based analysis of the decoding/doping process furnishes the collection delay analysis with a prediction on the number of required doped packets. The number of doped packets can be surprisingly small when employed with an Ideal Soliton code degree distribution and, hence, the doping strategy may have the least collection delay when the density of source nodes is sufficiently large. Furthermore, we demonstrate that network coding makes dissemination more efficient at the expense of a larger collection delay. Not surprisingly, a circular network allows for a significantly more (analytically and otherwise) tractable strategies relative to a network whose model is a random geometric graph.
Mapping General System Characteristics to Non- Functional Requirements
Venue: arXiv cs.SE 2010
Year: 2010

The Function point analysis (FPA) method is the preferred scheme of estimation for project managers to determine the size, effort, schedule, resource loading and other such parameters. The FPA method by International Function Point Users Group (IFPUG) has captured the critical implementation features of an application through fourteen general system characteristics. However, Non- functional requirements (NFRs) such as functionality, reliability, efficiency, usability, maintainability, portability, etc. have not been included in the FPA estimation method. This paper discusses some of the NFRs and tries to determine a degree of influence for each of them. An attempt to factor the NFRs into estimation has been made. This approach needs to be validated with data collection and analysis.
Fixed-Parameter Algorithms for Computing Kemeny Scores - Theory and Practice
Venue: arXiv cs.DS 2010
Year: 2010

The central problem in this work is to compute a ranking of a set of elements which is "closest to" a given set of input rankings of the elements. We define "closest to" in an established way as having the minimum sum of Kendall-Tau distances to each input ranking. Unfortunately, the resulting problem Kemeny consensus is NP-hard for instances with n input rankings, n being an even integer greater than three. Nevertheless this problem plays a central role in many rank aggregation problems. It was shown that one can compute the corresponding Kemeny consensus list in f(k) + poly(n) time, being f(k) a computable function in one of the parameters "score of the consensus", "maximum distance between two input rankings", "number of candidates" and "average pairwise Kendall-Tau distance" and poly(n) a polynomial in the input size. This work will demonstrate the practical usefulness of the corresponding algorithms by applying them to randomly generated and several real-world data. Thus, we show that these fixed-parameter algorithms are not only of theoretical interest. In a more theoretical part of this work we will develop an improved fixed-parameter algorithm for the parameter "score of the consensus" having a better upper bound for the running time than previous algorithms.
Defect Prevention Approaches In Medium Scale It Enterprises
Venue: arXiv cs.SE 2010
Year: 2010

The software industry is successful, if it can draw the complete attention of the customers towards it. This is achievable if the organization can produce a high quality product. To identify a product to be of high quality, it should be free of defects, should be capable of producing expected results. It should be delivered in an estimated cost, time and be maintainable with minimum effort.