OpenRaiser/Intern-Atlas huggingface dataset:
Scalable Continual Top-k Keyword Search in Relational Databases
Venue: arXiv cs.DB 2011
Year: 2011

Keyword search in relational databases has been widely studied in recent years because it does not require users neither to master a certain structured query language nor to know the complex underlying database schemas. Most of existing methods focus on answering snapshot keyword queries in static databases. In practice, however, databases are updated frequently, and users may have long-term interests on specific topics. To deal with such a situation, it is necessary to build effective and efficient facility in a database system to support continual keyword queries. In this paper, we propose an efficient method for answering continual top-$k$ keyword queries over relational databases. The proposed method is built on an existing scheme of keyword search on relational data streams, but incorporates the ranking mechanisms into the query processing methods and makes two improvements to support efficient top-$k$ keyword search in relational databases. Compared to the existing methods, our method is more efficient both in computing the top-$k$ results in a static database and in maintaining the top-$k$ results when the database continually being updated. Experimental results validate the effectiveness and efficiency of the proposed method.
Improving the performance of the ripper in insurance risk classification : A comparitive study using feature selection
Venue: arXiv cs.LG 2011
Year: 2011

The Ripper algorithm is designed to generate rule sets for large datasets with many features. However, it was shown that the algorithm struggles with classification performance in the presence of missing data. The algorithm struggles to classify instances when the quality of the data deteriorates as a result of increasing missing data. In this paper, a feature selection technique is used to help improve the classification performance of the Ripper model. Principal component analysis and evidence automatic relevance determination techniques are used to improve the performance. A comparison is done to see which technique helps the algorithm improve the most. Training datasets with completely observable data were used to construct the model and testing datasets with missing values were used for measuring accuracy. The results showed that principal component analysis is a better feature selection for the Ripper in improving the classification performance.
Simplicity Effects in the Experience of Near-Miss
Venue: arXiv cs.OH 2011
Year: 2011

Near-miss experiences are one of the main sources of intense emotions. Despite people's consistency when judging near-miss situations and when communicating about them, there is no integrated theoretical account of the phenomenon. In particular, individuals' reaction to near-miss situations is not correctly predicted by rationality-based or probability-based optimization. The present study suggests that emotional intensity in the case of near-miss is in part predicted by Simplicity Theory.
Emotion in good luck and bad luck: predictions from simplicity theory
Venue: arXiv cs.OH 2011
Year: 2011

The feeling of good or bad luck occurs whenever there is an emotion contrast between an event and an easily accessible counterfactual alternative. This study suggests that cognitive simplicity plays a key role in the human ability to experience good and bad luck after the occurrence of an event.
Verbal Characterization of Probabilistic Clusters using Minimal Discriminative Propositions
Venue: arXiv cs.AI 2011
Year: 2011

In a knowledge discovery process, interpretation and evaluation of the mined results are indispensable in practice. In the case of data clustering, however, it is often difficult to see in what aspect each cluster has been formed. This paper proposes a method for automatic and objective characterization or "verbalization" of the clusters obtained by mixture models, in which we collect conjunctions of propositions (attribute-value pairs) that help us interpret or evaluate the clusters. The proposed method provides us with a new, in-depth and consistent tool for cluster interpretation/evaluation, and works for various types of datasets including continuous attributes and missing values. Experimental results with a couple of standard datasets exhibit the utility of the proposed method, and the importance of the feedbacks from the interpretation/evaluation step.
A Non-Standard Semantics for Kahn Networks in Continuous Time
Venue: arXiv cs.PL 2011
Year: 2011

In a seminal article, Kahn has introduced the notion of process network and given a semantics for those using Scott domains whose elements are (possibly infinite) sequences of values. This model has since then become a standard tool for studying distributed asynchronous computations. From the beginning, process networks have been drawn as particular graphs, but this syntax is never formalized. We take the opportunity to clarify it by giving a precise definition of these graphs, that we call nets. The resulting category is shown to be a fixpoint category, i.e. a cartesian category which is traced wrt the monoidal structure given by the product, and interestingly this structure characterizes the category: we show that it is the free fixpoint category containing a given set of morphisms, thus providing a complete axiomatics that models of process networks should satisfy. We then use these tools to build a model of networks in which data vary over a continuous time, in order to elaborate on the idea that process networks should also be able to encompass computational models such as hybrid systems or electric circuits. We relate this model to Kahn's semantics by introducing a third model of networks based on non-standard analysis, whose elements form an internal complete partial order for which many properties of standard domains can be reformulated. The use of hyperreals in this model allows it to formally consider the notion of infinitesimal, and thus to make a bridge between discrete and continuous time: time is "discrete", but the duration between two instants is infinitesimal. Finally, we give some examples of uses of the model by describing some networks implementing common constructions in analysis.
Linear Time Inference of Strings from Cover Arrays using a Binary Alphabet
Venue: arXiv cs.DS 2011
Year: 2011

Covers being one of the most popular form of regularities in strings, have drawn much attention over time. In this paper, we focus on the problem of linear time inference of strings from cover arrays using the least sized alphabet possible. We present an algorithm that can reconstruct a string $x$ over a two-letter alphabet whenever a valid cover array $C$ is given as an input. This algorithm uses several interesting combinatorial properties of cover arrays and an interesting relation between border array and cover array to achieve this. Our algorithm runs in linear time.
Probabilistic Performance Analysis of Networks using an Improved Network Service Envelope Approach
Venue: arXiv cs.NI 2011
Year: 2011

Stochastic network calculus is an evolving theory which accounts for statistical multiplexing and uses an envelope approach for probabilistic delay and backlog analysis of networks. One of the key ideas of stochastic network calculus is the possibility to describe service offered at network node as a stochastic service envelope, which in turn can be used to describe the stochastic service available in a network of nodes and determine end-to-end probabilistic delay and backlog bounds. This paper introduces a new definition of stochastic service envelopes which yield a simple network service envelope and tighter end-to-end performance bounds. It is shown for ($σ(θ), ρ(θ)$) - constrained traffic model that the end-to-end performance measures computed using the new stochastic network service envelope are tight in comparison to the ones obtained using the existing start-of-the-art definition of statistical network service envelope and are bounded by ${\cal O}(H \log{H})$, where $H$ is the number of nodes traversed by the arrival traffic.
A Uniform Fixpoint Approach to the Implementation of Inference Methods for Deductive Databases
Venue: arXiv cs.DB 2011
Year: 2011

Within the research area of deductive databases three different database tasks have been deeply investigated: query evaluation, update propagation and view updating. Over the last thirty years various inference mechanisms have been proposed for realizing these main functionalities of a rule-based system. However, these inference mechanisms have been rarely used in commercial DB systems until now. One important reason for this is the lack of a uniform approach well-suited for implementation in an SQL-based system. In this paper, we present such a uniform approach in form of a new version of the soft consequence operator. Additionally, we present improved transformation-based approaches to query optimization and update propagation and view updating which are all using this operator as underlying evaluation mechanism.
Deciding first order logic properties of matroids
Venue: arXiv cs.DS 2011
Year: 2011

Frick and Grohe [J. ACM 48 (2006), 1184-1206] introduced a notion of graph classes with locally bounded tree-width and established that every first order logic property can be decided in almost linear time in such a graph class. Here, we introduce an analogous notion for matroids (locally bounded branch-width) and show the existence of a fixed parameter algorithm for first order logic properties in classes of regular matroids with locally bounded branch-width. To obtain this result, we show that the problem of deciding the existence of a circuit of length at most k containing two given elements is fixed parameter tractable for regular matroids.
The Dimension of Subcode-Subfields of Shortened Generalized Reed Solomon Codes
Venue: arXiv cs.IT 2011
Year: 2011

Reed-Solomon (RS) codes are among the most ubiquitous codes due to their good parameters as well as efficient encoding and decoding procedures. However, RS codes suffer from having a fixed length. In many applications where the length is static, the appropriate length can be obtained by an RS code by shortening or puncturing. Generalized Reed-Solomon (GRS) codes are a generalization of RS codes, whose subfield-subcodes are extensively studied. In this paper we show that a particular class of GRS codes produces many subfield-subcodes with large dimension. An algorithm for searching through the codes is presented as well as a list of new codes obtained from this method.
Strategic Learning and Robust Protocol Design for Online Communities with Selfish Users
Venue: arXiv cs.LG 2011
Year: 2011

This paper focuses on analyzing the free-riding behavior of self-interested users in online communities. Hence, traditional optimization methods for communities composed of compliant users such as network utility maximization cannot be applied here. In our prior work, we show how social reciprocation protocols can be designed in online communities which have populations consisting of a continuum of users and are stationary under stochastic permutations. Under these assumptions, we are able to prove that users voluntarily comply with the pre-determined social norms and cooperate with other users in the community by providing their services. In this paper, we generalize the study by analyzing the interactions of self-interested users in online communities with finite populations and are not stationary. To optimize their long-term performance based on their knowledge, users adapt their strategies to play their best response by solving individual stochastic control problems. The best-response dynamic introduces a stochastic dynamic process in the community, in which the strategies of users evolve over time. We then investigate the long-term evolution of a community, and prove that the community will converge to stochastically stable equilibria which are stable against stochastic permutations. Understanding the evolution of a community provides protocol designers with guidelines for designing social norms in which no user has incentives to adapt its strategy and deviate from the prescribed protocol, thereby ensuring that the adopted protocol will enable the community to achieve the optimal social welfare.
FdConfig: A Constraint-Based Interactive Product Configurator
Venue: arXiv cs.AI 2011
Year: 2011

We present a constraint-based approach to interactive product configuration. Our configurator tool FdConfig is based on feature models for the representation of the product domain. Such models can be directly mapped into constraint satisfaction problems and dealt with by appropriate constraint solvers. During the interactive configuration process the user generates new constraints as a result of his configuration decisions and even may retract constraints posted earlier. We discuss the configuration process, explain the underlying techniques and show optimizations.
A prototype of a knowledge-based programming environment
Venue: arXiv cs.AI 2011
Year: 2011

In this paper we present a proposal for a knowledge-based programming environment. In such an environment, declarative background knowledge, procedures, and concrete data are represented in suitable languages and combined in a flexible manner. This leads to a highly declarative programming style. We illustrate our approach on an example and report about our prototype implementation.
Generalized Fast Approximate Energy Minimization via Graph Cuts: Alpha-Expansion Beta-Shrink Moves
Venue: arXiv cs.CV 2011
Year: 2011

We present alpha-expansion beta-shrink moves, a simple generalization of the widely-used alpha-beta swap and alpha-expansion algorithms for approximate energy minimization. We show that in a certain sense, these moves dominate both alpha-beta-swap and alpha-expansion moves, but unlike previous generalizations the new moves require no additional assumptions and are still solvable in polynomial-time. We show promising experimental results with the new moves, which we believe could be used in any context where alpha-expansions are currently employed.
On the enumerating series of an abstract numeration system
Venue: arXiv cs.DM 2011
Year: 2011

It is known that any rational abstract numeration system is faithfully, and effectively, represented by an N-rational series. A simple proof of this result is given which yields a representation of this series which in turn allows a simple computation of the value of words in this system and easy constructions for the recognition of recognisable sets of numbers. It is also shown that conversely it is decidable whether an N-rational series corresponds to a rational abstract numeration system.
Balancing Degree, Diameter and Weight in Euclidean Spanners
Venue: arXiv cs.CG 2011
Year: 2011

In this paper we devise a novel \emph{unified} construction of Euclidean spanners that trades between the maximum degree, diameter and weight gracefully. For a positive integer k, our construction provides a (1+eps)-spanner with maximum degree O(k), diameter O(log_k n + alpha(k)), weight O(k \cdot log_k n \cdot log n) \cdot w(MST(S)), and O(n) edges. Note that for k= n^{1/alpha(n)} this gives rise to diameter O(alpha(n)), weight O(n^{1/alpha(n)} \cdot log n \cdot alpha(n)) \cdot w(MST(S)) and maximum degree O(n^{1/alpha(n)}), which improves upon a classical result of Arya et al. \cite{ADMSS95}; in the corresponding result from \cite{ADMSS95} the spanner has the same number of edges and diameter, but its weight and degree may be arbitrarily large. Also, for k = O(1) this gives rise to maximum degree O(1), diameter O(log n) and weight O(log^2 n) \cdot w(MST(S)), which reproves another classical result of Arya et al. \cite{ADMSS95}. Our bound of O(log_k n + alpha(k)) on the diameter is optimal under the constraints that the maximum degree is O(k) and the number of edges is O(n). Our bound on the weight is optimal up to a factor of log n. Our construction also provides a similar tradeoff in the complementary range of parameters, i.e., when the weight should be smaller than log^2 n, but the diameter is allowed to grow beyond log n. For random point sets in the d-dimensional unit cube, we "shave" a factor of log n from the weight bound. Specifically, in this case our construction achieves maximum degree O(k), diameter O(log_k n + alpha(k)) and weight that is with high probability O(k \cdot log_k n) \cdot w(MST(S)). Finally, en route to these results we devise optimal constructions of 1-spanners for general tree metrics, which are of independent interest.
Weighted Reed-Muller codes revisited
Venue: arXiv cs.IT 2011
Year: 2011

We consider weighted Reed-Muller codes over point ensemble $S_1 \times...\times S_m$ where $S_i$ needs not be of the same size as $S_j$. For $m = 2$ we determine optimal weights and analyze in detail what is the impact of the ratio $|S_1|/|S_2|$ on the minimum distance. In conclusion the weighted Reed-Muller code construction is much better than its reputation. For a class of affine variety codes that contains the weighted Reed-Muller codes we then present two list decoding algorithms. With a small modification one of these algorithms is able to correct up to 31 errors of the [49, 11, 28] Joyner code.
Decision Support for e-Governance: A Text Mining Approach
Venue: arXiv cs.DB 2011
Year: 2011

Information and communication technology has the capability to improve the process by which governments involve citizens in formulating public policy and public projects. Even though much of government regulations may now be in digital form (and often available online), due to their complexity and diversity, identifying the ones relevant to a particular context is a non-trivial task. Similarly, with the advent of a number of electronic online forums, social networking sites and blogs, the opportunity of gathering citizens' petitions and stakeholders' views on government policy and proposals has increased greatly, but the volume and the complexity of analyzing unstructured data makes this difficult. On the other hand, text mining has come a long way from simple keyword search, and matured into a discipline capable of dealing with much more complex tasks. In this paper we discuss how text-mining techniques can help in retrieval of information and relationships from textual data sources, thereby assisting policy makers in discovering associations between policies and citizens' opinions expressed in electronic public forums and blogs etc. We also present here, an integrated text mining based architecture for e-governance decision support along with a discussion on the Indian scenario.
Efficient data compression from statistical physics of codes over finite fields
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we discuss a novel data compression technique for binary symmetric sources based on the cavity method over a Galois Field of order q (GF(q)). We present a scheme of low complexity and near optimal empirical performance. The compression step is based on a reduction of sparse low density parity check codes over GF(q) and is done through the so called reinforced belief-propagation equations. These reduced codes appear to have a non-trivial geometrical modification of the space of codewords which makes such compression computationally feasible. The computational complexity is O(d.n.q.log(q)) per iteration, where d is the average degree of the check nodes and n is the number of bits. For our code ensemble, decompression can be done in a time linear in the code's length by a simple leaf-removal algorithm.
Dynamic MDS Matrices for Substantial Cryptographic Strength
Venue: arXiv cs.CR 2011
Year: 2011

Ciphers get their strength from the mathematical functions of confusion and diffusion, also known as substitution and permutation. These were the basics of classical cryptography and they are still the basic part of modern ciphers. In block ciphers diffusion is achieved by the use of Maximum Distance Separable (MDS) matrices. In this paper we present some methods for constructing dynamic (and random) MDS matrices.
Semantic Integration in the IFF
Venue: arXiv cs.DL 2011
Year: 2011

The IEEE P1600.1 Standard Upper Ontology (SUO) project aims to specify an upper ontology that will provide a structure and a set of general concepts upon which domain ontologies could be constructed. The Information Flow Framework (IFF), which is being developed under the auspices of the SUO Working Group, represents the structural aspect of the SUO. The IFF is based on category theory. Semantic integration of object-level ontologies in the IFF is represented with its fusion construction. The IFF maintains ontologies using powerful composition primitives, which includes the fusion construction.
Provide a Model for Handover Technology in Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

Fast Handovers for the MIPv6 (FMIPv6) has been proposed to reduce the Handover latency, in the IETF. It could not find the acceptable reduction, so led to more efforts to improve it and however the creation of multiple Handover methods in the literature. A stable connection is very important in mobile services so the mobility of device would not cause any interruption in network services and thus mobility management plays a very important role. Mobile IPv6 has become a general solution for supporting mobility between different networks on the internet which a flawless connection needs to be managed properly. In order to select the appropriate method, in this paper, all the proposed methods have been classified according to the identified performance metrics. Call blocking probability, Handover blocking probability, Probability of an unnecessary handover, Duration of interruption and delay, as the most important Handover algorithm performance metrics are introduced. The AHP method will be deployed to weight the metrics in a sample topology according to the selected sound application. Then the TOPSIS method will be employed to find the appropriate Handover algorithm.
Self-Adaptation Mechanism to Control the Diversity of the Population in Genetic Algorithm
Venue: arXiv cs.NE 2011
Year: 2011

One of the problems in applying Genetic Algorithm is that there is some situation where the evolutionary process converges too fast to a solution which causes it to be trapped in local optima. To overcome this problem, a proper diversity in the candidate solutions must be determined. Most existing diversity-maintenance mechanisms require a problem specific knowledge to setup parameters properly. This work proposes a method to control diversity of the population without explicit parameter setting. A self-adaptation mechanism is proposed based on the competition of preference characteristic in mating. It can adapt the population toward proper diversity for the problems. The experiments are carried out to measure the effectiveness of the proposed method based on nine well-known test problems. The performance of the adaptive method is comparable to traditional Genetic Algorithm with the best parameter setting.
(Re)configuration based on model generation
Venue: arXiv cs.AI 2011
Year: 2011

Reconfiguration is an important activity for companies selling configurable products or services which have a long life time. However, identification of a set of required changes in a legacy configuration is a hard problem, since even small changes in the requirements might imply significant modifications. In this paper we show a solution based on answer set programming, which is a logic-based knowledge representation formalism well suited for a compact description of (re)configuration problems. Its applicability is demonstrated on simple abstractions of several real-world scenarios. The evaluation of our solution on a set of benchmark instances derived from commercial (re)configuration problems shows its practical applicability.