OpenRaiser/Intern-Atlas huggingface dataset:
Graph measures and network robustness
Venue: arXiv cs.DM 2013
Year: 2013

Network robustness research aims at finding a measure to quantify network robustness. Once such a measure has been established, we will be able to compare networks, to improve existing networks and to design new networks that are able to continue to perform well when it is subject to failures or attacks. In this paper we survey a large amount of robustness measures on simple, undirected and unweighted graphs, in order to offer a tool for network administrators to evaluate and improve the robustness of their network. The measures discussed in this paper are based on the concepts of connectivity (including reliability polynomials), distance, betweenness and clustering. Some other measures are notions from spectral graph theory, more precisely, they are functions of the Laplacian eigenvalues. In addition to surveying these graph measures, the paper also contains a discussion of their functionality as a measure for topological network robustness.
Combining the Shortest Paths and the Bottleneck Paths Problems
Venue: arXiv cs.DS 2013
Year: 2013

We combine the well known Shortest Paths (SP) problem and the Bottleneck Paths (BP) problem to introduce a new problem called the Shortest Paths for All Flows (SP-AF) problem that has relevance in real life applications. We first solve the Single Source Shortest Paths for All Flows (SSSP-AF) problem on directed graphs with unit edge costs in $O(mn)$ worst case time bound. We then present two algorithms to solve SSSP-AF on directed graphs with integer edge costs bounded by $c$ in $O(m^2 + nc)$ and $O(m^2 + mn\log{(\frac{c}{m})})$ time bounds. Finally we extend our algorithms for the SSSP-AF problem to solve the All Pairs Shortest Paths for All Flows (APSP-AF) problem in $O(m^{2}n + nc)$ and $O(m^{2}n + mn^{2}\log{(\frac{c}{mn})})$ time bounds. All algorithms presented in this paper are practical for implementation.
Pearltrees as a tool for referencing and teaching
Venue: arXiv cs.CY 2013
Year: 2013

Pearltrees is a social service, using which people can organise Web contents, photos and notes. These contents are the "pearls" on some trees. Besides the social opportunities, the trees can be used as a tool to organise references and for content curation. However, they can be helpful for teaching purposes too.
Breaking the quadratic barrier for 3-LCCs over the Reals
Venue: arXiv cs.CC 2013
Year: 2013

We prove that 3-query linear locally correctable codes over the Reals of dimension $d$ require block length $n>d^{2+λ}$ for some fixed, positive $λ>0$. Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spanned by a linear number of disjoint triples of others, then it must be that $n > d^{2+λ}$. This improves the known quadratic lower bounds (e.g. {KdW04, Wood07}). While a modest improvement, we expect that the new techniques introduced in this work will be useful for further progress on lower bounds of locally correctable and decodable codes with more than 2 queries, possibly over other fields as well. Our proof introduces several new ideas to existing lower bound techniques, several of which work over every field. At a high level, our proof has two parts, {\it clustering} and {\it random restriction}. The clustering step uses a powerful theorem of Barthe from convex geometry. It can be used (after preprocessing our LCC to be {\it balanced}), to apply a basis change (and rescaling) of the vectors, so that the resulting unit vectors become {\it nearly isotropic}. This together with the fact that any LCC must have many `correlated' pairs of points, lets us deduce that the vectors must have a surprisingly strong geometric clustering, and hence also combinatorial clustering with respect to the spanning triples. In the restriction step, we devise a new variant of the dimension reduction technique used in previous lower bounds, which is able to take advantage of the combinatorial clustering structure above. The analysis of our random projection method reduces to a simple (weakly) random graph process, and works over any field.
On Quantifying Qualitative Geospatial Data: A Probabilistic Approach
Venue: arXiv cs.DB 2013
Year: 2013

Living in the era of data deluge, we have witnessed a web content explosion, largely due to the massive availability of User-Generated Content (UGC). In this work, we specifically consider the problem of geospatial information extraction and representation, where one can exploit diverse sources of information (such as image and audio data, text data, etc), going beyond traditional volunteered geographic information. Our ambition is to include available narrative information in an effort to better explain geospatial relationships: with spatial reasoning being a basic form of human cognition, narratives expressing such experiences typically contain qualitative spatial data, i.e., spatial objects and spatial relationships. To this end, we formulate a quantitative approach for the representation of qualitative spatial relations extracted from UGC in the form of texts. The proposed method quantifies such relations based on multiple text observations. Such observations provide distance and orientation features which are utilized by a greedy Expectation Maximization-based (EM) algorithm to infer a probability distribution over predefined spatial relationships; the latter represent the quantified relationships under user-defined probabilistic assumptions. We evaluate the applicability and quality of the proposed approach using real UGC data originating from an actual travel blog text corpus. To verify the quality of the result, we generate grid-based maps visualizing the spatial extent of the various relations.
Expressiveness of Visibly Pushdown Transducers
Venue: arXiv cs.FL 2013
Year: 2013

Visibly pushdown transducers (VPTs) are visibly pushdown automata extended with outputs. They have been introduced to model transformations of nested words, i.e. words with a call/return structure. As trees and more generally hedges can be linearized into (well) nested words, VPTs are a natural formalism to express tree transformations evaluated in streaming. This paper aims at characterizing precisely the expressive power of VPTs with respect to other tree transducer models.
Node Query Preservation for Deterministic Linear Top-Down Tree Transducers
Venue: arXiv cs.FL 2013
Year: 2013

This paper discusses the decidability of node query preservation problems for XML document transformations. We assume a transformation given by a deterministic linear top-down data tree transducer (abbreviated as DLT^V) and an n-ary query based on runs of a tree automaton. We say that a DLT^V Tr strongly preserves a query Q if there is a query Q' such that for every document t, the answer set of Q' for Tr(t) is equal to the answer set of Q for t. Also we say that Tr weakly preserves Q if there is a query Q' such that for every t_d in the range of Tr, the answer set of Q' for t_d is equal to the union of the answer set of Q for t such that t_d = Tr(t). We show that the weak preservation problem is coNP-complete and the strong preservation problem is in 2-EXPTIME.
XPath Node Selection over Grammar-Compressed Trees
Venue: arXiv cs.DB 2013
Year: 2013

XML document markup is highly repetitive and therefore well compressible using grammar-based compression. Downward, navigational XPath can be executed over grammar-compressed trees in PTIME: the query is translated into an automaton which is executed in one pass over the grammar. This result is well-known and has been mentioned before. Here we present precise bounds on the time complexity of this problem, in terms of big-O notation. For a given grammar and XPath query, we consider three different tasks: (1) to count the number of nodes selected by the query, (2) to materialize the pre-order numbers of the selected nodes, and (3) to serialize the subtrees at the selected nodes.
On Nonrigid Shape Similarity and Correspondence
Venue: arXiv cs.CV 2013
Year: 2013

An important operation in geometry processing is finding the correspondences between pairs of shapes. The Gromov-Hausdorff distance, a measure of dissimilarity between metric spaces, has been found to be highly useful for nonrigid shape comparison. Here, we explore the applicability of related shape similarity measures to the problem of shape correspondence, adopting spectral type distances. We propose to evaluate the spectral kernel distance, the spectral embedding distance and the novel spectral quasi-conformal distance, comparing the manifolds from different viewpoints. By matching the shapes in the spectral domain, important attributes of surface structure are being aligned. For the purpose of testing our ideas, we introduce a fully automatic framework for finding intrinsic correspondence between two shapes. The proposed method achieves state-of-the-art results on the Princeton isometric shape matching protocol applied, as usual, to the TOSCA and SCAPE benchmarks.
Flow analysis, linearity, and PTIME
Venue: arXiv cs.PL 2013
Year: 2013

Flow analysis is a ubiquitous and much-studied component of compiler technology---and its variations abound. Amongst the most well known is Shivers' 0CFA; however, the best known algorithm for 0CFA requires time cubic in the size of the analyzed program and is unlikely to be improved. Consequently, several analyses have been designed to approximate 0CFA by trading precision for faster computation. Henglein's simple closure analysis, for example, forfeits the notion of directionality in flows and enjoys an "almost linear" time algorithm. But in making trade-offs between precision and complexity, what has been given up and what has been gained? Where do these analyses differ and where do they coincide? We identify a core language---the linear $λ$-calculus---where 0CFA, simple closure analysis, and many other known approximations or restrictions to 0CFA are rendered identical. Moreover, for this core language, analysis corresponds with (instrumented) evaluation. Because analysis faithfully captures evaluation, and because the linear $λ$-calculus is complete for PTIME, we derive PTIME-completeness results for all of these analyses.
Dictionary-Learning-Based Reconstruction Method for Electron Tomography
Venue: arXiv cs.CV 2013
Year: 2013

Electron tomography usually suffers from so called missing wedge artifacts caused by limited tilt angle range. An equally sloped tomography (EST) acquisition scheme (which should be called the linogram sampling scheme) was recently applied to achieve 2.4-angstrom resolution. On the other hand, a compressive sensing-inspired reconstruction algorithm, known as adaptive dictionary based statistical iterative reconstruction (ADSIR), has been reported for x-ray computed tomography. In this paper, we evaluate the EST, ADSIR and an ordered-subset simultaneous algebraic reconstruction technique (OS-SART), and compare the ES and equally angled (EA) data acquisition modes. Our results show that OS-SART is comparable to EST, and the ADSIR outperforms EST and OS-SART. Furthermore, the equally sloped projection data acquisition mode has no advantage over the conventional equally angled mode in the context.
Unveil Compressed Sensing
Venue: arXiv cs.IT 2013
Year: 2013

We discuss the applicability of compressed sensing theory. We take a genuine look at both experimental results and theoretical works. We answer the following questions: 1) What can compressed sensing really do? 2) More importantly, why?
Traffic and Statistical Multiplexing Characterization of 3D Video Representation Formats (Extended Version)
Venue: arXiv cs.MM 2013
Year: 2013

The network transport of 3D video, which contains two views of a video scene, poses significant challenges due to the increased video data compared to conventional single-view video. Addressing these challenges requires a thorough understanding of the traffic and multiplexing characteristics of the different representation formats of 3D video. We examine the average bitrate-distortion (RD) and bitrate variability-distortion (VD) characteristics of three main representation formats. Specifically, we compare multiview video (MV) representation and encoding, frame sequential (FS) representation, and side-by-side (SBS) representation, whereby conventional single-view encoding is employed for the FS and SBS representations. Our results for long 3D videos in full HD format indicate that the MV representation and encoding achieves the highest RD efficiency, while exhibiting the highest bitrate variabilities. We examine the impact of these bitrate variabilities on network transport through extensive statistical multiplexing simulations. We find that when multiplexing a small number of streams, the MV and FS representations require the same bandwidth. However, when multiplexing a large number of streams or smoothing traffic, the MV representation and encoding reduces the bandwidth requirement relative to the FS representation.
A Continuous Refinement Strategy for the Multilevel Computation of Vertex Separators
Venue: arXiv cs.DS 2013
Year: 2013

The Vertex Separator Problem (VSP) on a graph is the problem of finding the smallest collection of vertices whose removal separates the graph into two disjoint subsets of roughly equal size. Recently, Hager and Hungerford [1] developed a continuous bilinear programming formulation of the VSP. In this paper, we reinforce the bilinear programming approach with a multilevel scheme for learning the structure of the graph.
Efficient Data Collection in Multimedia Vehicular Sensing Platforms
Venue: arXiv cs.NI 2013
Year: 2013

Vehicles provide an ideal platform for urban sensing applications, as they can be equipped with all kinds of sensing devices that can continuously monitor the environment around the travelling vehicle. In this work we are particularly concerned with the use of vehicles as building blocks of a multimedia mobile sensor system able to capture camera snapshots of the streets to support traffic monitoring and urban surveillance tasks. However, cameras are high data-rate sensors while wireless infrastructures used for vehicular communications may face performance constraints. Thus, data redundancy mitigation is of paramount importance in such systems. To address this issue in this paper we exploit sub-modular optimisation techniques to design efficient and robust data collection schemes for multimedia vehicular sensor networks. We also explore an alternative approach for data collection that operates on longer time scales and relies only on localised decisions rather than centralised computations. We use network simulations with realistic vehicular mobility patterns to verify the performance gains of our proposed schemes compared to a baseline solution that ignores data redundancy. Simulation results show that our data collection techniques can ensure a more accurate coverage of the road network while significantly reducing the amount of transferred data.
On the Sustainability of Electrical Vehicles
Venue: arXiv cs.SY 2013
Year: 2013

Many perceive electric vehicles (EVs) to be eco-environmentally sustainable because they are free of emissions of toxic and greenhouse gases to the environment. However, few have questioned the sustainability of the electric power required to drive these vehicles. This paper presents an in-depth study that indicates that massive infusion of EVs to our society in a short time span will likely create a colossal demand for additional electric power generation much beyond what the US electric power generating industry can provide with its current generating capacity. Additionally, such demand would result in much adverse environmental consequences if the current technology of electric power generation by predominant fossil fuels continues. Other rarely accounted facts on environmental impacts by EVs are the substantial electric energy required to produce batteries that drive EVs, and the negative consequences relating to the recycling of spent batteries.
Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing
Venue: arXiv cs.DS 2013
Year: 2013

We consider vehicle-routing problems (VRPs) that incorporate the notion of {\em regret} of a client, which is a measure of the waiting time of a client relative to its shortest-path distance from the depot. Formally, we consider both the additive and multiplicative versions of, what we call, the {\em regret-bounded vehicle routing problem} (RVRP). In these problems, we are given an undirected complete graph $G=(\{r\}\cup V,E)$ on $n$ nodes with a distinguished root (depot) node $r$, edge costs $\{c_{uv}\}$ that form a metric, and a regret bound $R$. Given a path $P$ rooted at $r$ and a node $v\in P$, let $c_P(v)$ be the distance from $r$ to $v$ along $P$. The goal is to find the fewest number of paths rooted at $r$ that cover all the nodes so that for every node $v$ covered by (say) path $P$: (i) its additive regret $c_P(v)-c_{rv}$, with respect to $P$ is at most $R$ in {\em additive-RVRP}; or (ii) its multiplicative regret, $c_P(c)/c_{rv}$, with respect to $P$ is at most $R$ in {\em multiplicative-RVRP}. Our main result is the {\em first} constant-factor approximation algorithm for additive-RVRP by devising rounding techniques for a natural {\em configuration-style LP}. This is a substantial improvement over the previous-best $O(\log n)$-approximation. Additive-RVRP turns out be a rather central vehicle-routing problem, whose study reveals insights into a variety of other regret-related problems as well as the classical {\em distance-constrained VRP} ({DVRP}). We obtain approximation ratios of $O\bigl(\log(\frac{R}{R-1})\bigr)$ for multiplicative-RVRP, and $O\bigl(\min\bigl\{\mathit{OPT},\frac{\log D}{\log\log D}\bigr\}\bigr)$ for DVRP with distance bound $D$ via reductions to additive-RVRP; the latter improves upon the previous-best approximation for DVRP.
Packing and Covering a Polygon with Geodesic Disks
Venue: arXiv cs.CG 2013
Year: 2013

Given a polygon $P$, for two points $s$ and $t$ contained in the polygon, their \emph{geodesic distance} is the length of the shortest $st$-path within $P$. A \emph{geodesic disk} of radius $r$ centered at a point $v \in P$ is the set of points in $P$ whose geodesic distance to $v$ is at most $r$. We present a polynomial time $2$-approximation algorithm for finding a densest geodesic unit disk packing in $P$. Allowing arbitrary radii but constraining the number of disks to be $k$, we present a $4$-approximation algorithm for finding a packing in $P$ with $k$ geodesic disks whose minimum radius is maximized. We then turn our focus on \emph{coverings} of $P$ and present a $2$-approximation algorithm for covering $P$ with $k$ geodesic disks whose maximal radius is minimized. Furthermore, we show that all these problems are $\mathsf{NP}$-hard in polygons with holes. Lastly, we present a polynomial time exact algorithm which covers a polygon with two geodesic disks of minimum maximal radius.
Agent Based Negotiation using Cloud - an Approach in E-Commerce
Venue: arXiv cs.MA 2013
Year: 2013

Cloud computing allows subscription based access to computing. It also allows storage services over Internet. Automated Negotiation is becoming an emerging, and important area in the field of Multi Agent Systems in ECommerce. Multi Agent based negotiation system is necessary to increase the efficiency of E-negotiation process. Cloud computing provides security and privacy to the user data and low maintenance costs. We propose a Negotiation system using cloud. In this system, all product information and multiple agent details are stored on cloud. Both parties select their agents through cloud for negotiation. Agent acts as a negotiator. Agents have users details and their requirements for a particular product. Using users requirement, agents negotiate on some issues such as price, volume, duration, quality and so on. After completing negotiation process, agents give feedback to the user about whether negotiation is successful or not. This negotiation system is dynamic in nature and increases the agents with the increase in participating user.
Web-page Indexing based on the Prioritize Ontology Terms
Venue: arXiv cs.IR 2013
Year: 2013

In this world, globalization has become a basic and most popular human trend. To globalize information, people are going to publish the documents in the internet. As a result, information volume of internet has become huge. To handle that huge volume of information, Web searcher uses search engines. The Webpage indexing mechanism of a search engine plays a big role to retrieve Web search results in a faster way from the huge volume of Web resources. Web researchers have introduced various types of Web-page indexing mechanism to retrieve Webpages from Webpage repository. In this paper, we have illustrated a new approach of design and development of Webpage indexing. The proposed Webpage indexing mechanism has applied on domain specific Webpages and we have identified the Webpage domain based on an Ontology. In our approach, first we prioritize the Ontology terms that exist in the Webpage content then apply our own indexing mechanism to index that Webpage. The main advantage of storing an index is to optimize the speed and performance while finding relevant documents from the domain specific search engine storage area for a user given search query.
Thwarting Selfish Behavior in 802.11 WLANs
Venue: arXiv cs.NI 2013
Year: 2013

The 802.11e standard enables user configuration of several MAC parameters, making WLANs vulnerable to users that selfishly configure these parameters to gain throughput. In this paper we propose a novel distributed algorithm to thwart such selfish behavior. The key idea of the algorithm is for honest stations to react, upon detecting a selfish station, by using a more aggressive configuration that penalizes this station. We show that the proposed algorithm guarantees global stability while providing good response times. By conducting a game theoretic analysis of the algorithm based on repeated games, we also show its effectiveness against selfish stations. Simulation results confirm that the proposed algorithm optimizes throughput performance while discouraging selfish behavior. We also present an experimental prototype of the proposed algorithm demonstrating that it can be implemented on commodity hardware.
Are all training examples equally valuable?
Venue: arXiv cs.CV 2013
Year: 2013

When learning a new concept, not all training examples may prove equally useful for training: some may have higher or lower training value than others. The goal of this paper is to bring to the attention of the vision community the following considerations: (1) some examples are better than others for training detectors or classifiers, and (2) in the presence of better examples, some examples may negatively impact performance and removing them may be beneficial. In this paper, we propose an approach for measuring the training value of an example, and use it for ranking and greedily sorting examples. We test our methods on different vision tasks, models, datasets and classifiers. Our experiments show that the performance of current state-of-the-art detectors and classifiers can be improved when training on a subset, rather than the whole training set.
Simulation Model Of Functional Stability Of Business Processes
Venue: arXiv cs.OH 2013
Year: 2013

Functioning of business processes of high-tech enterprise is in a constant interaction with the environment. Herewith a wide range of such interaction represents a variety of conflicts affecting the achievement of the goals of business processes. All these things lead to the disruption of functioning of business processes. That's why modern enterprises should have mechanisms to provide a new property of business processes - ability to maintain and/or restore functions in various adverse effects. This property is called functional stability of business processes (FSBP). In this article we offer, showcase and test the new approach to assessing the results of business process re-engineering by simulating their functional stability before and after re-engineering.