OpenRaiser/Intern-Atlas huggingface dataset:
k-Nearest Neighbor Classification over Semantically Secure Encrypted Relational Data
Venue: arXiv cs.CR 2014
Year: 2014

Data Mining has wide applications in many areas such as banking, medicine, scientific research and among government agencies. Classification is one of the commonly used tasks in data mining applications. For the past decade, due to the rise of various privacy issues, many theoretical and practical solutions to the classification problem have been proposed under different security models. However, with the recent popularity of cloud computing, users now have the opportunity to outsource their data, in encrypted form, as well as the data mining tasks to the cloud. Since the data on the cloud is in encrypted form, existing privacy preserving classification techniques are not applicable. In this paper, we focus on solving the classification problem over encrypted data. In particular, we propose a secure k-NN classifier over encrypted data in the cloud. The proposed k-NN protocol protects the confidentiality of the data, user's input query, and data access patterns. To the best of our knowledge, our work is the first to develop a secure k-NN classifier over encrypted data under the semi-honest model. Also, we empirically analyze the efficiency of our solution through various experiments.
On Throughput-Delay Optimal Access to Storage Clouds via Load Adaptive Coding and Chunking
Venue: arXiv cs.NI 2014
Year: 2014

Recent literature including our past work provide analysis and solutions for using (i) erasure coding, (ii) parallelism, or (iii) variable slicing/chunking (i.e., dividing an object of a specific size into a variable number of smaller chunks) in speeding the I/O performance of storage clouds. However, a comprehensive approach that considers all three dimensions together to achieve the best throughput-delay trade-off curve had been lacking. This paper presents the first set of solutions that can pick the best combination of coding rate and object chunking/slicing options as the load dynamically changes. Our specific contributions are as follows: (1) We establish via measurement that combining variable coding rate and chunking is mostly feasible over a popular public cloud. (2) We relate the delay optimal values for chunking level and code rate to the queue backlogs via an approximate queueing analysis. (3) Based on this analysis, we propose TOFEC that adapts the chunking level and coding rate against the queue backlogs. Our trace-driven simulation results show that TOFEC's adaptation mechanism converges to an appropriate code that provides the optimal throughput-delay trade-off without reducing system capacity. Compared to a non-adaptive strategy optimized for throughput, TOFEC delivers $2.5\times$ lower latency under light workloads; compared to a non-adaptive strategy optimized for latency, TOFEC can scale to support over $3\times$ as many requests. (4) We propose a simpler greedy solution that performs on a par with TOFEC in average delay performance, but exhibits significantly more performance variations.
A Physarum-Inspired Approach to Optimal Supply Chain Network Design at Minimum Total Cost with Demand Satisfaction
Venue: arXiv cs.NE 2014
Year: 2014

A supply chain is a system which moves products from a supplier to customers. The supply chains are ubiquitous. They play a key role in all economic activities. Inspired by biological principles of nutrients' distribution in protoplasmic networks of slime mould Physarum polycephalum we propose a novel algorithm for a supply chain design. The algorithm handles the supply networks where capacity investments and product flows are variables. The networks are constrained by a need to satisfy product demands. Two features of the slime mould are adopted in our algorithm. The first is the continuity of a flux during the iterative process, which is used in real-time update of the costs associated with the supply links. The second feature is adaptivity. The supply chain can converge to an equilibrium state when costs are changed. Practicality and flexibility of our algorithm is illustrated on numerical examples.
(α, k)-Minimal Sorting and Skew Join in MPI and MapReduce
Venue: arXiv cs.DB 2014
Year: 2014

As computer clusters are found to be highly effective for handling massive datasets, the design of efficient parallel algorithms for such a computing model is of great interest. We consider (α, k)-minimal algorithms for such a purpose, where α is the number of rounds in the algorithm, and k is a bound on the deviation from perfect workload balance. We focus on new (α, k)-minimal algorithms for sorting and skew equijoin operations for computer clusters. To the best of our knowledge the proposed sorting and skew join algorithms achieve the best workload balancing guarantee when compared to previous works. Our empirical study shows that they are close to optimal in workload balancing. In particular, our proposed sorting algorithm is around 25% more efficient than the state-of-the-art Terasort algorithm and achieves significantly more even workload distribution by over 50%.
Image Fusion Techniques in Remote Sensing
Venue: arXiv cs.CV 2014
Year: 2014

Remote sensing image fusion is an effective way to use a large volume of data from multisensor images. Most earth satellites such as SPOT, Landsat 7, IKONOS and QuickBird provide both panchromatic (Pan) images at a higher spatial resolution and multispectral (MS) images at a lower spatial resolution and many remote sensing applications require both high spatial and high spectral resolutions, especially for GIS based applications. An effective image fusion technique can produce such remotely sensed images. Image fusion is the combination of two or more different images to form a new image by using a certain algorithm to obtain more and better information about an object or a study area than. The image fusion is performed at three different processing levels which are pixel level, feature level and decision level according to the stage at which the fusion takes place. There are many image fusion methods that can be used to produce high resolution multispectral images from a high resolution pan image and low resolution multispectral images. This paper explores the major remote sensing data fusion techniques at pixel level and reviews the concept, principals, limitations and advantages for each technique. This paper focused on traditional techniques like intensity hue-saturation- (HIS), Brovey, principal component analysis (PCA) and Wavelet.
Missing Data Prediction and Classification: The Use of Auto-Associative Neural Networks and Optimization Algorithms
Venue: arXiv cs.NE 2014
Year: 2014

This paper presents methods which are aimed at finding approximations to missing data in a dataset by using optimization algorithms to optimize the network parameters after which prediction and classification tasks can be performed. The optimization methods that are considered are genetic algorithm (GA), simulated annealing (SA), particle swarm optimization (PSO), random forest (RF) and negative selection (NS) and these methods are individually used in combination with auto-associative neural networks (AANN) for missing data estimation and the results obtained are compared. The methods suggested use the optimization algorithms to minimize an error function derived from training the auto-associative neural network during which the interrelationships between the inputs and the outputs are obtained and stored in the weights connecting the different layers of the network. The error function is expressed as the square of the difference between the actual observations and predicted values from an auto-associative neural network. In the event of missing data, all the values of the actual observations are not known hence, the error function is decomposed to depend on the known and unknown variable values. Multi-layer perceptron (MLP) neural network is employed to train the neural networks using the scaled conjugate gradient (SCG) method. Prediction accuracy is determined by mean squared error (MSE), root mean squared error (RMSE), mean absolute error (MAE), and correlation coefficient (r) computations. Accuracy in classification is obtained by plotting ROC curves and calculating the areas under these. Analysis of results depicts that the approach using RF with AANN produces the most accurate predictions and classifications while on the other end of the scale is the approach which entails using NS with AANN.
On the Outage Capacity of Orthogonal Space-time Block Codes Over Multi-cluster Scattering MIMO Channels
Venue: arXiv cs.IT 2014
Year: 2014

Multiple cluster scattering MIMO channel is a useful model for pico-cellular MIMO networks. In this paper, orthogonal space-time block coded transmission over such a channel is considered, where the effective channel equals the product of n complex Gaussian matrices. A simple and accurate closed-form approximation to the channel outage capacity has been derived in this setting. The result is valid for an arbitrary number of clusters n-1 of scatterers and an arbitrary antenna configuration. Numerical results are provided to study the relative outage performance between the multi-cluster and the Rayleigh-fading MIMO channels for which n=1.
A Lemma Based Evaluator for Semitic Language Text Summarization Systems
Venue: arXiv cs.CL 2014
Year: 2014

Matching texts in highly inflected languages such as Arabic by simple stemming strategy is unlikely to perform well. In this paper, we present a strategy for automatic text matching technique for for inflectional languages, using Arabic as the test case. The system is an extension of ROUGE test in which texts are matched on token's lemma level. The experimental results show an enhancement of detecting similarities between different sentences having same semantics but written in different lexical forms..
Forecasting Popularity of Videos using Social Media
Venue: arXiv cs.LG 2014
Year: 2014

This paper presents a systematic online prediction method (Social-Forecast) that is capable to accurately forecast the popularity of videos promoted by social media. Social-Forecast explicitly considers the dynamically changing and evolving propagation patterns of videos in social media when making popularity forecasts, thereby being situation and context aware. Social-Forecast aims to maximize the forecast reward, which is defined as a tradeoff between the popularity prediction accuracy and the timeliness with which a prediction is issued. The forecasting is performed online and requires no training phase or a priori knowledge. We analytically bound the prediction performance loss of Social-Forecast as compared to that obtained by an omniscient oracle and prove that the bound is sublinear in the number of video arrivals, thereby guaranteeing its short-term performance as well as its asymptotic convergence to the optimal performance. In addition, we conduct extensive experiments using real-world data traces collected from the videos shared in RenRen, one of the largest online social networks in China. These experiments show that our proposed method outperforms existing view-based approaches for popularity prediction (which are not context-aware) by more than 30% in terms of prediction rewards.
Transaction Repair: Full Serializability Without Locks
Venue: arXiv cs.DB 2014
Year: 2014

Transaction Repair is a method for lock-free, scalable transaction processing that achieves full serializability. It demonstrates parallel speedup even in inimical scenarios where all pairs of transactions have significant read-write conflicts. In the transaction repair approach, each transaction runs in complete isolation in a branch of the database; when conflicts occur, we detect and repair them. These repairs are performed efficiently in parallel, and the net effect is that of serial processing. Within transactions, we use no locks. This frees users from the complications and performance hazards of locks, and from the anomalies of sub-SERIALIZABLE isolation levels. Our approach builds on an incrementalized variant of leapfrog triejoin, a worst-case optimal algorithm for $\exists_1$ formulae, and on well-established techniques from programming languages: declarative languages, purely functional data structures, incremental computation, and fixpoint equations.
Synchronizing weighted automata
Venue: arXiv cs.FL 2014
Year: 2014

We introduce two generalizations of synchronizability to automata with transitions weighted in an arbitrary semiring K=(K,+,*,0,1). (or equivalently, to finite sets of matrices in K^nxn.) Let us call a matrix A location-synchronizing if there exists a column in A consisting of nonzero entries such that all the other columns of A are filled by zeros. If additionally all the entries of this designated column are the same, we call A synchronizing. Note that these notions coincide for stochastic matrices and also in the Boolean semiring. A set M of matrices in K^nxn is called (location-)synchronizing if M generates a matrix subsemigroup containing a (location-)synchronizing matrix. The K-(location-)synchronizability problem is the following: given a finite set M of nxn matrices with entries in K, is it (location-)synchronizing? Both problems are PSPACE-hard for any nontrivial semiring. We give sufficient conditions for the semiring K when the problems are PSPACE-complete and show several undecidability results as well, e.g. synchronizability is undecidable if 1 has infinite order in (K,+,0) or when the free semigroup on two generators can be embedded into (K,*,1).
Optimizing Your Online-Advertisement Asynchronously
Venue: arXiv cs.SY 2014
Year: 2014

We consider the problem of designing optimal online-ad investment strategies for a single advertiser, who invests at multiple sponsored search sites simultaneously, with the objective of maximizing his average revenue subject to the advertising budget constraint. A greedy online investment scheme is developed to achieve an average revenue that can be pushed to within $O(ε)$ of the optimal, for any $ε>0$, with a tradeoff that the temporal budget violation is $O(1/ε)$. Different from many existing algorithms, our scheme allows the advertiser to \emph{asynchronously} update his investments on each search engine site, hence applies to systems where the timescales of action update intervals are heterogeneous for different sites. We also quantify the impact of inaccurate estimation of the system dynamics and show that the algorithm is robust against imperfect system knowledge.
$L$-Primitive Words in Submonoids
Venue: arXiv cs.FL 2014
Year: 2014

This work considers a natural generalization of primitivity with respect to a language. Given a language $L$, a nonempty word $w$ is said to be $L$-primitive if $w$ is not a proper power of any word in $L$. After ascertaining the number of primitive words in submonoids of a free monoid, the work proceeds to count $L$-primitive words in submonoids of a free monoid. The work also studies the distribution of $L$-primitive words in certain subsets of free monoids.
Self-stabilizing uncoupled dynamics
Venue: arXiv cs.GT 2014
Year: 2014

Dynamics in a distributed system are self-stabilizing if they are guaranteed to reach a stable state regardless of how the system is initialized. Game dynamics are uncoupled if each player's behavior is independent of the other players' preferences. Recognizing an equilibrium in this setting is a distributed computational task. Self-stabilizing uncoupled dynamics, then, have both resilience to arbitrary initial states and distribution of knowledge. We study these dynamics by analyzing their behavior in a bounded-recall synchronous environment. We determine, for every "size" of game, the minimum number of periods of play that stochastic (randomized) players must recall in order for uncoupled dynamics to be self-stabilizing. We also do this for the special case when the game is guaranteed to have unique best replies. For deterministic players, we demonstrate two self-stabilizing uncoupled protocols. One applies to all games and uses three steps of recall. The other uses two steps of recall and applies to games where each player has at least four available actions. For uncoupled deterministic players, we prove that a single step of recall is insufficient to achieve self-stabilization, regardless of the number of available actions.
Heterogeneous epidemic model for assessing data dissemination in opportunistic networks
Venue: arXiv cs.SI 2014
Year: 2014

In this paper we investigate a susceptible-infected-susceptible (SIS) epidemic model describing data dissemination in opportunistic networks with heterogeneous setting of transmission parameters. We obtained the estimation of the final epidemic size assuming that amount of data transferred between network nodes possesses a Pareto distribution, implying scale-free properties. In this context, more heterogeneity in susceptibility means the less severe epidemic progression, and, on the contrary, more heterogeneity in infectivity leads to more severe epidemics -- assuming that the other parameter (either heterogeneity or susceptibility) stays fixed. The results are general enough and can be useful in general epidemic theory for estimating the epidemic progression for diseases with no significant acquired immunity -- in the cases where Pareto distribution holds.
The state of play of ASC-Inclusion: An Integrated Internet-Based Environment for Social Inclusion of Children with Autism Spectrum Conditions
Venue: arXiv cs.HC 2014
Year: 2014

Individuals with Autism Spectrum Conditions (ASC) have marked difficulties using verbal and non-verbal communication for social interaction. The running ASC-Inclusion project aims to help children with ASC by allowing them to learn how emotions can be expressed and recognised via playing games in a virtual world. The platform includes analysis of users' gestures, facial, and vocal expressions using standard microphone and web-cam or a depth sensor, training through games, text communication with peers, animation, video and audio clips. We present the state of play in realising such a serious game platform and provide results for the different modalities.
Computer-Aided Discovery and Categorisation of Personality Axioms
Venue: arXiv cs.CE 2014
Year: 2014

We propose a computer-algebraic, order-theoretic framework based on intuitionistic logic for the computer-aided discovery of personality axioms from personality-test data and their mathematical categorisation into formal personality theories in the spirit of F.~Klein's Erlanger Programm for geometrical theories. As a result, formal personality theories can be automatically generated, diagrammatically visualised, and mathematically characterised in terms of categories of invariant-preserving transformations in the sense of Klein and category theory. Our personality theories and categories are induced by implicational invariants that are ground instances of intuitionistic implication, which we postulate as axioms. In our mindset, the essence of personality, and thus mental health and illness, is its invariance. The truth of these axioms is algorithmically extracted from histories of partially-ordered, symbolic data of observed behaviour. The personality-test data and the personality theories are related by a Galois-connection in our framework. As data format, we adopt the format of the symbolic values generated by the Szondi-test, a personality test based on L.~Szondi's unifying, depth-psychological theory of fate analysis.
Monoid automata for displacement context-free languages
Venue: arXiv cs.FL 2014
Year: 2014

In 2007 Kambites presented an algebraic interpretation of Chomsky-Schutzenberger theorem for context-free languages. We give an interpretation of the corresponding theorem for the class of displacement context-free languages which are equivalent to well-nested multiple context-free languages. We also obtain a characterization of k-displacement context-free languages in terms of monoid automata and show how such automata can be simulated on two stacks. We introduce the simultaneous two-stack automata and compare different variants of its definition. All the definitions considered are shown to be equivalent basing on the geometric interpretation of memory operations of these automata.
Collaborative Verification-Driven Engineering of Hybrid Systems
Venue: arXiv cs.LO 2014
Year: 2014

Hybrid systems with both discrete and continuous dynamics are an important model for real-world cyber-physical systems. The key challenge is to ensure their correct functioning w.r.t. safety requirements. Promising techniques to ensure safety seem to be model-driven engineering to develop hybrid systems in a well-defined and traceable manner, and formal verification to prove their correctness. Their combination forms the vision of verification-driven engineering. Often, hybrid systems are rather complex in that they require expertise from many domains (e.g., robotics, control systems, computer science, software engineering, and mechanical engineering). Moreover, despite the remarkable progress in automating formal verification of hybrid systems, the construction of proofs of complex systems often requires nontrivial human guidance, since hybrid systems verification tools solve undecidable problems. It is, thus, not uncommon for development and verification teams to consist of many players with diverse expertise. This paper introduces a verification-driven engineering toolset that extends our previous work on hybrid and arithmetic verification with tools for (i) graphical (UML) and textual modeling of hybrid systems, (ii) exchanging and comparing models and proofs, and (iii) managing verification tasks. This toolset makes it easier to tackle large-scale verification tasks.
A Pattern based methodology for evolution management in business process reuse
Venue: arXiv cs.SE 2014
Year: 2014

Today, there are Process-Aware Information Systems (PAIS) with a set of business process models which vary over time to meet the new requirements. In a competitive environment, the key challenge of enterprises is to reduce the cost and time of process design and application development. For this purpose, research on reuse in business process management have introduced the concept of configurable process models which attempts to manage business process variability, by integrating a set of process variants in a single model. In this context, many research works were interested in creating and elaborating configurable process models. However, this has become insufficient since the configurable process model should itself evolve to add new variations. In turn, this requires a comprehensive support for managing the evolution of configurable process models. In this paper, we present a complete pattern based methodology for managing the evolution of configurable process models in terms of activities, data and resources. Our objective is to propose a process patterns system for guiding designers in modeling and evolving configurable process models. Furthermore, our process patterns system will be used for an automated support so as to manage the evolution of configurable process models.