OpenRaiser/Intern-Atlas huggingface dataset:
Teegi: Tangible EEG Interface
Venue: arXiv cs.HC 2014
Year: 2014

We introduce Teegi, a Tangible ElectroEncephaloGraphy (EEG) Interface that enables novice users to get to know more about something as complex as brain signals, in an easy, en- gaging and informative way. To this end, we have designed a new system based on a unique combination of spatial aug- mented reality, tangible interaction and real-time neurotech- nologies. With Teegi, a user can visualize and analyze his or her own brain activity in real-time, on a tangible character that can be easily manipulated, and with which it is possible to interact. An exploration study has shown that interacting with Teegi seems to be easy, motivating, reliable and infor- mative. Overall, this suggests that Teegi is a promising and relevant training and mediation tool for the general public.
A parallel sampling based clustering
Venue: arXiv cs.LG 2014
Year: 2014

The problem of automatically clustering data is an age old problem. People have created numerous algorithms to tackle this problem. The execution time of any of this algorithm grows with the number of input points and the number of cluster centers required. To reduce the number of input points we could average the points locally and use the means or the local centers as the input for clustering. However since the required number of local centers is very high, running the clustering algorithm on the entire dataset to obtain these representational points is very time consuming. To remedy this problem, in this paper we are proposing two subclustering schemes where by we subdivide the dataset into smaller sets and run the clustering algorithm on the smaller datasets to obtain the required number of datapoints to run our clustering algorithm with. As we are subdividing the given dataset, we could run clustering algorithm on each smaller piece of the dataset in parallel. We found that both parallel and serial execution of this method to be much faster than the original clustering algorithm and error in running the clustering algorithm on a reduced set to be very less.
On the Optimality of Simple Schedules for Networks with Multiple Half-Duplex Relays
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies networks with N half-duplex relays assisting the communication between a source and a destination. In ISIT'12 Brahma, Özgür and Fragouli conjectured that in Gaussian half-duplex diamond networks (i.e., without a direct link between the source and the destination, and with N non-interfering relays) an approximately optimal relay scheduling policy (i.e., achieving the cut-set upper bound to within a constant gap) has at most N+1 active states (i.e., at most N+1 out of the $2^N$ possible relay listen-transmit states have a strictly positive probability). Such relay scheduling policies were referred to as simple. In ITW'13 we conjectured that simple approximately optimal relay scheduling policies exist for any Gaussian half-duplex multi-relay network irrespectively of the topology. This paper formally proves this more general version of the conjecture and shows it holds beyond Gaussian noise networks. In particular, for any memoryless half-duplex N-relay network with independent noises and for which independent inputs are approximately optimal in the cut-set upper bound, an approximately optimal simple relay scheduling policy exists. A convergent iterative polynomial-time algorithm, which alternates between minimizing a submodular function and maximizing a linear program, is proposed to find the approximately optimal simple relay schedule. As an example, for N-relay Gaussian networks with independent noises, where each node in equipped with multiple antennas and where each antenna can be configured to listen or transmit irrespectively of the others, the existence of an approximately optimal simple relay scheduling policy with at most N+1 active states is proved. Through a line-network example it is also shown that independently switching the antennas at each relay can provide a strictly larger multiplexing gain compared to using the antennas for the same purpose.
Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
Venue: arXiv cs.IT 2014
Year: 2014

The generalized approximate message passing (GAMP) algorithm is an efficient method of MAP or approximate-MMSE estimation of $x$ observed from a noisy version of the transform coefficients $z = Ax$. In fact, for large zero-mean i.i.d sub-Gaussian $A$, GAMP is characterized by a state evolution whose fixed points, when unique, are optimal. For generic $A$, however, GAMP may diverge. In this paper, we propose adaptive damping and mean-removal strategies that aim to prevent divergence. Numerical results demonstrate significantly enhanced robustness to non-zero-mean, rank-deficient, column-correlated, and ill-conditioned $A$.
Dwell Time Prediction Model for Minimizing Unnecessary Handovers in Heterogenous Wireless Networks, Considering Amoebic Shaped Coverage Region
Venue: arXiv cs.NI 2014
Year: 2014

Over the years, vertical handover necessity estimation has attracted the interest of numerous researchers. Despite the attractive benefits of integrating different wireless platforms, mobile users are confronted with the issue of detrimental handover. This paper used extensive geometric and probability analysis in modelling the coverage area of a WLAN cell. Thus, presents a realistic and novel model with an attempt to minimize unnecessary handover and handover failure of a mobile node (MN) traversing the WLAN cell from a third generation (3G) network. The dwell time is estimated along with the threshold values to ensure an optimal handover decision by the MN, while the probability of unnecessary handover and handover failure are kept within tolerable bounds. Monte-Carlo simulations were carried out to show the behavior of the proposed model. Results were validated by comparing this model with existing models for unnecessary handover minimization.
Modeling Dynamics of Online Video Popularity
Venue: arXiv cs.NI 2014
Year: 2014

Large Internet video delivery systems serve millions of videos to tens of millions of users on daily basis, via Video-on-Demand and live streaming. Video popularity evolves over time. It represents the workload, as welll as business value, of the video to the overall system. The ability to predict video popularity is very helpful for improving service quality and operating efficiency. Previous studies adopted simple models for video popularity, or directly adopted patterns from measurement studies. In this paper, we develop a stochastic fluid model that tries to capture two hidden processes that give rise to different patterns of a given video's popularity evolution: the information spreading process, and the user reaction process. Specifically, these processes model how the video is recommended to the user, the videos inherent attractiveness, and users reaction rate, and yield specific popularity evolution patterns. We then validate our model by matching the predictions of the model with observed patterns from our collaborator, a large content provider in China. This model thus gives us the insight to explain the common and different video popularity evolution patterns and why.
Minimum-weight Spanning Tree Construction in $O(\log \log \log n)$ Rounds on the Congested Clique
Venue: arXiv cs.DC 2014
Year: 2014

This paper considers the \textit{minimum spanning tree (MST)} problem in the Congested Clique model and presents an algorithm that runs in $O(\log \log \log n)$ rounds, with high probability. Prior to this, the fastest MST algorithm in this model was a deterministic algorithm due to Lotker et al.~(SIAM J on Comp, 2005) from about a decade ago. A key step along the way to designing this MST algorithm is a \textit{connectivity verification} algorithm that not only runs in $O(\log \log \log n)$ rounds with high probability, but also has low message complexity. This allows the fast computation of an MST by running multiple instances of the connectivity verification algorithm in parallel. These results depend on a new edge-sampling theorem, developed in the paper, that says that if each edge $e = \{u, v\}$ is sampled independently with probability $c \log^2 n/\min\{\mbox{degree}(u), \mbox{degree}(v)\}$ (for a large enough constant $c$) then all cuts of size at least $n$ are approximated in the sampled graph. This sampling theorem is inspired by series of papers on graph sparsification via random edge sampling due to Karger~(STOC 1994), Benczúr and Karger~(STOC 1996, arxiv 2002), and Fung et al.~(STOC 2011). The edge sampling techniques in these papers use probabilities that are functions of edge-connectivity or a related measure called edge-strength. For the purposes of this paper, these edge-connectivity measures seem too costly to compute and the main technical contribution of this paper is to show that degree-based edge-sampling suffices to approximate large cuts.
Model Predictive Control for Micro Aerial Vehicle Systems (MAV) Systems
Venue: arXiv cs.RO 2014
Year: 2014

This paper presents a method for path-following for quadcopter trajectories in real time. Non-Linear Guidance Logic is used to find the intercepts of the subsequent destination. Trajectory tracking is implemented by formulating the trajectory of the quadcopter using its jerk, in discrete time, and then solving a convex optimization problem on each decoupled axis. Based on the maximum possible thrust and angular rates of the quadcopter, feasibility constraints for the quadcopter have been derived. In this report we describe the design and implementation of explicit MPC controllers where the controllers were executed on a computer using sparse solvers to control the vehicle in hovering flight.
Asymptotically Optimal Matching of Multiple Sequences to Source Distributions and Training Sequences
Venue: arXiv cs.IT 2014
Year: 2014

Consider a finite set of sources, each producing i.i.d. observations that follow a unique probability distribution on a finite alphabet. We study the problem of matching a finite set of observed sequences to the set of sources under the constraint that the observed sequences are produced by distinct sources. In general, the number of sequences $N$ may be different from the number of sources $M$, and only some $K \leq \min\{M,N\}$ of the observed sequences may be produced by a source from the set of sources of interest. We consider two versions of the problem -- one in which the probability laws of the sources are known, and another in which the probability laws of the sources are unspecified but one training sequence from each of the sources is available. We show that both these problems can be solved using a sequence of tests that are allowed to produce "no-match" decisions. The tests ensure exponential decay of the probabilities of incorrect matching as the sequence lengths increase, and minimize the "no-match" decisions. Both tests can be implemented using variants of the minimum weight matching algorithm applied to a weighted bipartite graph. We also compare the performances obtained by using these tests with those obtained by using tests that do not take into account the constraint that the sequences are produced by distinct sources. For the version of the problem in which the probability laws of the sources are known, we compute the rejection exponents and error exponents of the tests and show that tests that make use of the constraint have better exponents than tests that do not make use of this information.
Negative Link Prediction in Social Media
Venue: arXiv cs.SI 2014
Year: 2014

Signed network analysis has attracted increasing attention in recent years. This is in part because research on signed network analysis suggests that negative links have added value in the analytical process. A major impediment in their effective use is that most social media sites do not enable users to specify them explicitly. In other words, a gap exists between the importance of negative links and their availability in real data sets. Therefore, it is natural to explore whether one can predict negative links automatically from the commonly available social network data. In this paper, we investigate the novel problem of negative link prediction with only positive links and content-centric interactions in social media. We make a number of important observations about negative links, and propose a principled framework NeLP, which can exploit positive links and content-centric interactions to predict negative links. Our experimental results on real-world social networks demonstrate that the proposed NeLP framework can accurately predict negative links with positive links and content-centric interactions. Our detailed experiments also illustrate the relative importance of various factors to the effectiveness of the proposed framework.
Unsupervised Induction of Semantic Roles within a Reconstruction-Error Minimization Framework
Venue: arXiv cs.CL 2014
Year: 2014

We introduce a new approach to unsupervised estimation of feature-rich semantic role labeling models. Our model consists of two components: (1) an encoding component: a semantic role labeling model which predicts roles given a rich set of syntactic and lexical features; (2) a reconstruction component: a tensor factorization model which relies on roles to predict argument fillers. When the components are estimated jointly to minimize errors in argument reconstruction, the induced roles largely correspond to roles defined in annotated resources. Our method performs on par with most accurate role induction methods on English and German, even though, unlike these previous approaches, we do not incorporate any prior linguistic knowledge about the languages.
Zipf's Law and the Frequency of Characters or Words of Oracles
Venue: arXiv cs.CL 2014
Year: 2014

The article discusses the frequency of characters of Oracle,concluding that the frequency and the rank of a word or character is fit to Zipf-Mandelboit Law or Zipf's law with three parameters,and figuring out the parameters based on the frequency,and pointing out that what some researchers of Oracle call the assembling on the two ends is just a description by their impression about the Oracle data.
Evaluating Learning Games during their Conception
Venue: arXiv cs.CY 2014
Year: 2014

Learning Games (LGs) are educational environments based on a playful approach to learning. Their use has proven to be promising in many domains, but is at present restricted by the time consuming and costly nature of the developing process. In this paper, we propose a set of quality indicators that can help the conception team to evaluate the quality of their LG during the designing process, and before it is developed. By doing so, the designers can identify and repair problems in the early phases of the conception and therefore reduce the alteration phases, that occur after testing the LG's prototype. These quality indicators have been validated by 6 LG experts that used them to assess the quality of 24 LGs in the process of being designed. They have also proven to be useful as design guidelines for novice LG designers.
Multi-Platform Generative Development of Component & Connector Systems using Model and Code Libraries
Venue: arXiv cs.SE 2014
Year: 2014

Component-based software engineering aims to reduce software development effort by reusing established components as building blocks of complex systems. Defining components in general-purpose programming languages restricts their reuse to platforms supporting these languages and complicates component composition with implementation details. The vision of model-driven engineering is to reduce the gap between developer intention and implementation details by lifting abstract models to primary development artifacts and systematically transforming these into executable systems. For sufficiently complex systems the transformation from abstract models to platform-specific implementations requires augmentation with platform-specific components. We propose a model-driven mechanism to transform platform-independent logical component & connector architectures into platform-specific implementations combining model and code libraries. This mechanism allows to postpone commitment to a specific platform and thus increases reuse of software architectures and components.
Rapid Sampling for Visualizations with Ordering Guarantees
Venue: arXiv cs.DB 2014
Year: 2014

Visualizations are frequently used as a means to understand trends and gather insights from datasets, but often take a long time to generate. In this paper, we focus on the problem of rapidly generating approximate visualizations while preserving crucial visual proper- ties of interest to analysts. Our primary focus will be on sampling algorithms that preserve the visual property of ordering; our techniques will also apply to some other visual properties. For instance, our algorithms can be used to generate an approximate visualization of a bar chart very rapidly, where the comparisons between any two bars are correct. We formally show that our sampling algorithms are generally applicable and provably optimal in theory, in that they do not take more samples than necessary to generate the visualizations with ordering guarantees. They also work well in practice, correctly ordering output groups while taking orders of magnitude fewer samples and much less time than conventional sampling schemes.
Phishing Detection in IMs using Domain Ontology and CBA - An innovative Rule Generation Approach
Venue: arXiv cs.CR 2014
Year: 2014

User ignorance towards the use of communication services like Instant Messengers, emails, websites, social networks etc. is becoming the biggest advantage for phishers. It is required to create technical awareness in users by educating them to create a phishing detection application which would generate phishing alerts for the user so that phishing messages are not ignored. The lack of basic security features to detect and prevent phishing has had a profound effect on the IM clients, as they lose their faith in e-banking and e-commerce transactions, which will have a disastrous impact on the corporate and banking sectors and businesses which rely heavily on the internet. Very little research contributions were available in for phishing detection in Instant messengers. A context based, dynamic and intelligent phishing detection methodology in IMs is proposed, to analyze and detect phishing in Instant Messages with relevance to domain ontology (OBIE) and utilizes the Classification based on Association (CBA) for generating phishing rules and alerting the victims. A PDS Monitoring system algorithm is used to identify the phishing activity during exchange of messages in IMs, with high ratio of precision and recall. The results have shown improvement by the increased percentage of precision and recall when compared to the existing methods.
Array Orthogonality in Higher Dimensions
Venue: arXiv cs.IT 2014
Year: 2014

We generalize the array orthogonality property for perfect autocorrelation sequences to $n$-dimensional arrays. The generalized array orthogonality property is used to derive a number of $n$-dimensional perfect array constructions.
Prophet: A Speculative Multi-threading Execution Model with Architectural Support Based on CMP
Venue: arXiv cs.AR 2014
Year: 2014

Speculative multi-threading (SpMT) has been proposed as a perspective method to exploit Chip Multiprocessors (CMP) hardware potential. It is a thread level speculation (TLS) model mainly depending on software and hardware co-design. This paper researches speculative thread-level parallelism of general purpose programs and a speculative multi-threading execution model called Prophet is presented. The architectural support for Prophet execution model is designed based on CMP. In Prophet the inter-thread data dependency are predicted by pre-computation slice (p-slice) to reduce RAW violation. Prophet multi-versioning Cache system along with thread state control mechanism in architectural support are utilized for buffering the speculative data, and a snooping bus based cache coherence protocol is used to detect data dependence violation. The simulation-based evaluation shows that the Prophet system could achieve significant speedup for general-purpose programs.
A Second-Order Formulation of Non-Termination
Venue: arXiv cs.LO 2014
Year: 2014

We consider the termination/non-termination property of a class of loops. Such loops are commonly used abstractions of real program pieces. Second-order logic is a convenient language to express non-termination. Of course, such property is generally undecidable. However, by restricting the language to known decidable cases, we exhibit new classes of loops, the non-termination of which is decidable. We present a bunch of examples.
User-driven Privacy Enforcement for Cloud-based Services in the Internet of Things
Venue: arXiv cs.SE 2014
Year: 2014

Internet of Things devices are envisioned to penetrate essentially all aspects of life, including homes and urbanspaces, in use cases such as health care, assisted living, and smart cities. One often proposed solution for dealing with the massive amount of data collected by these devices and offering services on top of them is the federation of the Internet of Things and cloud computing. However, user acceptance of such systems is a critical factor that hinders the adoption of this promising approach due to severe privacy concerns. We present UPECSI, an approach for user-driven privacy enforcement for cloud-based services in the Internet of Things to address this critical factor. UPECSI enables enforcement of all privacy requirements of the user once her sensitive data leaves the border of her network, provides a novel approach for the integration of privacy functionality into the development process of cloud-based services, and offers the user an adaptable and transparent configuration of her privacy requirements. Hence, UPECSI demonstrates an approach for realizing user-accepted cloud services in the Internet of Things.
Computational Complexity of Competitive Diffusion on (Un)weighted Graphs
Venue: arXiv cs.CC 2014
Year: 2014

Consider an undirected graph modeling a social network, where the vertices represent users, and the edges do connections among them. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her opinion, and then it spreads along the edges in the graphs. The objective of every player is to maximize the number of vertices the opinion infects. In this paper, we investigate a computational problem of asking whether a pure Nash equilibrium exists in the competitive diffusion game on unweighed and weighted graphs, and present several negative and positive results. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forest of paths with arbitrary weights is solvable in pseudo-polynomial time; and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem for chain, cochain, and threshold graphs with arbitrary integer weights is solvable in polynomial time.