OpenRaiser/Intern-Atlas huggingface dataset:
Optimize Unsynchronized Garbage Collection in an SSD Array
Venue: arXiv cs.OS 2015
Year: 2015

Solid state disks (SSDs) have advanced to outperform traditional hard drives significantly in both random reads and writes. However, heavy random writes trigger fre- quent garbage collection and decrease the performance of SSDs. In an SSD array, garbage collection of individ- ual SSDs is not synchronized, leading to underutilization of some of the SSDs. We propose a software solution to tackle the unsyn- chronized garbage collection in an SSD array installed in a host bus adaptor (HBA), where individual SSDs are exposed to an operating system. We maintain a long I/O queue for each SSD and flush dirty pages intelligently to fill the long I/O queues so that we hide the performance imbalance among SSDs even when there are few parallel application writes. We further define a policy of select- ing dirty pages to flush and a policy of taking out stale flush requests to reduce the amount of data written to SSDs. We evaluate our solution in a real system. Experi- ments show that our solution fully utilizes all SSDs in an array under random write-heavy workloads. It improves I/O throughput by up to 62% under random workloads of mixed reads and writes when SSDs are under active garbage collection. It causes little extra data writeback and increases the cache hit rate.
Analytic MMSE Bounds in Linear Dynamic Systems with Gaussian Mixture Noise Statistics
Venue: arXiv cs.SY 2015
Year: 2015

Using state-space representation, mobile object positioning problems can be described as dynamic systems, with the state representing the unknown location and the observations being the information gathered from the location sensors. For linear dynamic systems with Gaussian noise, the Kalman filter provides the Minimum Mean-Square Error (MMSE) state estimation by tracking the posterior. Hence, by approximating non-Gaussian noise distributions with Gaussian Mixtures (GM), a bank of Kalman filters or Gaussian Sum Filter (GSF), can provide the MMSE state estimation. However, the MMSE itself is not analytically tractable. Moreover, the general analytic bounds proposed in the literature are not tractable for GM noise statistics. Hence, in this work, we evaluate the MMSE of linear dynamic systems with GM noise statistics and propose its analytic lower and upper bounds. We provide two analytic upper bounds which are the Mean-Square Errors (MSE) of implementable filters, and we show that based on the shape of the GM noise distributions, the tighter upper bound can be selected. We also show that for highly multimodal GM noise distributions, the bounds and the MMSE converge. Simulation results support the validity of the proposed bounds and their behavior in limits.
Performance Improvement for Papr Reduction in Lte Downlink System with Elliptic Filtering
Venue: arXiv cs.IT 2015
Year: 2015

This paper is concerned with the performance improvement of PAPR reduction of orthogonal frequency division multiplexing (OFDM) signal using amplitude clipping & filtering based design. Note that OFDM is one of the well adept multi-carrier multiplexing transmission scheme which has been implemented in long term evolution (LTE) downlink. Nonetheless peak to average power ratio (PAPR) is the more rattling problem with OFDM, consequently in this paper a reduction procedure of the PAPR by using amplitude clipping and filtering is proposed. Here we used IIR bandpass elliptic filter after amplitude clipping to reduce the PAPR. The performance of the system in terms of bit error rate (BER) is also canvased as a new filter based clipping method. Our results show that the proposed methodology of clipping method with the IIR elliptic band pass filter significantly reduces the PAPR value.
A structural approach to kernels for ILPs: Treewidth and Total Unimodularity
Venue: arXiv cs.CC 2015
Year: 2015

Kernelization is a theoretical formalization of efficient preprocessing for NP-hard problems. Empirically, preprocessing is highly successful in practice, for example in state-of-the-art ILP-solvers like CPLEX. Motivated by this, previous work studied the existence of kernelizations for ILP related problems, e.g., for testing feasibility of Ax <= b. In contrast to the observed success of CPLEX, however, the results were largely negative. Intuitively, practical instances have far more useful structure than the worst-case instances used to prove these lower bounds. In the present paper, we study the effect that subsystems with (Gaifman graph of) bounded treewidth or totally unimodularity have on the kernelizability of the ILP feasibility problem. We show that, on the positive side, if these subsystems have a small number of variables on which they interact with the remaining instance, then we can efficiently replace them by smaller subsystems of size polynomial in the domain without changing feasibility. Thus, if large parts of an instance consist of such subsystems, then this yields a substantial size reduction. We complement this by proving that relaxations to the considered structures, e.g., larger boundaries of the subsystems, allow worst-case lower bounds against kernelization. Thus, these relaxed structures can be used to build instance families that cannot be efficiently reduced, by any approach.
Maximum weighted independent sets with a budget
Venue: arXiv cs.CC 2015
Year: 2015

Given a graph $G$, a non-negative integer $k$, and a weight function that maps each vertex in $G$ to a positive real number, the \emph{Maximum Weighted Budgeted Independent Set (MWBIS) problem} is about finding a maximum weighted independent set in $G$ of cardinality at most $k$. A special case of MWBIS, when the weight assigned to each vertex is equal to its degree in $G$, is called the \emph{Maximum Independent Vertex Coverage (MIVC)} problem. In other words, the MIVC problem is about finding an independent set of cardinality at most $k$ with maximum coverage. Since it is a generalization of the well-known Maximum Weighted Independent Set (MWIS) problem, MWBIS too does not have any constant factor polynomial time approximation algorithm assuming $P \neq NP$. In this paper, we study MWBIS in the context of bipartite graphs. We show that, unlike MWIS, the MIVC (and thereby the MWBIS) problem in bipartite graphs is NP-hard. Then, we show that the MWBIS problem admits a $\frac{1}{2}$-factor approximation algorithm in the class of bipartite graphs, which matches the integrality gap of a natural LP relaxation.
Tightening the Complexity of Equivalence Problems for Commutative Grammars
Venue: arXiv cs.FL 2015
Year: 2015

We show that the language equivalence problem for regular and context-free commutative grammars is coNEXP-complete. In addition, our lower bound immediately yields further coNEXP-completeness results for equivalence problems for communication-free Petri nets and reversal-bounded counter automata. Moreover, we improve both lower and upper bounds for language equivalence for exponent-sensitive commutative grammars.
An Experimental Evaluation of the Best-of-Many Christofides' Algorithm for the Traveling Salesman Problem
Venue: arXiv cs.DS 2015
Year: 2015

Recent papers on approximation algorithms for the traveling salesman problem (TSP) have given a new variant on the well-known Christofides' algorithm for the TSP, called the Best-of-Many Christofides' algorithm. The algorithm involves sampling a spanning tree from the solution the standard LP relaxation of the TSP, subject to the condition that each edge is sampled with probability at most its value in the LP relaxation. One then runs Christofides' algorithm on the tree by computing a minimum-cost matching on the odd-degree vertices in the tree, and shortcutting the resulting Eulerian graph to a tour. In this paper we perform an experimental evaluation of the Best-of-Many Christofides' algorithm to see if there are empirical reasons to believe its performance is better than that of Christofides' algorithm. Furthermore, several different sampling schemes have been proposed; we implement several different schemes to determine which ones might be the most promising for obtaining improved performance guarantees over that of Christofides' algorithm. In our experiments, all of the implemented methods perform significantly better than the Christofides' algorithm; an algorithm that samples from a maximum entropy distribution over spanning trees seems to be particularly good, though there are others that perform almost as well.
Microsimulations of Arching, Clogging, and Bursty Exit Phenomena in Crowd Dynamics
Venue: arXiv cs.MA 2015
Year: 2015

We present in this paper the behavior of an artificial agent who is a member of a crowd. The behavior is based on the social comparison theory, as well as the trajectory mapping towards an agent's goal considering the agent's field of vision. The crowd of artificial agents were able to exhibit arching, clogging, and bursty exit rates. We were also able to observe a new phenomenon we called double arching, which happens towards the end of the simulation, and whose onset is exhibited by a "calm" density graph within the exit passage. The density graph is usually bursty at this area. Because of these exhibited phenomena, we can use these agents with high confidence to perform microsimulation studies for modeling the behavior of humans and objects in very realistic ways.
Stateless Geocasting
Venue: arXiv cs.DC 2015
Year: 2015

We present two stateless algorithms that guarantee to deliver the message to every device in a designated geographic area: flooding and planar geocasting. Due to the algorithms' statelessness, intermediate devices do not have to keep message data between message transmissions. We formally prove the algorithms correct, estimate their message complexity and evaluate their performance through simulation.
Combining Visual Analytics and Content Based Data Retrieval Technology for Efficient Data Analysis
Venue: arXiv cs.GR 2015
Year: 2015

One of the most useful techniques to help visual data analysis systems is interactive filtering (brushing). However, visualization techniques often suffer from overlap of graphical items and multiple attributes complexity, making visual selection inefficient. In these situations, the benefits of data visualization are not fully observable because the graphical items do not pop up as comprehensive patterns. In this work we propose the use of content-based data retrieval technology combined with visual analytics. The idea is to use the similarity query functionalities provided by metric space systems in order to select regions of the data domain according to user-guidance and interests. After that, the data found in such regions feed multiple visualization workspaces so that the user can inspect the correspondent datasets. Our experiments showed that the methodology can break the visual analysis process into smaller problems (views) and that the views hold the expectations of the analyst according to his/her similarity query selection, improving data perception and analytical possibilities. Our contribution introduces a principle that can be used in all sorts of visualization techniques and systems, this principle can be extended with different kinds of integration visualization-metric-space, and with different metrics, expanding the possibilities of visual data analysis in aspects such as semantics and scalability.
Fake-Acknowledgment Attack on ACK-based Sensor Power Schedule for Remote State Estimation
Venue: arXiv cs.SY 2015
Year: 2015

We consider a class of malicious attacks against remote state estimation. A sensor with limited resources adopts an acknowledgement (ACK)-based online power schedule to improve the remote state estimation performance. A malicious attacker can modify the ACKs from the remote estimator and convey fake information to the sensor. When the capability of the attacker is limited, we propose an attack strategy for the attacker and analyze the corresponding effect on the estimation performance. The possible responses of the sensor are studied and a condition for the sensor to discard ACKs and switch from online schedule to offline schedule is provided.
A Super-Grover Separation Between Randomized and Quantum Query Complexities
Venue: arXiv cs.CC 2015
Year: 2015

We construct a total Boolean function $f$ satisfying $R(f)=\tildeΩ(Q(f)^{5/2})$, refuting the long-standing conjecture that $R(f)=O(Q(f)^2)$ for all total Boolean functions. Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions, we improve this to $R(f)=\tildeΩ(Q(f)^3)$. Our construction is motivated by the Göös-Pitassi-Watson function but does not use it.
Sparsified Cholesky Solvers for SDD linear systems
Venue: arXiv cs.DS 2015
Year: 2015

We show that Laplacian and symmetric diagonally dominant (SDD) matrices can be well approximated by linear-sized sparse Cholesky factorizations. We show that these matrices have constant-factor approximations of the form $L L^{T}$, where $L$ is a lower-triangular matrix with a number of nonzero entries linear in its dimension. Furthermore linear systems in $L$ and $L^{T}$ can be solved in $O (n)$ work and $O(\log{n}\log^2\log{n})$ depth, where $n$ is the dimension of the matrix. We present nearly linear time algorithms that construct solvers that are almost this efficient. In doing so, we give the first nearly-linear work routine for constructing spectral vertex sparsifiers---that is, spectral approximations of Schur complements of Laplacian matrices.
On the Approximation Theory of Linear Variational Subspace Design
Venue: arXiv cs.GR 2015
Year: 2015

Solving large-scale optimization on-the-fly is often a difficult task for real-time computer graphics applications. To tackle this challenge, model reduction is a well-adopted technique. Despite its usefulness, model reduction often requires a handcrafted subspace that spans a domain that hypothetically embodies desirable solutions. For many applications, obtaining such subspaces case-by-case either is impossible or requires extensive human labors, hence does not readily have a scalable solution for growing number of tasks. We propose linear variational subspace design for large-scale constrained quadratic programming, which can be computed automatically without any human interventions. We provide meaningful approximation error bound that substantiates the quality of calculated subspace, and demonstrate its empirical success in interactive deformable modeling for triangular and tetrahedral meshes.
The Multi-Strand Graph for a PTZ Tracker
Venue: arXiv cs.CV 2015
Year: 2015

High-resolution images can be used to resolve matching ambiguities between trajectory fragments (tracklets), which is one of the main challenges in multiple target tracking. A PTZ camera, which can pan, tilt and zoom, is a powerful and efficient tool that offers both close-up views and wide area coverage on demand. The wide-area view makes it possible to track many targets while the close-up view allows individuals to be identified from high-resolution images of their faces. A central component of a PTZ tracking system is a scheduling algorithm that determines which target to zoom in on. In this paper we study this scheduling problem from a theoretical perspective, where the high resolution images are also used for tracklet matching. We propose a novel data structure, the Multi-Strand Tracking Graph (MSG), which represents the set of tracklets computed by a tracker and the possible associations between them. The MSG allows efficient scheduling as well as resolving -- directly or by elimination -- matching ambiguities between tracklets. The main feature of the MSG is the auxiliary data saved in each vertex, which allows efficient computation while avoiding time-consuming graph traversal. Synthetic data simulations are used to evaluate our scheduling algorithm and to demonstrate its superiority over a naïve one.
Study of Buffer-Aided Space-Time Coding for Multiple-Antenna Cooperative Wireless Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this work we propose an adaptive buffer-aided space-time coding scheme for cooperative wireless networks. A maximum likelihood receiver and adjustable code vectors are considered subject to a power constraint with an amplify-and-forward cooperation strategy. Each multiple-antenna relay is equipped with a buffer and is capable of storing the received symbols before forwarding them to the destination. We also present an adaptive relay selection and optimization algorithm, in which the instantaneous signal to noise ratio in each link is calculated and compared at the destination. An adjustable code vector obtained by a feedback channel at each relay is employed to form a space-time coded vector which achieves a higher coding gain than standard schemes. A stochastic gradient algorithm is developed to compute the parameters of the adjustable code vector with reduced computational complexity. Simulation results show that the proposed buffer-aided scheme and algorithm obtain performance gains over existing schemes.
Multi-mode Sampling Period Selection for Embedded Real Time Control
Venue: arXiv cs.SY 2015
Year: 2015

Recent studies have shown that adaptively regulating the sampling rate results in significant reduction in computational resources in embedded software based control. Selecting a uniform sampling rate for a control loop is robust, but overtly pessimistic for sharing processors among multiple control loops. Fine grained regulation of periodicity achieves better resource utilization, but is hard to implement online in a robust way. In this paper we propose multi-mode sampling period selection, derived from an offline control theoretic analysis of the system. We report significant gains in computational efficiency without trading off control performance.
On the Security of MTA-OTIBASs (Multiple-TA One-Time Identity-Based Aggregate Signatures)
Venue: arXiv cs.CR 2015
Year: 2015

In [3] the authors proposed a new aggregate signature scheme referred to as multiple-TA (trusted authority) one-time identity-based aggregate signature (MTA-OTIBAS). Further, they gave a concrete MTA-OTIBAS scheme. We recall here the definition of MTA-OTIBAS and the concrete proposed scheme. Then we prove that our MTA-OTIBAS concrete scheme is existentially unforgeable against adaptively chosen-message attacks in the random oracle model under the co-CDH problem assumption.
Automatic Channel Network Extraction from Remotely Sensed Images by Singularity Analysis
Venue: arXiv cs.CV 2015
Year: 2015

Quantitative analysis of channel networks plays an important role in river studies. To provide a quantitative representation of channel networks, we propose a new method that extracts channels from remotely sensed images and estimates their widths. Our fully automated method is based on a recently proposed Multiscale Singularity Index that responds strongly to curvilinear structures but weakly to edges. The algorithm produces a channel map, using a single image where water and non-water pixels have contrast, such as a Landsat near-infrared band image or a water index defined on multiple bands. The proposed method provides a robust alternative to the procedures that are used in remote sensing of fluvial geomorphology and makes classification and analysis of channel networks easier. The source code of the algorithm is available at: http://live.ece.utexas.edu/research/cne/.
5G mmWave Module for ns-3 Network Simulator
Venue: arXiv cs.NI 2015
Year: 2015

The increasing demand of data, along with the spectrum scarcity, are motivating a urgent shift towards exploiting new bands. This is the main reason behind identifying mmWaves as the key disruptive enabling technology for 5G cellular networks. Indeed, utilizing new bands means facing new challenges; in this context, they are mainly related to the radio propagation, which is shorter in range and more sensitive to obstacles. The resulting key aspects that need to be taken into account when designing mmWave cellular systems are directionality and link intermittency. The lack of network level results motivated this work, which aims at providing the first of a kind open source mmWave framework, based on the network simulator ns-3. The main focus of this work is the modeling of customizable channel, physical (PHY) and medium access control (MAC) layers for mmWave systems. The overall design and architecture of the model are discussed in details. Finally, the validity of our proposed framework is corroborated through the simulation of a simple scenario.
A new approach for image compression using normal matrices
Venue: arXiv cs.MM 2015
Year: 2015

In this paper, we present methods for image compression on the basis of eigenvalue decomposition of normal matrices. The proposed methods are convenient and self-explanatory, requiring fewer and easier computations as compared to some existing methods. Through the proposed techniques, the image is transformed to the space of normal matrices. Then, the properties of spectral decomposition are dealt with to obtain compressed images. Experimental results are provided to illustrate the validity of the methods.
Waveform Optimization for Wireless Power Transfer with Nonlinear Energy Harvester Modeling
Venue: arXiv cs.IT 2015
Year: 2015

Far-field Wireless Power Transfer (WPT) and Simultaneous Wireless Information and Power Transfer (SWIPT) have attracted significant attention in the RF and communication communities. Despite the rapid progress, the problem of waveform design to enhance the output DC power of wireless energy harvester has received limited attention so far. In this paper, we bridge communication and RF design and derive novel multisine waveforms for multi-antenna wireless power transfer. The waveforms are adaptive to the channel state information and result from a posynomial maximization problem that originates from the non-linearity of the energy harvester. They are shown through realistic simulations to provide significant gains (in terms of harvested DC power) over state-of-the-art waveforms under a fixed transmit power constraint.
Detecting Table Region in PDF Documents Using Distant Supervision
Venue: arXiv cs.CV 2015
Year: 2015

Superior to state-of-the-art approaches which compete in table recognition with 67 annotated government reports in PDF format released by {\it ICDAR 2013 Table Competition}, this paper contributes a novel paradigm leveraging large-scale unlabeled PDF documents to open-domain table detection. We integrate the paradigm into our latest developed system ({\it PdfExtra}) to detect the region of tables by means of 9,466 academic articles from the entire repository of {\it ACL Anthology}, where almost all papers are archived by PDF format without annotation for tables. The paradigm first designs heuristics to automatically construct weakly labeled data. It then feeds diverse evidences, such as layouts of documents and linguistic features, which are extracted by {\it Apache PDFBox} and processed by {\it Stanford NLP} toolkit, into different canonical classifiers. We finally use these classifiers, i.e. {\it Naive Bayes}, {\it Logistic Regression} and {\it Support Vector Machine}, to collaboratively vote on the region of tables. Experimental results show that {\it PdfExtra} achieves a great leap forward, compared with the state-of-the-art approach. Moreover, we discuss the factors of different features, learning models and even domains of documents that may impact the performance. Extensive evaluations demonstrate that our paradigm is compatible enough to leverage various features and learning models for open-domain table region detection within PDF files.