OpenRaiser/Intern-Atlas huggingface dataset:
XLSearch: A Search Engine for Spreadsheets
Venue: arXiv cs.DB 2014
Year: 2014

Spreadsheets are end-user programs and domain models that are heavily employed in administration, financial forecasting, education, and science because of their intuitive, flexible, and direct approach to computation. As a result, institutions are swamped by millions of spreadsheets that are becoming increasingly difficult to manage, access, and control. This note presents the XLSearch system, a novel search engine for spreadsheets. It indexes spreadsheet formulae and efficiently answers formula queries via unification (a complex query language that allows metavariables in both the query as well as the index). But a web-based search engine is only one application of the underlying technology: Spreadsheet formula export to web standards like MathML combined with formula indexing can be used to find similar spreadsheets or common formula errors.
A New Approach to Analyzing Robin Hood Hashing
Venue: arXiv cs.DS 2014
Year: 2014

Robin Hood hashing is a variation on open addressing hashing designed to reduce the maximum search time as well as the variance in the search time for elements in the hash table. While the case of insertions only using Robin Hood hashing is well understood, the behavior with deletions has remained open. Here we show that Robin Hood hashing can be analyzed under the framework of finite-level finite-dimensional jump Markov chains. This framework allows us to re-derive some past results for the insertion-only case with some new insight, as well as provide a new analysis for a standard deletion model, where we alternate between deleting a random old key and inserting a new one. In particular, we show that a simple but apparently unstudied approach for handling deletions with Robin Hood hashing offers good performance even under high loads.
Tailored Source Code Transformations to Synthesize Computationally Diverse Program Variants
Venue: arXiv cs.SE 2014
Year: 2014

The predictability of program execution provides attackers a rich source of knowledge who can exploit it to spy or remotely control the program. Moving target defense addresses this issue by constantly switching between many diverse variants of a program, which reduces the certainty that an attacker can have about the program execution. The effectiveness of this approach relies on the availability of a large number of software variants that exhibit different executions. However, current approaches rely on the natural diversity provided by off-the-shelf components, which is very limited. In this paper, we explore the automatic synthesis of large sets of program variants, called sosies. Sosies provide the same expected functionality as the original program, while exhibiting different executions. They are said to be computationally diverse. This work addresses two objectives: comparing different transformations for increasing the likelihood of sosie synthesis (densifying the search space for sosies); demonstrating computation diversity in synthesized sosies. We synthesized 30184 sosies in total, for 9 large, real-world, open source applications. For all these programs we identified one type of program analysis that systematically increases the density of sosies; we measured computation diversity for sosies of 3 programs and found diversity in method calls or data in more than 40% of sosies. This is a step towards controlled massive unpredictability of software.
ReducedCBT and SuperCBT, Two New and Improved Complete Binary Tree Structures
Venue: arXiv cs.DS 2014
Year: 2014

Between the leaves and the nodes of a complete binary tree, a separate parent-child-sister hierarchy is employed independent of the parent-child-sister hierarchy used for the rest of the tree. Two different versions of such a local hierarchy are introduced. The result of the first proposed hierarchy is a faster and smaller footprint, while the second one provides the size variation functionality without a significant computational overhead. This novel approach brings considerable memory gains and performance boosts to the complete binary tree based algorithms.
Effective Features of Remote Sensing Image Classification Using Interactive Adaptive Thresholding Method
Venue: arXiv cs.CV 2014
Year: 2014

Remote sensing image classification can be performed in many different ways to extract meaningful features. One common approach is to perform edge detection. A second approach is to try and detect whole shapes, given the fact that these shapes usually tend to have distinctive properties such as object foreground or background. To get optimal results, these two approaches can be combined. This paper adopts a combinatorial optimization method to adaptively select threshold based features to improve remote sensing image. Feature selection is an important combinatorial optimization problem in the remote sensing image classification. The feature selection method has to achieve three characteristics: first the performance issues by facilitating data collection and reducing storage space and classification time, second to perform semantics analysis helping to understand the problem, and third to improve prediction accuracy by avoiding the curse of dimensionality. The goal of this thresholding an image is to classify pixels as either dark or light and evaluation of classification results. Interactive adaptive thresholding is a form of thresholding that takes into account spatial variations in illumination of remote sensing image. We present a technique for remote sensing based adaptive thresholding using the interactive satellite image of the input. However, our solution is more robust to illumination changes in the remote sensing image. Additionally, our method is simple and easy to implement but it is effective algorithm to classify the image pixels. This technique is suitable for preprocessing the remote sensing image classification, making it a valuable tool for interactive remote based applications such as augmented reality of the classification procedure.
Focusing Testing by Using Inspection and Product Metrics
Venue: arXiv cs.SE 2014
Year: 2014

A well-known approach for identifying defect-prone parts of software in order to focus testing is to use different kinds of product metrics such as size or complexity. Although this approach has been evaluated in many contexts, the question remains if there are further opportunities to improve test focusing. One idea is to identify other types of information that may indicate the location of defect-prone software parts. Data from software inspections, in particular, appear to be promising. This kind of data might already lead to software parts that have inherent difficulties or programming challenges, and in consequence might be defect-prone. This article first explains how inspection and product metrics can be used to focus testing activities. Second, we compare selected product and inspection metrics commonly used to predict defect-prone parts (e.g., size and complexity metrics, inspection defect content metrics, and defect density metrics). Based on initial experience from two case studies performed in different environments, the suitability of different metrics for predicting defect-prone parts is illustrated. The studies revealed that inspection defect data seems to be a suitable predictor, and a combination of certain inspection and product metrics led to the best prioritizations in our contexts. In addition, qualitative experience is presented, which substantiates the expected benefit of using inspection results to optimize testing.
Introducing Morphit, a new type of spreadsheet technology
Venue: arXiv cs.SE 2014
Year: 2014

This paper describes a new type of spreadsheet which mitigates the errors caused by incorrect range referencing in formulae. This spreadsheet is composed of structured worksheets called tables which contain a hierarchical organization of fields. Formulae are defined at the field-level removing the need for positional references. In addition, relationships can be defined between fields in tables, allowing data to be modeled rather than simply processed and providing a re-usable framework for authoring spreadsheets. We shall describe the key features of tables with an emphasis on error detection and avoidance.
Exploring the Relationship between Membership Turnover and Productivity in Online Communities
Venue: arXiv cs.SI 2014
Year: 2014

One of the more disruptive reforms associated with the modern Internet is the emergence of online communities working together on knowledge artefacts such as Wikipedia and OpenStreetMap. Recently it has become clear that these initiatives are vulnerable because of problems with membership turnover. This study presents a longitudinal analysis of 891 WikiProjects where we model the impact of member turnover and social capital losses on project productivity. By examining social capital losses we attempt to provide a more nuanced analysis of member turnover. In this context social capital is modelled from a social network perspective where the loss of more central members has more impact. We find that only a small proportion of WikiProjects are in a relatively healthy state with low levels of membership turnover and social capital losses. The results show that the relationship between social capital losses and project performance is U-shaped, and that member withdrawal has significant negative effect on project outcomes. The results also support the mediation of turnover rate and network density on the curvilinear relationship.
Numerical application and Turbo C program using the Gauss-Jordan Method
Venue: arXiv cs.MS 2014
Year: 2014

The article presents the general notions and algorithm about the Gauss-Jordan method. An eloquent example is given and the Turbo C program illustrated this method. We conclude that we can obtain by this method the determinant, by simple calculations and reducing the rounding errors
Priority-Aware Private Matching Schemes for Proximity-Based Mobile Social Networks
Venue: arXiv cs.CR 2014
Year: 2014

The rapid developments of mobile devices and online social networks have resulted in increasing attention to Mobile Social Networking (MSN). The explosive growth of mobile-connected and location-aware devices makes it possible and meaningful to do the Proximity-based Mobile Social Networks (PMSNs). Users can discover and make new social interactions easily with physical-proximate mobile users through WiFi/Bluetooth interfaces embedded in their smartphones. However, users enjoy these conveniences at the cost of their growing privacy concerns. To address this problem, we propose a suit of priority-aware private matching schemes to privately match the similarity with potential friends in the vicinity. Unlike most existing work, our proposed priority-aware matching scheme (P-match) achieves the privacy goal by combining the commutative encryption function and the Tanimoto similarity coefficient which considers both the number of common attributes between users as well as the corresponding priorities on each common attribute. Further, based on the newly constructed similarity function which takes the ratio of attributes matched over all the input set into consideration, we design an enhanced version to deal with some potential attacks such as unlimitedly inputting the attribute set on either the initiator side or the responder side, etc. Finally, our proposed E-match avoids the heavy cryptographic operations and improves the system performance significantly by employing a novel use of the Bloom filter. The security and communication/computation overhead of our schemes are thoroughly analyzed and evaluated via detailed simulations and implementation.
ICT technologies for the refurbishment of wooden structure buildings
Venue: arXiv cs.OH 2014
Year: 2014

Nowadays, one would think that after years of massive concrete and steel construction in Spain, there are not many wood structure buildings left to be refurbished except for some palaces or cathedrals. However, if we go for a walk and have a look at the old part of any city, we will realize that still most of the buildings have a wood structure. In spite of the fact that the majority of urban regulations forbid their demolition, other bad practices such as casting and overloading the wood structure are very common. Considering that we want to reach a standard of sustainable construction, the economical and environmental costs, which are implied by the deficient refurbishment makes it well worth a previous study of the structure, which in most cases represents less than a 1% of the total budget. The main goal of this paper is to present most relevant parts of the whole process of diagnosis of a wood structure building by means of Non-Destructive Testing Techniques. Among the ones to be considered, we could mention the analysis of the building and its surroundings, on-site inspection of the building, structural diagnosis, definition of the corrective actions to be taken, definition of treatments, quality control and a maintenance plan. For the on-site inspection of the building, in the paper we will highlight the use of Non-Destructive methods such as resistograph drilling, X-ray imaging, ultrasound-based testing or moisture measurement. We will provide practical examples of all this. The aim of this paper is to give the audience an overall idea on how a pre-assessment work can enhance the refurbishment of a wood structure building while reducing costs and environmental impact.
Distributed Area Coverage by Connected Set Cover Partitioning in Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

Assuming a random uniform distribution of n sensor nodes over a virtual grid, this paper addresses the problem of finding the maximum number of connected set covers each ensuring 100% coverage of the query region. The connected sets remain active one after another in a round robin fashion such that if there are P such set covers, it can enhance the network lifetime P-fold. From graph-theoretic point of view, a centralized O(n3) heuristic is proposed here to maximize P. Next, for large self-organized sensor networks, a distributed algorithm is developed. The proposed algorithm is to be executed just once, during the initialization of the network. In case of failure, a distributed recovery algorithm is executed to rearrange the partitions. Simulation studies show that the performance of the proposed distributed algorithm is comparable with that of the centralized algorithm in terms of number of partitions. Also, comparison with earlier works shows significant improvement in terms of number of partitions, message complexity and network lifetime.
Human Activity Recognition using Smartphone
Venue: arXiv cs.CY 2014
Year: 2014

Human activity recognition has wide applications in medical research and human survey system. In this project, we design a robust activity recognition system based on a smartphone. The system uses a 3-dimentional smartphone accelerometer as the only sensor to collect time series signals, from which 31 features are generated in both time and frequency domain. Activities are classified using 4 different passive learning methods, i.e., quadratic classifier, k-nearest neighbor algorithm, support vector machine, and artificial neural networks. Dimensionality reduction is performed through both feature extraction and subset selection. Besides passive learning, we also apply active learning algorithms to reduce data labeling expense. Experiment results show that the classification rate of passive learning reaches 84.4% and it is robust to common positions and poses of cellphone. The results of active learning on real data demonstrate a reduction of labeling labor to achieve comparable performance with passive learning.
Increasing precision of uniform pseudorandom number generators
Venue: arXiv cs.MS 2014
Year: 2014

A general method to produce uniformly distributed pseudorandom numbers with extended precision by combining two pseudorandom numbers with lower precision is proposed. In particular, this method can be used for pseudorandom number generation with extended precision on graphics processing units (GPU), where the performance of single and double precision operations can vary significantly.
Quantitative Analysis of Active Cyber Defenses Based on Temporal Platform Diversity
Venue: arXiv cs.CR 2014
Year: 2014

Active cyber defenses based on temporal platform diversity have been proposed as way to make systems more resistant to attacks. These defenses change the properties of the platforms in order to make attacks more complicated. Unfortunately, little work has been done on measuring the effectiveness of these defenses. In this work, we use four different approaches to quantitatively analyze these defenses; an abstract analysis studies the algebraic models of a temporal platform diversity system; a set of experiments on a test bed measures the metrics of interest for the system; a game theoretic analysis studies the impact of preferential selection of platforms and derives an optimal strategy; finally, a set of simulations evaluates the metrics of interest on the models. Our results from these approaches all agree and yet are counter-intuitive. We show that although platform diversity can mitigate some attacks, it can be detrimental for others. We also illustrate that the benefit from these systems heavily depends on their threat model and that the preferential selection of platforms can achieve better protection.
Distributed Algorithms for Stochastic Source Seeking with Mobile Robot Networks: Technical Report
Venue: arXiv cs.MA 2014
Year: 2014

Autonomous robot networks are an effective tool for monitoring large-scale environmental fields. This paper proposes distributed control strategies for localizing the source of a noisy signal, which could represent a physical quantity of interest such as magnetic force, heat, radio signal, or chemical concentration. We develop algorithms specific to two scenarios: one in which the sensors have a precise model of the signal formation process and one in which a signal model is not available. In the model-free scenario, a team of sensors is used to follow a stochastic gradient of the signal field. Our approach is distributed, robust to deformations in the group geometry, does not necessitate global localization, and is guaranteed to lead the sensors to a neighborhood of a local maximum of the field. In the model-based scenario, the sensors follow the stochastic gradient of the mutual information between their expected measurements and the location of the source in a distributed manner. The performance is demonstrated in simulation using a robot sensor network to localize the source of a wireless radio signal.
Collaborative Receptive Field Learning
Venue: arXiv cs.CV 2014
Year: 2014

The challenge of object categorization in images is largely due to arbitrary translations and scales of the foreground objects. To attack this difficulty, we propose a new approach called collaborative receptive field learning to extract specific receptive fields (RF's) or regions from multiple images, and the selected RF's are supposed to focus on the foreground objects of a common category. To this end, we solve the problem by maximizing a submodular function over a similarity graph constructed by a pool of RF candidates. However, measuring pairwise distance of RF's for building the similarity graph is a nontrivial problem. Hence, we introduce a similarity metric called pyramid-error distance (PED) to measure their pairwise distances through summing up pyramid-like matching errors over a set of low-level features. Besides, in consistent with the proposed PED, we construct a simple nonparametric classifier for classification. Experimental results show that our method effectively discovers the foreground objects in images, and improves classification performance.
Secure Debit Card Device Model
Venue: arXiv cs.CE 2014
Year: 2014

The project envisages the implementation of an e-payment system utilizing FIPS-201 Smart Card. The system combines hardware and software modules. The hardware module takes data insertions (e.g. currency notes), processes the data and then creates connection with the smart card using serial/USB ports to perform further mathematical manipulations. The hardware interacts with servers at the back for authentication and identification of users and for data storage pertaining to a particular user. The software module manages database, handles identities, provide authentication and secure communication between the various system components. It will also provide a component to the end users. This component can be in the form of software for computer or executable binaries for PoS devices. The idea is to receive data in the embedded system from data reader and smart card. After manipulations, the updated data is imprinted on smart card memory and also updated in the back end servers maintaining database. The information to be sent to a server is sent through a PoS device which has multiple transfer mediums involving wired and un-wired mediums. The user device also acts as an updater; therefore, whenever the smart card is inserted by user, it is automatically updated by synchronizing with back-end database. The project required expertise in embedded systems, networks, java and C++ (Optional).
A Bound on the Expected Optimality of Random Feasible Solutions to Combinatorial Optimization Problems
Venue: arXiv cs.DS 2014
Year: 2014

This paper investigates and bounds the expected solution quality of combinatorial optimization problems when feasible solutions are chosen at random. Loose general bounds are discovered, as well as families of combinatorial optimization problems for which random feasible solutions are expected to be a constant factor of optimal. One implication of this result is that, for graphical problems, if the average edge weight in a feasible solution is sufficiently small, then any randomly chosen feasible solution to the problem will be a constant factor of optimal. For example, under certain well-defined circumstances, the expected constant of approximation of a randomly chosen feasible solution to the Steiner network problem is bounded above by 3. Empirical analysis supports these bounds and actually suggest that they might be tightened.
Applying Supervised Learning Algorithms and a New Feature Selection Method to Predict Coronary Artery Disease
Venue: arXiv cs.LG 2014
Year: 2014

From a fresh data science perspective, this thesis discusses the prediction of coronary artery disease based on genetic variations at the DNA base pair level, called Single-Nucleotide Polymorphisms (SNPs), collected from the Ontario Heart Genomics Study (OHGS). First, the thesis explains two commonly used supervised learning algorithms, the k-Nearest Neighbour (k-NN) and Random Forest classifiers, and includes a complete proof that the k-NN classifier is universally consistent in any finite dimensional normed vector space. Second, the thesis introduces two dimensionality reduction steps, Random Projections, a known feature extraction technique based on the Johnson-Lindenstrauss lemma, and a new method termed Mass Transportation Distance (MTD) Feature Selection for discrete domains. Then, this thesis compares the performance of Random Projections with the k-NN classifier against MTD Feature Selection and Random Forest, for predicting artery disease based on accuracy, the F-Measure, and area under the Receiver Operating Characteristic (ROC) curve. The comparative results demonstrate that MTD Feature Selection with Random Forest is vastly superior to Random Projections and k-NN. The Random Forest classifier is able to obtain an accuracy of 0.6660 and an area under the ROC curve of 0.8562 on the OHGS genetic dataset, when 3335 SNPs are selected by MTD Feature Selection for classification. This area is considerably better than the previous high score of 0.608 obtained by Davies et al. in 2010 on the same dataset.