OpenRaiser/Intern-Atlas huggingface dataset:
Location Estimation Using Crowdsourced Geospatial Narratives
Venue: arXiv cs.DB 2014
Year: 2014

The "crowd" has become a very important geospatial data provider. Subsumed under the term Volunteered Geographic Information (VGI), non-expert users have been providing a wealth of quantitative geospatial data online. With spatial reasoning being a basic form of human cognition, narratives expressing geospatial experiences, e.g., travel blogs, would provide an even bigger source of geospatial data. Textual narratives typically contain qualitative data in the form of objects and spatial relationships. The scope of this work is (i) to extract these relationships from user-generated texts, (ii) to quantify them and (iii) to reason about object locations based only on this qualitative data. We use information extraction methods to identify toponyms and spatial relationships and to formulate a quantitative approach based on distance and orientation features to represent the latter. Positional probability distributions for spatial relationships are determined by means of a greedy Expectation Maximization-based (EM) algorithm. These estimates are then used to "triangulate" the positions of unknown object locations. Experiments using a text corpus harvested from travel blog sites establish the considerable location estimation accuracy of the proposed approach.
On the Path-Width of Integer Linear Programming
Venue: arXiv cs.LO 2014
Year: 2014

We consider the feasibility problem of integer linear programming (ILP). We show that solutions of any ILP instance can be naturally represented by an FO-definable class of graphs. For each solution there may be many graphs representing it. However, one of these graphs is of path-width at most 2n, where n is the number of variables in the instance. Since FO is decidable on graphs of bounded path- width, we obtain an alternative decidability result for ILP. The technique we use underlines a common principle to prove decidability which has previously been employed for automata with auxiliary storage. We also show how this new result links to automata theory and program verification.
Deterministic Automata for Unordered Trees
Venue: arXiv cs.FL 2014
Year: 2014

Automata for unordered unranked trees are relevant for defining schemas and queries for data trees in Json or Xml format. While the existing notions are well-investigated concerning expressiveness, they all lack a proper notion of determinism, which makes it difficult to distinguish subclasses of automata for which problems such as inclusion, equivalence, and minimization can be solved efficiently. In this paper, we propose and investigate different notions of "horizontal determinism", starting from automata for unranked trees in which the horizontal evaluation is performed by finite state automata. We show that a restriction to confluent horizontal evaluation leads to polynomial-time emptiness and universality, but still suffers from coNP-completeness of the emptiness of binary intersections. Finally, efficient algorithms can be obtained by imposing an order of horizontal evaluation globally for all automata in the class. Depending on the choice of the order, we obtain different classes of automata, each of which has the same expressiveness as CMso.
Visibly Pushdown Modular Games
Venue: arXiv cs.LO 2014
Year: 2014

Games on recursive game graphs can be used to reason about the control flow of sequential programs with recursion. In games over recursive game graphs, the most natural notion of strategy is the modular strategy, i.e., a strategy that is local to a module and is oblivious to previous module invocations, and thus does not depend on the context of invocation. In this work, we study for the first time modular strategies with respect to winning conditions that can be expressed by a pushdown automaton. We show that such games are undecidable in general, and become decidable for visibly pushdown automata specifications. Our solution relies on a reduction to modular games with finite-state automata winning conditions, which are known in the literature. We carefully characterize the computational complexity of the considered decision problem. In particular, we show that modular games with a universal Buchi or co Buchi visibly pushdown winning condition are EXPTIME-complete, and when the winning condition is given by a CARET or NWTL temporal logic formula the problem is 2EXPTIME-complete, and it remains 2EXPTIME-hard even for simple fragments of these logics. As a further contribution, we present a different solution for modular games with finite-state automata winning condition that runs faster than known solutions for large specifications and many exits.
Self-Adaptation and Secure Information Flow in Multiparty Structured Communications: A Unified Perspective
Venue: arXiv cs.LO 2014
Year: 2014

We present initial results on a comprehensive model of structured communications, in which self- adaptation and security concerns are jointly addressed. More specifically, we propose a model of self-adaptive, multiparty communications with secure information flow guarantees. In this model, security violations occur when processes attempt to read or write messages of inappropriate security levels within directed exchanges. Such violations trigger adaptation mechanisms that prevent the violations to occur and/or to propagate their effect in the choreography. Our model is equipped with local and global mechanisms for reacting to security violations; type soundness results ensure that global protocols are still correctly executed, while the system adapts itself to preserve security.
On the Statistical Multiplexing Gain of Virtual Base Station Pools
Venue: arXiv cs.IT 2014
Year: 2014

Facing the explosion of mobile data traffic, cloud radio access network (C-RAN) is proposed recently to overcome the efficiency and flexibility problems with the traditional RAN architecture by centralizing baseband processing. However, there lacks a mathematical model to analyze the statistical multiplexing gain from the pooling of virtual base stations (VBSs) so that the expenditure on fronthaul networks can be justified. In this paper, we address this problem by capturing the session-level dynamics of VBS pools with a multi-dimensional Markov model. This model reflects the constraints imposed by both radio resources and computational resources. To evaluate the pooling gain, we derive a product-form solution for the stationary distribution and give a recursive method to calculate the blocking probabilities. For comparison, we also derive the limit of resource utilization ratio as the pool size approaches infinity. Numerical results show that VBS pools can obtain considerable pooling gain readily at medium size, but the convergence to large pool limit is slow because of the quickly diminishing marginal pooling gain. We also find that parameters such as traffic load and desired Quality of Service (QoS) have significant influence on the performance of VBS pools.
An $O(n^2)$ Algorithm for Computing Optimal Continuous Voltage Schedules
Venue: arXiv cs.DS 2014
Year: 2014

Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. In the continuous model, the processor can run at any speed, while in the discrete model, the processor can only run at finite number of speeds given as input. The current best algorithm for computing the optimal schedules for the continuous model runs at $O(n^2\log n)$ time for scheduling $n$ jobs. In this paper, we improve the running time to $O(n^2)$ by speeding up the calculation of s-schedules using a more refined data structure. For the discrete model, we improve the computation of the optimal schedule from the current best $O(dn\log n)$ to $O(n\log \max\{d,n\})$ where $d$ is the number of allowed speeds.
Engineering Gesture-Based Authentication Systems
Venue: arXiv cs.CR 2014
Year: 2014

Gestures are a topic of increasing interest in authentication and successful implementation as a security layer requires reliable gesture recognition. So far much work focuses on new ways to recognize gestures, leaving discussion on the viability of recognition in an authentication scheme to the background. It is unclear how recognition should be deployed for practical and robust real-world authentication. In this article, we analyze the effectiveness of different approaches to recognizing gestures and the potential for use in secure gesture-based authentication systems.
The proposal of a novel software testing framework
Venue: arXiv cs.SE 2014
Year: 2014

Software testing is normally used to check the validity of a program. Test oracle performs an important role in software testing. The focus in this research is to perform class level test by introducing a testing framework. A technique is developed to generate test oracle for specification-based software testing using Vienna Development Method (VDM++) formal language. A three stage translation process, of VDM++ specifications of container classes to C++ test oracle classes, is described in this paper. It is also presented that how derived test oracle is integrated into a proposed functional testing framework. This technique caters object oriented features such as inheritance and aggregation, but concurrency is not considered in this work. Translation issues, limitations and evaluation of the technique are also discussed. The proposed approach is illustrated with the help of popular triangle problem case study.
The proposal of improved inexact isomorphic graph algorithm to detect design patterns
Venue: arXiv cs.SE 2014
Year: 2014

Design patterns being applied more and more to solve the software engineering difficulties in the object oriented software design procedures. So, the design pattern detection is widely used by software industries. Currently, many solutions presented to detect the design pattern in the system design. In this paper, we will propose a new one which first; we will use the graph implementation to implement both the system design UML diagram and the design pattern UML diagram. Second, we will implement the edges for each one of the both two graphs in a set of 4-tuple elements. Then, we will apply a new inexact graph isomorphic algorithm to detect the design pattern in the system design.
Estimation of the new agile XP process model for medium-scale projects using industrial case studies
Venue: arXiv cs.SE 2014
Year: 2014

Agile is one of the terms with which software professionals are quite familiar. Agile models promote fast development to develop high quality software. XP process model is one of the most widely used and most documented agile models. XP model is meant for small-scale projects. Since XP model is a good model, therefore there is need of its extension for the development of medium and large-scale projects. XP model has certain drawbacks such as weak documentation and poor performance while adapting it for the development of medium and large-scale projects having large teams. A new XP model is proposed in this paper to cater the needs of software development companies for medium-scale projects having large teams. This research may prove to be step forward for adaptation of the proposed new XP model for the development of large-scale projects. Two independent industrial case studies are conducted to validate the proposed new XP model handling for small and medium scale software projects, one case study for each type of project.
Remarks on Quantum Modular Exponentiation and Some Experimental Demonstrations of Shor's Algorithm
Venue: arXiv cs.DS 2014
Year: 2014

An efficient quantum modular exponentiation method is indispensible for Shor's factoring algorithm. But we find that all descriptions presented by Shor, Nielsen and Chuang, Markov and Saeedi, et al., are flawed. We also remark that some experimental demonstrations of Shor's algorithm are misleading, because they violate the necessary condition that the selected number $q=2^s$, where $s$ is the number of qubits used in the first register, must satisfy $n^2 \leq q < 2n^2$, where $n$ is the large number to be factored.
Sparse Graph-based Transduction for Image Classification
Venue: arXiv cs.CV 2014
Year: 2014

Motivated by the remarkable successes of Graph-based Transduction (GT) and Sparse Representation (SR), we present a novel Classifier named Sparse Graph-based Classifier (SGC) for image classification. In SGC, SR is leveraged to measure the correlation (similarity) of each two samples and a graph is constructed for encoding these correlations. Then the Laplacian eigenmapping is adopted for deriving the graph Laplacian of the graph. Finally, SGC can be obtained by plugging the graph Laplacian into the conventional GT framework. In the image classification procedure, SGC utilizes the correlations, which are encoded in the learned graph Laplacian, to infer the labels of unlabeled images. SGC inherits the merits of both GT and SR. Compared to SR, SGC improves the robustness and the discriminating power of GT. Compared to GT, SGC sufficiently exploits the whole data. Therefore it alleviates the undercomplete dictionary issue suffered by SR. Four popular image databases are employed for evaluation. The results demonstrate that SGC can achieve a promising performance in comparison with the state-of-the-art classifiers, particularly in the small training sample size case and the noisy sample case.
Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
Venue: arXiv cs.DS 2014
Year: 2014

We investigate crossing minimization for 1-page and 2-page book drawings. We show that computing the 1-page crossing number is fixed-parameter tractable with respect to the number of crossings, that testing 2-page planarity is fixed-parameter tractable with respect to treewidth, and that computing the 2-page crossing number is fixed-parameter tractable with respect to the sum of the number of crossings and the treewidth of the input graph. We prove these results via Courcelle's theorem on the fixed-parameter tractability of properties expressible in monadic second order logic for graphs of bounded treewidth.
A constructive proof presenting languages in $Σ_2^P$ that cannot be decided by circuit families of size $n^k$
Venue: arXiv cs.CC 2014
Year: 2014

As far as I know, at the time that I originally devised this result (1998), this was the first constructive proof that, for any integer $k$, there is a language in $Σ_2^P$ that cannot be simulated by a family of logic circuits of size $n^k$. However, this result had previously been proved non-constructively: see Cai and Watanabe [CW08] for more information on the history of this problem. This constructive proof is based upon constructing a language $Γ$ derived from the satisfiabiility problem, and a language $Λ_k$ defined by an alternating Turing machine. We show that the union of $Γ$ and $Λ_k$ cannot be simulated by circuits of size $n^k$.
Bridging the Semantic Gap between RDF and SPARQL using Completeness Statements [Extended Version]
Venue: arXiv cs.DB 2014
Year: 2014

RDF data is often treated as incomplete, following the Open-World Assumption. On the other hand, SPARQL, the standard query language over RDF, usually follows the Closed-World Assumption, assuming RDF data to be complete. This gives rise to a semantic gap between RDF and SPARQL. In this paper, we address how to close the semantic gap between RDF and SPARQL in terms of certain answers and possible answers using completeness statements.
Tree games with regular objectives
Venue: arXiv cs.LO 2014
Year: 2014

We study tree games developed recently by Matteo Mio as a game interpretation of the probabilistic $μ$-calculus. With expressive power comes complexity. Mio showed that tree games are able to encode Blackwell games and, consequently, are not determined under deterministic strategies. We show that non-stochastic tree games with objectives recognisable by so-called game automata are determined under deterministic, finite memory strategies. Moreover, we give an elementary algorithmic procedure which, for an arbitrary regular language L and a finite non-stochastic tree game with a winning objective L decides if the game is determined under deterministic strategies.
Knowledge Engineering for Planning-Based Hypothesis Generation
Venue: arXiv cs.AI 2014
Year: 2014

In this paper, we address the knowledge engineering problems for hypothesis generation motivated by applications that require timely exploration of hypotheses under unreliable observations. We looked at two applications: malware detection and intensive care delivery. In intensive care, the goal is to generate plausible hypotheses about the condition of the patient from clinical observations and further refine these hypotheses to create a recovery plan for the patient. Similarly, preventing malware spread within a corporate network involves generating hypotheses from network traffic data and selecting preventive actions. To this end, building on the already established characterization and use of AI planning for similar problems, we propose use of planning for the hypothesis generation problem. However, to deal with uncertainty, incomplete model description and unreliable observations, we need to use a planner capable of generating multiple high-quality plans. To capture the model description we propose a language called LTS++ and a web-based tool that enables the specification of the LTS++ model and a set of observations. We also proposed a 9-step process that helps provide guidance to the domain expert in specifying the LTS++ model. The hypotheses are then generated by running a planner on the translated LTS++ model and the provided trace. The hypotheses can be visualized and shown to the analyst or can be further investigated automatically.
Voronoi Grid-Shell Structures
Venue: arXiv cs.GR 2014
Year: 2014

We introduce a framework for the generation of grid-shell structures that is based on Voronoi diagrams and allows us to design tessellations that achieve excellent static performances. We start from an analysis of stress on the input surface and we use the resulting tensor field to induce an anisotropic non-Euclidean metric over it. Then we compute a Centroidal Voronoi Tessellation under the same metric. The resulting mesh is hex-dominant and made of cells with a variable density, which depends on the amount of stress, and anisotropic shape, which depends on the direction of maximum stress. This mesh is further optimized taking into account symmetry and regularity of cells to improve aesthetics. We demonstrate that our grid-shells achieve better static performances with respect to quad-based grid shells, while offering an innovative and aesthetically pleasing look.
Memcomputing and Swarm Intelligence
Venue: arXiv cs.NE 2014
Year: 2014

We explore the relation between memcomputing, namely computing with and in memory, and swarm intelligence algorithms. In particular, we show that one can design memristive networks to solve short-path optimization problems that can also be solved by ant-colony algorithms. By employing appropriate memristive elements one can demonstrate an almost one-to-one correspondence between memcomputing and ant colony optimization approaches. However, the memristive network has the capability of finding the solution in one deterministic step, compared to the stochastic multi-step ant colony optimization. This result paves the way for nanoscale hardware implementations of several swarm intelligence algorithms that are presently explored, from scheduling problems to robotics.
Chatbot for admissions
Venue: arXiv cs.CY 2014
Year: 2014

The communication of potential students with a university department is performed manually and it is a very time consuming procedure. The opportunity to communicate with on a one-to-one basis is highly valued. However with many hundreds of applications each year, one-to-one conversations are not feasible in most cases. The communication will require a member of academic staff to expend several hours to find suitable answers and contact each student. It would be useful to reduce his costs and time. The project aims to reduce the burden on the head of admissions, and potentially other users, by developing a convincing chatbot. A suitable algorithm must be devised to search through the set of data and find a potential answer. The program then replies to the user and provides a relevant web link if the user is not satisfied by the answer. Furthermore a web interface is provided for both users and an administrator. The achievements of the project can be summarised as follows. To prepare the background of the project a literature review was undertaken, together with an investigation of existing tools, and consultation with the head of admissions. The requirements of the system were established and a range of algorithms and tools were investigated, including keyword and template matching. An algorithm that combines keyword matching with string similarity has been developed. A usable system using the proposed algorithm has been implemented. The system was evaluated by keeping logs of questions and answers and by feedback received by potential students that used it.
Computation of lower bounds for the induced L2 norm of LPV systems
Venue: arXiv cs.SY 2014
Year: 2014

Determining the induced L2 norm of a linear, parameter-varying (LPV) system is an integral part of many analysis and robust control design procedures. Most prior work has focused on efficiently computing upper bounds for the induced L2 norm. The conditions for upper bounds are typically based on scaled small-gain theorems with dynamic multipliers or dissipation inequalities with parameter dependent Lyapunov functions. This paper presents a complementary algorithm to compute lower bounds for the induced L2 norm. The proposed approach computes a lower bound on the gain by restricting the parameter trajectory to be a periodic signal. This restriction enables the use of recent results for exact calculation of the L2 norm for a periodic linear time varying system. The proposed lower bound algorithm has two benefits. First, the lower bound complements standard upper bound techniques. Specifically, a small gap between the bounds indicates that further computation, e.g. upper bounds with more complex Lyapunov functions, is unnecessary. Second, the lower bound algorithm returns a bad parameter trajectory for the LPV system that can be further analyzed to provide insight into the system performance.
A Model of Consistent Node Types in Signed Directed Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

Signed directed social networks, in which the relationships between users can be either positive (indicating relations such as trust) or negative (indicating relations such as distrust), are increasingly common. Thus the interplay between positive and negative relationships in such networks has become an important research topic. Most recent investigations focus upon edge sign inference using structural balance theory or social status theory. Neither of these two theories, however, can explain an observed edge sign well when the two nodes connected by this edge do not share a common neighbor (e.g., common friend). In this paper we develop a novel approach to handle this situation by applying a new model for node types. Initially, we analyze the local node structure in a fully observed signed directed network, inferring underlying node types. The sign of an edge between two nodes must be consistent with their types; this explains edge signs well even when there are no common neighbors. We show, moreover, that our approach can be extended to incorporate directed triads, when they exist, just as in models based upon structural balance or social status theory. We compute Bayesian node types within empirical studies based upon partially observed Wikipedia, Slashdot, and Epinions networks in which the largest network (Epinions) has 119K nodes and 841K edges. Our approach yields better performance than state-of-the-art approaches for these three signed directed networks.