OpenRaiser/Intern-Atlas huggingface dataset:
The SP theory of intelligence: benefits and applications
Venue: arXiv cs.AI 2013
Year: 2013

This article describes existing and expected benefits of the "SP theory of intelligence", and some potential applications. The theory aims to simplify and integrate ideas across artificial intelligence, mainstream computing, and human perception and cognition, with information compression as a unifying theme. It combines conceptual simplicity with descriptive and explanatory power across several areas of computing and cognition. In the "SP machine" -- an expression of the SP theory which is currently realized in the form of a computer model -- there is potential for an overall simplification of computing systems, including software. The SP theory promises deeper insights and better solutions in several areas of application including, most notably, unsupervised learning, natural language processing, autonomous robots, computer vision, intelligent databases, software engineering, information compression, medical diagnosis and big data. There is also potential in areas such as the semantic web, bioinformatics, structuring of documents, the detection of computer viruses, data fusion, new kinds of computer, and the development of scientific theories. The theory promises seamless integration of structures and functions within and between different areas of application. The potential value, worldwide, of these benefits and applications is at least $190 billion each year. Further development would be facilitated by the creation of a high-parallel, open-source version of the SP machine, available to researchers everywhere.
Auctioning based Coordinated TV White Space Spectrum Sharing for Home Networks
Venue: arXiv cs.NI 2013
Year: 2013

The idea of having the geolocation database monitor the secondary use of TV white space (TVWS) spectrum and assist in coordinating the secondary usage is gaining ground. Considering the home networking use case, we leverage the geolocation database for interference-aware coordinated TVWS sharing among secondary users (home networks) using {\em short-term auctions}, thereby realize a dynamic secondary market. To enable this auctioning based coordinated TVWS sharing framework, we propose an enhanced {\em market-driven TVWS spectrum access model}. For the short-term auctions, we propose an online multi-unit, iterative truthful mechanism called VERUM that takes into consideration spatially heterogeneous spectrum availability, an inherent characteristic in the TVWS context. We prove that VERUM is truthful (i.e., the best strategy for every bidder is to bid based on its true valuation) and is also efficient in that it allocates spectrum to users who value it the most. Evaluation results from scenarios with real home distributions in urban and dense-urban environments and using realistic TVWS spectrum availability maps show that VERUM performs close to optimal allocation in terms of revenue for the coordinating spectrum manager. Comparison with two existing efficient and truthful multi-unit spectrum auction schemes, VERITAS and SATYA, shows that VERUM fares better in terms of revenue, spectrum utilisation and percentage of winning bidders in diverse conditions. Taking all of the above together, VERUM can be seen to offer incentives to subscribed users encouraging them to use TVWS spectrum through greater spectrum availability (as measured by percentage of winning bidders) as well as to the coordinating spectrum manager through revenue generation.
The Anatomy of Web Censorship in Pakistan
Venue: arXiv cs.CY 2013
Year: 2013

Over the years, the Internet has democratized the flow of information. Unfortunately, in parallel, authoritarian regimes and other entities (such as ISPs) for their vested interests have curtailed this flow by partially or fully censoring the web. The policy, mechanism, and extent of this censorship varies from country to country. We present the first study of the cause, effect, and mechanism of web censorship in Pakistan. Specifically, we use a publicly available list of blocked websites and check their accessibility from multiple networks within the country. Our results indicate that the censorship mechanism varies across websites: some are blocked at the DNS level while others at the HTTP level. Interestingly, the government shifted to a centralized, Internet exchange level censorship system during the course of our study, enabling our findings to compare two generations of blocking systems. Furthermore, we report the outcome of a controlled survey to ascertain the mechanisms that are being actively employed by people to circumvent censorship. Finally, we discuss some simple but surprisingly unexplored methods of bypassing restrictions.
A Novel Robust Method to Add Watermarks to Bitmap Images by Fading Technique
Venue: arXiv cs.CV 2013
Year: 2013

Digital water marking is one of the essential fields in image security and copyright protection. The proposed technique in this paper was based on the principle of protecting images by hide an invisible watermark in the image. The technique starts with merging the cover image and the watermark image with suitable ratios, i.e., 99% from the cover image will be merged with 1% from the watermark image. Technically, the fading process is irreversible but with the proposed technique, the probability to reconstruct the original watermark image is great. There is no perceptible difference between the original and watermarked image by human eye. The experimental results show that the proposed technique proven its ability to hide images that have the same size of the cover image. Three performance measures were implemented to support the proposed techniques which are MSE, PSNR, and SSIM. Fortunately, all the three measures have excellent values.
A Formal Sociologic Study of Free Will
Venue: arXiv cs.SI 2013
Year: 2013

We make a formal sociologic study of the concept of free will. By using the language of mathematics and logic, we define what we call everlasting societies. Everlasting societies never age: persons never age, and the goods of the society are indestructible. The infinite history of an everlasting society unfolds by following deterministic and probabilistic laws that do their best to satisfy the free will of all the persons of the society. We define three possible kinds of histories for everlasting societies: primitive histories, good histories, and golden histories. In primitive histories, persons are inherently selfish, and they use their free will to obtain the personal ownerships of all the goods of the society. In good histories, persons are inherently good, and they use their free will to distribute the goods of the society. In good histories, a person is not only able to desire the personal ownership of goods, but is also able to desire that a good be owned by another person. In golden histories, free will is bound by the ethic of reciprocity, which states that "you should wish upon others as you would like others to wish upon yourself". In golden societies, the ethic of reciprocity becomes a law that partially binds free will, and that must be abided at all times. In other words, the verb "should" becomes the verb "must".
Machining of complex-shaped parts with guidance curves
Venue: arXiv cs.OH 2013
Year: 2013

Nowadays, high-speed machining is usually used for production of hardened material parts with complex shapes such as dies and molds. In such parts, tool paths generated for bottom machining feature with the conventional parallel plane strategy induced many feed rate reductions, especially when boundaries of the feature have a lot of curvatures and are not parallel. Several machining experiments on hardened material lead to the conclusion that a tool path implying stable cutting conditions might guarantee a better part surface integrity. To ensure this stability, the shape machined must be decomposed when conventional strategies are not suitable. In this paper, an experimental approach based on high-speed performance simulation is conducted on a master bottom machining feature in order to highlight the influence of the curvatures towards a suitable decomposition of machining area. The decomposition is achieved through the construction of intermediate curves between the closed boundaries of the feature. These intermediate curves are used as guidance curve for the tool paths generation with an alternative machining strategy called "guidance curve strategy". For the construction of intermediate curves, key parameters reflecting the influence of their proximity with each closed boundary and the influence of the curvatures of this latter are introduced. Based on the results, a method for defining guidance curves in four steps is proposed.
Algorithms for Producing Linear Dilution Gradient with Digital Microfluidics
Venue: arXiv cs.ET 2013
Year: 2013

Digital microfluidic (DMF) biochips are now being extensively used to automate several biochemical laboratory protocols such as clinical analysis, point-of-care diagnostics, and polymerase chain reaction (PCR). In many biological assays, e.g., in bacterial susceptibility tests, samples and reagents are required in multiple concentration (or dilution) factors, satisfying certain "gradient" patterns such as linear, exponential, or parabolic. Dilution gradients are usually prepared with continuous-flow microfluidic devices; however, they suffer from inflexibility, non-programmability, and from large requirement of costly stock solutions. DMF biochips, on the other hand, are shown to produce, more efficiently, a set of random dilution factors. However, all existing algorithms fail to optimize the cost or performance when a certain gradient pattern is required. In this work, we present an algorithm to generate any arbitrary linear gradient, on-chip, with minimum wastage, while satisfying a required accuracy in the concentration factor. We present new theoretical results on the number of mix-split operations and waste computation, and prove an upper bound on the storage requirement. The corresponding layout design of the biochip is also proposed. Simulation results on different linear gradients show a significant improvement in sample cost over three earlier algorithms used for the generation of multiple concentrations.
Byzantine Convex Consensus: An Optimal Algorithm
Venue: arXiv cs.DC 2013
Year: 2013

Much of the past work on asynchronous approximate Byzantine consensus has assumed scalar inputs at the nodes [4, 8]. Recent work has yielded approximate Byzantine consensus algorithms for the case when the input at each node is a d-dimensional vector, and the nodes must reach consensus on a vector in the convex hull of the input vectors at the fault-free nodes [9, 13]. The d-dimensional vectors can be equivalently viewed as points in the d-dimensional Euclidean space. Thus, the algorithms in [9, 13] require the fault-free nodes to decide on a point in the d-dimensional space. In our recent work [arXiv:/1307.1051], we proposed a generalization of the consensus problem, namely Byzantine convex consensus (BCC), which allows the decision to be a convex polytope in the d-dimensional space, such that the decided polytope is within the convex hull of the input vectors at the fault-free nodes. We also presented an asynchronous approximate BCC algorithm. In this paper, we propose a new BCC algorithm with optimal fault-tolerance that also agrees on a convex polytope that is as large as possible under adversarial conditions. Our prior work [arXiv:/1307.1051] does not guarantee the optimality of the output polytope.
Matching Known Patients to Health Records in Washington State Data
Venue: arXiv cs.CY 2013
Year: 2013

The State of Washington sells patient-level health data for $50. This publicly available dataset has virtually all hospitalizations occurring in the State in a given year, including patient demographics, diagnoses, procedures, attending physician, hospital, a summary of charges, and how the bill was paid. It does not contain patient names or addresses (only ZIPs). Newspaper stories printed in the State for the same year that contain the word "hospitalized" often include a patient's name and residential information and explain why the person was hospitalized, such as vehicle accident or assault. News information uniquely and exactly matched medical records in the State database for 35 of the 81 cases (or 43 percent) found in 2011, thereby putting names to patient records. A news reporter verified matches by contacting patients. Employers, financial organizations and others know the same kind of information as reported in news stories making it just as easy for them to identify the medical records of employees, debtors, and others.
The Application of a Data Mining Framework to Energy Usage Profiling in Domestic Residences using UK data
Venue: arXiv cs.CE 2013
Year: 2013

This paper describes a method for defining representative load profiles for domestic electricity users in the UK. It considers bottom up and clustering methods and then details the research plans for implementing and improving existing framework approaches based on the overall usage profile. The work focuses on adapting and applying analysis framework approaches to UK energy data in order to determine the effectiveness of creating a few (single figures) archetypical users with the intention of improving on the current methods of determining usage profiles. The work is currently in progress and the paper details initial results using data collected in Milton Keynes around 1990. Various possible enhancements to the work are considered including a split based on temperature to reflect the varying UK weather conditions.
An Elegant Algorithm for the Construction of Suffix Arrays
Venue: arXiv cs.DS 2013
Year: 2013

The suffix array is a data structure that finds numerous applications in string processing problems for both linguistic texts and biological data. It has been introduced as a memory efficient alternative for suffix trees. The suffix array consists of the sorted suffixes of a string. There are several linear time suffix array construction algorithms (SACAs) known in the literature. However, one of the fastest algorithms in practice has a worst case run time of $O(n^2)$. The problem of designing practically and theoretically efficient techniques remains open. In this paper we present an elegant algorithm for suffix array construction which takes linear time with high probability; the probability is on the space of all possible inputs. Our algorithm is one of the simplest of the known SACAs and it opens up a new dimension of suffix array construction that has not been explored until now. Our algorithm is easily parallelizable. We offer parallel implementations on various parallel models of computing. We prove a lemma on the $\ell$-mers of a random string which might find independent applications. We also present another algorithm that utilizes the above algorithm. This algorithm is called RadixSA and has a worst case run time of $O(n\log{n})$. RadixSA introduces an idea that may find independent applications as a speedup technique for other SACAs. An empirical comparison of RadixSA with other algorithms on various datasets reveals that our algorithm is one of the fastest algorithms to date. The C++ source code is freely available at http://www.engr.uconn.edu/~man09004/radixSA.zip
DOBBS: Towards a Comprehensive Dataset to Study the Browsing Behavior of Online Users
Venue: arXiv cs.HC 2013
Year: 2013

The investigation of the browsing behavior of users provides useful information to optimize web site design, web browser design, search engines offerings, and online advertisement. This has been a topic of active research since the Web started and a large body of work exists. However, new online services as well as advances in Web and mobile technologies clearly changed the meaning behind "browsing the Web" and require a fresh look at the problem and research, specifically in respect to whether the used models are still appropriate. Platforms such as YouTube, Netflix or last.fm have started to replace the traditional media channels (cinema, television, radio) and media distribution formats (CD, DVD, Blu-ray). Social networks (e.g., Facebook) and platforms for browser games attracted whole new, particularly less tech-savvy audiences. Furthermore, advances in mobile technologies and devices made browsing "on-the-move" the norm and changed the user behavior as in the mobile case browsing is often being influenced by the user's location and context in the physical world. Commonly used datasets, such as web server access logs or search engines transaction logs, are inherently not capable of capturing the browsing behavior of users in all these facets. DOBBS (DERI Online Behavior Study) is an effort to create such a dataset in a non-intrusive, completely anonymous and privacy-preserving way. To this end, DOBBS provides a browser add-on that users can install, which keeps track of their browsing behavior (e.g., how much time they spent on the Web, how long they stay on a website, how often they visit a website, how they use their browser, etc.). In this paper, we outline the motivation behind DOBBS, describe the add-on and captured data in detail, and present some first results to highlight the strengths of DOBBS.
Finding Information Through Integrated Ad-Hoc Socializing in the Virtual and Physical World
Venue: arXiv cs.IR 2013
Year: 2013

Despite the services of sophisticated search engines like Google, there are a number of interesting information sources which are useful but largely inaccessible to current Web users. These information sources are often ad-hoc, location-specific and only useful for users over short periods of time, or relate to tacit knowledge of users or implicit knowledge in crowds. The solution presented in this paper addresses these problems by introducing an integrated concept of "location" and "presence" across the physical and virtual worlds enabling ad-hoc socializing of users interested in, or looking for similar information. While the definition of presence in the physical world is straightforward - through a spatial location and vicinity at a certain point in time - their definitions in the virtual world are neither obvious nor trivial. Based on a detailed analysis we provide an integrated spatial model spanning both worlds which enables us to define presence of users in a unified way. This integrated model allows us to enable ad-hoc socializing of users browsing the Web with users in the physical world specific to their joint information needs and allows us to unlock the untapped information sources mentioned above. We describe a proof-of-concept implementation of our model and provide an empirical analysis based on real-world experiments.
Compressed Pattern-Matching with Ranked Variables in Zimin Words
Venue: arXiv cs.DS 2013
Year: 2013

Zimin words are very special finite words which are closely related to the pattern-avoidability problem. This problem consists in testing if an instance of a given pattern with variables occurs in almost all words over any finite alphabet. The problem is not well understood, no polynomial time algorithm is known and its NP-hardness is also not known. The pattern-avoidability problem is equivalent to searching for a pattern (with variables) in a Zimin word. The main difficulty is potentially exponential size of Zimin words. We use special properties of Zimin words, especially that they are highly compressible, to design efficient algorithms for special version of the pattern-matching, called here ranked matching. It gives a new interpretation of Zimin algorithm in compressed setting. We discuss the structure of rankings of variables and compressed representations of values of variables. Moreover, for a ranked matching we present efficient algorithms to find the shortest instance and the number of valuations of instances of the pattern.
Towards Extracting Explicit Proofs from Totality Checking in Twelf
Venue: arXiv cs.LO 2013
Year: 2013

The Edinburgh Logical Framework (LF) is a dependently type lambda calculus that can be used to encode formal systems. The versatility of LF allows specifications to be constructed also about the encoded systems. The Twelf system exploits the correspondence between formulas and types to give specifications in LF a logic programming interpretation. By interpreting particular arguments as input and others as output, specifications can be seen as describing non-deterministic functions. If particular such functions can be shown to be total, they represent constructive proofs of meta-theorems of the encoded systems. Twelf provides a suite of tools for establishing totality. However, all the resulting proofs of meta-theorems are implicit: Twelf's totality checking does not yield a certificate that can be given to a proof checker. We begin the process here of making these proofs explicit. We treat the restricted situation in Twelf where context definitions (regular worlds) and lemmas are not used. In this setting we describe and prove correct a translation of the steps in totality checking into an actual proof in the companion logic M2. We intend in the long term to extend our translation to all of Twelf and to use this work as the basis for producing proofs in the related Abella system.
Approximation Schemes for Maximum Weight Independent Set of Rectangles
Venue: arXiv cs.DS 2013
Year: 2013

In the Maximum Weight Independent Set of Rectangles (MWISR) problem we are given a set of n axis-parallel rectangles in the 2D-plane, and the goal is to select a maximum weight subset of pairwise non-overlapping rectangles. Due to many applications, e.g. in data mining, map labeling and admission control, the problem has received a lot of attention by various research communities. We present the first (1+epsilon)-approximation algorithm for the MWISR problem with quasi-polynomial running time 2^{poly(log n/epsilon)}. In contrast, the best known polynomial time approximation algorithms for the problem achieve superconstant approximation ratios of O(log log n) (unweighted case) and O(log n / log log n) (weighted case). Key to our results is a new geometric dynamic program which recursively subdivides the plane into polygons of bounded complexity. We provide the technical tools that are needed to analyze its performance. In particular, we present a method of partitioning the plane into small and simple areas such that the rectangles of an optimal solution are intersected in a very controlled manner. Together with a novel application of the weighted planar graph separator theorem due to Arora et al. this allows us to upper bound our approximation ratio by (1+epsilon). Our dynamic program is very general and we believe that it will be useful for other settings. In particular, we show that, when parametrized properly, it provides a polynomial time (1+epsilon)-approximation for the special case of the MWISR problem when each rectangle is relatively large in at least one dimension. Key to this analysis is a method to tile the plane in order to approximately describe the topology of these rectangles in an optimal solution. This technique might be a useful insight to design better polynomial time approximation algorithms or even a PTAS for the MWISR problem.
Communication Lower Bounds for Distributed-Memory Computations
Venue: arXiv cs.DS 2013
Year: 2013

We give lower bounds on the communication complexity required to solve several computational problems in a distributed-memory parallel machine, namely standard matrix multiplication, stencil computations, comparison sorting, and the Fast Fourier Transform. We revisit the assumptions under which preceding results were derived and provide new lower bounds which use much weaker and appropriate hypotheses. Our bounds rely on a mild assumption on work distribution, and strengthen previous results which require either the computation to be balanced among the processors, or specific initial distributions of the input data, or an upper bound on the size of processors' local memories.