OpenRaiser/Intern-Atlas huggingface dataset:
Skew Strikes Back: New Developments in the Theory of Join Algorithms
Venue: arXiv cs.DB 2013
Year: 2013

Evaluating the relational join is one of the central algorithmic and most well-studied problems in database systems. A staggering number of variants have been considered including Block-Nested loop join, Hash-Join, Grace, Sort-merge for discussions of more modern issues). Commercial database engines use finely tuned join heuristics that take into account a wide variety of factors including the selectivity of various predicates, memory, IO, etc. In spite of this study of join queries, the textbook description of join processing is suboptimal. This survey describes recent results on join algorithms that have provable worst-case optimality runtime guarantees. We survey recent work and provide a simpler and unified description of these algorithms that we hope is useful for theory-minded readers, algorithm designers, and systems implementors.
PCG-Cut: Graph Driven Segmentation of the Prostate Central Gland
Venue: arXiv cs.CV 2013
Year: 2013

Prostate cancer is the most abundant cancer in men, with over 200,000 expected new cases and around 28,000 deaths in 2012 in the US alone. In this study, the segmentation results for the prostate central gland (PCG) in MR scans are presented. The aim of this research study is to apply a graph-based algorithm to automated segmentation (i.e. delineation) of organ limits for the prostate central gland. The ultimate goal is to apply automated segmentation approach to facilitate efficient MR-guided biopsy and radiation treatment planning. The automated segmentation algorithm used is graph-driven based on a spherical template. Therefore, rays are sent through the surface points of a polyhedron to sample the graph's nodes. After graph construction - which only requires the center of the polyhedron defined by the user and located inside the prostate center gland - the minimal cost closed set on the graph is computed via a polynomial time s-t-cut, which results in the segmentation of the prostate center gland's boundaries and volume. The algorithm has been realized as a C++ modul within the medical research platform MeVisLab and the ground truth of the central gland boundaries were manually extracted by clinical experts (interventional radiologists) with several years of experience in prostate treatment. For evaluation the automated segmentations of the proposed scheme have been compared with the manual segmentations, yielding an average Dice Similarity Coefficient (DSC) of 78.94 +/- 10.85%.
A Domain-Specific Language for Discrete Mathematics
Venue: arXiv cs.PL 2013
Year: 2013

This paper discusses a Domain Specific Language (DSL) that has been developed to enable implementation of concepts of discrete mathematics. A library of data types and functions provides functionality which is frequently required by users. Covering the areas of Mathematical Logic, Set Theory, Functions, Graph Theory, Number Theory, Linear Algebra and Combinatorics, the language's syntax is close to the actual notation used in the specific fields.
Predicting Social Links for New Users across Aligned Heterogeneous Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

Online social networks have gained great success in recent years and many of them involve multiple kinds of nodes and complex relationships. Among these relationships, social links among users are of great importance. Many existing link prediction methods focus on predicting social links that will appear in the future among all users based upon a snapshot of the social network. In real-world social networks, many new users are joining in the service every day. Predicting links for new users are more important. Different from conventional link prediction problems, link prediction for new users are more challenging due to the following reasons: (1) differences in information distributions between new users and the existing active users (i.e., old users); (2) lack of information from the new users in the network. We propose a link prediction method called SCAN-PS (Supervised Cross Aligned Networks link prediction with Personalized Sampling), to solve the link prediction problem for new users with information transferred from both the existing active users in the target network and other source networks through aligned accounts. We proposed a within-target-network personalized sampling method to process the existing active users' information in order to accommodate the differences in information distributions before the intra-network knowledge transfer. SCAN-PS can also exploit information in other source networks, where the user accounts are aligned with the target network. In this way, SCAN-PS could solve the cold start problem when information of these new users is total absent in the target network.
New Ways to Promote Sustainability and Social Well-Being in a Complex, Strongly Interdependent World: The FuturICT Approach
Venue: arXiv cs.CY 2013
Year: 2013

FuturICT is one of six proposals currently being considered for support within the European Commission's Flagship Initiative (see Box 1). The vision of the FuturICT project is to develop new science and new information and communication systems that will promote social self-organization, self-regulation, well-being, sustainability, and resilience. One of the main aims of the approach is to increase individual opportunities for social, economic and political participation, combined with the creation of collective awareness of the impact that human actions have on our world. This requires us to mine large datasets ("Big Data") and to develop new methods and tools: a Planetary Nervous System (PNS) to answer "What is (the state of the world)..." questions, a Living Earth Simulator (LES) to study "What ... if ..." scenarios, and a Global Participatory Platform (GPP) for social exploration and interaction.
Forecasting of Events by Tweet Data Mining
Venue: arXiv cs.SI 2013
Year: 2013

This paper describes the analysis of quantitative characteristics of frequent sets and association rules in the posts of Twitter microblogs related to different event discussions. For the analysis, we used a theory of frequent sets, association rules and a theory of formal concept analysis. We revealed the frequent sets and association rules which characterize the semantic relations between the concepts of analyzed subjects. The support of some frequent sets reaches its global maximum before the expected event but with some time delay. Such frequent sets may be considered as predictive markers that characterize the significance of expected events for blogosphere users. We showed that the time dynamics of confidence in some revealed association rules can also have predictive characteristics. Exceeding a certain threshold may be a signal for corresponding reaction in the society within the time interval between the maximum and the probable coming of an event. In this paper, we considered two types of events: the Olympic tennis tournament final in London, 2012 and the prediction of Eurovision 2013 winner.
Watchdog-LEACH: A new method based on LEACH protocol to Secure Clustered Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Wireless sensor network comprises of small sensor nodes with limited resources. Clustered networks have been proposed in many researches to reduce the power consumption in sensor networks. LEACH is one of the most interested techniques that offer an efficient way to minimize the power consumption in sensor networks. However, due to the characteristics of restricted resources and operation in a hostile environment, WSNs are subjected to numerous threats and are vulnerable to attacks. This research proposes a solution that can be applied on LEACH to increase the level of security. In Watchdog-LEACH, some nodes are considered as watchdogs and some changes are applied on LEACH protocol for intrusion detection. Watchdog-LEACH is able to protect against a wide range of attacks and it provides security, energy efficiency and memory efficiency. The result of simulation shows that in comparison to LEACH, the energy overhead is about 2% so this method is practical and can be applied to WSNs.
Weak Bases of Boolean Co-Clones
Venue: arXiv cs.CC 2013
Year: 2013

Universal algebra and clone theory have proven to be a useful tool in the study of constraint satisfaction problems since the complexity, up to logspace reductions, is determined by the set of polymorphisms of the constraint language. For classifications where primitive positive definitions are unsuitable, such as size-preserving reductions, weaker closure operations may be necessary. In this article we consider strong partial clones which can be seen as a more fine-grained framework than Post's lattice where each clone splits into an interval of strong partial clones. We investigate these intervals and give simple relational descriptions, weak bases, of the largest elements. The weak bases have a highly regular form and are in many cases easily relatable to the smallest members in the intervals, which suggests that the lattice of strong partial clones is considerably simpler than the full lattice of partial clones.
Explicit schemes for parabolic and hyperbolic equations
Venue: arXiv cs.NA 2013
Year: 2013

Standard explicit schemes for parabolic equations are not very convenient for computing practice due to the fact that they have strong restrictions on a time step. More promising explicit schemes are associated with explicit-implicit splitting of the problem operator (Saul'yev asymmetric schemes, explicit alternating direction (ADE) schemes, group explicit method). These schemes belong to the class of unconditionally stable schemes, but they demonstrate bad approximation properties. These explicit schemes are treated as schemes of the alternating triangle method and can be considered as factorized schemes where the problem operator is splitted into the sum of two operators that are adjoint to each other. Here we propose a multilevel modification of the alternating triangle method, which demonstrates better properties in terms of accuracy. We also consider explicit schemes of the alternating triangle method for the numerical solution of boundary value problems for hyperbolic equations of second order. The study is based on the general theory of stability (well-posedness) for operator-difference schemes.
Context unification is in PSPACE
Venue: arXiv cs.LO 2013
Year: 2013

Contexts are terms with one `hole', i.e. a place in which we can substitute an argument. In context unification we are given an equation over terms with variables representing contexts and ask about the satisfiability of this equation. Context unification is a natural subvariant of second-order unification, which is undecidable, and a generalization of word equations, which are decidable, at the same time. It is the unique problem between those two whose decidability is uncertain (for already almost two decades). In this paper we show that the context unification is in PSPACE. The result holds under a (usual) assumption that the first-order signature is finite. This result is obtained by an extension of the recompression technique, recently developed by the author and used in particular to obtain a new PSPACE algorithm for satisfiability of word equations, to context unification. The recompression is based on performing simple compression rules (replacing pairs of neighbouring function symbols), which are (conceptually) applied on the solution of the context equation and modifying the equation in a way so that such compression steps can be in fact performed directly on the equation, without the knowledge of the actual solution.
The BeiHang Keystroke Dynamics Authentication System
Venue: arXiv cs.CR 2013
Year: 2013

Keystroke Dynamics is an important biometric solution for person authentication. Based upon keystroke dynamics, this paper designs an embedded password protection device, develops an online system, collects two public databases for promoting the research on keystroke authentication, exploits the Gabor filter bank to characterize keystroke dynamics, and provides benchmark results of three popular classification algorithms, one-class support vector machine, Gaussian classifier, and nearest neighbour classifier.
Multiple Attractor Cellular Automata (MACA) for Addressing Major Problems in Bioinformatics
Venue: arXiv cs.CE 2013
Year: 2013

CA has grown as potential classifier for addressing major problems in bioinformatics. Lot of bioinformatics problems like predicting the protein coding region, finding the promoter region, predicting the structure of protein and many other problems in bioinformatics can be addressed through Cellular Automata. Even though there are some prediction techniques addressing these problems, the approximate accuracy level is very less. An automated procedure was proposed with MACA (Multiple Attractor Cellular Automata) which can address all these problems. The genetic algorithm is also used to find rules with good fitness values. Extensive experiments are conducted for reporting the accuracy of the proposed tool. The average accuracy of MACA when tested with ENCODE, BG570, HMR195, Fickett and Tongue, ASP67 datasets is 78%.
A Dynamic Programming Solution to the Monotonic Path of Minimal Cost in a 3-Rows Matrix
Venue: arXiv cs.DS 2013
Year: 2013

We consider the problem of finding the path of minimal cost going from left to right in a 3-rows matrix, starting at the third row, and not going downwards, where there is an additional cost related to not changing rows, such that the higher the change in intensity within the row, the higher the cost of not moving upwards.
MAC-aware Routing Metrics for the Internet of Things
Venue: arXiv cs.NI 2013
Year: 2013

Wireless medium access control (MAC) and routing protocols are fundamental building blocks of the Internet of Things (IoT). As new IoT networking standards are being proposed and different existing solutions patched, evaluating the end-to-end performance of the network becomes challenging. Specific solutions designed to be beneficial, when stacked may have detrimental effects on the overall network performance. In this paper, an analysis of MAC and routing protocols for IoT is provided with focus on the IEEE 802.15.4 MAC and the IETF RPL standards. It is shown that existing routing metrics do not account for the complex interactions between MAC and routing, and thus novel metrics are proposed. This enables a protocol selection mechanism for selecting the routing option and adapting the MAC parameters, given specific performance constraints. Extensive analytical and experimental results show that the behavior of the MAC protocol can hurt the performance of the routing protocol and vice versa, unless these two are carefully optimized together by the proposed method.
Gruppen secret sharing, or, how to share several secrets if you must?
Venue: arXiv cs.CR 2013
Year: 2013

Each member of an $n$-person team has a secret, say a password. The $k$ out of $n$ gruppen secret sharing requires that any group of $k$ members should be able to recover the secrets of the other $n-k$ members, while any group of $k-1$ or less members should have no information on the secret of other team member even if other secrets leak out. We prove that when all secrets are chosen independently and have size $s$, then each team member must have a share of size at least $(n-k)s$, and we present a scheme which achieves this bound when $s$ is large enough. This result shows a significant saving over $n$ independent applications of Shamir's $k$ out of $n-1$ threshold schemes which assigns shares of size $(n-1)s$ to each team member independently of $k$. We also show how to set up such a scheme without any trusted dealer, and how the secrets can be recovered, possibly multiple times, without leaking information. We also discuss how our scheme fits to the much-investigated multiple secret sharing methods.
Price of Anarchy for Non-atomic Congestion Games with Stochastic Demands
Venue: arXiv cs.GT 2013
Year: 2013

We generalize the notions of user equilibrium and system optimum to non-atomic congestion games with stochastic demands. We establish upper bounds on the price of anarchy for three different settings of link cost functions and demand distributions, namely, (a) affine cost functions and general distributions, (b) polynomial cost functions and general positive-valued distributions, and (c) polynomial cost functions and the normal distributions. All the upper bounds are tight in some special cases, including the case of deterministic demands.
GV-Index:Scientific Contribution Rating Index That Takes into Account the Growth Degree of Research Area and Variance Values of the Publication Year of Cited Paper
Venue: arXiv cs.DL 2013
Year: 2013

There are a wide variety of scientific contribution rating indices including the impact factor and h-index. These are used for quantitative analyses on research papers published in the past, and therefore unable to incorporate in the assessment the growth, or deterioration, of the research area: whether the research area of a particular paper is in decline or conversely in a growing trend. Other hand, the use of the conventional rating indices may result in higher rates for papers that are hardly referenced nowadays in other papers although frequently cited in the past. This study proposes a new type of scientific contribution ranking index, "Growing Degree of Research Area and Variance Values Index (GV-Index)". The GV-Index is computed by a principal component analysis based on an estimated value obtained by PageRank Algorithm, which takes into account the growing degree of the research area and its variance. We also propose visualization system of a scientist's network using the GV-Index.
Dynamic Extraction of Key Paper from the Cluster Using Variance Values of Cited Literature
Venue: arXiv cs.DL 2013
Year: 2013

When looking into recent research trends in the field of academic landscape, citation network analysis is common and automated clustering of many academic papers has been achieved by making good use of various techniques. However, specifying the features of each area identified by automated clustering or dynamically extracted key papers in each research area has not yet been achieved. In this study, therefore, we propose a method for dynamically specifying the key papers in each area identified by clustering. We will investigate variance values of the publication year of the cited literature and calculate each cited paper's importance by applying the variance values to the PageRank algorithm.
Reducing Failure Probability of cloud storage services using Multi-Clouds
Venue: arXiv cs.DC 2013
Year: 2013

Any information is valuable as long as it has related data. If related data are not put together, the information is meaningless as unrelated data has no value. The mapped information is required only by authenticated users. So there is no necessity to store related information together. If the relations of a database are fragmented into chunks and these chunks are stored at different cloud service providers, it could prevent from any privacy breach and the data stored will be secure. It would also reduce the data transfer costs as the entire data is not always required, for e.g. during updates. Also, instead of storage of chunks at a single CSP, if each chunk or fragment is stored at multiple CSPs it ensures availability and also permits concurrent access. Additionally, it would prevent financial loss during cloud outages and also prevent data lock-in. Replicating data chunks at multiple clouds situated at geographically different locations would also have an additional decrease in response time. The work attempts to select multiple cloud service providers within a given budget so as to ensure maximum availability of data. The entire data can be stored at each of the data centers selected depending on the budget when there is no security or privacy issue. Data can also be stored in chunks by replicating each data chunk at two or more cloud service providers. Different chunks can be replicated at different service providers. The work also attempts to select various cloud service providers to ensure maximum valid data chunks within a given budget.
Thompson Sampling in Dynamic Systems for Contextual Bandit Problems
Venue: arXiv cs.LG 2013
Year: 2013

We consider the multiarm bandit problems in the timevarying dynamic system for rich structural features. For the nonlinear dynamic model, we propose the approximate inference for the posterior distributions based on Laplace Approximation. For the context bandit problems, Thompson Sampling is adopted based on the underlying posterior distributions of the parameters. More specifically, we introduce the discount decays on the previous samples impact and analyze the different decay rates with the underlying sample dynamics. Consequently, the exploration and exploitation is adaptively tradeoff according to the dynamics in the system.
Division of the Energy Market into Zones in Variable Weather Conditions using Locational Marginal Prices
Venue: arXiv cs.CE 2013
Year: 2013

Adopting a zonal structure of electricity market requires specification of zones' borders. One of the approaches to identify zones is based on clustering of Locational Marginal Prices (LMP). The purpose of the paper is twofold: (i) we extend the LMP methodology by taking into account variable weather conditions and (ii) we point out some weaknesses of the method and suggest their potential solutions. The offered extension comprises simulations based on the Optimal Power Flow (OPF) algorithm and twofold clustering method. First, LMP are calculated by OPF for each of scenario representing different weather conditions. Second, hierarchical clustering based on Ward's criterion is used on each realization of the prices separately. Then, another clustering method, i.e. consensus clustering, is used to aggregate the results from all simulations and to find the global division into zones. The offered method of aggregation is not limited only to LMP methodology and is universal.
Effect of data preprocessing on software effort estimation
Venue: arXiv cs.SE 2013
Year: 2013

Software effort estimation requires high accuracy, but accurate estimations are difficult to achieve. Increasingly, data mining is used to improve an organization's software process quality, e. g. the accuracy of effort estimations . There are a large number of different method combination exists for software effort estimation, selecting the most suitable combination becomes the subject of research in this paper. In this study, three simple preprocessors are taken (none, norm, log) and effort is measured using COCOMO model. Then results obtained from different preprocessors are compared and norm preprocessor proves to be more accurate as compared to other preprocessors.