OpenRaiser/Intern-Atlas huggingface dataset:
Online detection of temporal communities in evolving networks by estrangement confinement
Venue: arXiv cs.SI 2012
Year: 2012

Temporal communities result from a consistent partitioning of nodes across multiple snapshots of an evolving complex network that can help uncover how dense clusters in a network emerge, combine, split and decay with time. Current methods for finding communities in a single snapshot are not straightforwardly generalizable to finding temporal communities since the quality functions used for finding static communities have highly degenerate landscapes, and the eventual partition chosen among the many partitions of similar quality is highly sensitive to small changes in the network. To reliably detect temporal communities we need not only to find a good community partition in a given snapshot but also ensure that it bears some similarity to the partition(s) found in immediately preceding snapshots. We present a new measure of partition distance called "estrangement" motivated by the inertia of inter-node relationships which, when incorporated into the measurement of partition quality, facilitates the detection of meaningful temporal communities. Specifically, we propose the estrangement confinement method, which postulates that neighboring nodes in a community prefer to continue to share community affiliation as the network evolves. Constraining estrangement enables us to find meaningful temporal communities at various degrees of temporal smoothness in diverse real-world datasets. Specifically, we study the evolution of voting behavior of senators in the United States Congress, the evolution of proximity in human mobility datasets, and the detection of evolving communities in synthetic networks that are otherwise hard to find. Estrangement confinement thus provides a principled approach to uncovering temporal communities in evolving networks.
Acceleration of the shiftable O(1) algorithm for bilateral filtering and non-local means
Venue: arXiv cs.CV 2012
Year: 2012

A direct implementation of the bilateral filter [1] requires O(σ_s^2) operations per pixel, where σ_s is the (effective) width of the spatial kernel. A fast implementation of the bilateral filter was recently proposed in [2] that required O(1) operations per pixel with respect to σ_s. This was done by using trigonometric functions for the range kernel of the bilateral filter, and by exploiting their so-called shiftability property. In particular, a fast implementation of the Gaussian bilateral filter was realized by approximating the Gaussian range kernel using raised cosines. Later, it was demonstrated in [3] that this idea could be extended to a larger class of filters, including the popular non-local means filter [4]. As already observed in [2], a flip side of this approach was that the run time depended on the width σ_r of the range kernel. For an image with (local) intensity variations in the range [0,T], the run time scaled as O(T^2/σ^2_r) with σ_r. This made it difficult to implement narrow range kernels, particularly for images with large dynamic range. We discuss this problem in this note, and propose some simple steps to accelerate the implementation in general, and for small σ_r in particular. [1] C. Tomasi and R. Manduchi, "Bilateral filtering for gray and color images", Proc. IEEE International Conference on Computer Vision, 1998. [2] K.N. Chaudhury, Daniel Sage, and M. Unser, "Fast O(1) bilateral filtering using trigonometric range kernels", IEEE Transactions on Image Processing, 2011. [3] K.N. Chaudhury, "Constant-time filtering using shiftable kernels", IEEE Signal Processing Letters, 2011. [4] A. Buades, B. Coll, and J.M. Morel, "A review of image denoising algorithms, with a new one", Multiscale Modeling and Simulation, 2005.
Bayesian Games and the Smoothness Framework
Venue: arXiv cs.GT 2012
Year: 2012

We consider a general class of Bayesian Games where each players utility depends on his type (possibly multidimensional) and on the strategy profile and where players' types are distributed independently. We show that if their full information version for any fixed instance of the type profile is a smooth game then the Price of Anarchy bound implied by the smoothness property, carries over to the Bayes-Nash Price of Anarchy. We show how some proofs from the literature (item bidding auctions, greedy auctions) can be cast as smoothness proofs or be simplified using smoothness. For first price item bidding with fractionally subadditive bidders we actually manage to improve by much the existing result \cite{Hassidim2011a} from 4 to $\frac{e}{e-1}\approx 1.58$. This also shows a very interesting separation between first and second price item bidding since second price item bidding has PoA at least 2 even under complete information. For a larger class of Bayesian Games where the strategy space of a player also changes with his type we are able to show that a slightly stronger definition of smoothness also implies a Bayes-Nash PoA bound. We show how weighted congestion games actually satisfy this stronger definition of smoothness. This allows us to show that the inefficiency bounds of weighted congestion games known in the literature carry over to incomplete versions where the weights of the players are private information. We also show how an incomplete version of a natural class of monotone valid utility games, called effort market games are universally $(1,1)$-smooth. Hence, we show that incomplete versions of effort market games where the abilities of the players and their budgets are private information has Bayes-Nash PoA at most 2.
Post-Editing Error Correction Algorithm for Speech Recognition using Bing Spelling Suggestion
Venue: arXiv cs.CL 2012
Year: 2012

ASR short for Automatic Speech Recognition is the process of converting a spoken speech into text that can be manipulated by a computer. Although ASR has several applications, it is still erroneous and imprecise especially if used in a harsh surrounding wherein the input speech is of low quality. This paper proposes a post-editing ASR error correction method and algorithm based on Bing's online spelling suggestion. In this approach, the ASR recognized output text is spell-checked using Bing's spelling suggestion technology to detect and correct misrecognized words. More specifically, the proposed algorithm breaks down the ASR output text into several word-tokens that are submitted as search queries to Bing search engine. A returned spelling suggestion implies that a query is misspelled; and thus it is replaced by the suggested correction; otherwise, no correction is performed and the algorithm continues with the next token until all tokens get validated. Experiments carried out on various speeches in different languages indicated a successful decrease in the number of ASR errors and an improvement in the overall error correction rate. Future research can improve upon the proposed algorithm so much so that it can be parallelized to take advantage of multiprocessor computers.
Bound Analysis of Imperative Programs with the Size-change Abstraction (extended version)
Venue: arXiv cs.PL 2012
Year: 2012

The size-change abstraction (SCA) is an important program abstraction for termination analysis, which has been successfully implemented in many tools for functional and logic programs. In this paper, we demonstrate that SCA is also a highly effective abstract domain for the bound analysis of imperative programs. We have implemented a bound analysis tool based on SCA for imperative programs. We abstract programs in a pathwise and context dependent manner, which enables our tool to analyze real-world programs effectively. Our work shows that SCA captures many of the essential ideas of previous termination and bound analysis and goes beyond in a conceptually simpler framework.
The state complexity of star-complement-star
Venue: arXiv cs.FL 2012
Year: 2012

We resolve an open question by determining matching (asymptotic) upper and lower bounds on the state complexity of the operation that sends a language L to (c(L*))*, where c() denotes complement.
Expurgated PPM Using Symmetric Balanced Incomplete Block Designs
Venue: arXiv cs.IT 2012
Year: 2012

In this letter, we propose a new pulse position modulation (PPM) scheme, called expurgated PPM (EPPM), for application in peak power limited communication systems, such as impulse radio (IR) ultra wide band (UWB) systems and free space optical (FSO) communications. Using the proposed scheme, the constellation size and the bit-rate can be increased significantly in these systems. The symbols are obtained using symmetric balanced incomplete block designs (BIBD), forming a set of pair-wise equidistance symbols. The performance of Q-ary EPPM is better than any Q-ary pulse position-based modulation scheme with the same symbol length. Since the code is cyclic, the receiver for EPPM is simpler compared to multipulse PPM (MPPM).
Incremental Collaborative Filtering Considering Temporal Effects
Venue: arXiv cs.IR 2012
Year: 2012

Recommender systems require their recommendation algorithms to be accurate, scalable and should handle very sparse training data which keep changing over time. Inspired by ant colony optimization, we propose a novel collaborative filtering scheme: Ant Collaborative Filtering that enjoys those favorable characteristics above mentioned. With the mechanism of pheromone transmission between users and items, our method can pinpoint most relative users and items even in face of the sparsity problem. By virtue of the evaporation of existing pheromone, we capture the evolution of user preference over time. Meanwhile, the computation complexity is comparatively small and the incremental update can be done online. We design three experiments on three typical recommender systems, namely movie recommendation, book recommendation and music recommendation, which cover both explicit and implicit rating data. The results show that the proposed algorithm is well suited for real-world recommendation scenarios which have a high throughput and are time sensitive.
Multiple faults diagnosis using causal graph
Venue: arXiv cs.SY 2012
Year: 2012

This work proposes to put up a tool for diagnosing multi faults based on model using techniques of detection and localization inspired from the community of artificial intelligence and that of automatic. The diagnostic procedure to be integrated into the supervisory system must therefore be provided with explanatory features. Techniques based on causal reasoning are a pertinent approach for this purpose. Bond graph modeling is used to describe the cause effect relationship between process variables. Experimental results are presented and discussed in order to compare performance of causal graph technique and classic methods inspired from artificial intelligence (DX) and control theory (FDI).
Graph-Theoretic Characterizations of Structural Controllability for Multi-Agent System with Switching Topology
Venue: arXiv cs.MA 2012
Year: 2012

This paper considers the controllability problem for multi-agent systems. In particular, the structural controllability of multi-agent systems under switching topologies is investigated. The structural controllability of multi-agent systems is a generalization of the traditional controllability concept for dynamical systems, and purely based on the communication topologies among agents. The main contributions of the paper are graph-theoretic characterizations of the structural controllability for multi-agent systems. It turns out that the multi-agent system with switching topology is structurally controllable if and only if the union graph G of the underlying communication topologies is connected (single leader) or leader-follower connected (multi-leader). Finally, the paper concludes with several illustrative examples and discussions of the results and future work.
Closed-Form Critical Conditions of Subharmonic Oscillations for Buck Converters
Venue: arXiv cs.SY 2012
Year: 2012

A general critical condition of subharmonic oscillation in terms of the loop gain is derived. Many closed-form critical conditions for various control schemes in terms of converter parameters are also derived. Some previously known critical conditions become special cases in the generalized framework. Given an arbitrary control scheme, a systematic procedure is proposed to derive the critical condition for that control scheme. Different control schemes share similar forms of critical conditions. For example, both V2 control and voltage mode control have the same form of critical condition. A peculiar phenomenon in average current mode control where subharmonic oscillation occurs in a window value of pole can be explained by the derived critical condition. A ripple amplitude index to predict subharmonic oscillation proposed in the past research has limited application and is shown invalid for a converter with a large pole.
Adaptive Row-grouped CSR Format for Storing of Sparse Matrices on GPU
Venue: arXiv cs.DC 2012
Year: 2012

We present new adaptive format for storing sparse matrices on GPU. We compare it with several other formats including CUSPARSE which is today probably the best choice for processing of sparse matrices on GPU in CUDA. Contrary to CUSPARSE which works with common CSR format, our new format requires conversion. However, multiplication of sparse-matrix and vector is significantly faster for many atrices. We demonstrate it on set of 1 600 matrices and we show for what types of matrices our format is profitable.
G-equivalence in group algebras and minimal abelian codes
Venue: arXiv cs.IT 2012
Year: 2012

Let G be a finite abelian group and F a field such that char(F) does not divide |G|. Denote by FG the group algebra of G over F. A (semisimple) abelian code is an ideal of FG. Two codes I and J of FG are G-equivalent if there exists an automorphism of G whose linear extension to FG maps I onto J In this paper we give a necessary and sufficient condition for minimal abelian codes to be G-equivalent and show how to correct some results in the literature.
Towards a Mathematical Theory of Super-Resolution
Venue: arXiv cs.IT 2012
Year: 2012

This paper develops a mathematical theory of super-resolution. Broadly speaking, super-resolution is the problem of recovering the fine details of an object---the high end of its spectrum---from coarse scale information only---from samples at the low end of the spectrum. Suppose we have many point sources at unknown locations in $[0,1]$ and with unknown complex-valued amplitudes. We only observe Fourier samples of this object up until a frequency cut-off $f_c$. We show that one can super-resolve these point sources with infinite precision---i.e. recover the exact locations and amplitudes---by solving a simple convex optimization problem, which can essentially be reformulated as a semidefinite program. This holds provided that the distance between sources is at least $2/f_c$. This result extends to higher dimensions and other models. In one dimension for instance, it is possible to recover a piecewise smooth function by resolving the discontinuity points with infinite precision as well. We also show that the theory and methods are robust to noise. In particular, in the discrete setting we develop some theoretical results explaining how the accuracy of the super-resolved signal is expected to degrade when both the noise level and the {\em super-resolution factor} vary.
A "Hybrid" Approach for Synthesizing Optimal Controllers of Hybrid Systems: A Case Study of the Oil Pump Industrial Example
Venue: arXiv cs.SY 2012
Year: 2012

In this paper, we propose an approach to reduce the optimal controller synthesis problem of hybrid systems to quantifier elimination; furthermore, we also show how to combine quantifier elimination with numerical computation in order to make it more scalable but at the same time, keep arising errors due to discretization manageable and within bounds. A major advantage of our approach is not only that it avoids errors due to numerical computation, but it also gives a better optimal controller. In order to illustrate our approach, we use the real industrial example of an oil pump provided by the German company HYDAC within the European project Quasimodo as a case study throughout this paper, and show that our method improves (up to 7.5%) the results reported in [3] based on game theory and model checking.
Tracing the Man in the Middle in Monoidal Categories
Venue: arXiv cs.LO 2012
Year: 2012

Man-in-the-Middle (MM) is not only a ubiquitous attack pattern in security, but also an important paradigm of network computation and economics. Recognizing ongoing MM-attacks is an important security task; modeling MM-interactions is an interesting task for semantics of computation. Traced monoidal categories are a natural framework for MM-modelling, as the trace structure provides a tool to hide what happens *in the middle*. An effective analysis of what has been traced out seems to require an additional property of traces, called *normality*. We describe a modest model of network computation, based on partially ordered multisets (pomsets), where basic network interactions arise from the monoidal trace structure, and a normal trace structure arises from an iterative, i.e. coalgebraic structure over terms and messages used in computation and communication. The correspondence is established using a convenient monadic description of normally traced monoidal categories.
Analysis of Magnification in Depth from Defocus
Venue: arXiv cs.CV 2012
Year: 2012

In depth from defocus (DFD), when images are captured with different camera parameters, a relative magnification is induced between them. Image warping is a simpler solution to account for magnification than seemingly more accurate optical approaches. This work is an investigation into the effects of magnification on the accuracy of DFD. We comment on issues regarding scaling effect on relative blur computation. We statistically analyze accountability of scale factor, commenting on the bias and efficiency of the estimator that does not consider scale. We also discuss the effect of interpolation errors on blur estimation in a warping based solution to handle magnification and carry out experimental analysis to comment on the blur estimation accuracy.
Definition, Detection, and Recovery of Single-Page Failures, a Fourth Class of Database Failures
Venue: arXiv cs.DB 2012
Year: 2012

The three traditional failure classes are system, media, and transaction failures. Sometimes, however, modern storage exhibits failures that differ from all of those. In order to capture and describe such cases, single-page failures are introduced as a fourth failure class. This class encompasses all failures to read a data page correctly and with plausible contents despite all correction attempts in lower system levels. Efficient recovery seems to require a new data structure called the page recovery index. Its transactional maintenance can be accomplished writing the same number of log records as today's efficient implementations of logging and recovery. Detection and recovery of a single-page failure can be sufficiently fast that the affected data access is merely delayed, without the need to abort the transaction.
Concurrency Control for Adaptive Indexing
Venue: arXiv cs.DB 2012
Year: 2012

Adaptive indexing initializes and optimizes indexes incrementally, as a side effect of query processing. The goal is to achieve the benefits of indexes while hiding or minimizing the costs of index creation. However, index-optimizing side effects seem to turn read-only queries into update transactions that might, for example, create lock contention. This paper studies concurrency control in the context of adaptive indexing. We show that the design and implementation of adaptive indexing rigorously separates index structures from index contents; this relaxes the constraints and requirements during adaptive indexing compared to those of traditional index updates. Our design adapts to the fact that an adaptive index is refined continuously, and exploits any concurrency opportunities in a dynamic way. A detailed experimental analysis demonstrates that (a) adaptive indexing maintains its adaptive properties even when running concurrent queries, (b) adaptive indexing can exploit the opportunity for parallelism due to concurrent queries, (c) the number of concurrency conflicts and any concurrency administration overheads follow an adaptive behavior, decreasing as the workload evolves and adapting to the workload needs.
An Analysis of Structured Data on the Web
Venue: arXiv cs.DB 2012
Year: 2012

In this paper, we analyze the nature and distribution of structured data on the Web. Web-scale information extraction, or the problem of creating structured tables using extraction from the entire web, is gathering lots of research interest. We perform a study to understand and quantify the value of Web-scale extraction, and how structured information is distributed amongst top aggregator websites and tail sites for various interesting domains. We believe this is the first study of its kind, and gives us new insights for information extraction over the Web.
Interrupt Timed Automata: verification and expressiveness
Venue: arXiv cs.FL 2012
Year: 2012

We introduce the class of Interrupt Timed Automata (ITA), a subclass of hybrid automata well suited to the description of timed multi-task systems with interruptions in a single processor environment. While the reachability problem is undecidable for hybrid automata we show that it is decidable for ITA. More precisely we prove that the untimed language of an ITA is regular, by building a finite automaton as a generalized class graph. We then establish that the reachability problem for ITA is in NEXPTIME and in PTIME when the number of clocks is fixed. To prove the first result, we define a subclass ITA- of ITA, and show that (1) any ITA can be reduced to a language-equivalent automaton in ITA- and (2) the reachability problem in this subclass is in NEXPTIME (without any class graph). In the next step, we investigate the verification of real time properties over ITA. We prove that model checking SCL, a fragment of a timed linear time logic, is undecidable. On the other hand, we give model checking procedures for two fragments of timed branching time logic. We also compare the expressive power of classical timed automata and ITA and prove that the corresponding families of accepted languages are incomparable. The result also holds for languages accepted by controlled real-time automata (CRTA), that extend timed automata. We finally combine ITA with CRTA, in a model which encompasses both classes and show that the reachability problem is still decidable. Additionally we show that the languages of ITA are neither closed under complementation nor under intersection.
Polylogarithmic Approximation for Generalized Minimum Manhattan Networks
Venue: arXiv cs.CG 2012
Year: 2012

Given a set of $n$ terminals, which are points in $d$-dimensional Euclidean space, the minimum Manhattan network problem (MMN) asks for a minimum-length rectilinear network that connects each pair of terminals by a Manhattan path, that is, a path consisting of axis-parallel segments whose total length equals the pair's Manhattan distance. Even for $d=2$, the problem is NP-hard, but constant-factor approximations are known. For $d \ge 3$, the problem is APX-hard; it is known to admit, for any $\eps > 0$, an $O(n^\eps)$-approximation. In the generalized minimum Manhattan network problem (GMMN), we are given a set $R$ of $n$ terminal pairs, and the goal is to find a minimum-length rectilinear network such that each pair in $R$ is connected by a Manhattan path. GMMN is a generalization of both MMN and the well-known rectilinear Steiner arborescence problem (RSA). So far, only special cases of GMMN have been considered. We present an $O(\log^{d+1} n)$-approximation algorithm for GMMN (and, hence, MMN) in $d \ge 2$ dimensions and an $O(\log n)$-approximation algorithm for 2D. We show that an existing $O(\log n)$-approximation algorithm for RSA in 2D generalizes easily to $d>2$ dimensions.