OpenRaiser/Intern-Atlas huggingface dataset:
Developing a Visual Interactive Search History Exploration System
Venue: arXiv cs.IR 2013
Year: 2013

As users advance in their search within a system, different queries are conducted and various results are examined by them. These objects form an implicit individual library representing the acquired knowledge. In our research we aim to supply the user with visualizations of the search history and interaction methods to organize the history. The fundamental question is what role search history exploration can play in the users search process. In this paper we want to introduce Ideas of a prototypical system for search history exploration and discuss methods to address the questions mentioned above.
Geo-located Twitter as the proxy for global mobility patterns
Venue: arXiv cs.SI 2013
Year: 2013

In the advent of a pervasive presence of location sharing services researchers gained an unprecedented access to the direct records of human activity in space and time. This paper analyses geo-located Twitter messages in order to uncover global patterns of human mobility. Based on a dataset of almost a billion tweets recorded in 2012 we estimate volumes of international travelers in respect to their country of residence. We examine mobility profiles of different nations looking at the characteristics such as mobility rate, radius of gyration, diversity of destinations and a balance of the inflows and outflows. The temporal patterns disclose the universal seasons of increased international mobility and the peculiar national nature of overseen travels. Our analysis of the community structure of the Twitter mobility network, obtained with the iterative network partitioning, reveals spatially cohesive regions that follow the regional division of the world. Finally, we validate our result with the global tourism statistics and mobility models provided by other authors, and argue that Twitter is a viable source to understand and quantify global mobility patterns.
A multi-terabyte relational database for geo-tagged social network data
Venue: arXiv cs.DB 2013
Year: 2013

Despite their relatively low sampling factor, the freely available, randomly sampled status streams of Twitter are very useful sources of geographically embedded social network data. To statistically analyze the information Twitter provides via these streams, we have collected a year's worth of data and built a multi-terabyte relational database from it. The database is designed for fast data loading and to support a wide range of studies focusing on the statistics and geographic features of social networks, as well as on the linguistic analysis of tweets. In this paper we present the method of data collection, the database design, the data loading procedure and special treatment of geo-tagged and multi-lingual data. We also provide some SQL recipes for computing network statistics.
The Complexity of Order Type Isomorphism
Venue: arXiv cs.CG 2013
Year: 2013

The order type of a point set in $R^d$ maps each $(d{+}1)$-tuple of points to its orientation (e.g., clockwise or counterclockwise in $R^2$). Two point sets $X$ and $Y$ have the same order type if there exists a mapping $f$ from $X$ to $Y$ for which every $(d{+}1)$-tuple $(a_1,a_2,\ldots,a_{d+1})$ of $X$ and the corresponding tuple $(f(a_1),f(a_2),\ldots,f(a_{d+1}))$ in $Y$ have the same orientation. In this paper we investigate the complexity of determining whether two point sets have the same order type. We provide an $O(n^d)$ algorithm for this task, thereby improving upon the $O(n^{\lfloor{3d/2}\rfloor})$ algorithm of Goodman and Pollack (1983). The algorithm uses only order type queries and also works for abstract order types (or acyclic oriented matroids). Our algorithm is optimal, both in the abstract setting and for realizable points sets if the algorithm only uses order type queries.
Road Accident Prevention Unit: An prototyping approach towards mitigating an omnipresent threat
Venue: arXiv cs.OH 2013
Year: 2013

An intelligent multisensor front end based on the ARM Cortex M3. It deduces a driver's configuration, ascertains his ability to drive safely and contacts near ones with location data for urgent disaster mitigation. Prevention measures are undertaken through external display modules and provision for being vehicle-powered through external voltage regulated supplies. The proof of concept for this paper is an ALL INDIA THIRD PRIZE WINNER at the Texas Instruments Analog Design Contest 2012-13 National Finals and this paper is due for digital publication in IEEE Xplore. All documentation is property of Texas Instruments, the Texas Instruments Analog Design Contest 2012-13 and IEEE Xplore.
Performance of Uplink Multiuser Massive MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

We study the performance of uplink transmission in a large-scale (massive) MIMO system, where all the transmitters have single antennas and the receiver (base station) has a large number of antennas. Specifically, we analyze achievable degrees of freedom of the system without assuming channel state information at the receiver. Also, we quantify the amount of power saving that is possible with increasing number of receive antennas.
Variable is Better Than Invariable: Stable Sparse VSS-NLMS Algorithms with Application to Estimating MIMO Channels
Venue: arXiv cs.IT 2013
Year: 2013

To estimate multiple-input multiple-output (MIMO) channels, invariable step-size normalized least mean square (ISSNLMS) algorithm was applied to adaptive channel estimation (ACE). Since the MIMO channel is often described by sparse channel model due to broadband signal transmission, such sparsity can be exploited by adaptive sparse channel estimation (ASCE) methods using sparse ISS-NLMS algorithms. It is well known that step-size is a critical parameter which controls three aspects: algorithm stability, estimation performance and computational cost. The previous approaches can exploit channel sparsity but their step-sizes are keeping invariant which unable balances well the three aspects and easily cause either estimation performance loss or instability. In this paper, we propose two stable sparse variable step-size NLMS (VSS-NLMS) algorithms to improve the accuracy of MIMO channel estimators. First, ASCE for estimating MIMO channels is formulated in MIMO systems. Second, different sparse penalties are introduced to VSS-NLMS algorithm for ASCE. In addition, difference between sparse ISS-NLMS algorithms and sparse VSS-NLMS ones are explained. At last, to verify the effectiveness of the proposed algorithms for ASCE, several selected simulation results are shown to prove that the proposed sparse VSS-NLMS algorithms can achieve better estimation performance than the conventional methods via mean square error (MSE) and bit error rate (BER) metrics.
Nominal Coalgebraic Data Types with Applications to Lambda Calculus
Venue: arXiv cs.LO 2013
Year: 2013

We investigate final coalgebras in nominal sets. This allows us to define types of infinite data with binding for which all constructions automatically respect alpha equivalence. We give applications to the infinitary lambda calculus.
Approximate Bayesian Probabilistic-Data-Association-Aided Iterative Detection for MIMO Systems Using Arbitrary M-ary Modulation
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, the issue of designing an iterative-detection-and-decoding (IDD)-aided receiver, relying on the low-complexity probabilistic data association (PDA) method, is addressed for turbo-coded multiple-input-multiple-output (MIMO) systems using general M-ary modulations. We demonstrate that the classic candidate-search-aided bit-based extrinsic log-likelihood ratio (LLR) calculation method is not applicable to the family of PDA-based detectors. Additionally, we reveal that, in contrast to the interpretation in the existing literature, the output symbol probabilities of existing PDA algorithms are not the true a posteriori probabilities (APPs) but, rather, the normalized symbol likelihoods. Therefore, the classic relationship, where the extrinsic LLRs are given by subtracting the a priori LLRs from the a posteriori LLRs, does not hold for the existing PDA-based detectors. Motivated by these revelations, we conceive a new approximate Bayesian-theorem-based logarithmic-domain PDA (AB-Log-PDA) method and unveil the technique of calculating bit-based extrinsic LLRs for the AB-Log-PDA, which facilitates the employment of the AB-Log-PDA in a simplified IDD receiver structure. Additionally, we demonstrate that we may dispense with inner iterations within the AB-Log-PDA in the context of IDD receivers. Our complexity analysis and numerical results recorded for Nakagami-m fading channels demonstrate that the proposed AB-Log-PDA-based IDD scheme is capable of achieving a performance comparable with that of the optimal maximum a posteriori (MAP)-detector-based IDD receiver, while imposing significantly lower computational complexity in the scenarios considered.
Kan injectivity in order-enriched categories
Venue: arXiv cs.LO 2013
Year: 2013

Continuous lattices were characterised by Martin Escardo as precisely the objects that are Kan-injective w.r.t. a certain class of morphisms. We study Kan-injectivity in general categories enriched in posets. For every class H of morphisms we study the subcategory of all objects Kan-injective w.r.t. H and all morphisms preserving Kan-extensions. For categories such as Top_0 and Pos we prove that whenever H is a set of morphisms, the above subcategory is monadic, and the monad it creates is a Kock-Zoeberlein monad. However, this does not generalise to proper classes: we present a class of continuous mappings in Top_0 for which Kan-injectivity does not yield a monadic category.
Managing Requirement Elicitation Issues Using Step-Wise Refinement Model
Venue: arXiv cs.SE 2013
Year: 2013

In this paper, a Step-wise Refinement model is proposed to elicit requirements in a more effective manner.
Strong Stability of Nash Equilibria in Load Balancing Games
Venue: arXiv cs.GT 2013
Year: 2013

We study strong stability of Nash equilibria in load balancing games of m (m >= 2) identical servers, in which every job chooses one of the m servers and each job wishes to minimize its cost, given by the workload of the server it chooses. A Nash equilibrium (NE) is a strategy profile that is resilient to unilateral deviations. Finding an NE in such a game is simple. However, an NE assignment is not stable against coordinated deviations of several jobs, while a strong Nash equilibrium (SNE) is. We study how well an NE approximates an SNE. Given any job assignment in a load balancing game, the improvement ratio (IR) of a deviation of a job is defined as the ratio between the pre- and post-deviation costs. An NE is said to be a r-approximate SNE (r >= 1) if there is no coalition of jobs such that each job of the coalition will have an IR more than r from coordinated deviations of the coalition. While it is already known that NEs are the same as SNEs in the 2-server load balancing game, we prove that, in the m-server load balancing game for any given m >= 3, any NE is a (5/4)-approximate SNE, which together with the lower bound already established in the literature yields a tight approximation bound. This closes the final gap in the literature on the study of approximation of general NEs to SNEs in load balancing games. To establish our upper bound, we make a novel use of a graph-theoretic tool.
Simple DFS on the Complement of a Graph and on Partially Complemented Digraphs
Venue: arXiv cs.DS 2013
Year: 2013

A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. A partially complemented digraph $\widetilde{G}$ is a digraph obtained from a sequence of vertex complement operations on $G$. Dahlhaus et al. showed that, given an adjacency-list representation of $\widetilde{G}$, depth-first search (DFS) on $G$ can be performed in $O(n + \widetilde{m})$ time, where $n$ is the number of vertices and $\widetilde{m}$ is the number of edges in $\widetilde{G}$. To achieve this bound, their algorithm makes use of a somewhat complicated stack-like data structure to simulate the recursion stack, instead of implementing it directly as a recursive algorithm. We give a recursive $O(n+\widetilde{m})$ algorithm that uses no complicated data-structures.
A new stopping criterion for the mean shift iterative algorithm
Venue: arXiv cs.CV 2013
Year: 2013

The mean shift iterative algorithm was proposed in 2006, for using the entropy as a stopping criterion. From then on, a theoretical base has been developed and a group of applications has been carried out using this algorithm. This paper proposes a new stopping criterion for the mean shift iterative algorithm, where stopping threshold via entropy is used now, but in another way. Many segmentation experiments were carried out by utilizing standard images and it was verified that a better segmentation was reached, and that the algorithm had better stability. An analysis on the convergence, through a theorem, with the new stopping criterion was carried out. The goal of this paper is to compare the new stopping criterion with the old criterion. For this reason, the obtained results were not compared with other segmentation approaches, since with the old stopping criterion were previously carried out.
Credible Autocoding of Fault Detection Observers
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, we present a domain specific process to assist the verification of observer-based fault detection software. Observer-based fault detection systems, like control systems, yield invariant properties of quadratic types. These quadratic invariants express both safety properties of the software such as the boundedness of the states and correctness properties such as the absence of false alarms from the fault detector. We seek to leverage these quadratic invariants, in an automated fashion, for the formal verification of the fault detection software. The approach, referred to as the credible autocoding framework [1], can be characterized as autocoding with proofs. The process starts with the fault detector model, along with its safety and correctness properties, all expressed formally in a synchronous modeling environment such as Simulink. The model is then transformed by a prototype credible autocoder into both code and analyzable annotations for the code. We demonstrate the credible autocoding process on a running example of an output observer fault detector for a 3-degrees-of-freedom (3DOF) helicopter control system.
An Experimental Comparison of Trust Region and Level Sets
Venue: arXiv cs.CV 2013
Year: 2013

High-order (non-linear) functionals have become very popular in segmentation, stereo and other computer vision problems. Level sets is a well established general gradient descent framework, which is directly applicable to optimization of such functionals and widely used in practice. Recently, another general optimization approach based on trust region methodology was proposed for regional non-linear functionals. Our goal is a comprehensive experimental comparison of these two frameworks in regard to practical efficiency, robustness to parameters, and optimality. We experiment on a wide range of problems with non-linear constraints on segment volume, appearance and shape.
Idea of a new Personality-Type based Recommendation Engine
Venue: arXiv cs.IR 2013
Year: 2013

Myers-Briggs Type Indicator (MBTI) types depict the psychological preferences by which a person perceives the world and make decisions. There are 4 principal functions through which the people see the world: sensation, intuition, feeling, and thinking. These functions along with the Introverted\Extroverted nature of the person, there are 16 personalities types, the humans are divided into. Here an idea is presented where a user can get recommendations for books, web media content, music and movies on the basis of the users' MBTI type. Only things like books and other media content has been chosen because the preferences in such things are mostly subjective. Apart from the recommended content that is generally generated on the basis of the previous purchases, searches can be enhanced by using the MBTI. A minimalist survey was designed for collecting the data. This has a more than 100 features that show the preference of a personality type. Those include preferences in book genres, music genres, movie genres and even video games genres. After analyzing the data that is collected from the survey, some inferences were drawn from it which can be used to design a new recommendation engine for recommending the content that coincides with the personality of the user.
Coding based Data Broadcasting for Time Critical Applications with Rate Adaptation
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we dynamically select the transmission rate and design wireless network coding to improve the quality of services such as delay for time critical applications. In a network coded system, with low transmission rate and hence longer transmission range, more packets may be encoded, which increases the coding opportunity. However, low transmission rate may incur extra transmission delay, which is intolerable for time critical applications. We design a novel joint rate selection and wireless network coding (RSNC) scheme with delay constraint, so as to maximize the total benefit (where we can define the benefit based on the priority or importance of a packet for example) of the packets that are successfully received at the destinations without missing their deadlines. We prove that the proposed problem is NP-hard, and propose a novel graph model to mathematically formulate the problem. For the general case, we propose a transmission metric and design an efficient algorithm to determine the transmission rate and coding strategy for each transmission. For a special case when all delay constraints are the same, we study the pairwise coding and present a polynomial time pairwise coding algorithm that achieves an approximation ratio of 1 - 1/e to the optimal pairwise coding solution, where e is the base of the natural logarithm. Finally, simulation results demonstrate the superiority of the proposed RSNC scheme.
Uplink Scheduling Strategy Based on A Population Game in Vehicular Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Recent advances in the integration of vehicular sensor network (VSN) technology, and crowd sensing leveraging pervasive sensors called onboard units (OBUs), like smartphones and radio frequency IDentifications to provide sensing services, have attracted increasing attention from both industry and academy. Nowadays, existing vehicular sensing applications lack good mechanisms to improve the maximum achievable throughput and minimizing service time of participating sensing OBUs in vehicular sensor networks. To fill these gaps, in this paper, first, we introduce real imperfect link states to the calculation of Markov chains. Second, we incorporate the result of different link states for multiple types of vehicles with the calculations of uplink throughput and service time. Third, in order to accurately calculate the service time of an OBU, we introduce the steady state probability to calculate the exact time of a duration for back-off decrement, rather than using the traditional relative probability. Additionally, to our best knowledge, we first explore a multichannel scheduling strategy of uplink data access in a single roadside unit (RSU) by using a non-cooperative game in a RSU coverage region to maximize the uplink throughput and minimize service time under saturated and unsaturated traffic loads. To this end, we conduct a theoretical analysis and find the equilibrium point of the scheduling. The numerical results show that the solution of the equilibrium points are consistent with optimization problems.
Robust Adaptive Beamforming Based on Low-Complexity Shrinkage-Based Mismatch Estimation
Venue: arXiv cs.IT 2013
Year: 2013

In this work, we propose a low-complexity robust adaptive beamforming (RAB) technique which estimates the steering vector using a Low-Complexity Shrinkage-Based Mismatch Estimation (LOCSME) algorithm. The proposed LOCSME algorithm estimates the covariance matrix of the input data and the interference-plus-noise covariance (INC) matrix by using the Oracle Approximating Shrinkage (OAS) method. LOCSME only requires prior knowledge of the angular sector in which the actual steering vector is located and the antenna array geometry. LOCSME does not require a costly optimization algorithm and does not need to know extra information from the interferers, which avoids direction finding for all interferers. Simulations show that LOCSME outperforms previously reported RAB algorithms and has a performance very close to the optimum.
Providing Trustworthy Contributions via a Reputation Framework in Social Participatory Sensing Systems
Venue: arXiv cs.SI 2013
Year: 2013

Social participatory sensing is a newly proposed paradigm that tries to address the limitations of participatory sensing by leveraging online social networks as an infrastructure. A critical issue in the success of this paradigm is to assure the trustworthiness of contributions provided by participants. In this paper, we propose an application-agnostic reputation framework for social participatory sensing systems. Our framework considers both the quality of contribution and the trustworthiness level of participant within the social network. These two aspects are then combined via a fuzzy inference system to arrive at a final trust rating for a contribution. A reputation score is also calculated for each participant as a resultant of the trust ratings assigned to him. We adopt the utilization of PageRank algorithm as the building block for our reputation module. Extensive simulations demonstrate the efficacy of our framework in achieving high overall trust and assigning accurate reputation scores.
StreaMon: a data-plane programming abstraction for Software-defined Stream Monitoring
Venue: arXiv cs.NI 2013
Year: 2013

The fast evolving nature of modern cyber threats and network monitoring needs calls for new, "software-defined", approaches to simplify and quicken programming and deployment of online (stream-based) traffic analysis functions. StreaMon is a carefully designed data-plane abstraction devised to scalably decouple the "programming logic" of a traffic analysis application (tracked states, features, anomaly conditions, etc.) from elementary primitives (counting and metering, matching, events generation, etc), efficiently pre-implemented in the probes, and used as common instruction set for supporting the desired logic. Multi-stage multi-step real-time tracking and detection algorithms are supported via the ability to deploy custom states, relevant state transitions, and associated monitoring actions and triggering conditions. Such a separation entails platform-independent, portable, online traffic analysis tasks written in a high level language, without requiring developers to access the monitoring device internals and program their custom monitoring logic via low level compiled languages (e.g., C, assembly, VHDL). We validate our design by developing a prototype and a set of simple (but functionally demanding) use-case applications and by testing them over real traffic traces.