OpenRaiser/Intern-Atlas huggingface dataset:
Understanding Trajectory Behavior: A Motion Pattern Approach
Venue: arXiv cs.CV 2015
Year: 2015

Mining the underlying patterns in gigantic and complex data is of great importance to data analysts. In this paper, we propose a motion pattern approach to mine frequent behaviors in trajectory data. Motion patterns, defined by a set of highly similar flow vector groups in a spatial locality, have been shown to be very effective in extracting dominant motion behaviors in video sequences. Inspired by applications and properties of motion patterns, we have designed a framework that successfully solves the general task of trajectory clustering. Our proposed algorithm consists of four phases: flow vector computation, motion component extraction, motion component's reachability set creation, and motion pattern formation. For the first phase, we break down trajectories into flow vectors that indicate instantaneous movements. In the second phase, via a Kmeans clustering approach, we create motion components by clustering the flow vectors with respect to their location and velocity. Next, we create motion components' reachability set in terms of spatial proximity and motion similarity. Finally, for the fourth phase, we cluster motion components using agglomerative clustering with the weighted Jaccard distance between the motion components' signatures, a set created using path reachability. We have evaluated the effectiveness of our proposed method in an extensive set of experiments on diverse datasets. Further, we have shown how our proposed method handles difficulties in the general task of trajectory clustering that challenge the existing state-of-the-art methods.
Sum of Squares Lower Bounds from Pairwise Independence
Venue: arXiv cs.CC 2015
Year: 2015

We prove that for every $ε>0$ and predicate $P:\{0,1\}^k\rightarrow \{0,1\}$ that supports a pairwise independent distribution, there exists an instance $\mathcal{I}$ of the $\mathsf{Max}P$ constraint satisfaction problem on $n$ variables such that no assignment can satisfy more than a $\tfrac{|P^{-1}(1)|}{2^k}+ε$ fraction of $\mathcal{I}$'s constraints but the degree $Ω(n)$ Sum of Squares semidefinite programming hierarchy cannot certify that $\mathcal{I}$ is unsatisfiable. Similar results were previously only known for weaker hierarchies.
Identifying Relevant Document Facets for Keyword-Based Search Queries
Venue: arXiv cs.IR 2015
Year: 2015

As structured documents with rich metadata (such as products, movies, etc.) become increasingly prevalent, searching those documents has become an important IR problem. Although advanced search interfaces are widely available, most users still prefer to use keyword-based queries to search those documents. Query keywords often imply some hidden restrictions on the desired documents, which can be represented as document facet-value pairs. To achieve high retrieval performance, it's important to be able to identify the relevant facet-value pairs hidden in a query. In this paper, we study the problem of identifying document facet-value pairs that are relevant to a keyword-based search query. We propose a machine learning approach and a set of useful features, and evaluate our approach using a movie data set from INEX.
On Sharing, Memoization, and Polynomial Time (Long Version)
Venue: arXiv cs.CC 2015
Year: 2015

We study how the adoption of an evaluation mechanism with sharing and memoization impacts the class of functions which can be computed in polynomial time. We first show how a natural cost model in which lookup for an already computed value has no cost is indeed invariant. As a corollary, we then prove that the most general notion of ramified recurrence is sound for polynomial time, this way settling an open problem in implicit computational complexity.
The Effects of Research Level and Article Type on the Differences between Citation Metrics and F1000 Recommendations
Venue: arXiv cs.DL 2015
Year: 2015

F1000 recommendations have been validated as a potential data source for research evaluation, but reasons for differences between F1000 Article Factor (FFa scores) and citations remain to be explored. By linking 28254 publications in F1000 to citations in Scopus, we investigated the effect of research level and article type on the internal consistency of assessments based on citations and FFa scores. It turns out that research level has little impact, while article type has big effect on the differences. These two measures are significantly different for two groups: non-primary research or evidence-based research publications are more highly cited rather than highly recommended, however, translational research or transformative research publications are more highly recommended by faculty members but gather relatively lower citations. This can be expected because citation activities are usually practiced by academic authors while the potential for scientific revolutions and the suitability for clinical practice of an article should be investigated from the practitioners' points of view. We conclude with a policy relevant recommendation that the application of bibliometric approaches in research evaluation procedures should include the proportion of three types of publications: evidence-based research, transformative research, and translational research. The latter two types are more suitable to be assessed through peer review.
Constraint-based sequence mining using constraint programming
Venue: arXiv cs.AI 2015
Year: 2015

The goal of constraint-based sequence mining is to find sequences of symbols that are included in a large number of input sequences and that satisfy some constraints specified by the user. Many constraints have been proposed in the literature, but a general framework is still missing. We investigate the use of constraint programming as general framework for this task. We first identify four categories of constraints that are applicable to sequence mining. We then propose two constraint programming formulations. The first formulation introduces a new global constraint called exists-embedding. This formulation is the most efficient but does not support one type of constraint. To support such constraints, we develop a second formulation that is more general but incurs more overhead. Both formulations can use the projected database technique used in specialised algorithms. Experiments demonstrate the flexibility towards constraint-based settings and compare the approach to existing methods.
On Probability Estimation by Exponential Smoothing
Venue: arXiv cs.IT 2015
Year: 2015

Probability estimation is essential for every statistical data compression algorithm. In practice probability estimation should be adaptive, recent observations should receive a higher weight than older observations. We present a probability estimation method based on exponential smoothing that satisfies this requirement and runs in constant time per letter. Our main contribution is a theoretical analysis in case of a binary alphabet for various smoothing rate sequences: We show that the redundancy w.r.t. a piecewise stationary model with $s$ segments is $O\left(s\sqrt n\right)$ for any bit sequence of length $n$, an improvement over redundancy $O\left(s\sqrt{n\log n}\right)$ of previous approaches with similar time complexity.
Unknown Words Analysis in POS tagging of Sinhala Language
Venue: arXiv cs.CL 2015
Year: 2015

Part of Speech (POS) is a very vital topic in Natural Language Processing (NLP) task in any language, which involves analysing the construction of the language, behaviours and the dynamics of the language, the knowledge that could be utilized in computational linguistics analysis and automation applications. In this context, dealing with unknown words (words do not appear in the lexicon referred as unknown words) is also an important task, since growing NLP systems are used in more and more new applications. One aid of predicting lexical categories of unknown words is the use of syntactical knowledge of the language. The distinction between open class words and closed class words together with syntactical features of the language used in this research to predict lexical categories of unknown words in the tagging process. An experiment is performed to investigate the ability of the approach to parse unknown words using syntactical knowledge without human intervention. This experiment shows that the performance of the tagging process is enhanced when word class distinction is used together with syntactic rules to parse sentences containing unknown words in Sinhala language.
Tableaux Modulo Theories Using Superdeduction
Venue: arXiv cs.LO 2015
Year: 2015

We propose a method that allows us to develop tableaux modulo theories using the principles of superdeduction, among which the theory is used to enrich the deduction system with new deduction rules. This method is presented in the framework of the Zenon automated theorem prover, and is applied to the set theory of the B method. This allows us to provide another prover to Atelier B, which can be used to verify B proof rules in particular. We also propose some benchmarks, in which this prover is able to automatically verify a part of the rules coming from the database maintained by Siemens IC-MOL. Finally, we describe another extension of Zenon with superdeduction, which is able to deal with any first order theory, and provide a benchmark coming from the TPTP library, which contains a large set of first order problems.
Device Fingerprinting in Wireless Networks: Challenges and Opportunities
Venue: arXiv cs.NI 2015
Year: 2015

Node forgery or impersonation, in which legitimate cryptographic credentials are captured by an adversary, constitutes one major security threat facing wireless networks. The fact that mobile devices are prone to be compromised and reverse engineered significantly increases the risk of such attacks in which adversaries can obtain secret keys on trusted nodes and impersonate the legitimate node. One promising approach toward thwarting these attacks is through the extraction of unique fingerprints that can provide a reliable and robust means for device identification. These fingerprints can be extracted from transmitted signal by analyzing information across the protocol stack. In this paper, the first unified and comprehensive tutorial in the area of wireless device fingerprinting for security applications is presented. In particular, we aim to provide a detailed treatment on developing novel wireless security solutions using device fingerprinting techniques. The objectives are three-fold: (i) to introduce a comprehensive taxonomy of wireless features that can be used in fingerprinting, (ii) to provide a systematic review on fingerprint algorithms including both white-list based and unsupervised learning approaches, and (iii) to identify key open research problems in the area of device fingerprinting and feature extraction, as applied to wireless security.
A Case Study: Task Scheduling Methodologies for High Speed Computing Systems
Venue: arXiv cs.OS 2015
Year: 2015

High Speed computing meets ever increasing real-time computational demands through the leveraging of flexibility and parallelism. The flexibility is achieved when computing platform designed with heterogeneous resources to support multifarious tasks of an application where as task scheduling brings parallel processing. The efficient task scheduling is critical to obtain optimized performance in heterogeneous computing Systems (HCS). In this paper, we brought a review of various application scheduling models which provide parallelism for homogeneous and heterogeneous computing systems. In this paper, we made a review of various scheduling methodologies targeted to high speed computing systems and also prepared summary chart. The comparative study of scheduling methodologies for high speed computing systems has been carried out based on the attributes of platform & application as well. The attributes are execution time, nature of task, task handling capability, type of host & computing platform. Finally a summary chart has been prepared and it demonstrates that the need of developing scheduling methodologies for Heterogeneous Reconfigurable Computing Systems (HRCS) which is an emerging high speed computing platform for real time applications.
Warp-Level Parallelism: Enabling Multiple Replications In Parallel on GPU
Venue: arXiv cs.DC 2015
Year: 2015

Stochastic simulations need multiple replications in order to build confidence intervals for their results. Even if we do not need a large amount of replications, it is a good practice to speed-up the whole simulation time using the Multiple Replications In Parallel (MRIP) approach. This approach usually supposes to have access to a parallel computer such as a symmetric mul-tiprocessing machine (with many cores), a computing cluster or a computing grid. In this paper, we propose Warp-Level Parallelism (WLP), a GP-GPU-enabled solution to compute MRIP on GP-GPUs (General-Purpose Graphics Processing Units). These devices display a great amount of parallel computational power at low cost, but are tuned to process efficiently the same operation on several data, through different threads. Indeed, this paradigm is called Single Instruction, Multiple Threads (SIMT). Our approach proposes to rely on small threads groups, called warps, to perform independent computations such as replications. We have benchmarked WLP with three different models: it allows MRIP to be computed up to six times faster than with the SIMT computing paradigm.
An Effective Handover Analysis for the Randomly Distributed Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

Handover rate is one of the most import metrics to instruct mobility management and resource management in wireless cellular networks. In the literature, the mathematical expression of handover rate has been derived for homogeneous cellular network by both regular hexagon coverage model and stochastic geometry model, but there has not been any reliable result for heterogeneous cellular networks (HCNs). Recently, stochastic geometry modeling has been shown to model well the real deployment of HCNs and has been extensively used to analyze HCNs. In this paper, we give an effective handover analysis for HCNs by stochastic geometry modeling, derive the mathematical expression of handover rate by employing an infinitesimal method for a generalized multi-tier scenario, discuss the result by deriving some meaningful corollaries, and validate the analysis by computer simulation with multiple walking models. By our analysis, we find that in HCNs the handover rate is related to many factors like the base stations' densities and transmitting powers, user's velocity distribution, bias factor, pass loss factor and etc. Although our analysis focuses on the scenario of multi-tier HCNs, the analytical framework can be easily extended for more complex scenarios, and may shed some light for future study.
IEEE 802.11ax: High-Efficiency WLANs
Venue: arXiv cs.NI 2015
Year: 2015

IEEE 802.11ax-2019 will replace both IEEE 802.11n-2009 and IEEE 802.11ac-2013 as the next high-throughput Wireless Local Area Network (WLAN) amendment. In this paper, we review the expected future WLAN scenarios and use-cases that justify the push for a new PHY/MAC IEEE 802.11 amendment. After that, we overview a set of new technical features that may be included in the IEEE 802.11ax-2019 amendment and describe both their advantages and drawbacks. Finally, we discuss some of the network-level functionalities that are required to fully improve the user experience in next-generation WLANs and note their relation with other on-going IEEE 802.11 amendments.
Survey of Uncertainty Handling in Cloud Service Discovery and Composition
Venue: arXiv cs.SE 2015
Year: 2015

With the spread of services related to cloud environment, it is tiresome and time consuming for users to look for the appropriate service that meet with their needs. Therefore, finding a valid and reliable service is essential. However, in case a single cloud service cannot fulfil every user requirements, a composition of cloud services is needed. In addition, the need to treat uncertainty in cloud service discovery and composition induces a lot of concerns in order to minimize the risk. Risk includes some sort of either loss or damage which is possible to be received by a target (i.e., the environment, cloud providers or customers). In this paper, we will focus on the uncertainty application for cloud service discovery and composition. A set of existing approaches in literature are reviewed and categorized according to the risk modeling.
A New Proof for the DoF Region of the MIMO Networks with No CSIT
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a new proof for the degrees of freedom (DoF) region of the K-user multiple-input multiple-output (MIMO) broadcast channel (BC) with no channel state information at the transmitter (CSIT) and perfect channel state information at the receivers (CSIR) is provided. Based on this proof, the capacity region of a certain class of MIMO BC with channel distribution information at the transmitter (CDIT) and perfect CSIR is derived. Finally, an outer bound for the DoF region of the K-user MIMO interference channel (IC) with no CSIT is provided.
KitRobot: A multi-platform graphical programming IDE to program mini-robotic agents
Venue: arXiv cs.PL 2015
Year: 2015

The analysis, design and development of a graphical programming IDE for mini-robotic agents allows novice users to program robotic agents by a graphical drag and drop interface, without knowing the syntax and semantics of the intermediate programming language. Our work started with the definition of the syntax and semantics of the intermediate programming language. The major work is the definition of grammar for this language. The use of a graphical drag and drop interface for programming mini-robots offers a user-friendly interface to novice users. The user can program graphically by drag and drop program parts without having expertise of the intermediate programming language. The IDE is highly flexible as it uses xml technology to store program objects (i.e. loops, conditions) and robot objects (i.e. sensors, actuators). Use of xml technology allows making major changes and updating the interface without modifying the underlying design and programming.
Combinatorial Optimization Algorithms via Polymorphisms
Venue: arXiv cs.CC 2015
Year: 2015

An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, the characterization asserts that a CSP Λ is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to Λ to create new ones. In an entirely separate line of work, the unique games conjecture yields a characterization of approximability of Max-CSPs. Surprisingly, this characterization for Max-CSPs can also be reformulated in the language of polymorphisms. In this work, we study whether existence of non-trivial polymorphisms implies tractability beyond the realm of constraint satisfaction problems, namely in the value-oracle model. Specifically, given a function f in the value-oracle model along with an appropriate operation that never increases the value of f , we design algorithms to minimize f . In particular, we design a randomized algorithm to minimize a function f that admits a fractional polymorphism which is measure preserving and has a transitive symmetry. We also reinterpret known results on MaxCSPs and thereby reformulate the unique games conjecture as a characterization of approximability of max-CSPs in terms of their approximate polymorphisms.
LeoTask: a fast, flexible and reliable framework for computational research
Venue: arXiv cs.SE 2015
Year: 2015

LeoTask is a Java library for computation-intensive and time-consuming research tasks. It automatically executes tasks in parallel on multiple CPU cores on a computing facility. It uses a configuration file to enable automatic exploration of parameter space and flexible aggregation of results, and therefore allows researchers to focus on programming the key logic of a computing task. It also supports reliable recovery from interruptions, dynamic and cloneable networks, and integration with the plotting software Gnuplot.
Optimal Radiometric Calibration for Camera-Display Communication
Venue: arXiv cs.CV 2015
Year: 2015

We present a novel method for communicating between a camera and display by embedding and recovering hidden and dynamic information within a displayed image. A handheld camera pointed at the display can receive not only the display image, but also the underlying message. These active scenes are fundamentally different from traditional passive scenes like QR codes because image formation is based on display emittance, not surface reflectance. Detecting and decoding the message requires careful photometric modeling for computational message recovery. Unlike standard watermarking and steganography methods that lie outside the domain of computer vision, our message recovery algorithm uses illumination to optically communicate hidden messages in real world scenes. The key innovation of our approach is an algorithm that performs simultaneous radiometric calibration and message recovery in one convex optimization problem. By modeling the photometry of the system using a camera-display transfer function (CDTF), we derive a physics-based kernel function for support vector machine classification. We demonstrate that our method of optimal online radiometric calibration (OORC) leads to an efficient and robust algorithm for computational messaging between nine commercial cameras and displays.
Performance Analysis and Optimal Filter Design for Sigma-Delta Modulation via Duality with DPCM
Venue: arXiv cs.IT 2015
Year: 2015

Sampling above the Nyquist rate is at the heart of sigma-delta modulation, where the increase in sampling rate is translated to a reduction in the overall (mean-squared-error) reconstruction distortion. This is attained by using a feedback filter at the encoder, in conjunction with a low-pass filter at the decoder. The goal of this work is to characterize the optimal trade-off between the per-sample quantization rate and the resulting mean-squared-error distortion, under various restrictions on the feedback filter. To this end, we establish a duality relation between the performance of sigma-delta modulation, and that of differential pulse-code modulation when applied to (discrete-time) band-limited inputs. As the optimal trade-off for the latter scheme is fully understood, the full characterization for sigma-delta modulation, as well as the optimal feedback filters, immediately follow.
A study of the interface usability issues of mobile learning applications for smart phones from the users perspective
Venue: arXiv cs.CY 2015
Year: 2015

A conceptual framework for measuring the usability characteristics of mobile learning (m-Learning) application has been developed. Furthermore, a software prototype for smartphones to assess usability issues of m-Learning applications has also been designed and implemented. This prototype has been developed, using Java language and the Android Software Development Kit, based on the recommended guidelines of the proposed conceptual framework. The usability of the proposed model was compared to a generally available similar mobile application (based on the Blackboard) by conducting a questionnairebased survey at Western University. The two models were evaluated in terms of ease of use, user satisfaction, attractiveness, and learnability. The results of the questionnaire showed that the participants considered the user interface based on our proposed framework more user-friendly as compared to the Blackboard-based user interface.