OpenRaiser/Intern-Atlas huggingface dataset:
The Intermittent Traveling Salesman Problem with Different Temperature Profiles: Greedy or not?
Venue: arXiv cs.DS 2017
Year: 2017

In this research, we discuss the intermittent traveling salesman problem (ITSP), which extends the traditional traveling salesman problem (TSP) by imposing temperature restrictions on each node. These additional constraints limit the maximum allowable visit time per node, and result in multiple visits for each node which cannot be serviced in a single visit. We discuss three different temperature increase and decrease functions, namely a linear, a quadratic and an exponential function. To solve the problem, we consider three different solution representations as part of a metaheuristic approach. We argue that in case of similar temperature increase and decrease profiles, it is always beneficial to apply a greedy approach, i.e. to process as much as possible given the current node temperature.
RIoTBench: A Real-time IoT Benchmark for Distributed Stream Processing Platforms
Venue: arXiv cs.DC 2017
Year: 2017

The Internet of Things (IoT) is an emerging technology paradigm where millions of sensors and actuators help monitor and manage, physical, environmental and human systems in real-time. The inherent closedloop responsiveness and decision making of IoT applications make them ideal candidates for using low latency and scalable stream processing platforms. Distributed Stream Processing Systems (DSPS) hosted on Cloud data-centers are becoming the vital engine for real-time data processing and analytics in any IoT software architecture. But the efficacy and performance of contemporary DSPS have not been rigorously studied for IoT applications and data streams. Here, we develop RIoTBench, a Realtime IoT Benchmark suite, along with performance metrics, to evaluate DSPS for streaming IoT applications. The benchmark includes 27 common IoT tasks classified across various functional categories and implemented as reusable micro-benchmarks. Further, we propose four IoT application benchmarks composed from these tasks, and that leverage various dataflow semantics of DSPS. The applications are based on common IoT patterns for data pre-processing, statistical summarization and predictive analytics. These are coupled with four stream workloads sourced from real IoT observations on smart cities and fitness, with peak streams rates that range from 500 to 10000 messages/sec and diverse frequency distributions. We validate the RIoTBench suite for the popular Apache Storm DSPS on the Microsoft Azure public Cloud, and present empirical observations. This suite can be used by DSPS researchers for performance analysis and resource scheduling, and by IoT practitioners to evaluate DSPS platforms.
Survey on Models and Techniques for Root-Cause Analysis
Venue: arXiv cs.AI 2017
Year: 2017

Automation and computer intelligence to support complex human decisions becomes essential to manage large and distributed systems in the Cloud and IoT era. Understanding the root cause of an observed symptom in a complex system has been a major problem for decades. As industry dives into the IoT world and the amount of data generated per year grows at an amazing speed, an important question is how to find appropriate mechanisms to determine root causes that can handle huge amounts of data or may provide valuable feedback in real-time. While many survey papers aim at summarizing the landscape of techniques for modelling system behavior and infering the root cause of a problem based in the resulting models, none of those focuses on analyzing how the different techniques in the literature fit growing requirements in terms of performance and scalability. In this survey, we provide a review of root-cause analysis, focusing on these particular aspects. We also provide guidance to choose the best root-cause analysis strategy depending on the requirements of a particular system and application.
Autotuning GPU Kernels via Static and Predictive Analysis
Venue: arXiv cs.DC 2017
Year: 2017

Optimizing the performance of GPU kernels is challenging for both human programmers and code generators. For example, CUDA programmers must set thread and block parameters for a kernel, but might not have the intuition to make a good choice. Similarly, compilers can generate working code, but may miss tuning opportunities by not targeting GPU models or performing code transformations. Although empirical autotuning addresses some of these challenges, it requires extensive experimentation and search for optimal code variants. This research presents an approach for tuning CUDA kernels based on static analysis that considers fine-grained code structure and the specific GPU architecture features. Notably, our approach does not require any program runs in order to discover near-optimal parameter settings. We demonstrate the applicability of our approach in enabling code autotuners such as Orio to produce competitive code variants comparable with empirical-based methods, without the high cost of experiments.
Peduncle Detection of Sweet Pepper for Autonomous Crop Harvesting - Combined Colour and 3D Information
Venue: arXiv cs.RO 2017
Year: 2017

This paper presents a 3D visual detection method for the challenging task of detecting peduncles of sweet peppers (Capsicum annuum) in the field. Cutting the peduncle cleanly is one of the most difficult stages of the harvesting process, where the peduncle is the part of the crop that attaches it to the main stem of the plant. Accurate peduncle detection in 3D space is therefore a vital step in reliable autonomous harvesting of sweet peppers, as this can lead to precise cutting while avoiding damage to the surrounding plant. This paper makes use of both colour and geometry information acquired from an RGB-D sensor and utilises a supervised-learning approach for the peduncle detection task. The performance of the proposed method is demonstrated and evaluated using qualitative and quantitative results (the Area-Under-the-Curve (AUC) of the detection precision-recall curve). We are able to achieve an AUC of 0.71 for peduncle detection on field-grown sweet peppers. We release a set of manually annotated 3D sweet pepper and peduncle images to assist the research community in performing further research on this topic.
Ultra Reliable Communication via Optimum Power Allocation for Type-I ARQ in Finite Block-Length
Venue: arXiv cs.IT 2017
Year: 2017

We analyze the performance of the type-I automatic repeat request (ARQ) protocol with ultra-reliability constraints. First, we show that achieving a very low packet outage probability by using an open loop setup is a difficult task. Thus, we introduce the ARQ protocol as a solution for achieving the required low outage probabilities for ultra reliable communication. For this protocol, we present an optimal power allocation scheme that would allow us to reach any outage probability target in the finite block-length regime. We formulate the power allocation problem as minimization of the average transmitted power under a given outage probability and maximum transmit power constraint. By utilizing the Karush-Kuhn-Tucker (KKT) conditions, we solve the optimal power allocation problem and provide a closed form solution. Next, we analyze the effect of implementing the ARQ protocol on the throughput. We show that by using the proposed power allocation scheme we can minimize the loss of throughput that is caused from the retransmissions. Furthermore, we analyze the effect of the feedback delay length in our scheme.
Security Game with Non-additive Utilities and Multiple Attacker Resources
Venue: arXiv cs.GT 2017
Year: 2017

There has been significant interest in studying security games for modeling the interplay of attacks and defenses on various systems involving critical infrastructure, financial system security, political campaigns, and civil safeguarding. However, existing security game models typically either assume additive utility functions, or that the attacker can attack only one target. Such assumptions lead to tractable analysis, but miss key inherent dependencies that exist among different targets in current complex networks. In this paper, we generalize the classical security game models to allow for non-additive utility functions. We also allow attackers to be able to attack multiple targets. We examine such a general security game from a theoretical perspective and provide a unified view. In particular, we show that each security game is equivalent to a combinatorial optimization problem over a set system $\varepsilon$, which consists of defender's pure strategy space. The key technique we use is based on the transformation, projection of a polytope, and the elipsoid method. This work settles several open questions in security game domain and significantly extends the state of-the-art of both the polynomial solvable and NP-hard class of the security game.
Structural Analysis of Hindi Phonetics and A Method for Extraction of Phonetically Rich Sentences from a Very Large Hindi Text Corpus
Venue: arXiv cs.CL 2017
Year: 2017

Automatic speech recognition (ASR) and Text to speech (TTS) are two prominent area of research in human computer interaction nowadays. A set of phonetically rich sentences is in a matter of importance in order to develop these two interactive modules of HCI. Essentially, the set of phonetically rich sentences has to cover all possible phone units distributed uniformly. Selecting such a set from a big corpus with maintaining phonetic characteristic based similarity is still a challenging problem. The major objective of this paper is to devise a criteria in order to select a set of sentences encompassing all phonetic aspects of a corpus with size as minimum as possible. First, this paper presents a statistical analysis of Hindi phonetics by observing the structural characteristics. Further a two stage algorithm is proposed to extract phonetically rich sentences with a high variety of triphones from the EMILLE Hindi corpus. The algorithm consists of a distance measuring criteria to select a sentence in order to improve the triphone distribution. Moreover, a special preprocessing method is proposed to score each triphone in terms of inverse probability in order to fasten the algorithm. The results show that the approach efficiently build uniformly distributed phonetically-rich corpus with optimum number of sentences.
Scale effects on spatially embedded contact networks
Venue: arXiv cs.SI 2017
Year: 2017

Spatial phenomena are subject to scale effects, but there are rarely studies addressing such effects on spatially embedded contact networks. There are two types of structure in these networks, network structure and spatial structure. The network structure has been actively studied. The spatial structure of these networks has received attention only in recent years. Certainly little is known whether the two structures respond to each other. This study examines the scale effects, in terms of spatial extent, on the network structure and the spatial structure of spatially embedded contact networks. Two issues are explored, how the two types of structures change in response to scale changes, and the range of the scale effects. Two sets of areal units, regular grids with 24 different levels of spatial extent and census units of three levels of spatial extent, are used to divide one observed and two reference random networks into multiple scales. Six metrics are used to represent the two structures. Results show different scale effects. In terms of the network structure, the properties of the observed network are sensitive to scale changes at fine scales. In comparison, the clustered spatial structure of the network is scale independent. The behaviors of the network structure are affected by the spatial structure. This information helps identify vulnerable households and communities to health risks and helps deploy intervention strategies to spatially targeted areas.
Adaptive local surface refinement based on LR NURBS and its application to contact
Venue: arXiv cs.CE 2017
Year: 2017

A novel adaptive local surface refinement technique based on Locally Refined Non-Uniform Rational B-Splines (LR NURBS) is presented. LR NURBS can model complex geometries exactly and are the rational extension of LR B-splines. The local representation of the parameter space overcomes the drawback of non-existent local refinement in standard NURBS-based isogeometric analysis. For a convenient embedding into general finite element code, the Bézier extraction operator for LR NURBS is formulated. An automatic remeshing technique is presented that allows adaptive local refinement and coarsening of LR NURBS. In this work, LR NURBS are applied to contact computations of 3D solids and membranes. For solids, LR NURBS-enriched finite elements are used to discretize the contact surfaces with LR NURBS finite elements, while the rest of the body is discretized by linear Lagrange finite elements. For membranes, the entire surface is discretized by LR NURBS. Various numerical examples are shown, and they demonstrate the benefit of using LR NURBS: Compared to uniform refinement, LR NURBS can achieve high accuracy at lower computational cost.
Mr. Doc: A Doctor Appointment Application System
Venue: arXiv cs.CY 2017
Year: 2017

Life is becoming too busy to get medical appointments in person and to maintain a proper health care. The main idea of this work is to provide ease and comfort to patients while taking appointment from doctors and it also resolves the problems that the patients has to face while making an appointment. The android application Mr.Doc acts as a client whereas the database containing the doctor's details, patient's details and appointment details is maintained by a website that acts as a server.
Dynamic Task Allocation for Crowdsourcing Settings
Venue: arXiv cs.LG 2017
Year: 2017

We consider the problem of optimal budget allocation for crowdsourcing problems, allocating users to tasks to maximize our final confidence in the crowdsourced answers. Such an optimized worker assignment method allows us to boost the efficacy of any popular crowdsourcing estimation algorithm. We consider a mutual information interpretation of the crowdsourcing problem, which leads to a stochastic subset selection problem with a submodular objective function. We present experimental simulation results which demonstrate the effectiveness of our dynamic task allocation method for achieving higher accuracy, possibly requiring fewer labels, as well as improving upon a previous method which is sensitive to the proportion of users to questions.
Scalable Bicriteria Algorithms for the Threshold Activation Problem in Online Social Networks
Venue: arXiv cs.SI 2017
Year: 2017

We consider the Threshold Activation Problem (TAP): given social network $G$ and positive threshold $T$, find a minimum-size seed set $A$ that can trigger expected activation of at least $T$. We introduce the first scalable, parallelizable algorithm with performance guarantee for TAP suitable for datasets with millions of nodes and edges; we exploit the bicriteria nature of solutions to TAP to allow the user to control the running time versus accuracy of our algorithm through a parameter $α\in (0,1)$: given $η> 0$, with probability $1 - η$ our algorithm returns a solution $A$ with expected activation greater than $T - 2 αT$, and the size of the solution $A$ is within factor $1 + 4 αT + \log ( T )$ of the optimal size. The algorithm runs in time $O \left( α^{-2}\log \left( n / η\right) (n + m) |A| \right)$, where $n$, $m$, refer to the number of nodes, edges in the network. The performance guarantee holds for the general triggering model of internal influence and also incorporates external influence, provided a certain condition is met on the cost-effectivity of seed selection.
Scheduling Maintenance Jobs in Networks
Venue: arXiv cs.DS 2017
Year: 2017

We investigate the problem of scheduling the maintenance of edges in a network, motivated by the goal of minimizing outages in transportation or telecommunication networks. We focus on maintaining connectivity between two nodes over time; for the special case of path networks, this is related to the problem of minimizing the busy time of machines. We show that the problem can be solved in polynomial time in arbitrary networks if preemption is allowed. If preemption is restricted to integral time points, the problem is NP-hard and in the non-preemptive case we give strong non-approximability results. Furthermore, we give tight bounds on the power of preemption, that is, the maximum ratio of the values of non-preemptive and preemptive optimal solutions. Interestingly, the preemptive and the non-preemptive problem can be solved efficiently on paths, whereas we show that mixing both leads to a weakly NP-hard problem that allows for a simple 2-approximation.
Performance Characterization of a Real-Time Massive MIMO System with LOS Mobile Channels
Venue: arXiv cs.IT 2017
Year: 2017

The first measured results for massive MIMO performance in a line-of-sight (LOS) scenario with moderate mobility are presented, with 8 users served in real-time using a 100-antenna base Station (BS) at 3.7 GHz. When such a large number of channels dynamically change, the inherent propagation and processing delay has a critical relationship with the rate of change, as the use of outdated channel information can result in severe detection and precoding inaccuracies. For the downlink (DL) in particular, a time division duplex (TDD) configuration synonymous with massive multiple-input, multiple-output (MIMO) deployments could mean only the uplink (UL) is usable in extreme cases. Therefore, it is of great interest to investigate the impact of mobility on massive MIMO performance and consider ways to combat the potential limitations. In a mobile scenario with moving cars and pedestrians, the massive MIMO channel is sampled across many points in space to build a picture of the overall user orthogonality, and the impact of both azimuth and elevation array configurations are considered. Temporal analysis is also conducted for vehicles moving up to 29km/h and real-time bit error rates (BERs) for both the UL and DL without power control are presented. For a 100-antenna system, it is found that the channel state information (CSI) update rate requirement may increase by 7 times when compared to an 8-antenna system, whilst the power control update rate could be decreased by at least 5 times relative to a single antenna system.
Emergence of Selective Invariance in Hierarchical Feed Forward Networks
Venue: arXiv cs.LG 2017
Year: 2017

Many theories have emerged which investigate how in- variance is generated in hierarchical networks through sim- ple schemes such as max and mean pooling. The restriction to max/mean pooling in theoretical and empirical studies has diverted attention away from a more general way of generating invariance to nuisance transformations. We con- jecture that hierarchically building selective invariance (i.e. carefully choosing the range of the transformation to be in- variant to at each layer of a hierarchical network) is im- portant for pattern recognition. We utilize a novel pooling layer called adaptive pooling to find linear pooling weights within networks. These networks with the learnt pooling weights have performances on object categorization tasks that are comparable to max/mean pooling networks. In- terestingly, adaptive pooling can converge to mean pooling (when initialized with random pooling weights), find more general linear pooling schemes or even decide not to pool at all. We illustrate the general notion of selective invari- ance through object categorization experiments on large- scale datasets such as SVHN and ILSVRC 2012.
Towards Optimal Distributed Node Scheduling in a Multihop Wireless Network through Local Voting
Venue: arXiv cs.NI 2017
Year: 2017

In a multihop wireless network, it is crucial but challenging to schedule transmissions in an efficient and fair manner. In this paper, a novel distributed node scheduling algorithm, called Local Voting, is proposed. This algorithm tries to semi-equalize the load (defined as the ratio of the queue length over the number of allocated slots) through slot reallocation based on local information exchange. The algorithm stems from the finding that the shortest delivery time or delay is obtained when the load is semi-equalized throughout the network. In addition, we prove that, with Local Voting, the network system converges asymptotically towards the optimal scheduling. Moreover, through extensive simulations, the performance of Local Voting is further investigated in comparison with several representative scheduling algorithms from the literature. Simulation results show that the proposed algorithm achieves better performance than the other distributed algorithms in terms of average delay, maximum delay, and fairness. Despite being distributed, the performance of Local Voting is also found to be very close to a centralized algorithm that is deemed to have the optimal performance.
Ties That Bind - Characterizing Classes by Attributes and Social Ties
Venue: arXiv cs.SI 2017
Year: 2017

Given a set of attributed subgraphs known to be from different classes, how can we discover their differences? There are many cases where collections of subgraphs may be contrasted against each other. For example, they may be assigned ground truth labels (spam/not-spam), or it may be desired to directly compare the biological networks of different species or compound networks of different chemicals. In this work we introduce the problem of characterizing the differences between attributed subgraphs that belong to different classes. We define this characterization problem as one of partitioning the attributes into as many groups as the number of classes, while maximizing the total attributed quality score of all the given subgraphs. We show that our attribute-to-class assignment problem is NP-hard and an optimal $(1 - 1/e)$-approximation algorithm exists. We also propose two different faster heuristics that are linear-time in the number of attributes and subgraphs. Unlike previous work where only attributes were taken into account for characterization, here we exploit both attributes and social ties (i.e. graph structure). Through extensive experiments, we compare our proposed algorithms, show findings that agree with human intuition on datasets from Amazon co-purchases, Congressional bill sponsorships, and DBLP co-authorships. We also show that our approach of characterizing subgraphs is better suited for sense-making than discriminating classification approaches.