OpenRaiser/Intern-Atlas huggingface dataset:
Reduction of Event Structures under History Preserving Bisimulation
Venue: arXiv cs.LO 2014
Year: 2014

Event structures represent concurrent processes in terms of events and dependencies between events modelling behavioural relations like causality and conflict. Since the introduction of prime event structures, many variants of event structures have been proposed with different behavioural relations and, hence, with differences in their expressive power. One of the possible benefits of using a more expressive event structure is that of having a more compact representation for the same behaviour when considering the number of events used in a prime event structure. Therefore, this article addresses the problem of reducing the size of an event structure while preserving behaviour under a well-known notion of equivalence, namely history preserving bisimulation. In particular, we investigate this problem on two generalisations of the prime event structures. The first one, known as asymmetric event structure, relies on a asymmetric form of the conflict relation. The second one, known as flow event structure, supports a form of disjunctive causality. More specifically, we describe the conditions under which a set of events in an event structure can be folded into a single event while preserving the original behaviour. The successive application of this folding operation leads to a minimal size event structure. However, the order on which the folding operation is applied may lead to different minimal size event structures. The latter has a negative implication on the potential use of a minimal size event structure as a canonical representation for behaviour.
Emotion Analysis Platform on Chinese Microblog
Venue: arXiv cs.CL 2014
Year: 2014

Weibo, as the largest social media service in China, has billions of messages generated every day. The huge number of messages contain rich sentimental information. In order to analyze the emotional changes in accordance with time and space, this paper presents an Emotion Analysis Platform (EAP), which explores the emotional distribution of each province, so that can monitor the global pulse of each province in China. The massive data of Weibo and the real-time requirements make the building of EAP challenging. In order to solve the above problems, emoticons, emotion lexicon and emotion-shifting rules are adopted in EAP to analyze the emotion of each tweet. In order to verify the effectiveness of the platform, case study on the Sichuan earthquake is done, and the analysis result of the platform accords with the fact. In order to analyze from quantity, we manually annotate a test set and conduct experiment on it. The experimental results show that the macro-Precision of EAP reaches 80% and the EAP works effectively.
O(log log rank) Competitive-Ratio for the Matroid Secretary Problem
Venue: arXiv cs.DS 2014
Year: 2014

In the \textit{Matroid Secretary Problem} (MSP), the elements of the ground set of a Matroid are revealed on-line one by one, each together with its value. An algorithm for the MSP is \textit{Matroid-Unknown} if, at every stage of its execution: (i) it only knows the elements that have been revealed so far and their values, and (ii) it has access to an oracle for testing whether or not any subset of the elements that have been revealed so far is an independent set. An algorithm is \textit{Known-Cardinality} if, in addition to (i) and (ii), it also initially knows the cardinality of the ground set of the Matroid. We present here a Known-Cardinality and \textit{Order-Oblivious} algorithm that, with constant probability, selects an independent set of elements, whose value is at least the optimal value divided by $O(\log{\logρ})$, where $ρ$ is the rank of the Matroid; that is, the algorithm has a \textit{competitive-ratio} of $O(\log{\logρ})$. The best previous results for a Known-Cardinality algorithm are a competitive-ratio of $O(\logρ)$, by Babaioff \textit{et al.} (2007), and a competitive-ratio of $O(\sqrt{\logρ})$, by Chakraborty and Lachish (2012). In many non-trivial cases the algorithm we present has a competitive-ratio that is better than the $O(\log{\logρ})$. The cases in which it fails to do so are easily characterized. Understanding these cases may lead to improved algorithms for the problem or, conversely, to non-trivial lower bounds.
Expectation-Maximization Technique and Spatial-Adaptation Applied to Pel-Recursive Motion Estimation
Venue: arXiv cs.CV 2014
Year: 2014

Pel-recursive motion estimation isa well-established approach. However, in the presence of noise, it becomes an ill-posed problem that requires regularization. In this paper, motion vectors are estimated in an iterative fashion by means of the Expectation-Maximization (EM) algorithm and a Gaussian data model. Our proposed algorithm also utilizes the local image properties of the scene to improve the motion vector estimates following a spatially adaptive approach. Numerical experiments are presented that demonstrate the merits of our method.
Parallel Hierarchical Affinity Propagation with MapReduce
Venue: arXiv cs.DC 2014
Year: 2014

The accelerated evolution and explosion of the Internet and social media is generating voluminous quantities of data (on zettabyte scales). Paramount amongst the desires to manipulate and extract actionable intelligence from vast big data volumes is the need for scalable, performance-conscious analytics algorithms. To directly address this need, we propose a novel MapReduce implementation of the exemplar-based clustering algorithm known as Affinity Propagation. Our parallelization strategy extends to the multilevel Hierarchical Affinity Propagation algorithm and enables tiered aggregation of unstructured data with minimal free parameters, in principle requiring only a similarity measure between data points. We detail the linear run-time complexity of our approach, overcoming the limiting quadratic complexity of the original algorithm. Experimental validation of our clustering methodology on a variety of synthetic and real data sets (e.g. images and point data) demonstrates our competitiveness against other state-of-the-art MapReduce clustering techniques.
Big Questions for Social Media Big Data: Representativeness, Validity and Other Methodological Pitfalls
Venue: arXiv cs.SI 2014
Year: 2014

Large-scale databases of human activity in social media have captured scientific and policy attention, producing a flood of research and discussion. This paper considers methodological and conceptual challenges for this emergent field, with special attention to the validity and representativeness of social media big data analyses. Persistent issues include the over-emphasis of a single platform, Twitter, sampling biases arising from selection by hashtags, and vague and unrepresentative sampling frames. The socio-cultural complexity of user behavior aimed at algorithmic invisibility (such as subtweeting, mock-retweeting, use of "screen captures" for text, etc.) further complicate interpretation of big data social media. Other challenges include accounting for field effects, i.e. broadly consequential events that do not diffuse only through the network under study but affect the whole society. The application of network methods from other fields to the study of human social activity may not always be appropriate. The paper concludes with a call to action on practical steps to improve our analytic capacity in this promising, rapidly-growing field.
An Overview of Hierarchical Task Network Planning
Venue: arXiv cs.AI 2014
Year: 2014

Hierarchies are the most common structure used to understand the world better. In galaxies, for instance, multiple-star systems are organised in a hierarchical system. Then, governmental and company organisations are structured using a hierarchy, while the Internet, which is used on a daily basis, has a space of domain names arranged hierarchically. Since Artificial Intelligence (AI) planning portrays information about the world and reasons to solve some of world's problems, Hierarchical Task Network (HTN) planning has been introduced almost 40 years ago to represent and deal with hierarchies. Its requirement for rich domain knowledge to characterise the world enables HTN planning to be very useful, but also to perform well. However, the history of almost 40 years obfuscates the current understanding of HTN planning in terms of accomplishments, planning models, similarities and differences among hierarchical planners, and its current and objective image. On top of these issues, attention attracts the ability of hierarchical planning to truly cope with the requirements of applications from the real world. We propose a framework-based approach to remedy this situation. First, we provide a basis for defining different formal models of hierarchical planning, and define two models that comprise a large portion of HTN planners. Second, we provide a set of concepts that helps to interpret HTN planners from the aspect of their search space. Then, we analyse and compare the planners based on a variety of properties organised in five segments, namely domain authoring, expressiveness, competence, performance and applicability. Furthermore, we select Web service composition as a real-world and current application, and classify and compare the approaches that employ HTN planning to solve the problem of service composition. Finally, we conclude with our findings and present directions for future work.
Shiva: A Framework for Graph Based Ontology Matching
Venue: arXiv cs.AI 2014
Year: 2014

Since long, corporations are looking for knowledge sources which can provide structured description of data and can focus on meaning and shared understanding. Structures which can facilitate open world assumptions and can be flexible enough to incorporate and recognize more than one name for an entity. A source whose major purpose is to facilitate human communication and interoperability. Clearly, databases fail to provide these features and ontologies have emerged as an alternative choice, but corporations working on same domain tend to make different ontologies. The problem occurs when they want to share their data/knowledge. Thus we need tools to merge ontologies into one. This task is termed as ontology matching. This is an emerging area and still we have to go a long way in having an ideal matcher which can produce good results. In this paper we have shown a framework to matching ontologies using graphs.
Mobile Conductance in Sparse Networks and Mobility-Connectivity Tradeoff
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, our recently proposed mobile-conductance based analytical framework is extended to the sparse settings, thus offering a unified tool for analyzing information spreading in mobile networks. A penalty factor is identified for information spreading in sparse networks as compared to the connected scenario, which is then intuitively interpreted and verified by simulations. With the analytical results obtained, the mobility-connectivity tradeoff is quantitatively analyzed to determine how much mobility may be exploited to make up for network connectivity deficiency.
Algebraic Properties of Stochastic Effectivity Functions
Venue: arXiv cs.LO 2014
Year: 2014

Effectivity functions are the basic formalism for investigating the semantics game logic. We discuss algebraic properties of stochastic effectivity functions, in particular the relationship to stochastic relations, morphisms and congruences are defined, and the relationship of abstract logical equivalence and behavioral equivalence is investigated.
Multi-label Ferns for Efficient Recognition of Musical Instruments in Recordings
Venue: arXiv cs.LG 2014
Year: 2014

In this paper we introduce multi-label ferns, and apply this technique for automatic classification of musical instruments in audio recordings. We compare the performance of our proposed method to a set of binary random ferns, using jazz recordings as input data. Our main result is obtaining much faster classification and higher F-score. We also achieve substantial reduction of the model size.
Distributed Channel Quantization for Two-User Interference Networks
Venue: arXiv cs.IT 2014
Year: 2014

We introduce conferencing-based distributed channel quantizers for two-user interference networks where interference signals are treated as noise. Compared with the conventional distributed quantizers where each receiver quantizes its own channel independently, the proposed quantizers allow multiple rounds of feedback communication in the form of conferencing between receivers. We take the network outage probabilities of sum rate and minimum rate as performance measures and consider quantizer design in the transmission strategies of time sharing and interference transmission. First, we propose distributed quantizers that achieve the optimal network outage probability of sum rate for both time sharing and interference transmission strategies with an average feedback rate of only two bits per channel state. Then, for the time sharing strategy, we propose a distributed quantizer that achieves the optimal network outage probability of minimum rate with finite average feedback rate; conventional quantizers require infinite rate to achieve the same performance. For the interference transmission strategy, a distributed quantizer that can approach the optimal network outage probability of minimum rate closely is also proposed. Numerical simulations confirm that our distributed quantizers based on conferencing outperform the conventional ones.
Implementation of interaction between soft tissues and foreign bodies using modified voxel model
Venue: arXiv cs.CG 2014
Year: 2014

Interactive bodies collision detection and elimination is one of the most popular task nowadays. Collisions can be detected in different ways. Collision search using space voxelization is one of the most fast. This paper describes improved voxel model that covers only area of collision interest and quickly eliminates collisions. This new method can be useful in real time collision processing of different rigid and soft bodies grids.
Probabilistic Intra-Retinal Layer Segmentation in 3-D OCT Images Using Global Shape Regularization
Venue: arXiv cs.CV 2014
Year: 2014

With the introduction of spectral-domain optical coherence tomography (OCT), resulting in a significant increase in acquisition speed, the fast and accurate segmentation of 3-D OCT scans has become evermore important. This paper presents a novel probabilistic approach, that models the appearance of retinal layers as well as the global shape variations of layer boundaries. Given an OCT scan, the full posterior distribution over segmentations is approximately inferred using a variational method enabling efficient probabilistic inference in terms of computationally tractable model components: Segmenting a full 3-D volume takes around a minute. Accurate segmentations demonstrate the benefit of using global shape regularization: We segmented 35 fovea-centered 3-D volumes with an average unsigned error of 2.46 $\pm$ 0.22 μm as well as 80 normal and 66 glaucomatous 2-D circular scans with errors of 2.92 $\pm$ 0.53 μm and 4.09 $\pm$ 0.98 μm respectively. Furthermore, we utilized the inferred posterior distribution to rate the quality of the segmentation, point out potentially erroneous regions and discriminate normal from pathological scans. No pre- or postprocessing was required and we used the same set of parameters for all data sets, underlining the robustness and out-of-the-box nature of our approach.
Privacy Tradeoffs in Predictive Analytics
Venue: arXiv cs.CR 2014
Year: 2014

Online services routinely mine user data to predict user preferences, make recommendations, and place targeted ads. Recent research has demonstrated that several private user attributes (such as political affiliation, sexual orientation, and gender) can be inferred from such data. Can a privacy-conscious user benefit from personalization while simultaneously protecting her private attributes? We study this question in the context of a rating prediction service based on matrix factorization. We construct a protocol of interactions between the service and users that has remarkable optimality properties: it is privacy-preserving, in that no inference algorithm can succeed in inferring a user's private attribute with a probability better than random guessing; it has maximal accuracy, in that no other privacy-preserving protocol improves rating prediction; and, finally, it involves a minimal disclosure, as the prediction accuracy strictly decreases when the service reveals less information. We extensively evaluate our protocol using several rating datasets, demonstrating that it successfully blocks the inference of gender, age and political affiliation, while incurring less than 5% decrease in the accuracy of rating prediction.
A Percolation based M2M Networking Architecture for Data Transmission and Routing
Venue: arXiv cs.NI 2014
Year: 2014

We propose a percolation based M2M networking architecture and its data transmission method. The proposed network architecture can be server-free and router-free, which allows us to operate routing efficiently with percolations based on six degrees of separation theory in small world network modeling. The data transmission can be divided into two phases: routing and data transmission phases. In the routing phase, probe packets will be transmitted and forwarded in the network thus multiple paths are selected and performed based on the constriction of the maximum hop number. In the second phase, the information will be encoded, say, with the fountain codes, and transmitted using the paths generated in the first phase. In such a way, an efficient routing and data transmission mechanism can be built, which allow us to construct a low-cost, flexible and ubiquitous network. Such a networking architecture and data transmission can be used in many M2M communications, such as the stub network of internet of things, and deep space networking, and so on.
Secure and scalable match: overcoming the universal circuit bottleneck using group programs
Venue: arXiv cs.CR 2014
Year: 2014

Confidential Content-Based Publish/Subscribe (C-CBPS) is an interaction (pub/sub) model that allows parties to exchange data while still protecting their security and privacy interests. In this paper we advance the state of the art in C-CBPS by showing how all predicate circuits in NC1 (logarithmic-depth, bounded fan-in) can be securely computed by a broker while guaranteeing perfect information-theoretic security. Previous work could handle only strictly shallower circuits (e.g. those with depth O(\sqrt{\lg n}) [SYY99, V76]. We present three protocols -- UGP-Match, FSGP-Match and OFSGP-Match -- all three are based on (2-decomposable randomized encodings of) group programs and handle circuits in NC1. UGP-Match is conceptually simple and has a clean proof of correctness but it is inefficient and impractical. FSGP-Match uses a "fixed structure" trick to achieve efficiency and scalability. And, finally, OFSGP-Match uses hand-optimized group programs to wring greater efficiencies. We complete our investigation with an experimental evaluation of a prototype implementation.
Approximation Schemes for Many-Objective Query Optimization
Venue: arXiv cs.DB 2014
Year: 2014

The goal of multi-objective query optimization (MOQO) is to find query plans that realize a good compromise between conflicting objectives such as minimizing execution time and minimizing monetary fees in a Cloud scenario. A previously proposed exhaustive MOQO algorithm needs hours to optimize even simple TPC-H queries. This is why we propose several approximation schemes for MOQO that generate guaranteed near-optimal plans in seconds where exhaustive optimization takes hours. We integrated all MOQO algorithms into the Postgres optimizer and present experimental results for TPC-H queries; we extended the Postgres cost model and optimize for up to nine conflicting objectives in our experiments. The proposed algorithms are based on a formal analysis of typical cost functions that occur in the context of MOQO. We identify properties that hold for a broad range of objectives and can be exploited for the design of future MOQO algorithms.
Proof-graphs for Minimal Implicational Logic
Venue: arXiv cs.LO 2014
Year: 2014

It is well-known that the size of propositional classical proofs can be huge. Proof theoretical studies discovered exponential gaps between normal or cut free proofs and their respective non-normal proofs. The aim of this work is to study how to reduce the weight of propositional deductions. We present the formalism of proof-graphs for purely implicational logic, which are graphs of a specific shape that are intended to capture the logical structure of a deduction. The advantage of this formalism is that formulas can be shared in the reduced proof. In the present paper we give a precise definition of proof-graphs for the minimal implicational logic, together with a normalization procedure for these proof-graphs. In contrast to standard tree-like formalisms, our normalization does not increase the number of nodes, when applied to the corresponding minimal proof-graph representations.
Causal Dynamics of Discrete Surfaces
Venue: arXiv cs.DM 2014
Year: 2014

We formalize the intuitive idea of a labelled discrete surface which evolves in time, subject to two natural constraints: the evolution does not propagate information too fast; and it acts everywhere the same.
A Calculus of Located Entities
Venue: arXiv cs.PL 2014
Year: 2014

We define BioScapeL, a stochastic pi-calculus in 3D-space. A novel aspect of BioScapeL is that entities have programmable locations. The programmer can specify a particular location where to place an entity, or a location relative to the current location of the entity. The motivation for the extension comes from the need to describe the evolution of populations of biochemical species in space, while keeping a sufficiently high level description, so that phenomena like diffusion, collision, and confinement can remain part of the semantics of the calculus. Combined with the random diffusion movement inherited from BioScape, programmable locations allow us to capture the assemblies of configurations of polymers, oligomers, and complexes such as microtubules or actin filaments. Further new aspects of BioScapeL include random translation and scaling. Random translation is instrumental in describing the location of new entities relative to the old ones. For example, when a cell secretes a hydronium ion, the ion should be placed at a given distance from the originating cell, but in a random direction. Additionally, scaling allows us to capture at a high level events such as division and growth; for example, daughter cells after mitosis have half the size of the mother cell.
Using HMM in Strategic Games
Venue: arXiv cs.GT 2014
Year: 2014

In this paper we describe an approach to resolve strategic games in which players can assume different types along the game. Our goal is to infer which type the opponent is adopting at each moment so that we can increase the player's odds. To achieve that we use Markov games combined with hidden Markov model. We discuss a hypothetical example of a tennis game whose solution can be applied to any game with similar characteristics.