OpenRaiser/Intern-Atlas huggingface dataset:
A Real-time Group Auction System for Efficient Allocation of Cloud Internet Applications
Venue: arXiv cs.GT 2013
Year: 2013

Increasing number of the cloud-based Internet applications demands for efficient resource and cost management. This paper proposes a real-time group auction system for the cloud instance market. The system is designed based on a combinatorial double auction, and its applicability and effectiveness are evaluated in terms of resource efficiency and monetary benefits to auction participants (e.g., cloud users and providers). The proposed auction system assists them to decide when and how providers allocate their resources to which users. Furthermore, we propose a distributed algorithm using a group formation game that determines which users and providers will trade resources by their cooperative decisions. To find how to allocate the resources, the utility optimization problem is formulated as a binary integer programming problem, and the nearly optimal solution is obtained by a heuristic algorithm with quadratic time complexity. In comparison studies, the proposed real-time group auction system with cooperation outperforms an individual auction in terms of the resource efficiency (e.g., the request acceptance rate for users and resource utilization for providers) and monetary benefits (e.g., average payments for users and total profits for providers).
A Goal Question Metric Approach for Evaluating Security in a Service Oriented Architecture Context
Venue: arXiv cs.SE 2013
Year: 2013

For interactions to be possible within the Service Oriented Architecture (SOA) ecosystem, each actor must be enough confident of other actors to engage safely in the interactions. Therefore, the establishing of objective metrics tailored to the context of SOA that show security of a system and lead to enhancements is very attractive. The purpose of our paper is to present a GQM (Goal Question Metric) approach based on Standard security metrics and on SOA maturity that can be a support for organizations to assess SOA Security and to ensure the safety of their SOA based collaborations
Software for creating pictures in the LaTeX environment
Venue: arXiv cs.GR 2013
Year: 2013

To create a text with graphic instructions for output pictures into LATEX document, we offer software that allows us to build a picture in WIZIWIG mode and for setting the text with these graphical instructions.
Disjunctive Logic Programs versus Normal Logic Programs
Venue: arXiv cs.AI 2013
Year: 2013

This paper focuses on the expressive power of disjunctive and normal logic programs under the stable model semantics over finite, infinite, or arbitrary structures. A translation from disjunctive logic programs into normal logic programs is proposed and then proved to be sound over infinite structures. The equivalence of expressive power of two kinds of logic programs over arbitrary structures is shown to coincide with that over finite structures, and coincide with whether or not NP is closed under complement. Over finite structures, the intranslatability from disjunctive logic programs to normal logic programs is also proved if arities of auxiliary predicates and functions are bounded in a certain way.
Edge Contractions and Simplicial Homology
Venue: arXiv cs.CG 2013
Year: 2013

We study the effect of edge contractions on simplicial homology because these contractions have turned to be useful in various applications involving topology. It was observed previously that contracting edges that satisfy the so called link condition preserves homeomorphism in low dimensional complexes, and homotopy in general. But, checking the link condition involves computation in all dimensions, and hence can be costly, especially in high dimensional complexes. We define a weaker and more local condition called the p-link condition for each dimension p, and study its effect on edge contractions. We prove the following: (i) For homology groups, edges satisfying the p- and (p-1)-link conditions can be contracted without disturbing the p-dimensional homology group. (ii) For relative homology groups, the (p-1)-, and the (p-2)-link conditions suffice to guarantee that the contraction does not introduce any new class in any of the resulting relative homology groups, though some of the existing classes can be destroyed. Unfortunately, the surjection in relative homolgy groups does not guarantee that no new relative torsion is created. (iii) For torsions, edges satisfying the p-link condition alone can be contracted without creating any new relative torsion and the p-link condition cannot be avoided. The results on relative homology and relative torsion are motivated by recent results on computing optimal homologous chains, which state that such problems can be solved by linear programming if the complex has no relative torsion. Edge contractions that do not introduce new relative torsions, can safely be availed in these contexts.
Preliminary Experiments with EVA - Serious Games Virtual Fire Drill Simulator
Venue: arXiv cs.CY 2013
Year: 2013

Fire keeps claiming a large number of victims in building fires. Although there are ways to minimize such events, fire drills are used to train the building occupants for emergency situations. However, organizing and implement these exercises is a complex task, and sometimes not sucessfull. Furthermore, fire drills require the mobilization of some finantial resources and time, and affect the normal functioning of the site where they occur. To overcome the aforementioned issues, computer games have a set of features that might overcome this problem. They offer engagement to their players, keeping them focused, and providing training to real life situations. The game evaluate users, providing them some feedback, making possible for the players to improve their performance. The proposed methodology aims to study the viability of using a game that recreates a fire drill in a 3D environment using Serious Games. The information acquired through the player's performance is very valuable and will be later used to implement an artificial population. A sample of 20 subjects was selected to test the application. Preliminary results are promising, showing that the exercise had a positive impact on users. Moreover, the data acquired is of great important and will be later used to demonstrate the possibility of creating an artificial population based on human behaviour.
Hubs and Authorities of the English Premier League for 2010-2011
Venue: arXiv cs.OH 2013
Year: 2013

In this work author applies well known web search algorithm Hyperlink - Induced Topic Search (HITS) to problem of ranking football teams in English Premier League (EPL). The algorithm allows the ranking of the teams using the notions of hubs and authorities well known for ranking pages in the World Wide Web. Results of the games introduced as a graph where losing team 'gives a link' to a winning team and, if draw registered both team give links to each other. In case of a win link is weighted as three points in adjacent matrix and in case of draw as one point. Author uses notion of authority in order to define team which win a game and hub as a team which lose a game, the winner of the competition defined as the 'worst' hub, team that didn't reinforced any other team. Using this ranking system, the champion's team, which is a 'worst hub' must not lose, or draw games to other 'good authorities' teams. If by the end of the competition there are teams with an equal number of wins and losses then the team which has beaten more teams with higher authority ranks, wins.
Phase-Aligned Space-Time Coding for a Single Stream MIMO system
Venue: arXiv cs.IT 2013
Year: 2013

We present a phase-aligned space-time coding scheme that expands the original Alamouti codeword to three or four transmit antennas ($N_t = 3$ or 4) with phase alignment. With $1 \sim 2$ bits feedback for the phase information, the fundamental performance penalty of $10log_{10}(N_t)$ dB of orthogonal space-time coding compared to the optimum beamforming is reduced by 1 dB (for $N_t=3$) or 2 dB (for $N_t = 4$) on average. With the proposed scheme, the full diversity order of $N_t$ is achievable, whereas the receiver architecture remains the same as the legacy Alamouti decoding with codeword size of two, since the spatial expansion is transparent to the receiver. Our results show the proposed scheme outperforms open-loop space-time coding for three or four transmit antennas by more than 3 dB.
Coexistence of Near-Field and Far-Field Sources: the Angular Resolution Limit
Venue: arXiv cs.IT 2013
Year: 2013

Passive source localization is a well known inverse problem in which we convert the observed measurements into information about the direction of arrivals. In this paper we focus on the optimal resolution of such problem. More precisely, we propose in this contribution to derive and analyze the Angular Resolution Limit (ARL) for the scenario of mixed Near-Field (NF) and Far-Field (FF) Sources. This scenario is relevant to some realistic situations. We base our analysis on the Smith's equation which involves the Cramér-Rao Bound (CRB). This equation provides the theoretical ARL which is independent of a specific estimator. Our methodology is the following: first, we derive a closed-form expression of the CRB for the considered problem. Using these expressions, we can rewrite the Smith's equation as a 4-th order polynomial by assuming a small separation of the sources. Finally, we derive in closed-form the analytic ARL under or not the assumption of low noise variance. The obtained expression is compact and can provide useful qualitative informations on the behavior of the ARL.
Improved Anomaly Detection in Crowded Scenes via Cell-based Analysis of Foreground Speed, Size and Texture
Venue: arXiv cs.CV 2013
Year: 2013

A robust and efficient anomaly detection technique is proposed, capable of dealing with crowded scenes where traditional tracking based approaches tend to fail. Initial foreground segmentation of the input frames confines the analysis to foreground objects and effectively ignores irrelevant background dynamics. Input frames are split into non-overlapping cells, followed by extracting features based on motion, size and texture from each cell. Each feature type is independently analysed for the presence of an anomaly. Unlike most methods, a refined estimate of object motion is achieved by computing the optical flow of only the foreground pixels. The motion and size features are modelled by an approximated version of kernel density estimation, which is computationally efficient even for large training datasets. Texture features are modelled by an adaptively grown codebook, with the number of entries in the codebook selected in an online fashion. Experiments on the recently published UCSD Anomaly Detection dataset show that the proposed method obtains considerably better results than three recent approaches: MPPCA, social force, and mixture of dynamic textures (MDT). The proposed method is also several orders of magnitude faster than MDT, the next best performing method.
A Succinct Grammar Compression
Venue: arXiv cs.DS 2013
Year: 2013

We solve an open problem related to an optimal encoding of a straight line program (SLP), a canonical form of grammar compression deriving a single string deterministically. We show that an information-theoretic lower bound for representing an SLP with n symbols requires at least 2n+logn!+o(n) bits. We then present a succinct representation of an SLP; this representation is asymptotically equivalent to the lower bound. The space is at most 2n log {rho}(1 + o(1)) bits for rho leq 2sqrt{n}, while supporting random access to any production rule of an SLP in O(log log n) time. In addition, we present a novel dynamic data structure associating a digram with a unique symbol. Such a data structure is called a naming function and has been implemented using a hash table that has a space-time tradeoff. Thus, the memory space is mainly occupied by the hash table during the development of production rules. Alternatively, we build a dynamic data structure for the naming function by leveraging the idea behind the wavelet tree. The space is strictly bounded by 2n log n(1 + o(1)) bits, while supporting O(log n) query and update time.
Linear-in-$Δ$ Lower Bounds in the LOCAL Model
Venue: arXiv cs.DC 2013
Year: 2013

By prior work, there is a distributed algorithm that finds a maximal fractional matching (maximal edge packing) in $O(Δ)$ rounds, where $Δ$ is the maximum degree of the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in $o(Δ)$ rounds. Our work gives the first linear-in-$Δ$ lower bound for a natural graph problem in the standard model of distributed computing---prior lower bounds for a wide range of graph problems have been at best logarithmic in $Δ$.
An Improved LR-aided K-Best Algorithm for MIMO Detection
Venue: arXiv cs.IT 2013
Year: 2013

Recently, lattice reduction (LR) technique has caught great attention for multi-input multi-output (MIMO) receiver because of its low complexity and high performance. However, when the number of antennas is large, LR-aided linear detectors and successive interference cancellation (SIC) detectors still exhibit considerable performance gap to the optimal maximum likelihood detector (MLD). To enhance the performance of the LR-aided detectors, the LR-aided K-best algorithm was developed at the cost of the extra complexity on the order $\mathcal{O}(N_t^2 K + N_t K^2)$, where $N_t$ is the number of transmit antennas and $K$ is the number of candidates. In this paper, we develop an LR-aided K-best algorithm with lower complexity by exploiting a priority queue. With the aid of the priority queue, our analysis shows that the complexity of the LR-aided K-best algorithm can be further reduced to $\mathcal{O}(N_t^2 K + N_t K {\rm log}_2(K))$. The low complexity of the proposed LR-aided K-best algorithm allows us to perform the algorithm for large MIMO systems (e.g., 50x50 MIMO systems) with large candidate sizes. Simulations show that as the number of antennas increases, the error performance approaches that of AWGN channel.
The core of games on ordered structures and graphs
Venue: arXiv cs.GT 2013
Year: 2013

In cooperative games, the core is the most popular solution concept, and its properties are well known. In the classical setting of cooperative games, it is generally assumed that all coalitions can form, i.e., they are all feasible. In many situations, this assumption is too strong and one has to deal with some unfeasible coalitions. Defining a game on a subcollection of the power set of the set of players has many implications on the mathematical structure of the core, depending on the precise structure of the subcollection of feasible coalitions. Many authors have contributed to this topic, and we give a unified view of these different results.
Dynamic Construction of Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

We describe a method for incrementally constructing belief networks. We have developed a network-construction language similar to a forward-chaining language using data dependencies, but with additional features for specifying distributions. Using this language, we can define parameterized classes of probabilistic models. These parameterized models make it possible to apply probabilistic reasoning to problems for which it is impractical to have a single large static model.
A New Algorithm for Finding MAP Assignments to Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

We present a new algorithm for finding maximum a-posterior) (MAP) assignments of values to belief networks. The belief network is compiled into a network consisting only of nodes with boolean (i.e. only 0 or 1) conditional probabilities. The MAP assignment is then found using a best-first search on the resulting network. We argue that, as one would anticipate, the algorithm is exponential for the general case, but only linear in the size of the network for poly trees.
A Randomized Approximation Algorithm of Logic Sampling
Venue: arXiv cs.AI 2013
Year: 2013

In recent years, researchers in decision analysis and artificial intelligence (AI) have used Bayesian belief networks to build models of expert opinion. Using standard methods drawn from the theory of computational complexity, workers in the field have shown that the problem of exact probabilistic inference on belief networks almost certainly requires exponential computation in the worst ease [3]. We have previously described a randomized approximation scheme, called BN-RAS, for computation on belief networks [ 1, 2, 4]. We gave precise analytic bounds on the convergence of BN-RAS and showed how to trade running time for accuracy in the evaluation of posterior marginal probabilities. We now extend our previous results and demonstrate the generality of our framework by applying similar mathematical techniques to the analysis of convergence for logic sampling [7], an alternative simulation algorithm for probabilistic inference.
Minimum Error Tree Decomposition
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes a generalization of previous methods for constructing tree-structured belief network with hidden variables. The major new feature of the described method is the ability to produce a tree decomposition even when there are errors in the correlation data among the input variables. This is an important extension of existing methods since the correlational coefficients usually cannot be measured with precision. The technique involves using a greedy search algorithm that locally minimizes an error function.
Pruning Bayesian Networks for Efficient Computation
Venue: arXiv cs.AI 2013
Year: 2013

This paper analyzes the circumstances under which Bayesian networks can be pruned in order to reduce computational complexity without altering the computation for variables of interest. Given a problem instance which consists of a query and evidence for a set of nodes in the network, it is possible to delete portions of the network which do not participate in the computation for the query. Savings in computational complexity can be large when the original network is not singly connected. Results analogous to those described in this paper have been derived before [Geiger, Verma, and Pearl 89, Shachter 88] but the implications for reducing complexity of the computations in Bayesian networks have not been stated explicitly. We show how a preprocessing step can be used to prune a Bayesian network prior to using standard algorithms to solve a given problem instance. We also show how our results can be used in a parallel distributed implementation in order to achieve greater savings. We define a computationally equivalent subgraph of a Bayesian network. The algorithm developed in [Geiger, Verma, and Pearl 89] is modified to construct the subgraphs described in this paper with O(e) complexity, where e is the number of edges in the Bayesian network. Finally, we define a minimal computationally equivalent subgraph and prove that the subgraphs described are minimal.
Using Dempster-Shafer Theory in Knowledge Representation
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we suggest marrying Dempster-Shafer (DS) theory with Knowledge Representation (KR). Born out of this marriage is the definition of "Dempster-Shafer Belief Bases", abstract data types representing uncertain knowledge that use DS theory for representing strength of belief about our knowledge, and the linguistic structures of an arbitrary KR system for representing the knowledge itself. A formal result guarantees that both the properties of the given KR system and of DS theory are preserved. The general model is exemplified by defining DS Belief Bases where First Order Logic and (an extension of) KRYPTON are used as KR systems. The implementation problem is also touched upon.
A Hierarchical Approach to Designing Approximate Reasoning-Based Controllers for Dynamic Physical Systems
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a new technique for the design of approximate reasoning based controllers for dynamic physical systems with interacting goals. In this approach, goals are achieved based on a hierarchy defined by a control knowledge base and remain highly interactive during the execution of the control task. The approach has been implemented in a rule-based computer program which is used in conjunction with a prototype hardware system to solve the cart-pole balancing problem in real-time. It provides a complementary approach to the conventional analytical control methodology, and is of substantial use where a precise mathematical model of the process being controlled is not available.
An Architecture for Probabilistic Concept-Based Information Retrieval
Venue: arXiv cs.AI 2013
Year: 2013

While concept-based methods for information retrieval can provide improved performance over more conventional techniques, they require large amounts of effort to acquire the concepts and their qualitative and quantitative relationships. This paper discusses an architecture for probabilistic concept-based information retrieval which addresses the knowledge acquisition problem. The architecture makes use of the probabilistic networks technology for representing and reasoning about concepts and includes a knowledge acquisition component which partially automates the construction of concept knowledge bases from data. We describe two experiments that apply the architecture to the task of retrieving documents about terrorism from a set of documents from the Reuters news service. The experiments provide positive evidence that the architecture design is feasible and that there are advantages to concept-based methods.
On Non-monotonic Conditional Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

This note is concerned with a formal analysis of the problem of non-monotonic reasoning in intelligent systems, especially when the uncertainty is taken into account in a quantitative way. A firm connection between logic and probability is established by introducing conditioning notions by means of formal structures that do not rely on quantitative measures. The associated conditional logic, compatible with conditional probability evaluations, is non-monotonic relative to additional evidence. Computational aspects of conditional probability logic are mentioned. The importance of this development lies on its role to provide a conceptual basis for various forms of evidence combination and on its significance to unify multi-valued and non-monotonic logics
Decisions with Limited Observations over a Finite Product Space: the Klir Effect
Venue: arXiv cs.AI 2013
Year: 2013

Probability estimation by maximum entropy reconstruction of an initial relative frequency estimate from its projection onto a hypergraph model of the approximate conditional independence relations exhibited by it is investigated. The results of this study suggest that use of this estimation technique may improve the quality of decisions that must be made on the basis of limited observations over a decomposable finite product space.
Fine-Grained Decision-Theoretic Search Control
Venue: arXiv cs.AI 2013
Year: 2013

Decision-theoretic control of search has previously used as its basic unit. of computation the generation and evaluation of a complete set of successors. Although this simplifies analysis, it results in some lost opportunities for pruning and satisficing. This paper therefore extends the analysis of the value of computation to cover individual successor evaluations. The analytic techniques used may prove useful for control of reasoning in more general settings. A formula is developed for the expected value of a node, k of whose n successors have been evaluated. This formula is used to estimate the value of expanding further successors, using a general formula for the value of a computation in game-playing developed in earlier work. We exhibit an improved version of the MGSS* algorithm, giving empirical results for the game of Othello.