OpenRaiser/Intern-Atlas huggingface dataset:
Where Businesses Thrive: Predicting the Impact of the Olympic Games on Local Retailers through Location-based Services Data
Venue: arXiv cs.SI 2014
Year: 2014

The Olympic Games are an important sporting event with notable consequences for the general economic landscape of the host city. Traditional economic assessments focus on the aggregated impact of the event on the national income, but fail to provide micro-scale insights on why local businesses will benefit from the increased activity during the Games. In this paper we provide a novel approach to modeling the impact of the Olympic Games on local retailers by analyzing a dataset mined from a large location-based social service, Foursquare. We hypothesize that the spatial positioning of businesses as well as the mobility trends of visitors are primary indicators of whether retailers will rise their popularity during the event. To confirm this we formulate a retail winners prediction task in the context of which we evaluate a set of geographic and mobility metrics. We find that the proximity to stadiums, the diversity of activity in the neighborhood, the nearby area sociability, as well as the probability of customer flows from and to event places such as stadiums and parks are all vital factors. Through supervised learning techniques we demonstrate that the success of businesses hinges on a combination of both geographic and mobility factors. Our results suggest that location-based social networks, where crowdsourced information about the dynamic interaction of users with urban spaces becomes publicly available, present an alternative medium to assess the economic impact of large scale events in a city.
Sharpened Error Bounds for Random Sampling Based $\ell_2$ Regression
Venue: arXiv cs.LG 2014
Year: 2014

Given a data matrix $X \in R^{n\times d}$ and a response vector $y \in R^{n}$, suppose $n>d$, it costs $O(n d^2)$ time and $O(n d)$ space to solve the least squares regression (LSR) problem. When $n$ and $d$ are both large, exactly solving the LSR problem is very expensive. When $n \gg d$, one feasible approach to speeding up LSR is to randomly embed $y$ and all columns of $X$ into a smaller subspace $R^c$; the induced LSR problem has the same number of columns but much fewer number of rows, and it can be solved in $O(c d^2)$ time and $O(c d)$ space. We discuss in this paper two random sampling based methods for solving LSR more efficiently. Previous work showed that the leverage scores based sampling based LSR achieves $1+ε$ accuracy when $c \geq O(d ε^{-2} \log d)$. In this paper we sharpen this error bound, showing that $c = O(d \log d + d ε^{-1})$ is enough for achieving $1+ε$ accuracy. We also show that when $c \geq O(μd ε^{-2} \log d)$, the uniform sampling based LSR attains a $2+ε$ bound with positive probability.
Enhancing Automated Decision Support across Medical and Oral Health Domains with Semantic Web Technologies
Venue: arXiv cs.AI 2014
Year: 2014

Research has shown that the general health and oral health of an individual are closely related. Accordingly, current practice of isolating the information base of medical and oral health domains can be dangerous and detrimental to the health of the individual. However, technical issues such as heterogeneous data collection and storage formats, limited sharing of patient information and lack of decision support over the shared information are the principal reasons for the current state of affairs. To address these issues, the following research investigates the development and application of a cross-domain ontology and rules to build an evidence-based and reusable knowledge base consisting of the inter-dependent conditions from the two domains. Through example implementation of the knowledge base in Protege, we demonstrate the effectiveness of our approach in reasoning over and providing decision support for cross-domain patient information.
Scheduling in Time-correlated Wireless Networks with Imperfect CSI and Stringent Constraint
Venue: arXiv cs.NI 2014
Year: 2014

In a wireless network, the efficiency of scheduling algorithms over time-varying channels depends heavily on the accuracy of the Channel State Information (CSI), which is usually quite ``costly'' in terms of consuming network resources. Scheduling in such systems is also subject to stringent constraints such as power and bandwidth, which limit the maximum number of simultaneous transmissions. In the meanwhile, communication channels in wireless systems typically fluctuate in a time-correlated manner. We hence design schedulers to exploit the temporal-correlation inherent in channels with memory and ARQ-styled feedback from the users for better channel state knowledge, under the assumption of Markovian channels and the stringent constraint on the maximum number of simultaneously active users. We model this problem under the framework of a Partially Observable Markov Decision Processes. In recent work, a low-complexity optimal solution was developed for this problem under a long-term time-average resource constraint. However, in real systems with instantaneous resource constraints, how to optimally exploit the temporal correlation and satisfy realistic stringent constraint on the instantaneous service remains elusive. In this work, we incorporate a stringent constraint on the simultaneously scheduled users and propose a low-complexity scheduling algorithm that dynamically implements user scheduling and dummy packet broadcasting. We show that the throughput region of the optimal policy under the long-term average resource constraint can be asymptotically achieved in the stringent constrained scenario by the proposed algorithm, in the many users limiting regime.
Reasoning with !-Graphs
Venue: arXiv cs.LO 2014
Year: 2014

The aim of this thesis is to present an extension to the string graphs of Dixon, Duncan and Kissinger that allows the finite representation of certain infinite families of graphs and graph rewrite rules, and to demonstrate that a logic can be built on this to allow the formalisation of inductive proofs in the string diagrams of compact closed and traced symmetric monoidal categories. String diagrams provide an intuitive method for reasoning about monoidal categories. However, this does not negate the ability for those using them to make mistakes in proofs. To this end, there is a project (Quantomatic) to build a proof assistant for string diagrams, at least for those based on categories with a notion of trace. The development of string graphs has provided a combinatorial formalisation of string diagrams, laying the foundations for this project. The prevalence of commutative Frobenius algebras (CFAs) in quantum information theory, a major application area of these diagrams, has led to the use of variable-arity nodes as a shorthand for normalised networks of Frobenius algebra morphisms, so-called "spider notation". This notation greatly eases reasoning with CFAs, but string graphs are inadequate to properly encode this reasoning. This dissertation extends string graphs to allow for variable-arity nodes to be represented at all, and then introduces !-box notation (and structures to encode it) to represent string graph equations containing repeated subgraphs, where the number of repetitions is abitrary. It then demonstrates how we can reason directly about !-graphs, viewed as (typically infinite) families of string graphs. Of particular note is the presentation of a form of graph-based induction, allowing the formal encoding of proofs that previously could only be represented as a mix of string diagrams and explanatory text.
Integrated Data Acquisition, Storage, Retrieval and Processing Using the COMPASS DataBase (CDB)
Venue: arXiv cs.DB 2014
Year: 2014

We present a complex data handling system for the COMPASS tokamak, operated by IPP ASCR Prague, Czech Republic [1]. The system, called CDB (Compass DataBase), integrates different data sources as an assortment of data acquisition hardware and software from different vendors is used. Based on widely available open source technologies wherever possible, CDB is vendor and platform independent and it can be easily scaled and distributed. The data is directly stored and retrieved using a standard NAS (Network Attached Storage), hence independent of the particular technology; the description of the data (the metadata) is recorded in a relational database. Database structure is general and enables the inclusion of multi-dimensional data signals in multiple revisions (no data is overwritten). This design is inherently distributed as the work is off-loaded to the clients. Both NAS and database can be implemented and optimized for fast local access as well as secure remote access. CDB is implemented in Python language; bindings for Java, C/C++, IDL and Matlab are provided. Independent data acquisitions systems as well as nodes managed by FireSignal [2] are all integrated using CDB. An automated data post-processing server is a part of CDB. Based on dependency rules, the server executes, in parallel if possible, prescribed post-processing tasks.
Cache-aware Parallel Programming for Manycore Processors
Venue: arXiv cs.DC 2014
Year: 2014

With rapidly evolving technology, multicore and manycore processors have emerged as promising architectures to benefit from increasing transistor numbers. The transition towards these parallel architectures makes today an exciting time to investigate challenges in parallel computing. The TILEPro64 is a manycore accelerator, composed of 64 tiles interconnected via multiple 8x8 mesh networks. It contains per-tile caches and supports cache-coherent shared memory by default. In this paper we present a programming technique to take advantages of distributed caching facilities in manycore processors. However, unlike other work in this area, our approach does not use architecture-specific libraries. Instead, we provide the programmer with a novel technique on how to program future Non-Uniform Cache Architecture (NUCA) manycore systems, bearing in mind their caching organisation. We show that our localised programming approach can result in a significant improvement of the parallelisation efficiency (speed-up).
Optimal Power Allocation for Three-phase Bidirectional DF Relaying with Fixed Rates
Venue: arXiv cs.IT 2014
Year: 2014

Wireless systems that carry delay-sensitive information (such as speech and/or video signals) typically transmit with fixed data rates, but may occasionally suffer from transmission outages caused by the random nature of the fading channels. If the transmitter has instantaneous channel state information (CSI) available, it can compensate for a significant portion of these outages by utilizing power allocation. In this paper, we consider optimal power allocation for a conventional dual-hop bidirectional decode-and-forward (DF) relaying system with a three-phase transmission protocol. The proposed strategy minimizes the average power consumed by the end nodes and the relay, subject to some maximum allowable system outage probability (OP), or equivalently, minimizes the system OP while meeting average power constraints at the end nodes and the relay. We show that in the proposed power allocation scheme, the end nodes and the relay adjust their output powers to the minimum level required to avoid outages, but will sometimes be silent, in order to conserve power and prolong their lifetimes. For the proposed scheme, the end nodes use the instantaneous CSI of their respective source-relay links and the relay uses the instantaneous CSI of both links.
Robust Subspace Recovery via Bi-Sparsity Pursuit
Venue: arXiv cs.CV 2014
Year: 2014

Successful applications of sparse models in computer vision and machine learning imply that in many real-world applications, high dimensional data is distributed in a union of low dimensional subspaces. Nevertheless, the underlying structure may be affected by sparse errors and/or outliers. In this paper, we propose a bi-sparse model as a framework to analyze this problem and provide a novel algorithm to recover the union of subspaces in presence of sparse corruptions. We further show the effectiveness of our method by experiments on both synthetic data and real-world vision data.
Selection Combining for Differential Amplify-and-Forward Relaying Over Rayleigh-Fading Channel
Venue: arXiv cs.IT 2014
Year: 2014

This paper proposes and analyses selection combining (SC) at the destination for differential amplify-andforward (D-AF) relaying over slow Rayleigh-fading channels. The selection combiner chooses the link with the maximum magnitude of the decision variable to be used for non-coherent detection of the transmitted symbols. Therefore, in contrast to the maximum ratio combining (MRC), no channel information is needed at the destination. The exact average bit-error-rate (BER) of the proposed SC is derived and verified with simulation results. It is also shown that the performance of the SC method is very close to that of the MRC method, albeit with lower complexity
General dynamic recovery for compensating CSP
Venue: arXiv cs.PL 2014
Year: 2014

Compensation is a technique to roll-back a system to a consistent state in case of failure. Recovery mechanisms for compensating calculi specify the order of execution of compensation sequences. Dynamic recovery means that the order of execution is determined at runtime. In this paper, we define an extension of Compensating CSP, called DEcCSP, with general dynamic recovery. We provide a formal, operational semantics for the calculus, and illustrate its expressive power with a case study. In contrast with previous versions of Compensating CSP, DEcCSP provides mechanisms to replace or discard compensations at runtime. Additionally, we bring back to DEcCSP standard CSP operators that are not available in other compensating CSP calculi, and introduce channel communication.
MTL-Model Checking of One-Clock Parametric Timed Automata is Undecidable
Venue: arXiv cs.LO 2014
Year: 2014

Parametric timed automata extend timed automata (Alur and Dill, 1991) in that they allow the specification of parametric bounds on the clock values. Since their introduction in 1993 by Alur, Henzinger, and Vardi, it is known that the emptiness problem for parametric timed automata with one clock is decidable, whereas it is undecidable if the automaton uses three or more parametric clocks. The problem is open for parametric timed automata with two parametric clocks. Metric temporal logic, MTL for short, is a widely used specification language for real-time systems. MTL-model checking of timed automata is decidable, no matter how many clocks are used in the timed automaton. In this paper, we prove that MTL-model checking for parametric timed automata is undecidable, even if the automaton uses only one clock and one parameter and is deterministic.
Venture: a higher-order probabilistic programming platform with programmable inference
Venue: arXiv cs.AI 2014
Year: 2014

We describe Venture, an interactive virtual machine for probabilistic programming that aims to be sufficiently expressive, extensible, and efficient for general-purpose use. Like Church, probabilistic models and inference problems in Venture are specified via a Turing-complete, higher-order probabilistic language descended from Lisp. Unlike Church, Venture also provides a compositional language for custom inference strategies built out of scalable exact and approximate techniques. We also describe four key aspects of Venture's implementation that build on ideas from probabilistic graphical models. First, we describe the stochastic procedure interface (SPI) that specifies and encapsulates primitive random variables. The SPI supports custom control flow, higher-order probabilistic procedures, partially exchangeable sequences and ``likelihood-free'' stochastic simulators. It also supports external models that do inference over latent variables hidden from Venture. Second, we describe probabilistic execution traces (PETs), which represent execution histories of Venture programs. PETs capture conditional dependencies, existential dependencies and exchangeable coupling. Third, we describe partitions of execution histories called scaffolds that factor global inference problems into coherent sub-problems. Finally, we describe a family of stochastic regeneration algorithms for efficiently modifying PET fragments contained within scaffolds. Stochastic regeneration linear runtime scaling in cases where many previous approaches scaled quadratically. We show how to use stochastic regeneration and the SPI to implement general-purpose inference strategies such as Metropolis-Hastings, Gibbs sampling, and blocked proposals based on particle Markov chain Monte Carlo and mean-field variational inference techniques.
Traffic Monitoring Using M2M Communication
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents an intelligent traffic monitoring system using wireless vision sensor network that captures and processes the real-time video image to obtain the traffic flow rate and vehicle speeds along different urban roadways. This system will display the traffic states on the front roadways that can guide the drivers to select the right way and avoid potential traffic congestions. On the other hand, it will also monitor the vehicle speeds and store the vehicle details, for those breaking the roadway speed limits, in its database. The real-time traffic data is processed by the Personal Computer (PC) at the sub roadway station and the traffic flow rate data is transmitted to the main roadway station Arduino 3G via email, where the data is extracted and traffic flow rate displayed.
Extension theorems for self-dual codes over rings and new binary self-dual codes
Venue: arXiv cs.IT 2014
Year: 2014

In this work, extension theorems are generalized to self-dual codes over rings and as applications many new binary self-dual extremal codes are found from self-dual codes over F_2^m+uF_2^m for m = 1, 2. The duality and distance preserving Gray maps from F4 +uF4 to (F_2 +uF_2)^2 and (F_4)^2 are used to obtain self-dual codes whose binary Gray images are [64,32,12]-extremal self-dual. An F_2+uF_2-extension is used and as binary images, 178 extremal binary self-dual codes of length 68 with new weight enumerators are obtained. Especially the first examples of codes with gamma=3 and many codes with the rare gamma= 4, 6 parameters are obtained. In addition to these, two hundred fifty doubly even self dual [96,48,16]-codes with new weight enumerators are obtained from four-circulant codes over F_4 + uF_4. New extremal doubly even binary codes of lengths 80 and 88 are also found by the F_2+uF_2-lifts of binary four circulant codes and a corresponding result about 3-designs is stated.
A Case Where Interference Does Not Affect The Channel Dispersion
Venue: arXiv cs.IT 2014
Year: 2014

In 1975, Carleial presented a special case of an interference channel in which the interference does not reduce the capacity of the constituent point-to-point Gaussian channels. In this work, we show that if the inequalities in the conditions that Carleial stated are strict, the dispersions are similarly unaffected. More precisely, in this work, we characterize the second-order coding rates of the Gaussian interference channel in the strictly very strong interference regime. In other words, we characterize the speed of convergence of rates of optimal block codes towards a boundary point of the (rectangular) capacity region. These second-order rates are expressed in terms of the average probability of error and variances of some modified information densities which coincide with the dispersion of the (single-user) Gaussian channel. We thus conclude that the dispersions are unaffected by interference in this channel model.
Layout Decomposition for Quadruple Patterning Lithography and Beyond
Venue: arXiv cs.DS 2014
Year: 2014

For next-generation technology nodes, multiple patterning lithography (MPL) has emerged as a key solution, e.g., triple patterning lithography (TPL) for 14/11nm, and quadruple patterning lithography (QPL) for sub-10nm. In this paper, we propose a generic and robust layout decomposition framework for QPL, which can be further extended to handle any general K-patterning lithography (K$>$4). Our framework is based on the semidefinite programming (SDP) formulation with novel coloring encoding. Meanwhile, we propose fast yet effective coloring assignment and achieve significant speedup. To our best knowledge, this is the first work on the general multiple patterning lithography layout decomposition.
Performance of the Generalized Quantize-and-Forward Scheme over the Multiple-Access Relay Channel
Venue: arXiv cs.IT 2014
Year: 2014

This work focuses on the half-duplex (HD) relaying based on the generalized quantize-and-forward (GQF) scheme in the slow fading Multiple Access Relay Channel (MARC) where the relay has no channel state information (CSI) of the relay-to-destination link. Relay listens to the channel in the first slot of the transmission block and cooperatively transmits to the destination in the second slot. In order to investigate the performance of the GQF, the following steps have been taken: 1)The GQF scheme is applied to establish the achievable rate regions of the discrete memoryless half-duplex MARC and the corresponding additive white Gaussian noise channel. This scheme is developed based on the generalization of the Quantize-and-Forward (QF) scheme and single block with two slots coding structure. 2) as the general performance measure of the slow fading channel, the common outage probability and the expected sum rate (total throughput) of the GQF scheme have been characterized. The numerical examples show that when the relay has no access to the CSI of the relay-destination link, the GQF scheme outperforms other relaying schemes, e.g., classic compress-and-forward (CF), decode-and-forward (DF) and amplify-and-forward (AF). 3) for a MAC channel with heterogeneous user channels and quality-of-service (QoS) requirements, individual outage probability and total throughput of the GQF scheme are also obtained and shown to outperform the classic CF scheme.
The European Union, China, and the United States in the Top-1% and Top-10% Layers of Most-Frequently-Cited Publications: Competition and Collaborations
Venue: arXiv cs.DL 2014
Year: 2014

The percentages of shares of world publications of the European Union and its member states, China, and the United States have been represented differently as a result of using different databases. An analytical variant of the Web-of-Science (of Thomson Reuters) enables us to study the dynamics in the world publication system in terms of the field-normalized top-1% and top-10% most-frequently-cited publications. Comparing the EU28, USA, and China at the global level shows a top-level dynamics that is different from the analysis in terms of shares of publications: the United States remains far more productive in the top-1% of all papers; China drops out of the competition for elite status; and the EU28 increased its share among the top-cited papers from 2000-2010. Some of the EU28 member states overtook the U.S. during this decade, but a clear divide remains between EU15 (Western Europe) and the Accession Countries. Network analysis shows that internationally co-authored top-1% publications perform far above expectation and also above top-10% ones. In 2005, China was embedded in this top-layer of internationally co-authored publications. These publications often involve more than a single European nation.