OpenRaiser/Intern-Atlas huggingface dataset:
Online Visual Analytics of Text Streams
Venue: arXiv cs.IR 2015
Year: 2015

We present an online visual analytics approach to helping users explore and understand hierarchical topic evolution in high-volume text streams. The key idea behind this approach is to identify representative topics in incoming documents and align them with the existing representative topics that they immediately follow (in time). To this end, we learn a set of streaming tree cuts from topic trees based on user-selected focus nodes. A dynamic Bayesian network model has been developed to derive the tree cuts in the incoming topic trees to balance the fitness of each tree cut and the smoothness between adjacent tree cuts. By connecting the corresponding topics at different times, we are able to provide an overview of the evolving hierarchical topics. A sedimentation-based visualization has been designed to enable the interactive analysis of streaming text data from global patterns to local details. We evaluated our method on real-world datasets and the results are generally favorable.
Using Linear Constraints for Logic Program Termination Analysis
Venue: arXiv cs.AI 2015
Year: 2015

It is widely acknowledged that function symbols are an important feature in answer set programming, as they make modeling easier, increase the expressive power, and allow us to deal with infinite domains. The main issue with their introduction is that the evaluation of a program might not terminate and checking whether it terminates or not is undecidable. To cope with this problem, several classes of logic programs have been proposed where the use of function symbols is restricted but the program evaluation termination is guaranteed. Despite the significant body of work in this area, current approaches do not include many simple practical programs whose evaluation terminates. In this paper, we present the novel classes of rule-bounded and cycle-bounded programs, which overcome different limitations of current approaches by performing a more global analysis of how terms are propagated from the body to the head of rules. Results on the correctness, the complexity, and the expressivity of the proposed approach are provided.
Articulated Pose Estimation Using Hierarchical Exemplar-Based Models
Venue: arXiv cs.CV 2015
Year: 2015

Exemplar-based models have achieved great success on localizing the parts of semi-rigid objects. However, their efficacy on highly articulated objects such as humans is yet to be explored. Inspired by hierarchical object representation and recent application of Deep Convolutional Neural Networks (DCNNs) on human pose estimation, we propose a novel formulation that incorporates both hierarchical exemplar-based models and DCNNs in the spatial terms. Specifically, we obtain more expressive spatial models by assuming independence between exemplars at different levels in the hierarchy; we also obtain stronger spatial constraints by inferring the spatial relations between parts at the same level. As our method strikes a good balance between expressiveness and strength of spatial models, it is both effective and generalizable, achieving state-of-the-art results on different benchmarks: Leeds Sports Dataset and CUB-200-2011.
Amortized Averaging Algorithms for Approximate Consensus
Venue: arXiv cs.DC 2015
Year: 2015

We introduce a new class of distributed algorithms for the approximate consensus problem in dynamic rooted networks, which we call amortized averaging algorithms. They are deduced from ordinary averaging algorithms by adding a value-gathering phase before each value update. This allows their decision time to drop from being exponential in the number $n$ of processes to being linear under the assumption that each process knows $n$. In particular, the amortized midpoint algorithm, which achieves a linear decision time, works in completely anonymous dynamic rooted networks where processes can exchange and store continuous values, and under the assumption that the number of processes is known to all processes. We then study the way amortized averaging algorithms degrade when communication graphs are from time to time non rooted, or with a wrong estimate of the number of processes. Finally, we analyze the amortized midpoint algorithm under the additional constraint that processes can only store and send quantized values, and get as a corollary that the 2-set consensus problem is solvable in linear time in any rooted dynamic network model when allowing all decision values to be in the range of initial values.
Kinetic Clustering of Points on the Line
Venue: arXiv cs.CG 2015
Year: 2015

The problem of clustering a set of points moving on the line consists of the following: given positive integers n and k, the initial position and the velocity of n points, find an optimal k-clustering of the points. We consider two classical quality measures for the clustering: minimizing the sum of the clusters diameters and minimizing the maximum diameter of a cluster. For the former, we present polynomial-time algorithms under some assumptions and, for the latter, a (2.71 + epsilon)-approximation.
A proposal project for a blind image quality assessment by learning distortions from the full reference image quality assessments
Venue: arXiv cs.MM 2015
Year: 2015

This short paper presents a perspective plan to build a null reference image quality assessment. Its main goal is to deliver both the objective score and the distortion map for a given distorted image without the knowledge of its reference image.
Read-once polynomials: How many summands suffice?
Venue: arXiv cs.CC 2015
Year: 2015

An arithmetic read-once formula (ROF) is a formula (circuit of fan-out 1) over $+, \times$ where each variable labels at most one leaf. Every multilinear polynomial can be expressed as the sum of ROFs. In this work, we prove, for certain multilinear polynomials, a tight lower bound on the number of summands in such an expression.
Dropout Training of Matrix Factorization and Autoencoder for Link Prediction in Sparse Graphs
Venue: arXiv cs.LG 2015
Year: 2015

Matrix factorization (MF) and Autoencoder (AE) are among the most successful approaches of unsupervised learning. While MF based models have been extensively exploited in the graph modeling and link prediction literature, the AE family has not gained much attention. In this paper we investigate both MF and AE's application to the link prediction problem in sparse graphs. We show the connection between AE and MF from the perspective of multiview learning, and further propose MF+AE: a model training MF and AE jointly with shared parameters. We apply dropout to training both the MF and AE parts, and show that it can significantly prevent overfitting by acting as an adaptive regularization. We conduct experiments on six real world sparse graph datasets, and show that MF+AE consistently outperforms the competing methods, especially on datasets that demonstrate strong non-cohesive structures.
Efficient Algorithms for Personalized PageRank
Venue: arXiv cs.DS 2015
Year: 2015

We present new, more efficient algorithms for estimating random walk scores such as Personalized PageRank from a given source node to one or several target nodes. These scores are useful for personalized search and recommendations on networks including social networks, user-item networks, and the web. Past work has proposed using Monte Carlo or using linear algebra to estimate scores from a single source to every target, making them inefficient for a single pair. Our contribution is a new bidirectional algorithm which combines linear algebra and Monte Carlo to achieve significant speed improvements. On a diverse set of six graphs, our algorithm is 70x faster than past state-of-the-art algorithms. We also present theoretical analysis: while past algorithms require $Ω(n)$ time to estimate a random walk score of typical size $\frac{1}{n}$ on an $n$-node graph to a given constant accuracy, our algorithm requires only $O(\sqrt{m})$ expected time for an average target, where $m$ is the number of edges, and is provably accurate. In addition to our core bidirectional estimator for personalized PageRank, we present an alternative algorithm for undirected graphs, a generalization to arbitrary walk lengths and Markov Chains, an algorithm for personalized search ranking, and an algorithm for sampling random paths from a given source to a given set of targets. We expect our bidirectional methods can be extended in other ways and will be useful subroutines in other graph analysis problems.
Graphical Exchange Mechanisms
Venue: arXiv cs.GT 2015
Year: 2015

Consider an exchange mechanism which accepts diversified offers of various commodities and redistributes everything it receives. We impose certain conditions of fairness and convenience on such a mechanism and show that it admits unique prices, which equalize the value of offers and returns for each individual. We next define the complexity of a mechanism in terms of certain integers $τ_{ij},π_{ij}$ and $k_{i}$ that represent the time required to exchange $i$ for $j$, the difficulty in determining the exchange ratio, and the dimension of the message space. We show that there are a finite number of minimally complex mechanisms, in each of which all trade is conducted through markets for commodity pairs. Finally we consider minimal mechanisms with smallest worst-case complexities $τ=\maxτ_{ij}$ and $π=\maxπ_{ij}$. For $m>3$ commodities, there are precisely three such mechanisms, one of which has a distinguished commodity -- the money -- that serves as the sole medium of exchange. As $m\rightarrow \infty$ the money mechanism is the only one with bounded $\left( π,τ\right) $.
Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
Venue: arXiv cs.DS 2015
Year: 2015

In the bin covering problem, the goal is to fill as many bins as possible up to a certain minimal level with a given set of items of different sizes. Online variants, in which the items arrive one after another and have to be packed immediately on their arrival without knowledge about the future items, have been studied extensively in the literature. We study the simplest possible online algorithm Dual Next-Fit, which packs all arriving items into the same bin until it is filled and then proceeds with the next bin in the same manner. The competitive ratio of this and any other reasonable online algorithm is $1/2$. We study Dual Next-Fit in a probabilistic setting where the item sizes are chosen i.i.d.\ according to a discrete distribution and we prove that, for every distribution, its expected competitive ratio is at least $1/2+ε$ for a constant $ε>0$ independent of the distribution. We also prove an upper bound of $2/3$ and better lower bounds for certain restricted classes of distributions. Finally, we prove that the expected competitive ratio equals, for a large class of distributions, the random-order ratio, which is the expected competitive ratio when adversarially chosen items arrive in uniformly random order.
Smoothed Lp-Minimization for Green Cloud-RAN with User Admission Control
Venue: arXiv cs.IT 2015
Year: 2015

The cloud radio access network (Cloud-RAN) has recently been proposed as one cost-effective and energy-efficient technique for 5G wireless networks. By moving the signal processing functionality to a single baseband unit (BBU) pool, centralized signal processing and resource allocation are enabled in Cloud-RAN, thereby providing the promise of improving the energy efficiency via effective network adaptation and interference management. In this paper, we propose a holistic sparse optimization framework to design green Cloud-RAN by taking into consideration the power consumption of the fronthaul links, multicast services, as well as user admission control. Specifically, we first identify the sparsity structures in the solutions of both the network power minimization and user admission control problems. However, finding the optimal sparsity structures turns out to be NP-hard, with the coupled challenges of the l0-norm based objective functions and the nonconvex quadratic QoS constraints due to multicast beamforming. In contrast to the previous works on convex but non-smooth sparsity inducing approaches, e.g., the group sparse beamforming algorithm based on the mixed l1/l2-norm relaxation [1], we adopt the nonconvex but smoothed lp-minimization (0 < p <= 1) approach to promote sparsity in the multicast setting, thereby enabling efficient algorithm design based on the principle of the majorization-minimization (MM) algorithm and the semidefinite relaxation (SDR) technique. In particular, an iterative reweighted-l2 algorithm is developed, which will converge to a Karush-Kuhn-Tucker (KKT) point of the relaxed smoothed lp-minimization problem from the SDR technique. We illustrate the effectiveness of the proposed algorithms with extensive simulations for network power minimization and user admission control in multicast Cloud-RAN.
Tester Interactivity makes a Difference in Search-Based Software Testing: A Controlled Experiment
Venue: arXiv cs.SE 2015
Year: 2015

Context: Search-based software testing promises to provide users with the ability to generate high-quality test cases, and hence increase product quality, with a minimal increase in the time and effort required. One result that emerged out of a previous study to investigate the application of search-based software testing (SBST) in an industrial setting was the development of the Interactive Search-Based Software Testing (ISBST) system. ISBST allows users to interact with the underlying SBST system, guiding the search and assessing the results. An industrial evaluation indicated that the ISBST system could find test cases that are not created by testers employing manual techniques. The validity of the evaluation was threatened, however, by the low number of participants. Objective: This paper presents a follow-up study, to provide a more rigorous evaluation of the ISBST system. Method: To assess the ISBST system a two-way crossover controlled experiment was conducted with 58 students taking a Verification and Validation course. The NASA Task Load Index (NASA-TLX) is used to assess the workload experienced by the participants in the experiment. Results: The experimental results validated the hypothesis that the ISBST system generates test cases that are not found by the same participants employing manual testing techniques. A follow-up laboratory experiment also investigates the importance of interaction in obtaining the results. In addition to this main result, the subjective workload was assessed for each participant by means of the NASA-TLX tool. The evaluation showed that, while the ISBST system required more effort from the participants, they achieved the same performance. Conclusions: The paper provides evidence that the ISBST system develops test cases that are not found by manual techniques, and that interaction plays an important role in achieving that result.
Declarative, Secure, Convergent Edge Computation
Venue: arXiv cs.DC 2015
Year: 2015

Eventual consistency is a more natural model than strong consistency for a distributed system, since it is closer to the underlying physical reality. Therefore, we propose that it is important to find a programming model that is both congenial to developers and supports eventual consistency. In particular, we consider that a crucial test for such a model is that it should support edge computation in a both natural and secure way. We present a preliminary work report with an initial solution, called Lasp, which resembles a concurrent functional language while naturally supporting an eventually consistent coordination-free distribution model.
Software-Defined Hyper-Cellular Architecture for Green and Elastic Wireless Access
Venue: arXiv cs.NI 2015
Year: 2015

To meet the surging demand of increasing mobile Internet traffic from diverse applications while maintaining moderate energy cost, the radio access network (RAN) of cellular systems needs to take a green path into the future, and the key lies in providing elastic service to dynamic traffic demands. To achieve this, it is time to rethink RAN architectures and expect breakthroughs. In this article, we review the state-of-art literature which aims to renovate RANs from the perspectives of control-traffic decoupled air interface, cloud-based RANs, and software-defined RANs. We then propose a software-defined hyper-cellular architecture (SDHCA) that identifies a feasible way of integrating the above three trends to enable green and elastic wireless access. We further present key enabling technologies to realize SDHCA, including separation of the air interface, green base station operations, and base station functions virtualization, followed by our hardware testbed for SDHCA. Besides, we summarize several future research issues worth investigating.
An Operator for Entity Extraction in MapReduce
Venue: arXiv cs.DB 2015
Year: 2015

Dictionary-based entity extraction involves finding mentions of dictionary entities in text. Text mentions are often noisy, containing spurious or missing words. Efficient algorithms for detecting approximate entity mentions follow one of two general techniques. The first approach is to build an index on the entities and perform index lookups of document substrings. The second approach recognizes that the number of substrings generated from documents can explode to large numbers, to get around this, they use a filter to prune many such substrings which do not match any dictionary entity and then only verify the remaining substrings if they are entity mentions of dictionary entities, by means of a text join. The choice between the index-based approach and the filter & verification-based approach is a case-to-case decision as the best approach depends on the characteristics of the input entity dictionary, for example frequency of entity mentions. Choosing the right approach for the setting can make a substantial difference in execution time. Making this choice is however non-trivial as there are parameters within each of the approaches that make the space of possible approaches very large. In this paper, we present a cost-based operator for making the choice among execution plans for entity extraction. Since we need to deal with large dictionaries and even larger large datasets, our operator is developed for implementations of MapReduce distributed algorithms.
Conditions for Normative Decision Making at the Fire Ground
Venue: arXiv cs.AI 2015
Year: 2015

We discuss the changes in an attitude to decision making at the fire ground. The changes are driven by the recent technological shift. The emerging new approaches in sensing and data processing (under common umbrella of Cyber-Physical Systems) allow for leveling off the gap, between humans and machines, in perception of the fire ground. Furthermore, results from descriptive decision theory question the rationality of human choices. This creates the need for searching and testing new approaches for decision making during emergency. We propose the framework that addresses this need. The primary feature of the framework are possibilities for incorporation of normative and prescriptive approaches to decision making. The framework also allows for comparison of the performance of decisions, between human and machine.
Optimal Las Vegas reduction from one-way set reconciliation to error correction
Venue: arXiv cs.DS 2015
Year: 2015

Suppose we have two players $A$ and $C$, where player $A$ has a string $s[0..u-1]$ and player $C$ has a string $t[0..u-1]$ and none of the two players knows the other's string. Assume that $s$ and $t$ are both over an integer alphabet $[σ]$, where the first string contains $n$ non-zero entries. We would wish to answer to the following basic question. Assuming that $s$ and $t$ differ in at most $k$ positions, how many bits does player $A$ need to send to player $C$ so that he can recover $s$ with certainty? Further, how much time does player $A$ need to spend to compute the sent bits and how much time does player $C$ need to recover the string $s$? This problem has a certain number of applications, for example in databases, where each of the two parties possesses a set of $n$ key-value pairs, where keys are from the universe $[u]$ and values are from $[σ]$ and usually $n\ll u$. In this paper, we show a time and message-size optimal Las Vegas reduction from this problem to the problem of systematic error correction of $k$ errors for strings of length $Θ(n)$ over an alphabet of size $2^{Θ(\logσ+\log (u/n))}$. The additional running time incurred by the reduction is linear randomized for player $A$ and linear deterministic for player $B$, but the correction works with certainty. When using the popular Reed-Solomon codes, the reduction gives a protocol that transmits $O(k(\log u+\logσ))$ bits and runs in time $O(n\cdot\mathrm{polylog}(n)(\log u+\logσ))$ for all values of $k$. The time is randomized for player $A$ (encoding time) and deterministic for player $C$ (decoding time). The space is optimal whenever $k\leq (uσ)^{1-Ω(1)}$.
Relay Divide & Rule Technique to Solve Energy Hole Problem for Wireless Sensor Network
Venue: arXiv cs.NI 2015
Year: 2015

In remote sensor system, sensor hubs have the restricted battery power, so to use the vitality in a more productive manner a few creator's created a few strategies, yet at the same time there is have to decrease the vitality utilization of hubs. In this paper, we presented another method called as 'Partition and Rule strategy' to unravel the scope dividing so as to open the system field into subfield and next maintain a strategic distance from the vitality gap issue with the assistance of static bunching. Essentially, in gap and run plan system range is isolated into three locales to be specific internal, center and external to conquer the issue of vitality utilization. We execute this work in NS-2 and our recreation results demonstrate that our system is far superior than old procedures.
Smart Data Pricing Models for Internet-of-Things (IoT): A Bundling Strategy Approach
Venue: arXiv cs.GT 2015
Year: 2015

Internet of things (IoT) has emerged as a new paradigm for the future Internet. In IoT, enormous devices are connected to the Internet and thereby being a huge data source for numerous applications. In this article, we focus on addressing data management in IoT through using a smart data pricing (SDP) approach. With SDP, data can be managed flexibly and efficiently through intelligent and adaptive incentive mechanisms. Moreover, it is a major source of revenue for providers and partners. We propose a new pricing scheme for IoT service providers to determine the sensing data buying price and IoT service subscription fee offered to sensor owners and service users, respectively. Additionally, we adopt the bundling strategy that allows multiple providers to form a coalition and bid their services as a bundle, attracting more users and achieving higher revenue. Finally, we outline some important open research issues for SDP and IoT.
Computing the Complete Pareto Front
Venue: arXiv cs.DS 2015
Year: 2015

We give an efficient algorithm to enumerate all elements of a Pareto front in a multi-objective optimization problem in which the space of values is finite for all objectives. Our algorithm uses a feasibility check for a search space element as an oracle and minimizes the number of oracle calls that are necessary to identify the Pareto front of the problem. Given a $k$-dimensional search space in which each dimension has $n$ elements, it needs $p \cdot (k \cdot \lceil \log_2 n \rceil + 1) + ψ(p)$ oracle calls, where $p$ is the size of the Pareto front and $ψ(p)$ is the number of greatest elements of the part of the search space that is not dominated by the Pareto front elements. We show that this number of oracle calls is essentially optimal as approximately $p \cdot k \cdot \log_2 n$ oracle calls are needed to identify the Pareto front elements in sparse Pareto sets and $ψ(p)$ calls are needed to show that no element is missing in the set of Pareto front elements found.