OpenRaiser/Intern-Atlas huggingface dataset:
Energy-Aware Aggregation of Dynamic Temporal Workload in Data Centers
Venue: arXiv cs.DC 2013
Year: 2013

Data center providers seek to minimize their total cost of ownership (TCO), while power consumption has become a social concern. We present formulations to minimize server energy consumption and server cost under three different data center server setups (homogeneous, heterogeneous, and hybrid hetero-homogeneous clusters) with dynamic temporal workload. Our studies show that the homogeneous model significantly differs from the heterogeneous model in computational time (by an order of magnitude). To be able to compute optimal configurations in near real-time for large scale data centers, we propose two modes, aggregation by maximum and aggregation by mean. In addition, we propose two aggregation methods, static (periodic) aggregation and dynamic (aperiodic) aggregation. We found that in the aggregation by maximum mode, the dynamic aggregation resulted in cost savings of up to approximately 18% over the static aggregation. In the aggregation by mean mode, the dynamic aggregation by mean could save up to approximately 50% workload rearrangement compared to the static aggregation by mean mode. Overall, our methodology helps to understand the trade-off in energy-aware aggregation.
Problem Complexity Research from Energy Perspective
Venue: arXiv cs.CC 2013
Year: 2013

Computational complexity is a particularly important objective. The idea of Landauer principle was extended through mapping three classic problems (sorting,ordered searching and max of N unordered numbers) into Maxwell demon thought experiment in this paper. The problems'complexity is defined on the entropy basis and the minimum energy required to solve them are rigorous deduced from the perspective of energy (entropy) and the second law of thermodynamics. Then the theoretical energy consumed by real program and basic operators of classical computer are both analyzed, the time complexity lower bounds of three problems'all possible algorithms are derived in this way. The lower bound is also deduced for the two n*n matrix multiplication problem. In the end, the reason why reversible computation is impossible and the possibility of super-linear energy consumption capacity which may be the power behind quantum computation are discussed, a conjecture is proposed which may prove NP!=P. The study will bring fresh and profound understanding of computation complexity.
Profiling Web Archive Coverage for Top-Level Domain and Content Language
Venue: arXiv cs.DL 2013
Year: 2013

The Memento aggregator currently polls every known public web archive when serving a request for an archived web page, even though some web archives focus on only specific domains and ignore the others. Similar to query routing in distributed search, we investigate the impact on aggregated Memento TimeMaps (lists of when and where a web page was archived) by only sending queries to archives likely to hold the archived page. We profile twelve public web archives using data from a variety of sources (the web, archives' access logs, and full-text queries to archives) and discover that only sending queries to the top three web archives (i.e., a 75% reduction in the number of queries) for any request produces the full TimeMaps on 84% of the cases.
Secure Degrees of Freedom of MIMO X-Channels with Output Feedback and Delayed CSIT
Venue: arXiv cs.IT 2013
Year: 2013

We investigate the problem of secure transmission over a two-user multi-input multi-output (MIMO) X-channel in which channel state information is provided with one-unit delay to both transmitters (CSIT), and each receiver feeds back its channel output to a different transmitter. We refer to this model as MIMO X-channel with asymmetric output feedback and delayed CSIT. The transmitters are equipped with M-antennas each, and the receivers are equipped with N-antennas each. For this model, accounting for both messages at each receiver, we characterize the optimal sum secure degrees of freedom (SDoF) region. We show that, in presence of asymmetric output feedback and delayed CSIT, the sum SDoF region of the MIMO X-channel is same as the SDoF region of a two-user MIMO BC with 2M-antennas at the transmitter, N-antennas at each receiver and delayed CSIT. This result shows that, upon availability of asymmetric output feedback and delayed CSIT, there is no performance loss in terms of sum SDoF due to the distributed nature of the transmitters. Next, we show that this result also holds if only output feedback is conveyed to the transmitters, but in a symmetric manner, i.e., each receiver feeds back its output to both transmitters and no CSIT. We also study the case in which only asymmetric output feedback is provided to the transmitters, i.e., without CSIT, and derive a lower bound on the sum SDoF for this model. Furthermore, we specialize our results to the case in which there are no security constraints. In particular, similar to the setting with security constraints, we show that the optimal sum DoF region of the (M,M,N,N)--MIMO X-channel with asymmetric output feedback and delayed CSIT is same as the DoF region of a two-user MIMO BC with 2M-antennas at the transmitter, N-antennas at each receiver, and delayed CSIT. We illustrate our results with some numerical examples.
Multiobjective Tactical Planning under Uncertainty for Air Traffic Flow and Capacity Management
Venue: arXiv cs.AI 2013
Year: 2013

We investigate a method to deal with congestion of sectors and delays in the tactical phase of air traffic flow and capacity management. It relies on temporal objectives given for every point of the flight plans and shared among the controllers in order to create a collaborative environment. This would enhance the transition from the network view of the flow management to the local view of air traffic control. Uncertainty is modeled at the trajectory level with temporal information on the boundary points of the crossed sectors and then, we infer the probabilistic occupancy count. Therefore, we can model the accuracy of the trajectory prediction in the optimization process in order to fix some safety margins. On the one hand, more accurate is our prediction; more efficient will be the proposed solutions, because of the tighter safety margins. On the other hand, when uncertainty is not negligible, the proposed solutions will be more robust to disruptions. Furthermore, a multiobjective algorithm is used to find the tradeoff between the delays and congestion, which are antagonist in airspace with high traffic density. The flow management position can choose manually, or automatically with a preference-based algorithm, the adequate solution. This method is tested against two instances, one with 10 flights and 5 sectors and one with 300 flights and 16 sectors.
EgoNet-UIUC: A Dataset For Ego Network Research
Venue: arXiv cs.SI 2013
Year: 2013

In this report, we introduce the version one of EgoNet-UIUC, which is a dataset for ego network research. The dataset contains about 230 ego networks in Linkedin, which have about 33K users (with their attributes) and 283K relationships (with their relationship types) in total. We name this dataset as EgoNet-UIUC, which stands for Ego Network Dataset from University of Illinois at Urbana-Champaign.
Music Files Search System
Venue: arXiv cs.IR 2013
Year: 2013

This paper introduces a project of advanced system of music retrieval from the Internet. The system uses combination of text search (by author, title and other information about the music file included in id3 tag description or similar for other file types) with more intuitive and novel method of melody search using query by humming. The patterns for storing text and melody information as well as improved clustering algorithm for the pattern space were proposed. The search engine is planned to optimise the query due to the data input by user, thanks to the structure of text and melody index database. The system is planned to be a plug-in for popular digital music players or an independent player. An advanced system of recommendation based on information gathered from user's profile and search history is an integral part of the system. The recommendation mechanism uses scrobbling methods and is responsible for making suggestions of songs unknown to the user but similar to his preferred music styles and positioning search results.
Lambda Dependency-Based Compositional Semantics
Venue: arXiv cs.AI 2013
Year: 2013

This short note presents a new formal language, lambda dependency-based compositional semantics (lambda DCS) for representing logical forms in semantic parsing. By eliminating variables and making existential quantification implicit, lambda DCS logical forms are generally more compact than those in lambda calculus.
Mobile augmented reality survey: a bottom-up approach
Venue: arXiv cs.GR 2013
Year: 2013

Augmented Reality (AR) is becoming mobile. Mobile devices have many constraints but also rich new features that traditional desktop computers do not have. There are several survey papers on AR, but none is dedicated to Mobile Augmented Reality (MAR). Our work serves the purpose of closing this gap. The contents are organized with a bottom-up approach. We first present the state-of-the-art in system components including hardware platforms, software frameworks and display devices, follows with enabling technologies such as tracking and data management. We then survey the latest technologies and methods to improve run-time performance and energy efficiency for practical implementation. On top of these, we further introduce the application fields and several typical MAR applications. Finally we conclude the survey with several challenge problems, which are under exploration and require great research efforts in the future.
Evaluating socio-economic state of a country analyzing airtime credit and mobile phone datasets
Venue: arXiv cs.CY 2013
Year: 2013

Reliable statistical information is important to make political decisions on a sound basis and to help measure the impact of policies. Unfortunately, statistics offices in developing countries have scarce resources and statistical censuses are therefore conducted sporadically. Based on mobile phone communications and history of airtime credit purchases, we estimate the relative income of individuals, the diversity and inequality of income, and an indicator for socioeconomic segregation for fine-grained regions of an African country. Our study shows how to use mobile phone datasets as a starting point to understand the socio-economic state of a country, which can be especially useful in countries with few resources to conduct large surveys.
Exponential Integrators on Graphic Processing Units
Venue: arXiv cs.NA 2013
Year: 2013

In this paper we revisit stencil methods on GPUs in the context of exponential integrators. We further discuss boundary conditions, in the same context, and show that simple boundary conditions (for example, homogeneous Dirichlet or homogeneous Neumann boundary conditions) do not affect the performance if implemented directly into the CUDA kernel. In addition, we show that stencil methods with position-dependent coefficients can be implemented efficiently as well. As an application, we discuss the implementation of exponential integrators for different classes of problems in a single and multi GPU setup (up to 4 GPUs). We further show that for stencil based methods such parallelization can be done very efficiently, while for some unstructured matrices the parallelization to multiple GPUs is severely limited by the throughput of the PCIe bus.
On Adaptive Measurement Inclusion Rate In Real-Time Moving-Horizon Observers
Venue: arXiv cs.SY 2013
Year: 2013

This paper investigates a self adaptation mechanism regarding the rate with which new measurements have to be incorporated in Moving-Horizon state estimation algorithms. This investigation can be viewed as the dual of the one proposed by the author in the context of real-time model predictive control. An illustrative example is provided in order to assess the relevance of the proposed updating rule.
A Calibration Algorithm for Microelectromechanical Systems Accelerometers in Inertial Navigation Sensors
Venue: arXiv cs.OH 2013
Year: 2013

In the present work we develop an algorithm for calibrating MEMS sensors, which accounts for the nonorthogonality of the accelerometers' axis, as well as for the constant bias and scaling errors. We derive an explicit formula for computing the calibrated acceleration, given data from the sensors. We also study the error, that is caused by the nonorthogonality of the axis.
A Comparison of Well-Quasi Orders on Trees
Venue: arXiv cs.PL 2013
Year: 2013

Well-quasi orders such as homeomorphic embedding are commonly used to ensure termination of program analysis and program transformation, in particular supercompilation. We compare eight well-quasi orders on how discriminative they are and their computational complexity. The studied well-quasi orders comprise two very simple examples, two examples from literature on supercompilation and four new proposed by the author. We also discuss combining several well-quasi orders to get well-quasi orders of higher discriminative power. This adds 19 more well-quasi orders to the list.
Verification of Imperative Programs by Constraint Logic Program Transformation
Venue: arXiv cs.PL 2013
Year: 2013

We present a method for verifying partial correctness properties of imperative programs that manipulate integers and arrays by using techniques based on the transformation of constraint logic programs (CLP). We use CLP as a metalanguage for representing imperative programs, their executions, and their properties. First, we encode the correctness of an imperative program, say prog, as the negation of a predicate 'incorrect' defined by a CLP program T. By construction, 'incorrect' holds in the least model of T if and only if the execution of prog from an initial configuration eventually halts in an error configuration. Then, we apply to program T a sequence of transformations that preserve its least model semantics. These transformations are based on well-known transformation rules, such as unfolding and folding, guided by suitable transformation strategies, such as specialization and generalization. The objective of the transformations is to derive a new CLP program TransfT where the predicate 'incorrect' is defined either by (i) the fact 'incorrect.' (and in this case prog is not correct), or by (ii) the empty set of clauses (and in this case prog is correct). In the case where we derive a CLP program such that neither (i) nor (ii) holds, we iterate the transformation. Since the problem is undecidable, this process may not terminate. We show through examples that our method can be applied in a rather systematic way, and is amenable to automation by transferring to the field of program verification many techniques developed in the field of program transformation.
Simulation of Two-Way Pushdown Automata Revisited
Venue: arXiv cs.PL 2013
Year: 2013

The linear-time simulation of 2-way deterministic pushdown automata (2DPDA) by the Cook and Jones constructions is revisited. Following the semantics-based approach by Jones, an interpreter is given which, when extended with random-access memory, performs a linear-time simulation of 2DPDA. The recursive interpreter works without the dump list of the original constructions, which makes Cook's insight into linear-time simulation of exponential-time automata more intuitive and the complexity argument clearer. The simulation is then extended to 2-way nondeterministic pushdown automata (2NPDA) to provide for a cubic-time recognition of context-free languages. The time required to run the final construction depends on the degree of nondeterminism. The key mechanism that enables the polynomial-time simulations is the sharing of computations by memoization.
A short note on Simulation and Abstraction
Venue: arXiv cs.PL 2013
Year: 2013

This short note is written in celebration of David Schmidt's sixtieth birthday. He has now been active in the program analysis research community for over thirty years and we have enjoyed many interactions with him. His work on characterising simulations between Kripke structures using Galois connections was particularly influential in our own work on using probabilistic abstract interpretation to study Larsen and Skou's notion of probabilistic bisimulation. We briefly review this work and discuss some recent applications of these ideas in a variety of different application areas.
New Algorithms for Solving Tropical Linear Systems
Venue: arXiv cs.CC 2013
Year: 2013

The problem of solving tropical linear systems, a natural problem of tropical mathematics, has already proven to be very interesting from the algorithmic point of view: it is known to be in $NP\cap coNP$ but no polynomial time algorithm is known, although counterexamples for existing pseudopolynomial algorithms are (and have to be) very complex. In this work, we continue the study of algorithms for solving tropical linear systems. First, we present a new reformulation of Grigoriev's algorithm that brings it closer to the algorithm of Akian, Gaubert, and Guterman; this lets us formulate a whole family of new algorithms, and we present algorithms from this family for which no known superpolynomial counterexamples work. Second, we present a family of algorithms for solving overdetermined tropical systems. We show that for weakly overdetermined systems, there are polynomial algorithms in this family. We also present a concrete algorithm from this family that can solve a tropical linear system defined by an $m\times n$ matrix with maximal element $M$ in time $Θ\left({m \choose n} \mathrm{poly}\left(m, n, \log M\right)\right)$, and this time matches the complexity of the best of previously known algorithms for feasibility testing.
Exploring the Memory-Bandwidth Tradeoff in an Information-Centric Network
Venue: arXiv cs.NI 2013
Year: 2013

An information-centric network should realize significant economies by exploiting a favourable memory-bandwidth tradeoff: it is cheaper to store copies of popular content close to users than to fetch them repeatedly over the Internet. We evaluate this tradeoff for some simple cache network structures under realistic assumptions concerning the size of the content catalogue and its popularity distribution. Derived cost formulas reveal the relative impact of various cost, traffic and capacity parameters, allowing an appraisal of possible future network architectures. Our results suggest it probably makes more sense to envisage the future Internet as a loosely interconnected set of local data centers than a network like today's with routers augmented by limited capacity content stores.
Power Grid Simulation using Matrix Exponential Method with Rational Krylov Subspaces
Venue: arXiv cs.CE 2013
Year: 2013

One well adopted power grid simulation methodology is to factorize matrix once and perform only backward forward substitution with a deliberately chosen step size along the simulation. Since the required simulation time is usually long for the power grid design, the costly factorization is amortized. However, such fixed step size cannot exploit larger step size for the low frequency response in the power grid to speedup the simulation. In this work, we utilize the matrix exponential method with the rational Krylov subspace approximation to enable adaptive step size in the power grid simulation. The kernel operation in our method only demands one factorization and backward forward substitutions. Moreover, the rational Krylov subspace approximation can relax the stiffness constraint of the previous works. The cheap computation of adaptivity in our method could exploit the long low frequency response in a power grid and significantly accelerate the simulation. The experimental results show that our method achieves up to 18X speedup over the trapezoidal method with fixed step size.
Latent Fisher Discriminant Analysis
Venue: arXiv cs.LG 2013
Year: 2013

Linear Discriminant Analysis (LDA) is a well-known method for dimensionality reduction and classification. Previous studies have also extended the binary-class case into multi-classes. However, many applications, such as object detection and keyframe extraction cannot provide consistent instance-label pairs, while LDA requires labels on instance level for training. Thus it cannot be directly applied for semi-supervised classification problem. In this paper, we overcome this limitation and propose a latent variable Fisher discriminant analysis model. We relax the instance-level labeling into bag-level, is a kind of semi-supervised (video-level labels of event type are required for semantic frame extraction) and incorporates a data-driven prior over the latent variables. Hence, our method combines the latent variable inference and dimension reduction in an unified bayesian framework. We test our method on MUSK and Corel data sets and yield competitive results compared to the baseline approach. We also demonstrate its capacity on the challenging TRECVID MED11 dataset for semantic keyframe extraction and conduct a human-factors ranking-based experimental evaluation, which clearly demonstrates our proposed method consistently extracts more semantically meaningful keyframes than challenging baselines.
Fast $k$-NNG construction with GPU-based quick multi-select
Venue: arXiv cs.DC 2013
Year: 2013

In this paper we describe a new brute force algorithm for building the $k$-Nearest Neighbor Graph ($k$-NNG). The $k$-NNG algorithm has many applications in areas such as machine learning, bio-informatics, and clustering analysis. While there are very efficient algorithms for data of low dimensions, for high dimensional data the brute force search is the best algorithm. There are two main parts to the algorithm: the first part is finding the distances between the input vectors which may be formulated as a matrix multiplication problem. The second is the selection of the $k$-NNs for each of the query vectors. For the second part, we describe a novel graphics processing unit (GPU) -based multi-select algorithm based on quick sort. Our optimization makes clever use of warp voting functions available on the latest GPUs along with use-controlled cache. Benchmarks show significant improvement over state-of-the-art implementations of the $k$-NN search on GPUs.
Image-guided therapy system for interstitial gynecologic brachytherapy in a multimodality operating suite
Venue: arXiv cs.CE 2013
Year: 2013

In this contribution, an image-guided therapy system supporting gynecologic radiation therapy is introduced. The overall workflow of the presented system starts with the arrival of the patient and ends with follow-up examinations by imaging and a superimposed visualization of the modeled device from a PACS system. Thereby, the system covers all treatments stages (pre-, intra- and postoperative) and has been designed and constructed by a computer scientist with feedback from an interdisciplinary team of physicians and engineers. This integrated medical system enables dispatch of diagnostic images directly after acquisition to a processing workstation that has an on-board 3D Computer Aided Design model of a medical device. Thus, allowing precise identification of catheter location in the 3D imaging model which later provides rapid feedback to the clinician regarding device location. Moreover, the system enables the ability to perform patient-specific pre-implant evaluation by assessing the placement of interstitial needles prior to an intervention via virtual template matching with a diagnostic scan.