OpenRaiser/Intern-Atlas huggingface dataset:
Determination and (re)parametrization of rational developable surfaces
Venue: arXiv cs.SC 2013
Year: 2013

The developable surface is an important surface in computer aided design, geometric modeling and industrial manufactory. It is often given in the stan- dard parametric form, but it can also be in the implicit form which is commonly used in algebraic geometry. Not all algebraic developable surfaces have rational parametrizations. In this paper, we focus on the rational developable surfaces. For a given algebraic surface, we first determine whether it is developable by geometric inspection, and we give a rational proper parametrization for the af- firmative case. For a rational parametric surface, we can also determine the developability and give a proper reparametrization for the developable surface.
Strategic Planning for Network Data Analysis
Venue: arXiv cs.AI 2013
Year: 2013

As network traffic monitoring software for cybersecurity, malware detection, and other critical tasks becomes increasingly automated, the rate of alerts and supporting data gathered, as well as the complexity of the underlying model, regularly exceed human processing capabilities. Many of these applications require complex models and constituent rules in order to come up with decisions that influence the operation of entire systems. In this paper, we motivate the novel "strategic planning" problem -- one of gathering data from the world and applying the underlying model of the domain in order to come up with decisions that will monitor the system in an automated manner. We describe our use of automated planning methods to this problem, including the technique that we used to solve it in a manner that would scale to the demands of a real-time, real world scenario. We then present a PDDL model of one such application scenario related to network administration and monitoring, followed by a description of a novel integrated system that was built to accept generated plans and to continue the execution process. Finally, we present evaluations of two different automated planners and their different capabilities with our integrated system, both on a six-month window of network data, and using a simulator.
Cloud Computing Benefits for Educational Institutions
Venue: arXiv cs.CY 2013
Year: 2013

Education today is becoming completely associated with the Information Technology on the content delivery, communication and collaboration. The need for servers, storage and software are highly demanding in the universities, colleges and schools. Cloud Computing is an Internet based computing, whereby shared resources, software and information, are provided to computers and devices on-demand, like the electricity grid. Currently, IaaS (Infrastructure as a Service), PaaS (Platform as a Service) and SaaS (Software as a Service) are used as business model for Cloud Computing. The paper also introduces the cloud computing infrastructure provided by Microsoft, Google and Amazon Web Service. In this paper we will review the features the educational institutions can use from the cloud computing providers to increase the benefits of students and teachers.
Fibonacci Graphs and their Expressions
Venue: arXiv cs.DS 2013
Year: 2013

The paper investigates relationship between algebraic expressions and graphs. We consider a digraph called a Fibonacci graph which gives a generic example of non-series-parallel graphs. Our intention in this paper is to simplify the expressions of Fibonacci graphs and eventually find their shortest representations. With that end in view, we describe the number of methods for generating Fibonacci graph expressions and carry out their comparative analysis.
A Heuristic Approach for Web-Service Discovery and Selection
Venue: arXiv cs.DC 2013
Year: 2013

In today's businesses, service-oriented architectures represent the main paradigm for IT infrastructures. Indeed, the emergence of Internet made it possible to set up an exploitable environment to distribute applications on a large scale, and this, by adapting the notion of "service". With the integration of this paradigm in Business to Business Domain (B2B), the number of web services becomes very significant. Due to this increase, the discovery and selection of web services meeting customer requirement become a very difficult operation. Further, QoS properties must be taking into account in the web service selection. Moreover, with the significant number of web service, necessary time for the discovery of a service will be rather long. In this paper, we propose an approach based on a new heuristic method called "Bees Algorithm" inspired from honey bees behavior. We use this technique of optimization in order to discover appropriate web services, meeting customer requirements, in least time and taking into account the QoS properties.
Using Page Size for Controlling Duplicate Query Results in Semantic Web
Venue: arXiv cs.DB 2013
Year: 2013

Semantic web is a web of future. The Resource Description Framework (RDF) is a language to represent resources in the World Wide Web. When these resources are queried the problem of duplicate query results occurs. The present techniques used hash index comparison to remove duplicate query results. The major drawback of using the hash index to remove duplicate query results is that, if there is a slight change in formatting or word order, then hash index is changed and query results are no more considered as duplicate even though they have same contents. We presented an algorithm for detection and elimination of duplicate query results from semantic web using hash index and page size comparisons. Experimental results showed that the proposed technique removed duplicate query results from semantic web efficiently, solved the problems of using hash index for duplicate handling and could be embedded in existing SQL-Based query system for semantic web. Research could be carried out for certain flexibilities in existing SQL-Based query system of semantic web to accommodate other duplicate detection techniques as well.
Human Mood Detection For Human Computer Interaction
Venue: arXiv cs.CV 2013
Year: 2013

In this paper we propose an easiest approach for facial expression recognition. Here we are using concept of SVM for Expression Classification. Main problem is sub divided in three main modules. First one is Face detection in which we are using skin filter and Face segmentation. We are given more stress on feature Extraction. This method is effective enough for application where fast execution is required. Second, Facial Feature Extraction which is essential part for expression recognition. In this module we used Edge Projection Analysis. Finally extracted features vector is passed towards SVM classifier for Expression Recognition. We are considering six basic Expressions (Anger, Fear, Disgust, Joy, Sadness, and Surprise)
Dynamic Top-$k$ Dominating Queries
Venue: arXiv cs.CG 2013
Year: 2013

Let $\mathcal{S}$ be a dataset of $n$ 2-dimensional points. The top-$k$ dominating query aims to report the $k$ points that dominate the most points in $\mathcal{S}$. A point $p$ dominates a point $q$ iff all coordinates of $p$ are smaller than or equal to those of $q$ and at least one of them is strictly smaller. The top-$k$ dominating query combines the dominance concept of maxima queries with the ranking function of top-$k$ queries and can be used as an important tool in multi-criteria decision making systems. In this work, we propose novel algorithms for answering semi-dynamic (insertions only) and fully dynamic (insertions and deletions) top-$k$ dominating queries. To the best of our knowledge, this is the first work towards handling (semi-)dynamic top-$k$ dominating queries that offers algorithms with asymptotic guarantees regarding their time and space cost.
Evolution of Cooperation in an Incentive Based Business Game Environment
Venue: arXiv cs.CY 2013
Year: 2013

This paper discusses our investigation into the evolution of cooperative players in an online business environment. We explain our design of an incentive based system with its foundation over binary reputation system whose proportion of reward or punishment is a function of transaction value and the players past history of cooperation. We compare the evolution of cooperation in our setting with non-incentive based environment and our findings show that the incentive based method is more suitable for the evolution of trustworthy players.
Weighted Approach to General Entropy Function
Venue: arXiv cs.IT 2013
Year: 2013

The definition of weighted entropy allows for easy calculation of the entropy of the mixture of measures. In this paper we investigate the problem of equivalent definition of the general entropy function in weighted form. We show that under reasonable condition, which is satisfied by the well-known Shannon, Rényi and Tsallis entropies, every entropy function can be defined equivalently in the weighted way. As a corollary, we show how use the weighted form to compute Tsallis entropy of the mixture of measures.
The Degrees of Freedom of the MIMO Y-channel
Venue: arXiv cs.IT 2013
Year: 2013

The degrees of freedom (DoF) of the MIMO Y-channel, a multi-way communication network consisting of 3 users and a relay, are characterized for arbitrary number of antennas. The converse is provided by cut-set bounds and novel genie-aided bounds. The achievability is shown by a scheme that uses beamforming to establish network coding on-the-fly at the relay in the uplink, and zero-forcing pre-coding in the downlink. It is shown that the network has min{2M_2+2M_3,M_1+M_2+M_3,2N} DoF, where M_j and N represent the number of antennas at user j and the relay, respectively. Thus, in the extreme case where M_1+M_2+M_3 dominates the DoF expression and is smaller than N, the network has the same DoF as the MAC between the 3 users and the relay. In this case, a decode and forward strategy is optimal. In the other extreme where 2N dominates, the DoF of the network is twice that of the aforementioned MAC, and hence network coding is necessary. As a byproduct of this work, it is shown that channel output feedback from the relay to the users has no impact on the DoF of this channel.
Rule-Based Application Development using Webdamlog
Venue: arXiv cs.DB 2013
Year: 2013

We present the WebdamLog system for managing distributed data on the Web in a peer-to-peer manner. We demonstrate the main features of the system through an application called Wepic for sharing pictures between attendees of the sigmod conference. Using Wepic, the attendees will be able to share, download, rate and annotate pictures in a highly decentralized manner. We show how WebdamLog handles heterogeneity of the devices and services used to share data in such a Web setting. We exhibit the simple rules that define the Wepic application and show how to easily modify the Wepic application.
Mining Frequent Neighborhood Patterns in Large Labeled Graphs
Venue: arXiv cs.DB 2013
Year: 2013

Over the years, frequent subgraphs have been an important sort of targeted patterns in the pattern mining literatures, where most works deal with databases holding a number of graph transactions, e.g., chemical structures of compounds. These methods rely heavily on the downward-closure property (DCP) of the support measure to ensure an efficient pruning of the candidate patterns. When switching to the emerging scenario of single-graph databases such as Google Knowledge Graph and Facebook social graph, the traditional support measure turns out to be trivial (either 0 or 1). However, to the best of our knowledge, all attempts to redefine a single-graph support resulted in measures that either lose DCP, or are no longer semantically intuitive. This paper targets mining patterns in the single-graph setting. We resolve the "DCP-intuitiveness" dilemma by shifting the mining target from frequent subgraphs to frequent neighborhoods. A neighborhood is a specific topological pattern where a vertex is embedded, and the pattern is frequent if it is shared by a large portion (above a given threshold) of vertices. We show that the new patterns not only maintain DCP, but also have equally significant semantics as subgraph patterns. Experiments on real-life datasets display the feasibility of our algorithms on relatively large graphs, as well as the capability of mining interesting knowledge that is not discovered in prior works.
SECA: Snapshot-based Event Detection for Checking Asynchronous Context Consistency in Ubiquitous Computing
Venue: arXiv cs.DC 2013
Year: 2013

Context-consistency checking is challenging in the dynamic and uncertain ubiquitous computing environments. This is because contexts are often noisy owing to unreliable sensing data streams, inaccurate data measurement, fragile connectivity and resource constraints. One of the state-of-the-art efforts is CEDA, which concurrently detects context consistency by exploring the \emph{happened-before} relation among events. However, CEDA is seriously limited by several side effects --- centralized detection manner that easily gets down the checker process, heavy computing complexity and false negative. In this paper, we propose SECA: Snapshot-based Event Detection for Checking Asynchronous Context Consistency in ubiquitous computing. SECA introduces snapshot-based timestamp to check event relations, which can detect scenarios where CEDA fails. Moreover, it simplifies the logical clock instead of adopting the vector clock, and thus significantly reduces both time and space complexity. Empirical studies show that SECA outperforms CEDA in terms of detection accuracy, scalability, and computing complexity.
I Wish I Didn't Say That! Analyzing and Predicting Deleted Messages in Twitter
Venue: arXiv cs.SI 2013
Year: 2013

Twitter has become a major source of data for social media researchers. One important aspect of Twitter not previously considered are {\em deletions} -- removal of tweets from the stream. Deletions can be due to a multitude of reasons such as privacy concerns, rashness or attempts to undo public statements. We show how deletions can be automatically predicted ahead of time and analyse which tweets are likely to be deleted and how.
Refinement in the Tableau Synthesis Framework
Venue: arXiv cs.LO 2013
Year: 2013

This paper is concerned with the possibilities of refining and improving calculi generated in the tableau synthesis framework. A general method in the tableau synthesis framework allows to reduce the branching factor of tableau rules and preserves completeness if a general rule refinement condition holds. In this paper we consider two approaches to satisfy this general rule refinement condition.
Qualitative detection of oil adulteration with machine learning approaches
Venue: arXiv cs.CE 2013
Year: 2013

The study focused on the machine learning analysis approaches to identify the adulteration of 9 kinds of edible oil qualitatively and answered the following three questions: Is the oil sample adulterant? How does it constitute? What is the main ingredient of the adulteration oil? After extracting the high-performance liquid chromatography (HPLC) data on triglyceride from 370 oil samples, we applied the adaptive boosting with multi-class Hamming loss (AdaBoost.MH) to distinguish the oil adulteration in contrast with the support vector machine (SVM). Further, we regarded the adulterant oil and the pure oil samples as ones with multiple labels and with only one label, respectively. Then multi-label AdaBoost.MH and multi-label learning vector quantization (ML-LVQ) model were built to determine the ingredients and their relative ratio in the adulteration oil. The experimental results on six measures show that ML-LVQ achieves better performance than multi-label AdaBoost.MH.
Heaviest Induced Ancestors and Longest Common Substrings
Venue: arXiv cs.DS 2013
Year: 2013

Suppose we have two trees on the same set of leaves, in which nodes are weighted such that children are heavier than their parents. We say a node from the first tree and a node from the second tree are induced together if they have a common leaf descendant. In this paper we describe data structures that efficiently support the following heaviest-induced-ancestor query: given a node from the first tree and a node from the second tree, find an induced pair of their ancestors with maximum combined weight. Our solutions are based on a geometric interpretation that enables us to find heaviest induced ancestors using range queries. We then show how to use these results to build an LZ-compressed index with which we can quickly find with high probability a longest substring common to the indexed string and a given pattern.
Efficient Density Estimation via Piecewise Polynomial Approximation
Venue: arXiv cs.LG 2013
Year: 2013

We give a highly efficient "semi-agnostic" algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let $p$ be an arbitrary distribution over an interval $I$ which is $τ$-close (in total variation distance) to an unknown probability distribution $q$ that is defined by an unknown partition of $I$ into $t$ intervals and $t$ unknown degree-$d$ polynomials specifying $q$ over each of the intervals. We give an algorithm that draws $\tilde{O}(t\new{(d+1)}/\eps^2)$ samples from $p$, runs in time $\poly(t,d,1/\eps)$, and with high probability outputs a piecewise polynomial hypothesis distribution $h$ that is $(O(τ)+\eps)$-close (in total variation distance) to $p$. This sample complexity is essentially optimal; we show that even for $τ=0$, any algorithm that learns an unknown $t$-piecewise degree-$d$ probability distribution over $I$ to accuracy $\eps$ must use $Ω({\frac {t(d+1)} {\poly(1 + \log(d+1))}} \cdot {\frac 1 {\eps^2}})$ samples from the distribution, regardless of its running time. Our algorithm combines tools from approximation theory, uniform convergence, linear programming, and dynamic programming. We apply this general algorithm to obtain a wide range of results for many natural problems in density estimation over both continuous and discrete domains. These include state-of-the-art results for learning mixtures of log-concave distributions; mixtures of $t$-modal distributions; mixtures of Monotone Hazard Rate distributions; mixtures of Poisson Binomial Distributions; mixtures of Gaussians; and mixtures of $k$-monotone densities. Our general technique yields computationally efficient algorithms for all these problems, in many cases with provably optimal sample complexities (up to logarithmic factors) in all parameters.
Update-Efficiency and Local Repairability Limits for Capacity Approaching Codes
Venue: arXiv cs.IT 2013
Year: 2013

Motivated by distributed storage applications, we investigate the degree to which capacity achieving encodings can be efficiently updated when a single information bit changes, and the degree to which such encodings can be efficiently (i.e., locally) repaired when single encoded bit is lost. Specifically, we first develop conditions under which optimum error-correction and update-efficiency are possible, and establish that the number of encoded bits that must change in response to a change in a single information bit must scale logarithmically in the block-length of the code if we are to achieve any nontrivial rate with vanishing probability of error over the binary erasure or binary symmetric channels. Moreover, we show there exist capacity-achieving codes with this scaling. With respect to local repairability, we develop tight upper and lower bounds on the number of remaining encoded bits that are needed to recover a single lost bit of the encoding. In particular, we show that if the code-rate is $ε$ less than the capacity, then for optimal codes, the maximum number of codeword symbols required to recover one lost symbol must scale as $\log1/ε$. Several variations on---and extensions of---these results are also developed.
Strategy-Proof Facility Location for Concave Cost Functions
Venue: arXiv cs.GT 2013
Year: 2013

We consider k-Facility Location games, where n strategic agents report their locations on the real line, and a mechanism maps them to k facilities. Each agent seeks to minimize his connection cost, given by a nonnegative increasing function of his distance to the nearest facility. Departing from previous work, that mostly considers the identity cost function, we are interested in mechanisms without payments that are (group) strategyproof for any given cost function, and achieve a good approximation ratio for the social cost and/or the maximum cost of the agents. We present a randomized mechanism, called Equal Cost, which is group strategyproof and achieves a bounded approximation ratio for all k and n, for any given concave cost function. The approximation ratio is at most 2 for Max Cost and at most n for Social Cost. To the best of our knowledge, this is the first mechanism with a bounded approximation ratio for instances with k > 2 facilities and any number of agents. Our result implies an interesting separation between deterministic mechanisms, whose approximation ratio for Max Cost jumps from 2 to unbounded when k increases from 2 to 3, and randomized mechanisms, whose approximation ratio remains at most 2 for all k. On the negative side, we exclude the possibility of a mechanism with the properties of Equal Cost for strictly convex cost functions. We also present a randomized mechanism, called Pick the Loser, which applies to instances with k facilities and n = k+1 agents, and for any given concave cost function, is strongly group strategyproof and achieves an approximation ratio of 2 for Social Cost.
The Empirical Implications of Rank in Bimatrix Games
Venue: arXiv cs.GT 2013
Year: 2013

We study the structural complexity of bimatrix games, formalized via rank, from an empirical perspective. We consider a setting where we have data on player behavior in diverse strategic situations, but where we do not observe the relevant payoff functions. We prove that high complexity (high rank) has empirical consequences when arbitrary data is considered. Additionally, we prove that, in more restrictive classes of data (termed laminar), any observation is rationalizable using a low-rank game: specifically a zero-sum game. Hence complexity as a structural property of a game is not always testable. Finally, we prove a general result connecting the structure of the feasible data sets with the highest rank that may be needed to rationalize a set of observations.
An Efficient Method for Optimizing RFID Reader Deployment and Energy Saving
Venue: arXiv cs.NI 2013
Year: 2013

The rapid proliferation of Radio Frequency IDentification (RFID) systems realizes integration of physical world with the cyber ones. One of the most promising is the Internet of Things (IoT), a vision in which the Internet extends into our daily activities through wireless networks of uniquely identifiable objects. Given that modern RFID systems are being deployed in large-scale for different applications, without optimizing reader's distribution, many of the readers will be redundant, resulting waste of energy. Additionally, eliminating redundant eaders can also decrease probability of reader collisions, as a result, enhancing system performance and efficiency. In this paper, an overlap aware (OA) technique is proposed for eliminating redundant readers. The OA is a distributed approach, which does not need to collect global information for centralizing control, aims to detect maximum amount of redundant readers could be safely removed or turned off with preserving original RFID network coverage. A significant improvement of the OA scheme is that the amount of "write-to-tag" operations could be largely reduced during the redundant reader identification phase. In order to accurately evaluate the performance of the proposed method, it was performed in a variety of scenarios. The experiment results show that the proposed method can provide reliable performance with detecting higher redundancy and has lower algorithm overheads as compared with several well known methods, such as the RRE, LEO, the hybrid algorithm (LEO+RRE) and the DRRE.