OpenRaiser/Intern-Atlas huggingface dataset:
Lessons Learned from an Experiment in Crowdsourcing Complex Citizen Engineering Tasks with Amazon Mechanical Turk
Venue: arXiv cs.SI 2014
Year: 2014

We investigate the feasibility of obtaining highly trustworthy results using crowdsourcing on complex engineering tasks. Crowdsourcing is increasingly seen as a potentially powerful way of increasing the supply of labor for solving society's problems. While applications in domains such as citizen-science, citizen-journalism or knowledge organization (e.g., Wikipedia) have seen many successful applications, there have been fewer applications focused on solving engineering problems, especially those involving complex tasks. This may be in part because of concerns that low quality input into engineering analysis and design could result in failed structures leading to loss of life. We compared the quality of work of the anonymous workers of Amazon Mechanical Turk (AMT), an online crowdsourcing service, with the quality of work of expert engineers in solving the complex engineering task of evaluating virtual wind tunnel data graphs. On this representative complex engineering task, our results showed that there was little difference between expert engineers and crowdworkers in the quality of their work and explained reasons for these results. Along with showing that crowdworkers are effective at completing new complex tasks our paper supplies a number of important lessons that were learned in the process of collecting this data from AMT, which may be of value to other researchers.
Transmit Designs for the MIMO Broadcast Channel with Statistical CSI
Venue: arXiv cs.IT 2014
Year: 2014

We investigate the multiple-input multiple-output broadcast channel with statistical channel state information available at the transmitter. The so-called linear assignment operation is employed, and necessary conditions are derived for the optimal transmit design under general fading conditions. Based on this, we introduce an iterative algorithm to maximize the linear assignment weighted sum-rate by applying a gradient descent method. To reduce complexity, we derive an upper bound of the linear assignment achievable rate of each receiver, from which a simplified closed-form expression for a near-optimal linear assignment matrix is derived. This reveals an interesting construction analogous to that of dirty-paper coding. In light of this, a low complexity transmission scheme is provided. Numerical examples illustrate the significant performance of the proposed low complexity scheme.
Online Popularity and Topical Interests through the Lens of Instagram
Venue: arXiv cs.SI 2014
Year: 2014

Online socio-technical systems can be studied as proxy of the real world to investigate human behavior and social interactions at scale. Here we focus on Instagram, a media-sharing online platform whose popularity has been rising up to gathering hundred millions users. Instagram exhibits a mixture of features including social structure, social tagging and media sharing. The network of social interactions among users models various dynamics including follower/followee relations and users' communication by means of posts/comments. Users can upload and tag media such as photos and pictures, and they can "like" and comment each piece of information on the platform. In this work we investigate three major aspects on our Instagram dataset: (i) the structural characteristics of its network of heterogeneous interactions, to unveil the emergence of self organization and topically-induced community structure; (ii) the dynamics of content production and consumption, to understand how global trends and popular users emerge; (iii) the behavior of users labeling media with tags, to determine how they devote their attention and to explore the variety of their topical interests. Our analysis provides clues to understand human behavior dynamics on socio-technical systems, specifically users and content popularity, the mechanisms of users' interactions in online environments and how collective trends emerge from individuals' topical interests.
Query Containment for Highly Expressive Datalog Fragments
Venue: arXiv cs.DB 2014
Year: 2014

The containment problem of Datalog queries is well known to be undecidable. There are, however, several Datalog fragments for which containment is known to be decidable, most notably monadic Datalog and several "regular" query languages on graphs. Monadically Defined Queries (MQs) have been introduced recently as a joint generalization of these query languages. In this paper, we study a wide range of Datalog fragments with decidable query containment and determine exact complexity results for this problem. We generalize MQs to (Frontier-)Guarded Queries (GQs), and show that the containment problem is 3ExpTime-complete in either case, even if we allow arbitrary Datalog in the sub-query. If we focus on graph query languages, i.e., fragments of linear Datalog, then this complexity is reduced to 2ExpSpace. We also consider nested queries, which gain further expressivity by using predicates that are defined by inner queries. We show that nesting leads to an exponentially increasing hierarchy for the complexity of query containment, both in the linear and in the general case. Our results settle open problems for (nested) MQs, and they paint a comprehensive picture of the state of the art in Datalog query containment.
Sprinklers: A Randomized Variable-Size Striping Approach to Reordering-Free Load-Balanced Switching
Venue: arXiv cs.NI 2014
Year: 2014

Internet traffic continues to grow exponentially, calling for switches that can scale well in both size and speed. While load-balanced switches can achieve such scalability, they suffer from a fundamental packet reordering problem. Existing proposals either suffer from poor worst-case packet delays or require sophisticated matching mechanisms. In this paper, we propose a new family of stable load-balanced switches called "Sprinklers" that has comparable implementation cost and performance as the baseline load-balanced switch, but yet can guarantee packet ordering. The main idea is to force all packets within the same virtual output queue (VOQ) to traverse the same "fat path" through the switch, so that packet reordering cannot occur. At the core of Sprinklers are two key innovations: a randomized way to determine the "fat path" for each VOQ, and a way to determine its "fatness" roughly in proportion to the rate of the VOQ. These innovations enable Sprinklers to achieve near-perfect load-balancing under arbitrary admissible traffic. Proving this property rigorously using novel worst-case large deviation techniques is another key contribution of this work.
A Review on Failure Node Recovery Algorithms in Wireless Sensor Actor Networks
Venue: arXiv cs.NI 2014
Year: 2014

In wireless sensor-actor networks, sensors probe their surroundings and forward their data to actor nodes. Actors collect sensor data and perform certain tasks in response to various events. Since actors operate on harsh environment, they may easily get damaged or failed. Failed actor nodes may partition the network into disjoint subsets. In order to reestablish connectivity nodes may be relocated to new positions. This paper focus on review of three (LeDir, RIM, DARA) node recovery algorithms, and their performance has been analysed in terms network overhead and path length validation metrics.
Integer formula encoding SageTeX package
Venue: arXiv cs.MS 2014
Year: 2014

The paper describes a SageTeX implementation of an integer encoding procedures.
Single-Letter Characterization of Epsilon-Capacity for Mixed Memoryless Channels
Venue: arXiv cs.IT 2014
Year: 2014

For the class of mixed channels decomposed into stationary memoryless channels, single-letter characterizations of the $\varepsilon$-capacity have not been known except for restricted classes of channels such as the regular decomposable channel introduced by Winkelbauer. This paper gives single-letter characterizations of $\varepsilon$-capacity for mixed channels decomposed into at most countably many memoryless channels with a finite input alphabet and a general output alphabet with/without cost constraints. It is shown that a given characterization reduces to the one for the channel capacity given by Ahlswede when $\varepsilon$ is zero. In the proof of the coding theorem, the meta converse bound, originally given by Polyanskiy, Poor and Verdú, is particularized for the mixed channel decomposed into general component channels.
Application Specific Hardware Design Simulation for High Performance Embedded System
Venue: arXiv cs.AR 2014
Year: 2014

Application specific simulation is challenging task in various real time high performance embedded devices. In this study specific application is implemented with the help of Xilinx. Xilinx provides SDK and XPS tools, XPS tools used for develop complete hardware platform and SDK provides software platform for application creation and verification. Xilinx XUP-5 board have been used and implemented various specific Applications with hardware platform. In this study the base instruction set with customized instructions, supported with specific hardware resources are analyzed.
Should I Stay or Should I Go? Improving Event Recommendation in the Social Web
Venue: arXiv cs.HC 2014
Year: 2014

This paper focuses on the recommendation of events in the Social Web, and addresses the problem of finding if, and to which extent, certain features, which are peculiar to events, are relevant in predicting the users' interests and should thereby be taken into account in recommendation. We consider in particular three "additional" features that are usually shown to users within social networking environments: reachability from the user location, the reputation of the event in the community, and the participation of the user's friends. Our study is aimed at evaluating whether adding this information to the description of the event type and topic, and including in the user profile the information on the relevance of these factors, can improve our capability to predict the user's interest. We approached the problem by carrying out two surveys with users, who were asked to express %with a score their interest in a number of events. We then trained, by means of linear regression, a scoring function defined as a linear combination of the different factors, whose goal was to predict the user scores. We repeated this experiment under different hypotheses on the additional factors, in order to assess their relevance by comparing the predictive capabilities of the resulting functions. The compared results of our experiments show that additional factors, if properly weighted, can improve the prediction accuracy with an error reduction of 4.1%. The best results were obtained by combining content-based factors and additional factors in a proportion of approximately 10:4.
An Open Source P2P Encrypted VoIP Application
Venue: arXiv cs.PL 2014
Year: 2014

Open source is the future of technology. This community is growing by the day; developing and improving existing frameworks and software for free. Open source replacements are coming up for almost all proprietary software nowadays. This paper proposes an open source application which could replace Skype, a popular VoIP soft phone. The performance features of the developed software is analyzed and compared with Skype so that we can conclude that it can be an efficient replacement. This application is developed in pure Java using various APIs and package and boasts features like voice calling, chatting, file sharing etc. The target audience for this software will initially only be organizations (for internal communication) and later will be released on a larger scale.
Analysis of Bus Tracking System Using GPS on Smartphones
Venue: arXiv cs.CY 2014
Year: 2014

Public transport networks(PTNs)are difficult to use when the user is unfamiliar with the area they are traveling to.This is true for both infrequent users(including visitors)and regular users who need to travel to areas with which they are not acquainted.In these situations,adequate on-trip navigation information can substantially ease the use of public transportation and be the driving factor in motivating travelers to prefer it over other modes of transportation.However,estimating the localization of a user is not trivial,although it is critical for providing relevant information.I assess relevant design issues for a modular cost-efficient user-friendly on-trip Navigation service that uses position sensors.By helping travelers move from single-occupancy vehicles to public transportation systems, communities can reduce traffic congestion as well as its environmental impact.Here,I describe our efforts to increase the satisfaction of current public transportation users and help motivate more people to ride.
Transparency and Coordination in Peer Production
Venue: arXiv cs.HC 2014
Year: 2014

This paper examines coordination in transparent work environments - environments where the content of work artifacts, and the actions taken on these artifacts, are fully visible to organizational members. Our qualitative study of a community of open source software developers revealed a coordination system characterized by interest-based, asynchronous interaction and knowledge transfer. At the core of asynchronous knowledge transfer, lies the concept of quasi-codification, which occurs when rich process knowledge is implicitly encoded in work artifacts. Our findings suggest that members are able to more selectively form dependencies, monitor the trajectory of projects, and make their work understandable to others which facilitates coordination. We discuss two important characteristics that enable coordination activities in a transparent environment: the presence of an imagined audience that dictates the way artifacts are crafted, and experience within the environment, that allows individuals to derive knowledge from these artifacts. By showing how transparency influences coordination, this research challenges previous conceptions of coordination for complex, collaborative work.
Pregelix: Big(ger) Graph Analytics on A Dataflow Engine
Venue: arXiv cs.DB 2014
Year: 2014

There is a growing need for distributed graph processing systems that are capable of gracefully scaling to very large graph datasets. Unfortunately, this challenge has not been easily met due to the intense memory pressure imposed by process-centric, message passing designs that many graph processing systems follow. Pregelix is a new open source distributed graph processing system that is based on an iterative dataflow design that is better tuned to handle both in-memory and out-of-core workloads. As such, Pregelix offers improved performance characteristics and scaling properties over current open source systems (e.g., we have seen up to 15x speedup compared to Apache Giraph and up to 35x speedup compared to distributed GraphLab), and makes more effective use of available machine resources to support Big(ger) Graph Analytics.
Semantic Integration & Single-Site Opening of Multiple Governmental Data Sources
Venue: arXiv cs.IR 2014
Year: 2014

In many cases, government data is still "locked" in several "data silos", even within the boundaries of a single (inter-)national public organization with disparate and distributed organizational units and departments spread across multiple sites. Opening data and enabling its unified querying from a single site in an efficient and effective way is a semantic application integration and open government data challenge. This paper describes how NARA is using Semantic Web technology to implement an application integration approach within the boundaries of its organization via opening and querying multiple governmental data sources from a single site. The generic approach proposed, namely S3-AI, provides support to answering unified, ontology-mediated, federated queries to data produced and exploited by disparate applications, while these are being located in different organizational sites. S3-AI preserves ownership, autonomy and independency of applications and data. The paper extensively demonstrates S3-AI, using the D2RQ and Fuseki technologies, for addressing the needs of a governmental "IT helpdesk support" case.
No small nondeterministic read-once branching programs for CNFs of bounded treewidth
Venue: arXiv cs.CC 2014
Year: 2014

In this paper, given a parameter $k$, we demonstrate an infinite class of {\sc cnf}s of treewidth at most $k$ of their primary graphs such that the equivalent nondeterministic read-once branching programs ({\sc nrobp}s) are of size at least $n^{ck}$ for some universal constant $c$. Thus we rule out the possibility of fixed-parameter space complexity of {\sc nrobp}s parameterized by the smallest treewidth of the equivalent {\sc cnf}.
Sublinear Space Algorithms for the Longest Common Substring Problem
Venue: arXiv cs.DS 2014
Year: 2014

Given $m$ documents of total length $n$, we consider the problem of finding a longest string common to at least $d \geq 2$ of the documents. This problem is known as the \emph{longest common substring (LCS) problem} and has a classic $O(n)$ space and $O(n)$ time solution (Weiner [FOCS'73], Hui [CPM'92]). However, the use of linear space is impractical in many applications. In this paper we show that for any trade-off parameter $1 \leq τ\leq n$, the LCS problem can be solved in $O(τ)$ space and $O(n^2/τ)$ time, thus providing the first smooth deterministic time-space trade-off from constant to linear space. The result uses a new and very simple algorithm, which computes a $τ$-additive approximation to the LCS in $O(n^2/τ)$ time and $O(1)$ space. We also show a time-space trade-off lower bound for deterministic branching programs, which implies that any deterministic RAM algorithm solving the LCS problem on documents from a sufficiently large alphabet in $O(τ)$ space must use $Ω(n\sqrt{\log(n/(τ\log n))/\log\log(n/(τ\log n)})$ time.
The Predictive Power of Social Media: On the Predictability of U.S. Presidential Elections using Twitter
Venue: arXiv cs.SI 2014
Year: 2014

Twitter as a new form of social media potentially contains useful information that opens new opportunities for content analysis on tweets. This paper examines the predictive power of Twitter regarding the US presidential election of 2012. For this study, we analyzed 32 million tweets regarding the US presidential election by employing a combination of machine learning techniques. We devised an advanced classifier for sentiment analysis in order to increase the accuracy of Twitter content analysis. We carried out our analysis by comparing Twitter results with traditional opinion polls. In addition, we used the Latent Dirichlet Allocation model to extract the underlying topical structure from the selected tweets. Our results show that we can determine the popularity of candidates by running sentiment analysis. We can also uncover candidates popularities in the US states by running the sentiment analysis algorithm on geo-tagged tweets. To the best of our knowledge, no previous work in the field has presented a systematic analysis of a considerable number of tweets employing a combination of analysis techniques by which we conducted this study. Thus, our results aptly suggest that Twitter as a well-known social medium is a valid source in predicting future events such as elections. This implies that understanding public opinions and trends via social media in turn allows us to propose a cost- and time-effective way not only for spreading and sharing information, but also for predicting future events.
The Max-Distance Network Creation Game on General Host Graphs
Venue: arXiv cs.GT 2014
Year: 2014

In this paper we study a generalization of the classic \emph{network creation game} in the scenario in which the $n$ players sit on a given arbitrary \emph{host graph}, which constrains the set of edges a player can activate at a cost of $α\geq 0$ each. This finds its motivations in the physical limitations one can have in constructing links in practice, and it has been studied in the past only when the routing cost component of a player is given by the sum of distances to all the other nodes. Here, we focus on another popular routing cost, namely that which takes into account for each player its \emph{maximum} distance to any other player. For this version of the game, we first analyze some of its computational and dynamic aspects, and then we address the problem of understanding the structure of associated pure Nash equilibria. In this respect, we show that the corresponding price of anarchy (PoA) is fairly bad, even for several basic classes of host graphs. More precisely, we first exhibit a lower bound of $Ω(\sqrt{ n / (1+α)})$ for any $α= o(n)$. Notice that this implies a counter-intuitive lower bound of $Ω(\sqrt{n})$ for very small values of $α$ (i.e., edges can be activated almost for free). Then, we show that when the host graph is restricted to be either $k$-regular (for any constant $k \geq 3$), or a 2-dimensional grid, the PoA is still $Ω(1+\min\{α, \frac{n}α\})$, which is proven to be tight for $α=Ω(\sqrt{n})$. On the positive side, if $α\geq n$, we show the PoA is $O(1)$. Finally, in the case in which the host graph is very sparse (i.e., $|E(H)|=n-1+k$, with $k=O(1)$), we prove that the PoA is $O(1)$, for any $α$.
Deep Poselets for Human Detection
Venue: arXiv cs.CV 2014
Year: 2014

We address the problem of detecting people in natural scenes using a part approach based on poselets. We propose a bootstrapping method that allows us to collect millions of weakly labeled examples for each poselet type. We use these examples to train a Convolutional Neural Net to discriminate different poselet types and separate them from the background class. We then use the trained CNN as a way to represent poselet patches with a Pose Discriminative Feature (PDF) vector -- a compact 256-dimensional feature vector that is effective at discriminating pose from appearance. We train the poselet model on top of PDF features and combine them with object-level CNNs for detection and bounding box prediction. The resulting model leads to state-of-the-art performance for human detection on the PASCAL datasets.
Non-Linear Pattern-Matching against Unfree Data Types with Lexical Scoping
Venue: arXiv cs.PL 2014
Year: 2014

This paper proposes a pattern-matching system that enables non-linear pattern-matching against unfree data types. The system allows multiple occurrences of the same variables in a pattern, multiple results of pattern-matching and modularization of the way of pattern-matching for each data type at the same time. It enables us to represent pattern-matching against not only algebraic data types but also unfree data types such as sets, graphs and any other data types whose data have no canonical form and multiple ways of decomposition. I have realized that with a rule that pattern-matching is executed from the left side of a pattern and a rule that a binding to a variable in a pattern can be referred to in its right side of the pattern. Furthermore, I have realized modularization of these patterns with lexical scoping. In my system, a pattern is not a first class object, but a pattern-function that obtains only patterns and returns a pattern is a first class object. This restriction simplifies the non-linear pattern-matching system with lexical scoping. I have already implemented the pattern-matching system in the Egison programming language.