OpenRaiser/Intern-Atlas huggingface dataset:
Adaptive Computation of the Klee's Measure in High Dimensions
Venue: arXiv cs.DS 2015
Year: 2015

The KLEE'S MESURE of $n$ axis-parallel boxes in $\mathbb{R}^d$ is the volume of their union. It can be computed in time within $O(n^{d/2})$ in the worst case. We describe three techniques to boost its computation: one based on some type of "degeneracy'' of the input, and two ones on the inherent "easiness'' of the structure of the input. The first technique benefits from instances where the MAXIMA of the input is of small size $h$, and yields a solution running in time within $O(n\log^{2d-2}{h}+ h^{d/2}) \subseteq O(n^{d/2}$). The second technique takes advantage of instances where no $d$-dimensional axis-aligned hyperplane intersects more than $k$ boxes in some dimension, and yields a solution running in time within $O(n \log n + n k^{(d-2)/2}) \subseteq O(n^{d/2})$. The third technique takes advantage of instances where the \emph{intersection graph} of the input has small treewidth $ω$. It yields an algorithm running in time within $O(n^4ω\log ω+ n (ω\log ω)^{d/2})$ in general, and in time within $O(n \log n + n ω^{d/2})$ if an optimal tree decomposition of the intersection graph is given. We show how to combine these techniques in an algorithm which takes advantage of all three configurations.
Ontology Based Document Clustering Using MapReduce
Venue: arXiv cs.DB 2015
Year: 2015

Nowadays, document clustering is considered as a data intensive task due to the dramatic, fast increase in the number of available documents. Nevertheless, the features that represent those documents are also too large. The most common method for representing documents is the vector space model, which represents document features as a bag of words and does not represent semantic relations between words. In this paper we introduce a distributed implementation for the bisecting k-means using MapReduce programming model. The aim behind our proposed implementation is to solve the problem of clustering intensive data documents. In addition, we propose integrating the WordNet ontology with bisecting k-means in order to utilize the semantic relations between words to enhance document clustering results. Our presented experimental results show that using lexical categories for nouns only enhances internal evaluation measures of document clustering; and decreases the documents features from thousands to tens features. Our experiments were conducted using Amazon Elastic MapReduce to deploy the Bisecting k-means algorithm.
Optimal Data and Training Symbol Ratio for Communication over Uncertain Channels
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of determining the power ratio between the training symbols and data symbols in order to maximize the channel capacity for transmission over uncertain channels with a channel estimate available at both the transmitter and receiver. The receiver makes an estimate of the channel by using a known sequence of training symbols. This channel estimate is then transmitted back to the transmitter. The capacity that the transceiver maximizes is the worst case capacity, in the sense that given a noise covariance, the transceiver maximizes the minimal capacity over all distributions of the measurement noise under a fixed covariance matrix known at both the transmitter and receiver. We give an exact expression of the channel capacity as a function of the channel covariance matrix, and the number of training symbols used during a coherence time interval. This expression determines the number of training symbols that need to be used by finding the optimal integer number of training symbols that maximize the channel capacity. As a bi-product, we show that linear filters are optimal at both the transmitter and receiver.
Turn Segmentation into Utterances for Arabic Spontaneous Dialogues and Instance Messages
Venue: arXiv cs.CL 2015
Year: 2015

Text segmentation task is an essential processing task for many of Natural Language Processing (NLP) such as text summarization, text translation, dialogue language understanding, among others. Turns segmentation considered the key player in dialogue understanding task for building automatic Human-Computer systems. In this paper, we introduce a novel approach to turn segmentation into utterances for Egyptian spontaneous dialogues and Instance Messages (IM) using Machine Learning (ML) approach as a part of automatic understanding Egyptian spontaneous dialogues and IM task. Due to the lack of Egyptian dialect dialogue corpus the system evaluated by our corpus includes 3001 turns, which are collected, segmented, and annotated manually from Egyptian call-centers. The system achieves F1 scores of 90.74% and accuracy of 95.98%.
Sentiment Analysis For Modern Standard Arabic And Colloquial
Venue: arXiv cs.CL 2015
Year: 2015

The rise of social media such as blogs and social networks has fueled interest in sentiment analysis. With the proliferation of reviews, ratings, recommendations and other forms of online expression, online opinion has turned into a kind of virtual currency for businesses looking to market their products, identify new opportunities and manage their reputations, therefore many are now looking to the field of sentiment analysis. In this paper, we present a feature-based sentence level approach for Arabic sentiment analysis. Our approach is using Arabic idioms/saying phrases lexicon as a key importance for improving the detection of the sentiment polarity in Arabic sentences as well as a number of novels and rich set of linguistically motivated features contextual Intensifiers, contextual Shifter and negation handling), syntactic features for conflicting phrases which enhance the sentiment classification accuracy. Furthermore, we introduce an automatic expandable wide coverage polarity lexicon of Arabic sentiment words. The lexicon is built with gold-standard sentiment words as a seed which is manually collected and annotated and it expands and detects the sentiment orientation automatically of new sentiment words using synset aggregation technique and free online Arabic lexicons and thesauruses. Our data focus on modern standard Arabic (MSA) and Egyptian dialectal Arabic tweets and microblogs (hotel reservation, product reviews, etc.). The experimental results using our resources and techniques with SVM classifier indicate high performance levels, with accuracies of over 95%.
Musings on generic-case complexity
Venue: arXiv cs.CC 2015
Year: 2015

We propose a more general definition of generic-case complexity, based on using a random process for generating inputs of an algorithm and using the time needed to generate an input as a way of measuring the size of that input.
An Information-theoretic Model for Knowledge Sharing in Opportunistic Social Networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we establish fundamental limits on the performance of knowledge sharing in opportunistic social net- works. In particular, we introduce a novel information-theoretic model to characterize the performance limits of knowledge sharing policies. Towards this objective, we first introduce the notions of knowledge gain and its upper bound, knowledge gain limit, per user. Second, we characterize these quantities for a number of network topologies and sharing policies. This work constitutes a first step towards defining and characterizing the performance limits and trade-offs associated with knowledge sharing in opportunistic social networks. Finally, we present nu- merical results characterizing the cumulative knowledge gain over time and its upper bound, using publicly available smartphone data. The results confirm the key role of the proposed model to motivate future research in this ripe area of research as well as new knowledge sharing policies.
Network Internet-communications as an instrument of marketing
Venue: arXiv cs.CY 2015
Year: 2015

The article is about the features of application of network Internet-communications for advancement of the goods. Wide development of Internet technologies has transformed social communications into the independent tool of marketing. Authors classify and analyze possibilities of use of network Internet-communications in the marketing environment.
Institutionalization of the payment environment of e-commerce in Russia
Venue: arXiv cs.CY 2015
Year: 2015

Article about problems of Institutionalization of the payment environment of e-commerce. The author analyzes tendencies of development of payment institutes and prospect of creation of the International financial Centre in Russia on the basis of primary development of e-commerce in spheres B2C and C2C. The author proves, that in the conditions of globalization of the consumer markets the analysis of a role and a place of transboundary private payments in structure of National payment system of the Russian Federation become especially current.
Towards a Speed of Light Internet
Venue: arXiv cs.NI 2015
Year: 2015

In principle, a network can transfer data at nearly the speed of light. Today's Internet, however, is much slower: our measurements show that latencies are typically more than one, and often more than two orders of magnitude larger than the lower bound implied by the speed of light. Closing this gap would not only add value to today's Internet applications, but might also open the door to exciting new applications. Thus, we propose a grand challenge for the networking research community: building a speed-of-light Internet. Towards addressing this goal, we begin by investigating the causes of latency inflation in the Internet across the network stack. Our analysis reveals that while protocol overheads, which have dominated the community's attention, are indeed important, infrastructural inefficiencies are a significant and under-explored problem. Thus, we propose a radical, yet surprisingly low-cost approach to mitigating latency inflation at the lowest layers and building a nearly speed-of-light Internet infrastructure.
A Review Paper: Noise Models in Digital Image Processing
Venue: arXiv cs.CV 2015
Year: 2015

Noise is always presents in digital images during image acquisition, coding, transmission, and processing steps. Noise is very difficult to remove it from the digital images without the prior knowledge of noise model. That is why, review of noise models are essential in the study of image denoising techniques. In this paper, we express a brief overview of various noise models. These noise models can be selected by analysis of their origin. In this way, we present a complete and quantitative analysis of noise models available in digital images.
Some Analytics for Steiner Minimal Tree Problem for Four Terminals
Venue: arXiv cs.CG 2015
Year: 2015

Given the coordinates of four terminals in the Euclidean plane we present explicit formulas for Steiner point coordinates for Steiner minimal tree problem. We utilize the obtained formulas for evaluation of the influence of terminal coordinates on the loci of Steiner points.
Neural Network with Unbounded Activation Functions is Universal Approximator
Venue: arXiv cs.NE 2015
Year: 2015

This paper presents an investigation of the approximation property of neural networks with unbounded activation functions, such as the rectified linear unit (ReLU), which is the new de-facto standard of deep learning. The ReLU network can be analyzed by the ridgelet transform with respect to Lizorkin distributions. By showing three reconstruction formulas by using the Fourier slice theorem, the Radon transform, and Parseval's relation, it is shown that a neural network with unbounded activation functions still satisfies the universal approximation property. As an additional consequence, the ridgelet transform, or the backprojection filter in the Radon domain, is what the network learns after backpropagation. Subject to a constructive admissibility condition, the trained network can be obtained by simply discretizing the ridgelet transform, without backpropagation. Numerical examples not only support the consistency of the admissibility condition but also imply that some non-admissible cases result in low-pass filtering.
A light metric spanner
Venue: arXiv cs.CG 2015
Year: 2015

It has long been known that $d$-dimensional Euclidean point sets admit $(1+ε)$-stretch spanners with lightness $W_E = ε^{-O(d)}$, that is total edge weight at most $W_E$ times the weight of the minimum spaning tree of the set [DHN93]. Whether or not a similar result holds for metric spaces with low doubling dimension has remained an important open problem, and has resisted numerous attempts at resolution. In this paper, we resolve the question in the affirmative, and show that doubling spaces admit $(1+ε)$-stretch spanners with lightness $W_D = (ddim/ε)^{O(ddim)}$. Important in its own right, our result also implies a much faster polynomial-time approximation scheme for the traveling salesman problemin doubling metric spaces, improving upon the bound presented in [BGK-12].
A Generalized Non-Linear Composite Fading Model
Venue: arXiv cs.IT 2015
Year: 2015

This work is devoted to the formulation and derivation of the $α{-}κ{-}μ{/}$gamma distribution which corresponds to a physical fading model. The proposed distribution is composite and is constituted by the $α{-}κ{-}μ$ non-linear generalized multipath model and the gamma shadowing model. It also constitute the basis for deriving the $α{-}κ{-}μ$ \textit{Extreme}${/}$gamma model which accounts for non-linear severe multipath and shadowing effects and also includes the more widely known $α{-}μ$ and $κ{-}μ$ models which includes as special cases the Rice, Weibull, Nakagami-$m$ and Rayleigh distributions. The derived models provide accurate characterisation of the simultaneous occurrence of multipath fading and shadowing effects. This is achieved thanks to the remarkable flexibility of their named parameters which have been shown to render them capable of providing good fittings to experimental data associated with realistic communication scenarios. This is also evident by the fact that they include as special cases the widely known composite fading models such as the recently reported $κ{-}μ{/}$gamma model and the novel $α{-}μ{/}$gamma model. Novel analytic expressions are derived for the corresponding probability density function of these distributions which are expressed in a convenient algebraic form and can be efficiently utilized in the derivation of numerous vital measures in investigations related to the analytic performance evaluation of digital communications over composite multipath${/}$shadowing fading channels.
General Riemannian SOM
Venue: arXiv cs.NE 2015
Year: 2015

Kohonen's Self-Organizing Maps (SOMs) have proven to be a successful data-reduction method to identify the intrinsic lower-dimensional sub-manifold of a data set that is scattered in the higher-dimensional feature space. Motivated by the possibly non-Euclidian nature of the feature space and of the intrinsic geometry of the data set, we extend the definition of classic SOMs to obtain the General Riemannian SOM (GRiSOM). We additionally provide an implementation as a proof-of-concept for geometries with constant curvature. We furthermore perform the analytic and numerical analysis of the stability limits of certain (GRi)SOM configurations covering the different possible regular tessellation of the map space in each geometry. A deviation between the numerical and analytic stability limit has been observed for the square and hexagonal Euclidean maps for very small neighbourhoods in the map space as well as agreement in case of longer-ranged relations between the map nodes.
A multi-criteria service selection algorithm for business process requirements
Venue: arXiv cs.SE 2015
Year: 2015

The selection of the most appropriate Web services to realize business tasks still remain an open issue. We propose a multi-criteria algorithm for efficient service selection. Web services and their QoS values are stored in a Web service ontology (WSOnto) and business processes are modeled with the BPMN2.0 specifications. Our algorithm performs an instance-based ontology matching between the WSOnto and the business process ontology. The business context, functional properties and QoS values of Web services are considered. The algorithm computes the variation of QoS values over times. This strategy allows better accurate Web services ranking relevant to a user's request.
Spacecraft Attitude Stabilization with Piecewise-constant Magnetic Dipole Moment
Venue: arXiv cs.SY 2015
Year: 2015

In actual implementations of magnetic control laws for spacecraft attitude stabilization, the time in which Earth magnetic field is measured must be separated from the time in which magnetic dipole moment is generated. The latter separation translates into the constraint of being able to genere only piecewise-constant magnetic dipole moment. In this work we present attitude stabilization laws using only magnetic actuators that take into account of the latter aspect. Both a state feedback and an output feedback are presented, and it is shown that the proposed design allows for a systematic selection of the sampling period.
A Fast and Scalable Graph Coloring Algorithm for Multi-core and Many-core Architectures
Venue: arXiv cs.DC 2015
Year: 2015

Irregular computations on unstructured data are an important class of problems for parallel programming. Graph coloring is often an important preprocessing step, e.g. as a way to perform dependency analysis for safe parallel execution. The total run time of a coloring algorithm adds to the overall parallel overhead of the application whereas the number of colors used determines the amount of exposed parallelism. A fast and scalable coloring algorithm using as few colors as possible is vital for the overall parallel performance and scalability of many irregular applications that depend upon runtime dependency analysis. Catalyurek et al. have proposed a graph coloring algorithm which relies on speculative, local assignment of colors. In this paper we present an improved version which runs even more optimistically with less thread synchronization and reduced number of conflicts compared to Catalyurek et al.'s algorithm. We show that the new technique scales better on multi-core and many-core systems and performs up to 1.5x faster than its predecessor on graphs with high-degree vertices, while keeping the number of colors at the same near-optimal levels.
How, What and Why to test an ontology
Venue: arXiv cs.AI 2015
Year: 2015

Ontology development relates to software development in that they both involve the production of formal computational knowledge. It is possible, therefore, that some of the techniques used in software engineering could also be used for ontologies; for example, in software engineering testing is a well-established process, and part of many different methodologies. The application of testing to ontologies, therefore, seems attractive. The Karyotype Ontology is developed using the novel Tawny-OWL library. This provides a fully programmatic environment for ontology development, which includes a complete test harness. In this paper, we describe how we have used this harness to build an extensive series of tests as well as used a commodity continuous integration system to link testing deeply into our development process; this environment, is applicable to any OWL ontology whether written using Tawny-OWL or not. Moreover, we present a novel analysis of our tests, introducing a new classification of what our different tests are. For each class of test, we describe why we use these tests, also by comparison to software tests. We believe that this systematic comparison between ontology and software development will help us move to a more agile form of ontology development.
Scaffolding the Mitochondrial Disease Ontology from extant knowledge sources
Venue: arXiv cs.CE 2015
Year: 2015

Bio-medical ontologies can contain a large number of concepts. Often many of these concepts are very similar to each other, and similar or identical to concepts found in other bio-medical databases. This presents both a challenge and opportunity: maintaining many similar concepts is tedious and fastidious work, which could be substantially reduced if the data could be derived from pre-existing knowledge sources. In this paper, we describe how we have achieved this for an ontology of the mitochondria using our novel ontology development environment, the Tawny-OWL library.
Schur Complement based domain decomposition preconditioners with Low-rank corrections
Venue: arXiv cs.NA 2015
Year: 2015

This paper introduces a robust preconditioner for general sparse symmetric matrices, that is based on low-rank approximations of the Schur complement in a Domain Decomposition (DD) framework. In this "Schur Low Rank" (SLR) preconditioning approach, the coefficient matrix is first decoupled by DD, and then a low-rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface points. The method avoids explicit formation of the Schur complement matrix. We show the feasibility of this strategy for a model problem, and conduct a detailed spectral analysis for the relationship between the low-rank correction and the quality of the preconditioning. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach.
An Efficient Parameterization of the Room Transfer Function
Venue: arXiv cs.SD 2015
Year: 2015

This paper proposes an efficient parameterization of the Room Transfer Function (RTF). Typically, the RTF rapidly varies with varying source and receiver positions, hence requires an impractical number of point to point measurements to characterize a given room. Therefore, we derive a novel RTF parameterization that is robust to both receiver and source variations with the following salient features: (i) The parameterization is given in terms of a modal expansion of 3D basis functions. (ii) The aforementioned modal expansion can be truncated at a finite number of modes given that the source and receiver locations are from two sizeable spatial regions, which are arbitrarily distributed. (iii) The parameter weights/coefficients are independent of the source/receiver positions. Therefore, a finite set of coefficients is shown to be capable of accurately calculating the RTF between any two arbitrary points from a predefined spatial region where the source(s) lie and a pre-defined spatial region where the receiver(s) lie. A practical method to measure the RTF coefficients is also provided, which only requires a single microphone unit and a single loudspeaker unit, given that the room characteristics remain stationary over time. The accuracy of the above parameterization is verified using appropriate simulation examples.
Exploring the Self-enhanced Mechanism of Interactive Advertising Phenomenon---Based on the Research of Three Cases
Venue: arXiv cs.CY 2015
Year: 2015

Under the background of the new media era with the rapid development of interactive advertising, this paper used case study method based on the summary of the research of the communication effect of interactive advertising from both domestic and foreign academia. This paper divided interactive advertising into three types to examine ---- interactive ads on official website, interactive ads based on SNS and interactive ads based on mobile media. Furthermore, this paper induced and summarized a self-enhanced dissemination mechanism of the interactive advertising, including three parts which are micro level, meso level and macro level mechanism, micro level embodies core interaction, inner interaction and outer interaction which reveal the whole process of interact with contents, with people and with computer, and the communication approach and spread speed shown in meso level which is self-fission-type spread, finally in macro level the communication effect of IA achieved the spiral increasing. In a word, this article enriches research procedure of the interactive advertising communication effects.