OpenRaiser/Intern-Atlas huggingface dataset:
Verification and Validation Issues in Systems of Systems
Venue: arXiv cs.SE 2013
Year: 2013

The cutting edge in systems development today is in the area of "systems of systems" (SoS) large networks of inter-related systems that are developed and managed separately, but that also perform collective activities. Such large systems typically involve constituent systems operating with different life cycles, often with uncoordinated evolution. The result is an ever-changing SoS in which adaptation and evolution replace the older engineering paradigm of "development". This short paper presents key thoughts about verification and validation in this environment. Classic verification and validation methods rely on having (a) a basis of proof, in requirements and in operational scenarios, and (b) a known system configuration to be proven. However, with constant SoS evolution, management of both requirements and system configurations are problematic. Often, it is impossible to maintain a valid set of requirements for the SoS due to the ongoing changes in the constituent systems. Frequently, it is even difficult to maintain a vision of the SoS operational use as users find new ways to adapt the SoS. These features of the SoS result in significant challenges for system proof. In addition to discussing the issues, the paper also indicates some of the solutions that are currently used to prove the SoS.
Impact of system state dynamics on PMU placement in the electric power grid
Venue: arXiv cs.SY 2013
Year: 2013

The goal of this paper is to study the impact of the dynamic nature of bus voltage magnitudes and phase angles, which constitute the state of the power system, on the phasor measurement unit (PMU) placement problem. To facilitate this study, the placement problem is addressed from the perspective of the electrical structure which, unlike existing work on PMU placement, accounts for the sensitivity between power injections and nodal phase angle differences between various buses in the power network. A linear dynamic model captures the time evolution of system states, and a simple procedure is devised to estimate the state transition function at each time instant. The placement problem is formulated as a series (time steps) of binary integer programs, with the goal to obtain the minimum number of PMUs at each time step for complete network observability in the absence of zero injection measurements. Experiments are conducted on several standard IEEE test bus systems. The main thesis of this study is that, owing to the dynamic nature of the system states, for optimal power system operation the best one could do is to install a PMU on each bus of the given network, though it is undesirable from an economic standpoint.
Dynamic Resource Allocation for Multiple-Antenna Wireless Power Transfer
Venue: arXiv cs.IT 2013
Year: 2013

We consider a point-to-point multiple-input-single-output (MISO) system where a receiver harvests energy from a wireless power transmitter to power itself for various applications. The transmitter performs energy beamforming by using an instantaneous channel state information (CSI). The CSI is estimated at the receiver by training via a preamble, and fed back to the transmitter. The channel estimate is more accurate when longer preamble is used, but less time is left for wireless power transfer before the channel changes. To maximize the harvested energy, in this paper, we address the key challenge of balancing the time resource used for channel estimation and wireless power transfer (WPT), and also investigate the allocation of energy resource used for wireless power transfer. First, we consider the general scenario where the preamble length is allowed to vary dynamically. Taking into account the effects of imperfect CSI, the optimal preamble length is obtained online by solving a dynamic programming (DP) problem. The solution is shown to be a threshold-type policy that depends only on the channel estimate power. Next, we consider the scenario in which the preamble length is fixed. The optimal preamble length is optimized offline. Furthermore, we derive the optimal power allocation schemes for both scenarios. For the scenario of dynamic-length preamble, the power is allocated according to both the optimal preamble length and the channel estimate power; while for the scenario of fixed-length preamble, the power is allocated according to only the channel estimate power. The analysis results are validated by numerical simulations. Encouragingly, with optimal power allocation, the harvested energy by using optimized fixed-length preamble is almost the same as the harvested energy by employing dynamic-length preamble, hence allowing a low-complexity WPT system to be implemented in practice.
Application of Rough Set Theory in Data Mining
Venue: arXiv cs.DB 2013
Year: 2013

Rough set theory is a new method that deals with vagueness and uncertainty emphasized in decision making. Data mining is a discipline that has an important contribution to data analysis, discovery of new meaningful knowledge, and autonomous decision making. The rough set theory offers a viable approach for decision rule extraction from data.This paper, introduces the fundamental concepts of rough set theory and other aspects of data mining, a discussion of data representation with rough set theory including pairs of attribute-value blocks, information tables reducts, indiscernibility relation and decision tables. Additionally, the rough set approach to lower and upper approximations and certain possible rule sets concepts are introduced. Finally, some description about applications of the data mining system with rough set theory is included.
Towards Big Topic Modeling
Venue: arXiv cs.LG 2013
Year: 2013

To solve the big topic modeling problem, we need to reduce both time and space complexities of batch latent Dirichlet allocation (LDA) algorithms. Although parallel LDA algorithms on the multi-processor architecture have low time and space complexities, their communication costs among processors often scale linearly with the vocabulary size and the number of topics, leading to a serious scalability problem. To reduce the communication complexity among processors for a better scalability, we propose a novel communication-efficient parallel topic modeling architecture based on power law, which consumes orders of magnitude less communication time when the number of topics is large. We combine the proposed communication-efficient parallel architecture with the online belief propagation (OBP) algorithm referred to as POBP for big topic modeling tasks. Extensive empirical results confirm that POBP has the following advantages to solve the big topic modeling problem: 1) high accuracy, 2) communication-efficient, 3) fast speed, and 4) constant memory usage when compared with recent state-of-the-art parallel LDA algorithms on the multi-processor architecture.
Scalable Oriented-Service Architecture for Heterogeneous and Ubiquitous IoT Domains
Venue: arXiv cs.NI 2013
Year: 2013

Internet of Things (IoT) grows quickly, and 50 billion of IoT devices will be interconnected by 2020. For the huge number of IoT devices, a high scalable discovery architecture is required to provide autonomous registration and look-up of IoT resources and services. The architecture should enable dynamic updates when new IoT devices are incorporated into Internet, and changes are made to the existing ones. Nowadays in Internet, the most used discovery architecture is the Domain Name System (DNS). DNS offers a scalable solution through two distributed mechanisms: multicast DNS (mDNS) and DNS Service Directory (DNS-SD). Both mechanisms have been applied to discover resources and services in local IoT domains. However, a full architecture has not still been designed to support global discovery, local directories and a search engine for ubiquitous IoT domains. Moreover, the architecture should provide other transversal functionalities such as a common semantic for describing services and resources, and a service layer for interconnecting with M2M platforms and mobile clients. This paper presents an oriented-service architecture based on DNS to support a global discovery, local directories and a distributed search engine to enable a scalable looking-up of IoT resources and services. The architecture provides two lightweight discovery mechanisms based on mDNS and DNS-SD that have been optimized for the constraints of IoT devices to allow autonomous registration. Moreover, we analyse and provide other relevant elements such semantic description and communications interfaces to support the heterogeneity of IoT devices and clients. All these elements contribute to build a scalable architecture for the discovery and access of heterogeneous and ubiquitous IoT domains.
Distributed bounded-error state estimation for partitioned systems based on practical robust positive invariance
Venue: arXiv cs.SY 2013
Year: 2013

We propose a partition-based state estimator for linear discrete-time systems composed by coupled subsystems affected by bounded disturbances. The architecture is distributed in the sense that each subsystem is equipped with a local state estimator that exploits suitable pieces of information from parent subsystems. Moreover, differently from methods based on moving horizon estimation, our approach does not require the on-line solution to optimization problems. Our state-estimation scheme, that is based on the notion of practical robust positive invariance developed in Rakovic 2011, also guarantees satisfaction of constraints on local estimation errors and it can be updated with a limited computational effort when subsystems are added or removed.
Parameterized Model Checking of Token-Passing Systems
Venue: arXiv cs.LO 2013
Year: 2013

We revisit the parameterized model checking problem for token-passing systems and specifications in indexed $\textsf{CTL}^\ast \backslash \textsf{X}$. Emerson and Namjoshi (1995, 2003) have shown that parameterized model checking of indexed $\textsf{CTL}^\ast \backslash \textsf{X}$ in uni-directional token rings can be reduced to checking rings up to some \emph{cutoff} size. Clarke et al. (2004) have shown a similar result for general topologies and indexed $\textsf{LTL} \backslash \textsf{X}$, provided processes cannot choose the directions for sending or receiving the token. We unify and substantially extend these results by systematically exploring fragments of indexed $\textsf{CTL}^\ast \backslash \textsf{X}$ with respect to general topologies. For each fragment we establish whether a cutoff exists, and for some concrete topologies, such as rings, cliques and stars, we infer small cutoffs. Finally, we show that the problem becomes undecidable, and thus no cutoffs exist, if processes are allowed to choose the directions in which they send or from which they receive the token.
Efficient algorithms for the longest common subsequence in $k$-length substrings
Venue: arXiv cs.DS 2013
Year: 2013

Finding the longest common subsequence in $k$-length substrings (LCS$k$) is a recently proposed problem motivated by computational biology. This is a generalization of the well-known LCS problem in which matching symbols from two sequences $A$ and $B$ are replaced with matching non-overlapping substrings of length $k$ from $A$ and $B$. We propose several algorithms for LCS$k$, being non-trivial incarnations of the major concepts known from LCS research (dynamic programming, sparse dynamic programming, tabulation). Our algorithms make use of a linear-time and linear-space preprocessing finding the occurrences of all the substrings of length $k$ from one sequence in the other sequence.
Planning by case-based reasoning based on fuzzy logic
Venue: arXiv cs.AI 2013
Year: 2013

The treatment of complex systems often requires the manipulation of vague, imprecise and uncertain information. Indeed, the human being is competent in handling of such systems in a natural way. Instead of thinking in mathematical terms, humans describes the behavior of the system by language proposals. In order to represent this type of information, Zadeh proposed to model the mechanism of human thought by approximate reasoning based on linguistic variables. He introduced the theory of fuzzy sets in 1965, which provides an interface between language and digital worlds. In this paper, we propose a Boolean modeling of the fuzzy reasoning that we baptized Fuzzy-BML and uses the characteristics of induction graph classification. Fuzzy-BML is the process by which the retrieval phase of a CBR is modelled not in the conventional form of mathematical equations, but in the form of a database with membership functions of fuzzy rules.
Numerical modeling of friction stir welding process: a literature review
Venue: arXiv cs.CE 2013
Year: 2013

This survey presents a literature review on friction stir welding (FSW) modeling with a special focus on the heat generation due to the contact conditions between the FSW tool and the workpiece. The physical process is described and the main process parameters that are relevant to its modeling are highlighted. The contact conditions (sliding/sticking) are presented as well as an analytical model that allows estimating the associated heat generation. The modeling of the FSW process requires the knowledge of the heat loss mechanisms, which are discussed mainly considering the more commonly adopted formulations. Different approaches that have been used to investigate the material flow are presented and their advantages/drawbacks are discussed. A reliable FSW process modeling depends on the fine tuning of some process and material parameters. Usually, these parameters are achieved with base on experimental data. The numerical modeling of the FSW process can help to achieve such parameters with less effort and with economic advantages.
Scientific Workflows and Provenance: Introduction and Research Opportunities
Venue: arXiv cs.DB 2013
Year: 2013

Scientific workflows are becoming increasingly popular for compute-intensive and data-intensive scientific applications. The vision and promise of scientific workflows includes rapid, easy workflow design, reuse, scalable execution, and other advantages, e.g., to facilitate "reproducible science" through provenance (e.g., data lineage) support. However, as described in the paper, important research challenges remain. While the database community has studied (business) workflow technologies extensively in the past, most current work in scientific workflows seems to be done outside of the database community, e.g., by practitioners and researchers in the computational sciences and eScience. We provide a brief introduction to scientific workflows and provenance, and identify areas and problems that suggest new opportunities for database research.
How to improve the prediction based on citation impact percentiles for years shortly after the publication date?
Venue: arXiv cs.DL 2013
Year: 2013

The findings of Bornmann, Leydesdorff, and Wang (in press) revealed that the consideration of journal impact improves the prediction of long-term citation impact. This paper further explores the possibility of improving citation impact measurements on the base of a short citation window by the consideration of journal impact and other variables, such as the number of authors, the number of cited references, and the number of pages. The dataset contains 475,391 journal papers published in 1980 and indexed in Web of Science (WoS, Thomson Reuters), and all annual citation counts (from 1980 to 2010) for these papers. As an indicator of citation impact, we used percentiles of citations calculated using the approach of Hazen (1914). Our results show that citation impact measurement can really be improved: If factors generally influencing citation impact are considered in the statistical analysis, the explained variance in the long-term citation impact can be much increased. However, this increase is only visible when using the years shortly after publication but not when using later years.
The Complexity of Flow Analysis in Higher-Order Languages
Venue: arXiv cs.PL 2013
Year: 2013

This dissertation proves lower bounds on the inherent difficulty of deciding flow analysis problems in higher-order programming languages. We give exact characterizations of the computational complexity of 0CFA, the $k$CFA hierarchy, and related analyses. In each case, we precisely capture both the expressiveness and feasibility of the analysis, identifying the elements responsible for the trade-off. 0CFA is complete for polynomial time. This result relies on the insight that when a program is linear (each bound variable occurs exactly once), the analysis makes no approximation; abstract and concrete interpretation coincide, and therefore pro- gram analysis becomes evaluation under another guise. Moreover, this is true not only for 0CFA, but for a number of further approximations to 0CFA. In each case, we derive polynomial time completeness results. For any $k > 0$, $k$CFA is complete for exponential time. Even when $k = 1$, the distinction in binding contexts results in a limited form of closures, which do not occur in 0CFA. This theorem validates empirical observations that $k$CFA is intractably slow for any $k > 0$. There is, in the worst case---and plausibly, in practice---no way to tame the cost of the analysis. Exponential time is required. The empirically observed intractability of this analysis can be understood as being inherent in the approximation problem being solved, rather than reflecting unfortunate gaps in our programming abilities.
Uplink Performance of Large Optimum-Combining Antenna Arrays in Poisson-Cell Networks
Venue: arXiv cs.IT 2013
Year: 2013

The uplink of a wireless network with base stations distributed according to a Poisson Point Process (PPP) is analyzed. The base stations are assumed to have a large number of antennas and use linear minimum-mean-square-error (MMSE) spatial processing for multiple access. The number of active mobiles per cell is limited to permit channel estimation using pilot sequences that are orthogonal in each cell. The cumulative distribution function (CDF) of a randomly located link in a typical cell of such a system is derived when accurate channel estimation is available. A simple bound is provided for the spectral efficiency when channel estimates suffer from pilot contamination. The results provide insight into the performance of so-called massive Multiple-Input-Multiple-Output (MIMO) systems in spatially distributed cellular networks.
Computing Covers of Plane Forests
Venue: arXiv cs.CG 2013
Year: 2013

Let $ϕ$ be a function that maps any non-empty subset $A$ of $\mathbb{R}^2$ to a non-empty subset $ϕ(A)$ of $\mathbb{R}^2$. A $ϕ$-cover of a set $T=\{T_1, T_2, \dots, T_m\}$ of pairwise non-crossing trees in the plane is a set of pairwise disjoint connected regions such that each tree $T_i$ is contained in some region of the cover, and each region of the cover is either (1) $ϕ(T_i)$ for some $i$, or (2) $ϕ(A \cup B)$, where $A$ and $B$ are constructed by either (1) or (2), and $A \cap B \neq \emptyset$. We present two properties for the function $ϕ$ that make the $ϕ$-cover well-defined. Examples for such functions $ϕ$ are the convex hull and the axis-aligned bounding box. For both of these functions $ϕ$, we show that the $ϕ$-cover can be computed in $O(n\log^2n)$ time, where $n$ is the total number of vertices of the trees in $T$.
Analyzing Evolutionary Optimization in Noisy Environments
Venue: arXiv cs.AI 2013
Year: 2013

Many optimization tasks have to be handled in noisy environments, where we cannot obtain the exact evaluation of a solution but only a noisy one. For noisy optimization tasks, evolutionary algorithms (EAs), a kind of stochastic metaheuristic search algorithm, have been widely and successfully applied. Previous work mainly focuses on empirical studying and designing EAs for noisy optimization, while, the theoretical counterpart has been little investigated. In this paper, we investigate a largely ignored question, i.e., whether an optimization problem will always become harder for EAs in a noisy environment. We prove that the answer is negative, with respect to the measurement of the expected running time. The result implies that, for optimization tasks that have already been quite hard to solve, the noise may not have a negative effect, and the easier a task the more negatively affected by the noise. On a representative problem where the noise has a strong negative effect, we examine two commonly employed mechanisms in EAs dealing with noise, the re-evaluation and the threshold selection strategies. The analysis discloses that the two strategies, however, both are not effective, i.e., they do not make the EA more noise tolerant. We then find that a small modification of the threshold selection allows it to be proven as an effective strategy for dealing with the noise in the problem.
Data Mining Model for the Data Retrieval from Central Server Configuration
Venue: arXiv cs.IR 2013
Year: 2013

A server, which is to keep track of heavy document traffic, is unable to filter the documents that are most relevant and updated for continuous text search queries. This paper focuses on handling continuous text extraction sustaining high document traffic. The main objective is to retrieve recent updated documents that are most relevant to the query by applying sliding window technique. Our solution indexes the streamed documents in the main memory with structure based on the principles of inverted file, and processes document arrival and expiration events with incremental threshold-based method. It also ensures elimination of duplicate document retrieval using unsupervised duplicate detection. The documents are ranked based on user feedback and given higher priority for retrieval.
Algorithmic regularity for polynomials and applications
Venue: arXiv cs.CC 2013
Year: 2013

In analogy with the regularity lemma of Szemerédi, regularity lemmas for polynomials shown by Green and Tao (Contrib. Discrete Math. 2009) and by Kaufman and Lovett (FOCS 2008) modify a given collection of polynomials \calF = {P_1,...,P_m} to a new collection \calF' so that the polynomials in \calF' are "pseudorandom". These lemmas have various applications, such as (special cases) of Reed-Muller testing and worst-case to average-case reductions for polynomials. However, the transformation from \calF to \calF' is not algorithmic for either regularity lemma. We define new notions of regularity for polynomials, which are analogous to the above, but which allow for an efficient algorithm to compute the pseudorandom collection \calF'. In particular, when the field is of high characteristic, in polynomial time, we can refine \calF into \calF' where every nonzero linear combination of polynomials in \calF' has desirably small Gowers norm. Using the algorithmic regularity lemmas, we show that if a polynomial P of degree d is within (normalized) Hamming distance 1-1/|F| -\eps of some unknown polynomial of degree k over a prime field F (for k < d < |F|), then there is an efficient algorithm for finding a degree-k polynomial Q, which is within distance 1-1/|F| -ηof P, for some ηdepending on \eps. This can be thought of as decoding the Reed-Muller code of order k beyond the list decoding radius (finding one close codeword), when the received word P itself is a polynomial of degree d (with k < d < |F|). We also obtain an algorithmic version of the worst-case to average-case reductions by Kaufman and Lovett. They show that if a polynomial of degree d can be weakly approximated by a polynomial of lower degree, then it can be computed exactly using a collection of polynomials of degree at most d-1. We give an efficient (randomized) algorithm to find this collection.