OpenRaiser/Intern-Atlas huggingface dataset:
Quantifying the Effect of Sentiment on Information Diffusion in Social Media
Venue: arXiv cs.SI 2015
Year: 2015

Social media have become the main vehicle of information production and consumption online. Millions of users every day log on their Facebook or Twitter accounts to get updates and news, read about their topics of interest, and become exposed to new opportunities and interactions. Although recent studies suggest that the contents users produce will affect the emotions of their readers, we still lack a rigorous understanding of the role and effects of contents sentiment on the dynamics of information diffusion. This work aims at quantifying the effect of sentiment on information diffusion, to understand: (i) whether positive conversations spread faster and/or broader than negative ones (or vice-versa); (ii) what kind of emotions are more typical of popular conversations on social media; and, (iii) what type of sentiment is expressed in conversations characterized by different temporal dynamics. Our findings show that, at the level of contents, negative messages spread faster than positive ones, but positive ones reach larger audiences, suggesting that people are more inclined to share and favorite positive contents, the so-called positive bias. As for the entire conversations, we highlight how different temporal dynamics exhibit different sentiment patterns: for example, positive sentiment builds up for highly-anticipated events, while unexpected events are mainly characterized by negative sentiment. Our contribution is a milestone to understand how the emotions expressed in short texts affect their spreading in online social ecosystems, and may help to craft effective policies and strategies for content generation and diffusion.
The 12 prophets dataset
Venue: arXiv cs.GR 2015
Year: 2015

The "Ajeijadinho 3D" project is an initiative supported by the University of São Paulo (Museum of Science and Dean of Culture and Extension), which involves the 3D digitization of art works of Brazilian sculptor Antonio Francisco Lisboa, better known as Aleijadinho. The project made use of advanced acquisition and processing of 3D meshes for preservation and dissemination of the cultural heritage. The dissemination occurs through a Web portal, so that the population has the opportunity to meet the art works in detail using 3D visualization and interaction. The portal address is http://www.aleijadinho3d.icmc.usp.br. The 3D acquisitions were conducted over a week at the end of July 2013 in the cities of Ouro Preto, MG, Brazil and Congonhas do Campo, MG, Brazil. The scanning was done with a special equipment supplied by company Leica Geosystems, which allowed the work to take place at distances between 10 and 30 meters, defining a non-invasive procedure, simplified logistics, and without the need for preparation or isolation of the sites. In Ouro Preto, we digitized the churches of Francisco of Assis, Our Lady of Carmo, and Our Lady of Mercy; in Congonhas do Campo we scanned the entire Sanctuary of Bom Jesus de Matosinhos and his 12 prophets. Once scanned, the art works went through a long process of preparation, which required careful handling of meshes done by experts from the University of São Paulo in partnership with company Imprimate.
Avoiding Spoilers in Fan Wikis of Episodic Fiction
Venue: arXiv cs.DL 2015
Year: 2015

A variety of fan-based wikis about episodic fiction (e.g., television shows, novels, movies) exist on the World Wide Web. These wikis provide a wealth of information about complex stories, but if readers are behind in their viewing they run the risk of encountering "spoilers" -- information that gives away key plot points before the intended time of the show's writers. Enterprising readers might browse the wiki in a web archive so as to view the page prior to a specific episode date and thereby avoid spoilers. Unfortunately, due to how web archives choose the "best" page, it is still possible to see spoilers (especially in sparse archives). In this paper we discuss how to use Memento to avoid spoilers. Memento uses TimeGates to determine which best archived page to give back to the user, currently using a minimum distance heuristic. We quantify how this heuristic is inadequate for avoiding spoilers, analyzing data collected from fan wikis and the Internet Archive. We create an algorithm for calculating the probability of encountering a spoiler in a given wiki article. We conduct an experiment with 16 wiki sites for popular television shows. We find that 38% of those pages are unavailable in the Internet Archive. We find that when accessing fan wiki pages in the Internet Archive there is as much as a 66% chance of encountering a spoiler. Using sample access logs from the Internet Archive, we find that 19% of actual requests to the Wayback Machine for wikia.com pages ended in spoilers. We suggest the use of a different minimum distance heuristic, minpast, for wikis, using the desired datetime as an upper bound.
Upper bound on the number of steps for solving the subset sum problem by the Branch-and-Bound method
Venue: arXiv cs.DS 2015
Year: 2015

We study the computational complexity of one of the particular cases of the knapsack problem: the subset sum problem. For solving this problem we consider one of the basic variants of the Branch-and-Bound method in which any sub-problem is decomposed along the free variable with the maximal weight. By the complexity of solving a problem by the Branch-and-Bound method we mean the number of steps required for solving the problem by this method. In the paper we obtain upper bounds on the complexity of solving the subset sum problem by the Branch-and-Bound method. These bounds can be easily computed from the input data of the problem. So these bounds can be used for the the preliminary estimation of the computational resources required for solving the subset sum problem by the Branch-and-Bound method.
A QoS Guarantee Strategy for Multimedia Conferencing based on Bayesian Networks
Venue: arXiv cs.MM 2015
Year: 2015

Service Oriented Architecture (SOA) is commonly employed in the design and implementation of web service systems. The key technology to enable media communications in the context of SOA is the Service Oriented Communication. To exploit the advantage of SOA, we design and implement a web-based multimedia conferencing system that provides users with a hybrid orchestration of web and communication services. As the current SOA lacks effective QoS guarantee solutions for multimedia services, the user satisfaction is greatly challenged with QoS violations, e.g., low video PSNR (Peak Signal-to-Noise Ratio) and long playback delay. Motivated by addressing the critical problem, we firstly employ the Business Process Execution Language (BPEL) service engine for the hybrid services orchestration and execution. Secondly, we propose a novel context-aware approach to quantify and leverage the causal relationships between QoS metrics and available contexts based on Bayesian networks (CABIN). This approach includes three phases: (1) information discretization, (2) causal relationship profiling, and (3) optimal context tuning. We implement CABIN in a real-life multimedia conferencing system and compare its performance with existing delay and throughput oriented schemes. Experimental results show that CABIN outperforms the competing approaches in improving the video quality in terms of PSNR. It also provides a one-stop shop controls both the web and communication services.
Study on Scheduling Techniques for Ultra Dense Small Cell Networks
Venue: arXiv cs.IT 2015
Year: 2015

The most promising approach to enhance network capacity for the next generation of wireless cellular networks (5G) is densification, which benefits from the extensive spatial reuse of the spectrum and the reduced distance between transmitters and receivers. In this paper, we examine the performance of different schedulers in ultra dense small cell deployments. Due to the stronger line of sight (LOS) at low inter-site distances (ISDs), we discuss that the Rician fading channel model is more suitable to study network performance than the Rayleigh one, and model the Rician K factor as a function of distance between the user equipment (UE) and its serving base station (BS). We also construct a cross-correlation shadowing model that takes into account the ISD, and finally investigate potential multi-user diversity gains in ultra dense small cell deployments by comparing the performances of proportional fair (PF) and round robin (RR) schedulers. Our study shows that as network becomes denser, the LOS component starts to dominate the path loss model which significantly increases the interference. Simulation results also show that multi-user diversity is considerably reduced at low ISDs, and thus the PF scheduling gain over the RR one is small, around 10% in terms of cell throughput. As a result, the RR scheduling may be preferred for dense small cell deployments due to its simplicity. Despite both the interference aggravation as well as the multi-user diversity loss, network densification is still worth it from a capacity view point.
Extreme Extraction: Only One Hour per Relation
Venue: arXiv cs.CL 2015
Year: 2015

Information Extraction (IE) aims to automatically generate a large knowledge base from natural language text, but progress remains slow. Supervised learning requires copious human annotation, while unsupervised and weakly supervised approaches do not deliver competitive accuracy. As a result, most fielded applications of IE, as well as the leading TAC-KBP systems, rely on significant amounts of manual engineering. Even "Extreme" methods, such as those reported in Freedman et al. 2011, require about 10 hours of expert labor per relation. This paper shows how to reduce that effort by an order of magnitude. We present a novel system, InstaRead, that streamlines authoring with an ensemble of methods: 1) encoding extraction rules in an expressive and compositional representation, 2) guiding the user to promising rules based on corpus statistics and mined resources, and 3) introducing a new interactive development cycle that provides immediate feedback --- even on large datasets. Experiments show that experts can create quality extractors in under an hour and even NLP novices can author good extractors. These extractors equal or outperform ones obtained by comparably supervised and state-of-the-art distantly supervised approaches.
Parikh matrices and Parikh Rewriting Systems
Venue: arXiv cs.FL 2015
Year: 2015

Since the introduction of the Parikh matrix mapping, its injectivity problem is on top of the list of open problems in this topic. In 2010 Salomaa provided a solution for the ternary alphabet in terms of a Thue system with an additional feature called counter. This paper proposes the notion of a Parikh rewriting system as a generalization and systematization of Salomaa's result. It will be shown that every Parikh rewriting system induces a Thue system without counters that serves as a feasible solution to the injectivity problem.
Target Tracking In Real Time Surveillance Cameras and Videos
Venue: arXiv cs.CV 2015
Year: 2015

Security concerns has been kept on increasing, so it is important for everyone to keep their property safe from thefts and destruction. So the need for surveillance techniques are also increasing. The system has been developed to detect the motion in a video. A system has been developed for real time applications by using the techniques of background subtraction and frame differencing. In this system, motion is detected from the webcam or from the real time video. Background subtraction and frames differencing method has been used to detect the moving target. In background subtraction method, current frame is subtracted from the referenced frame and then the threshold is applied. If the difference is greater than the threshold then it is considered as the pixel from the moving object, otherwise it is considered as background pixel. Similarly, two frames difference method takes difference between two continuous frames. Then that resultant difference frame is thresholded and the amount of difference pixels is calculated.
Beyond Triangles: A Distributed Framework for Estimating 3-profiles of Large Graphs
Venue: arXiv cs.SI 2015
Year: 2015

We study the problem of approximating the $3$-profile of a large graph. $3$-profiles are generalizations of triangle counts that specify the number of times a small graph appears as an induced subgraph of a large graph. Our algorithm uses the novel concept of $3$-profile sparsifiers: sparse graphs that can be used to approximate the full $3$-profile counts for a given large graph. Further, we study the problem of estimating local and ego $3$-profiles, two graph quantities that characterize the local neighborhood of each vertex of a graph. Our algorithm is distributed and operates as a vertex program over the GraphLab PowerGraph framework. We introduce the concept of edge pivoting which allows us to collect $2$-hop information without maintaining an explicit $2$-hop neighborhood list at each vertex. This enables the computation of all the local $3$-profiles in parallel with minimal communication. We test out implementation in several experiments scaling up to $640$ cores on Amazon EC2. We find that our algorithm can estimate the $3$-profile of a graph in approximately the same time as triangle counting. For the harder problem of ego $3$-profiles, we introduce an algorithm that can estimate profiles of hundreds of thousands of vertices in parallel, in the timescale of minutes.
Adaptive Digital Scan Variable Pixels
Venue: arXiv cs.CV 2015
Year: 2015

The square and rectangular shape of the pixels in the digital images for sensing and display purposes introduces several inaccuracies in the representation of digital images. The major disadvantage of square pixel shapes is the inability to accurately capture and display the details in the objects having variable orientations to edges, shapes and regions. This effect can be observed by the inaccurate representation of diagonal edges in low resolution square pixel images. This paper explores a less investigated idea of using variable shaped pixels for improving visual quality of image scans without increasing the square pixel resolution. The proposed adaptive filtering technique reports an improvement in image PSNR.
Seeing Shapes in Clouds: On the Performance-Cost trade-off for Heterogeneous Infrastructure-as-a-Service
Venue: arXiv cs.DC 2015
Year: 2015

In the near future FPGAs will be available by the hour, however this new Infrastructure as a Service (IaaS) usage mode presents both an opportunity and a challenge: The opportunity is that programmers can potentially trade resources for performance on a much larger scale, for much shorter periods of time than before. The challenge is in finding and traversing the trade-off for heterogeneous IaaS that guarantees increased resources result in the greatest possible increased performance. Such a trade-off is Pareto optimal. The Pareto optimal trade-off for clusters of heterogeneous resources can be found by solving multiple, multi-objective optimisation problems, resulting in an optimal allocation of tasks to the available platforms. Solving these optimisation programs can be done using simple heuristic approaches or formal Mixed Integer Linear Programming (MILP) techniques. When pricing 128 financial options using a Monte Carlo algorithm upon a heterogeneous cluster of Multicore CPU, GPU and FPGA platforms, the MILP approach produces a trade-off that is up to 110% faster than a heuristic approach, and over 50% cheaper. These results suggest that high quality performance-resource trade-offs of heterogeneous IaaS are best realised through a formal optimisation approach.
Hybrid Memristor-CMOS (MeMOS) based Logic Gates and Adder Circuits
Venue: arXiv cs.ET 2015
Year: 2015

Practical memristor came into picture just few years back and instantly became the topic of interest for researchers and scientists. Memristor is the fourth basic two-terminal passive circuit element apart from well known resistor, capacitor and inductor. Recently, memristor based architectures has been proposed by many researchers. In this paper, we have designed a hybrid Memristor-CMOS (MeMOS) logic based adder circuit that can be used in numerous logic computational architectures. We have also analyzed the transient response of logic gates designed using MeMOS logic circuits. MeMOS use CMOS 180 nm process with memristor to compute boolean logic operations. Various parameters including speed, ares, delay and power dissipation are computed and compared with standard CMOS 180 nm logic design. The proposed logic shows better area utilization and excellent results from existing CMOS logic circuits at standard 1.8 V operating voltage.
Assistive Planning in Complex, Dynamic Environments: a Probabilistic Approach
Venue: arXiv cs.RO 2015
Year: 2015

We explore the probabilistic foundations of shared control in complex dynamic environments. In order to do this, we formulate shared control as a random process and describe the joint distribution that governs its behavior. For tractability, we model the relationships between the operator, autonomy, and crowd as an undirected graphical model. Further, we introduce an interaction function between the operator and the robot, that we call "agreeability"; in combination with the methods developed in~\cite{trautman-ijrr-2015}, we extend a cooperative collision avoidance autonomy to shared control. We therefore quantify the notion of simultaneously optimizing over agreeability (between the operator and autonomy), and safety and efficiency in crowded environments. We show that for a particular form of interaction function between the autonomy and the operator, linear blending is recovered exactly. Additionally, to recover linear blending, unimodal restrictions must be placed on the models describing the operator and the autonomy. In turn, these restrictions raise questions about the flexibility and applicability of the linear blending framework. Additionally, we present an extension of linear blending called "operator biased linear trajectory blending" (which formalizes some recent approaches in linear blending such as~\cite{dragan-ijrr-2013}) and show that not only is this also a restrictive special case of our probabilistic approach, but more importantly, is statistically unsound, and thus, mathematically, unsuitable for implementation. Instead, we suggest a statistically principled approach that guarantees data is used in a consistent manner, and show how this alternative approach converges to the full probabilistic framework. We conclude by proving that, in general, linear blending is suboptimal with respect to the joint metric of agreeability, safety, and efficiency.
A Feature-Based Analysis on the Impact of Set of Constraints for e-Constrained Differential Evolution
Venue: arXiv cs.NE 2015
Year: 2015

Different types of evolutionary algorithms have been developed for constrained continuous optimization. We carry out a feature-based analysis of evolved constrained continuous optimization instances to understand the characteristics of constraints that make problems hard for evolutionary algorithm. In our study, we examine how various sets of constraints can influence the behaviour of e-Constrained Differential Evolution. Investigating the evolved instances, we obtain knowledge of what type of constraints and their features make a problem difficult for the examined algorithm.
Autonomous 3D Reconstruction Using a MAV
Venue: arXiv cs.CV 2015
Year: 2015

An approach is proposed for high resolution 3D reconstruction of an object using a Micro Air Vehicle (MAV). A system is described which autonomously captures images and performs a dense 3D reconstruction via structure from motion with no prior knowledge of the environment. Only the MAVs own sensors, the front facing camera and the Inertial Measurement Unit (IMU) are utilized. Precision agriculture is considered as an example application for the system.
Person re-identification via efficient inference in fully connected CRF
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we address the problem of person re-identification problem, i.e., retrieving instances from gallery which are generated by the same person as the given probe image. This is very challenging because the person's appearance usually undergoes significant variations due to changes in illumination, camera angle and view, background clutter, and occlusion over the camera network. In this paper, we assume that the matched gallery images should not only be similar to the probe, but also be similar to each other, under suitable metric. We express this assumption with a fully connected CRF model in which each node corresponds to a gallery and every pair of nodes are connected by an edge. A label variable is associated with each node to indicate whether the corresponding image is from target person. We define unary potential for each node using existing feature calculation and matching techniques, which reflect the similarity between probe and gallery image, and define pairwise potential for each edge in terms of a weighed combination of Gaussian kernels, which encode appearance similarity between pair of gallery images. The specific form of pairwise potential allows us to exploit an efficient inference algorithm to calculate the marginal distribution of each label variable for this dense connected CRF. We show the superiority of our method by applying it to public datasets and comparing with the state of the art.
De-Fragmenting the Cloud
Venue: arXiv cs.DC 2015
Year: 2015

Existing VM placement schemes have measured their effectiveness solely by looking either Physical Machine's resources(CPU, memory) or network resource. However, real applications use all resource types to varying degrees. The result of applying existing placement schemes to VMs running real applications is a fragmented data center where resources along one dimension become unusable even though they are available because of the unavailability of resources along other dimensions. An example of this fragmentation is unusable CPU because of a bottlenecked network link from the physical machine which has available CPU. To date, evaluations of the efficacy of VM placement schemes has not recognized this fragmentation and it's ill effects, let alone try to measure it and avoid it. In this paper, we first define the notion of what we term "relative resource fragmentation" and illustrate how it can be measured in a data center. The metric we put forth for capturing the degree of fragmentation is comprehensive and includes all key data center resource types. We then propose a scheme of minimizing this fragmentation so as to maximize the availability of existing set of data center resources. Results of empirical evaluations of our placement scheme compared to existing network based placement schemes show a reduction of fragmentation by as much as 15% and increase in number of successfully placed applications by upto 20%.
The All-Seeing Eye: A Massive-Multi-Sensor Zero-Configuration Intrusion Detection System for Web Applications
Venue: arXiv cs.CR 2015
Year: 2015

Timing attacks are a challenge for current intrusion detection solutions. Timing attacks are dangerous for web applications because they may leak information about side channel vulnerabilities. This paper presents a massive-multi-sensor zero-configuration Intrusion Detection System that is especially good at detecting timing attacks. Unlike current solutions, the proposed Intrusion Detection System uses a huge number of sensors for attack detection. These sensors include sensors automatically inserted into web application or into the frameworks used to build web applications. With this approach the Intrusion Detection System is able to detect sophisticated attacks like timing attacks or other brute-force attacks with increased accuracy. The proposed massive-multi-sensor zero-configuration intrusion detection system does not need specific knowledge about the system to protect, hence it offers zero-configuration capability.