OpenRaiser/Intern-Atlas huggingface dataset:
Efficiently listing bounded length st-paths
Venue: arXiv cs.DS 2014
Year: 2014

The problem of listing the $K$ shortest simple (loopless) $st$-paths in a graph has been studied since the early 1960s. For a non-negatively weighted graph with $n$ vertices and $m$ edges, the most efficient solution is an $O(K(mn + n^2 \log n))$ algorithm for directed graphs by Yen and Lawler [Management Science, 1971 and 1972], and an $O(K(m+n \log n))$ algorithm for the undirected version by Katoh et al. [Networks, 1982], both using $O(Kn + m)$ space. In this work, we consider a different parameterization for this problem: instead of bounding the number of $st$-paths output, we bound their length. For the bounded length parameterization, we propose new non-trivial algorithms matching the time complexity of the classic algorithms but using only $O(m+n)$ space. Moreover, we provide a unified framework such that the solutions to both parameterizations -- the classic $K$-shortest and the new length-bounded paths -- can be seen as two different traversals of a same tree, a Dijkstra-like and a DFS-like traversal, respectively.
Audio Splicing Detection and Localization Using Environmental Signature
Venue: arXiv cs.CR 2014
Year: 2014

Audio splicing is one of the most common manipulation techniques in the area of audio forensics. In this paper, the magnitudes of acoustic channel impulse response and ambient noise are proposed as the environmental signature. Specifically, the spliced audio segments are detected according to the magnitude correlation between the query frames and reference frames via a statically optimal threshold. The detection accuracy is further refined by comparing the adjacent frames. The effectiveness of the proposed method is tested on two data sets. One is generated from TIMIT database, and the other one is made in four acoustic environments using a commercial grade microphones. Experimental results show that the proposed method not only detects the presence of spliced frames, but also localizes the forgery segments with near perfect accuracy. Comparison results illustrate that the identification accuracy of the proposed scheme is higher than the previous schemes. In addition, experimental results also show that the proposed scheme is robust to MP3 compression attack, which is also superior to the previous works.
Towards Efficient OpenMP Strategies for Non-Uniform Architectures
Venue: arXiv cs.DC 2014
Year: 2014

Parallel processing is considered as todays and future trend for improving performance of computers. Computing devices ranging from small embedded systems to big clusters of computers rely on parallelizing applications to reduce execution time. Many of current computing systems rely on Non-Uniform Memory Access (NUMA) based processors architectures. In these architectures, analyzing and considering the non-uniformity is of high importance for improving scalability of systems. In this paper, we analyze and develop a NUMA based approach for the OpenMP parallel programming model. Our technique applies a smart threads allocation method and an advanced tasks scheduling strategy for reducing remote memory accesses and consequently their extra time consumption. We implemented our approach within the NANOS runtime system. A set of tests was conducted using the BOTS benchmarks and results showed the capacity of our technique in improving the performance of OpenMP applications especially those dealing with a large amount of data.
Error Correction Capacity of Unary Coding
Venue: arXiv cs.IT 2014
Year: 2014

Unary coding has found applications in data compression, neural network training, and in explaining the production mechanism of birdsong. Unary coding is redundant; therefore it should have inherent error correction capacity. An expression for the error correction capability of unary coding for the correction of single errors has been derived in this paper.
SACRM: Social Aware Crowdsourcing with Reputation Management in Mobile Sensing
Venue: arXiv cs.NI 2014
Year: 2014

Mobile sensing has become a promising paradigm for mobile users to obtain information by task crowdsourcing. However, due to the social preferences of mobile users, the quality of sensing reports may be impacted by the underlying social attributes and selfishness of individuals. Therefore, it is crucial to consider the social impacts and trustworthiness of mobile users when selecting task participants in mobile sensing. In this paper, we propose a Social Aware Crowdsourcing with Reputation Management (SACRM) scheme to select the well-suited participants and allocate the task rewards in mobile sensing. Specifically, we consider the social attributes, task delay and reputation in crowdsourcing and propose a participant selection scheme to choose the well-suited participants for the sensing task under a fixed task budget. A report assessment and rewarding scheme is also introduced to measure the quality of the sensing reports and allocate the task rewards based the assessed report quality. In addition, we develop a reputation management scheme to evaluate the trustworthiness and cost performance ratio of mobile users for participant selection. Theoretical analysis and extensive simulations demonstrate that SACRM can efficiently improve the crowdsourcing utility and effectively stimulate the participants to improve the quality of their sensing reports.
Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection
Venue: arXiv cs.DS 2014
Year: 2014

The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, information retrieval and many other areas related to the World Wide Web. There exist several algorithms for the problem with acceptable runtimes for certain classes of graphs, but many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques and is able to find maximum cliques in very large, sparse graphs quickly. Extensive experiments on different kinds of synthetic and real-world graphs show that our new algorithm can be orders of magnitude faster than existing algorithms. We also present a heuristic that runs orders of magnitude faster than the exact algorithm while providing optimal or near-optimal solutions. We illustrate a simple application of the algorithms in developing methods for detection of overlapping communities in networks.
On zero neighbours and trial sets of linear codes
Venue: arXiv cs.IT 2014
Year: 2014

In this work we study the set of leader codewords of a non-binary linear code. This set has some nice properties related to the monotonicity of the weight compatible order on the generalized support of a vector in $\mathbb F_q^n$. This allows us to describe a test set, a trial set and the set zero neighbours in terms of the leader codewords.
A Two Stage CVT / Eikonal Convection Mesh Deformation Approach for Large Nodal Deformations
Venue: arXiv cs.NA 2014
Year: 2014

A two step mesh deformation approach for large nodal deformations, typically arising from non-parametric shape optimization, fluid-structure interaction or computer graphics, is considered. Two major difficulties, collapsed cells and an undesirable parameterization, are overcome by considering a special form of ray tracing paired with a centroid Voronoi reparameterization. The ray direction is computed by solving an Eikonal equation. With respect to the Hadamard form of the shape derivative, both steps are within the kernel of the objective and have no negative impact on the minimizer. The paper concludes with applications in 2D and 3D fluid dynamics and automatic code generation and manages to solve these problems without any remeshing. The methodology is available as a FEniCS shape optimization add-on at http://www.mathematik.uni-wuerzburg.de/~schmidt/femorph.
On color image quality assessment using natural image statistics
Venue: arXiv cs.CV 2014
Year: 2014

Color distortion can introduce a significant damage in visual quality perception, however, most of existing reduced-reference quality measures are designed for grayscale images. In this paper, we consider a basic extension of well-known image-statistics based quality assessment measures to color images. In order to evaluate the impact of color information on the measures efficiency, two color spaces are investigated: RGB and CIELAB. Results of an extensive evaluation using TID 2013 benchmark demonstrates that significant improvement can be achieved for a great number of distortion type when the CIELAB color representation is used.
Flying Objects Detection from a Single Moving Camera
Venue: arXiv cs.CV 2014
Year: 2014

We propose an approach to detect flying objects such as UAVs and aircrafts when they occupy a small portion of the field of view, possibly moving against complex backgrounds, and are filmed by a camera that itself moves. Solving such a difficult problem requires combining both appearance and motion cues. To this end we propose a regression-based approach to motion stabilization of local image patches that allows us to achieve effective classification on spatio-temporal image cubes and outperform state-of-the-art techniques. As the problem is relatively new, we collected two challenging datasets for UAVs and Aircrafts, which can be used as benchmarks for flying objects detection and vision-guided collision avoidance.
Model for simulating mechanisms responsible of similarities between people connected in networks of social relations
Venue: arXiv cs.SI 2014
Year: 2014

It the literature have been identified three social mechanisms explaining the similarity between people connected in the network of social relations homophily, confounding and social contagion. The article proposes a simple model for simulating mechanisms responsible for similarity of attitudes in networks of social relations; along with a measure that is able to indicate which of the three mechanisms has taken major role in the process.
A Flexible Framework for Accurate Simulation of Cloud In-Memory Data Stores
Venue: arXiv cs.PF 2014
Year: 2014

In-memory (transactional) data stores are recognized as a first-class data management technology for cloud platforms, thanks to their ability to match the elasticity requirements imposed by the pay-as-you-go cost model. On the other hand, defining the well-suited amount of cache servers to be deployed, and the degree of in-memory replication of slices of data, in order to optimize reliability/availability and performance tradeoffs, is far from being a trivial task. Yet, it is an essential aspect of the provisioning process of cloud platforms, given that it has an impact on how well cloud resources are actually exploited. To cope with the issue of determining optimized configurations of cloud in-memory data stores, in this article we present a flexible simulation framework offering skeleton simulation models that can be easily specialized in order to capture the dynamics of diverse data grid systems, such as those related to the specific protocol used to provide data consistency and/or transactional guarantees. Besides its flexibility, another peculiar aspect of the framework lies in that it integrates simulation and machine-learning (black-box) techniques, the latter being essentially used to capture the dynamics of the data-exchange layer (e.g. the message passing layer) across the cache servers. This is a relevant aspect when considering that the actual data-transport/networking infrastructure on top of which the data grid is deployed might be unknown, hence being not feasible to be modeled via white-box (namely purely simulative) approaches. We also provide an extended experimental study aimed at validating instances of simulation models supported by our framework against execution dynamics of real data grid systems deployed on top of either private or public cloud infrastructures.
Using Sentence Plausibility to Learn the Semantics of Transitive Verbs
Venue: arXiv cs.CL 2014
Year: 2014

The functional approach to compositional distributional semantics considers transitive verbs to be linear maps that transform the distributional vectors representing nouns into a vector representing a sentence. We conduct an initial investigation that uses a matrix consisting of the parameters of a logistic regression classifier trained on a plausibility task as a transitive verb function. We compare our method to a commonly used corpus-based method for constructing a verb matrix and find that the plausibility training may be more effective for disambiguation tasks.
3D-Assisted Image Feature Synthesis for Novel Views of an Object
Venue: arXiv cs.CV 2014
Year: 2014

Comparing two images in a view-invariant way has been a challenging problem in computer vision for a long time, as visual features are not stable under large view point changes. In this paper, given a single input image of an object, we synthesize new features for other views of the same object. To accomplish this, we introduce an aligned set of 3D models in the same class as the input object image. Each 3D model is represented by a set of views, and we study the correlation of image patches between different views, seeking what we call surrogates --- patches in one view whose feature content predicts well the features of a patch in another view. In particular, for each patch in the novel desired view, we seek surrogates from the observed view of the given image. For a given surrogate, we predict that surrogate using linear combination of the corresponding patches of the 3D model views, learn the coefficients, and then transfer these coefficients on a per patch basis to synthesize the features of the patch in the novel view. In this way we can create feature sets for all views of the latent object, providing us a multi-view representation of the object. View-invariant object comparisons are achieved simply by computing the $L^2$ distances between the features of corresponding views. We provide theoretical and empirical analysis of the feature synthesis process, and evaluate the proposed view-agnostic distance (VAD) in fine-grained image retrieval (100 object classes) and classification tasks. Experimental results show that our synthesized features do enable view-independent comparison between images and perform significantly better than traditional image features in this respect.
Classification of digital n-manifolds
Venue: arXiv cs.DM 2014
Year: 2014

This paper presents the classification of digital n-manifolds based on the notion of complexity and homotopy equivalence. We introduce compressed n-manifolds and study their properties. We show that any n-manifold with p points is homotopy equivalent to a compressed n-manifold with m points, m<p. We design an algorithm for the classification of digital n-manifolds of any dimension n.
Topology preserving representations of compact 2D manifolds by digital 2-surfaces. Compressed digital models and digital weights of compact 2D manifolds. Classification of closed surfaces by digital tools
Venue: arXiv cs.CG 2014
Year: 2014

Using digital topology approach, we construct digital models of closed surfaces as the intersection graphs of LCL covers of the surfaces. It is proved that digital models of closed surfaces are digital 2-dimensional surfaces preserving the geometry and topology of their continuous counterparts. In the framework of the proposed models, we show that for any closed surface there exists a compressed model of this surface with the minimal number of points. Key words: Closed Surface; Digital space; Cover; Graph; Digital model; Medical imaging;
Channel Estimation Techniques for Quantized Distributed Reception in MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

The Internet of Things (IoT) could enable the development of cloud multiple-input multiple-output (MIMO) systems where internet-enabled devices can work as distributed transmission/reception entities. We expect that spatial multiplexing with distributed reception using cloud MIMO would be a key factor of future wireless communication systems. In this paper, we first review practical receivers for distributed reception of spatially multiplexed transmit data where the fusion center relies on quantized received signals conveyed from geographically separated receive nodes. Using the structures of these receivers, we propose practical channel estimation techniques for the block-fading scenario. The proposed channel estimation techniques rely on very simple operations at the received nodes while achieving near-optimal channel estimation performance as the training length becomes large.
Fuzzy human motion analysis: A review
Venue: arXiv cs.CV 2014
Year: 2014

Human Motion Analysis (HMA) is currently one of the most popularly active research domains as such significant research interests are motivated by a number of real world applications such as video surveillance, sports analysis, healthcare monitoring and so on. However, most of these real world applications face high levels of uncertainties that can affect the operations of such applications. Hence, the fuzzy set theory has been applied and showed great success in the recent past. In this paper, we aim at reviewing the fuzzy set oriented approaches for HMA, individuating how the fuzzy set may improve the HMA, envisaging and delineating the future perspectives. To the best of our knowledge, there is not found a single survey in the current literature that has discussed and reviewed fuzzy approaches towards the HMA. For ease of understanding, we conceptually classify the human motion into three broad levels: Low-Level (LoL), Mid-Level (MiL), and High-Level (HiL) HMA.
Automatic adaptor synthesis for protocol transformation
Venue: arXiv cs.SE 2014
Year: 2014

Adaptation of software components is an important issue in Component Based Software Engineering (CBSE). Building a system from reusable or Commercial-Off-The-Shelf (COTS) components introduces a set of issues, mainly related to compatibility and communication aspects. Components may have incompatible interaction behavior. Moreover it might be necessary to enhance the current communication protocol to introduce more sophisticated interactions among components. We address these problems enhancing our architectural approach which allows for detection and recovery of integration mismatches by synthesizing a suitable coordinator. Starting from the specification of the system to be assembled and from the specification of the needed protocol enhancements, our framework automatically derives, in a compositional way, the glue code for the set of components. The synthesized glue code avoids interaction mismatches and provides a protocol-enhanced version of the composed system.
Beating the Generator-Enumeration Bound for Solvable-Group Isomorphism
Venue: arXiv cs.DS 2014
Year: 2014

We consider the isomorphism problem for groups specified by their multiplication tables. Until recently, the best published bound for the worst-case was achieved by the n^(log_p n + O(1)) generator-enumeration algorithm. In previous work with Fabian Wagner, we showed an n^((1 / 2) log_p n + O(log n / log log n)) time algorithm for testing isomorphism of p-groups by building graphs with degree bounded by p + O(1) that represent composition series for the groups and applying Luks' algorithm for testing isomorphism of bounded degree graphs. In this work, we extend this improvement to the more general class of solvable groups to obtain an n^((1 / 2) log_p n + O(log n / log log n)) time algorithm. In the case of solvable groups, the composition factors can be large which prevents previous methods from outperforming the generator-enumeration algorithm. Using Hall's theory of Sylow bases, we define a new object that generalizes the notion of a composition series with small factors but exists even when the composition factors are large. By constructing graphs that represent these objects and running Luks' algorithm, we obtain our algorithm for solvable-group isomorphism. We also extend our algorithm to compute canonical forms of solvable groups while retaining the same complexity.
Analysis of WiFi and WiMAX and Wireless Network Coexistence
Venue: arXiv cs.NI 2014
Year: 2014

Wireless networks are very popular nowadays. Wireless Local Area Network (WLAN) that uses the IEEE 802.11 standard and WiMAX (Worldwide Interoperability for Microwave Access) that uses the IEEE 802.16 standard are networks that we want to explore. WiMAX has been developed over 10 years, but it is still unknown to most people. However compared to WLAN, it has many advantages in transmission speed and coverage area. This paper will introduce these two technologies and make comparisons between WiMAX and WiFi. In addition, wireless network coexistence of WLAN and WiMAX will be explored through simulation. Lastly we want to discuss the future of WiMAX in relation to WiFi.
Expressiveness of Logic Programs under General Stable Model Semantics
Venue: arXiv cs.AI 2014
Year: 2014

The stable model semantics had been recently generalized to non-Herbrand structures by several works, which provides a unified framework and solid logical foundations for answer set programming. This paper focuses on the expressiveness of normal and disjunctive programs under the general stable model semantics. A translation from disjunctive programs to normal programs is proposed for infinite structures. Over finite structures, some disjunctive programs are proved to be intranslatable to normal programs if the arities of auxiliary predicates and functions are bounded in a certain way. The equivalence of the expressiveness of normal programs and disjunctive programs over arbitrary structures is also shown to coincide with that over finite structures, and coincide with whether NP is closed under complement. Moreover, to capture the exact expressiveness, some intertranslatability results between logic program classes and fragments of second-order logic are obtained.
Feedforward semantic segmentation with zoom-out features
Venue: arXiv cs.CV 2014
Year: 2014

We introduce a purely feed-forward architecture for semantic segmentation. We map small image elements (superpixels) to rich feature representations extracted from a sequence of nested regions of increasing extent. These regions are obtained by "zooming out" from the superpixel all the way to scene-level resolution. This approach exploits statistical structure in the image and in the label space without setting up explicit structured prediction mechanisms, and thus avoids complex and expensive inference. Instead superpixels are classified by a feedforward multilayer network. Our architecture achieves new state of the art performance in semantic segmentation, obtaining 64.4% average accuracy on the PASCAL VOC 2012 test set.
Analytical Comparison of Noise Reduction Filters for Image Restoration Using SNR Estimation
Venue: arXiv cs.CV 2014
Year: 2014

Noise removal from images is a part of image restoration in which we try to reconstruct or recover an image that has been degraded by using apriori knowledge of the degradation phenomenon. Noises present in images can be of various types with their characteristic Probability Distribution Functions (PDF). Noise removal techniques depend on the kind of noise present in the image rather than on the image itself. This paper explores the effects of applying noise reduction filters having similar properties on noisy images with emphasis on Signal-to-Noise-Ratio (SNR) value estimation for comparing the results.