OpenRaiser/Intern-Atlas huggingface dataset:
Quantitative Methods for Comparing Different HVAC Control Schemes
Venue: arXiv cs.SY 2012
Year: 2012

Experimentally comparing the energy usage and comfort characteristics of different controllers in heating, ventilation, and air-conditioning (HVAC) systems is difficult because variations in weather and occupancy conditions preclude the possibility of establishing equivalent experimental conditions across the order of hours, days, and weeks. This paper is concerned with defining quantitative metrics of energy usage and occupant comfort, which can be computed and compared in a rigorous manner that is capable of determining whether differences between controllers are statistically significant in the presence of such environmental fluctuations. Experimental case studies are presented that compare two alternative controllers (a schedule controller and a hybrid system learning-based model predictive controller) to the default controller in a building-wide HVAC system. Lastly, we discuss how our proposed methodology may also be able to quantify the efficiency of other building automation systems.
Defining and Evaluating Network Communities based on Ground-truth
Venue: arXiv cs.SI 2012
Year: 2012

Nodes in real-world networks organize into densely linked communities where edges appear with high concentration among the members of the community. Identifying such communities of nodes has proven to be a challenging task mainly due to a plethora of definitions of a community, intractability of algorithms, issues with evaluation and the lack of a reliable gold-standard ground-truth. In this paper we study a set of 230 large real-world social, collaboration and information networks where nodes explicitly state their group memberships. For example, in social networks nodes explicitly join various interest based social groups. We use such groups to define a reliable and robust notion of ground-truth communities. We then propose a methodology which allows us to compare and quantitatively evaluate how different structural definitions of network communities correspond to ground-truth communities. We choose 13 commonly used structural definitions of network communities and examine their sensitivity, robustness and performance in identifying the ground-truth. We show that the 13 structural definitions are heavily correlated and naturally group into four classes. We find that two of these definitions, Conductance and Triad-participation-ratio, consistently give the best performance in identifying ground-truth communities. We also investigate a task of detecting communities given a single seed node. We extend the local spectral clustering algorithm into a heuristic parameter-free community detection method that easily scales to networks with more than hundred million nodes. The proposed method achieves 30% relative improvement over current local clustering methods.
On the Stretch Factor of Randomly Embedded Random Graphs
Venue: arXiv cs.CG 2012
Year: 2012

We consider a random graph G(n,p) whose vertex set V has been randomly embedded in the unit square and whose edges are given weight equal to the geometric distance between their end vertices. Then each pair {u,v} of vertices have a distance in the weighted graph, and a Euclidean distance. The stretch factor of the embedded graph is defined as the maximum ratio of these two distances, over all u,v in V. We give upper and lower bounds on the stretch factor (holding asymptotically almost surely), and show that for p not too close to 0 or 1, these bounds are best possible in a certain sense. Our results imply that the stretch factor is bounded with probability tending to 1 if and only if n(1-p) tends to 0, answering a question of O'Rourke.
Forming Teams for Teaching Programming based on Static Code Analysis
Venue: arXiv cs.SE 2012
Year: 2012

The use of team for teaching programming can be effective in the classroom because it helps students to generate and acquire new knowledge in less time, but these groups to be formed without taking into account some respects, may cause an adverse effect on the teaching-learning process. This paper proposes a tool for the formation of team based on the semantics of source code (SOFORG). This semantics is based on metrics extracted from the preferences, styles and good programming practices. All this is achieved through a static analysis of code that each student develops. In this way, you will have a record of students with the information extracted; it evaluates the best formation of teams in a given course. The team's formations are based on programming styles, skills, pair programming or with leader.
Proposed Challenges And Areas of Concern in Operating System Research and Development
Venue: arXiv cs.OS 2012
Year: 2012

Computers are a very important part of our lives and the major reason why they have been such a success is because of the excellent graphical operating systems that run on these powerful machines. As the computer hardware is becoming more and more powerful, it is also vital to keep the software updated in order to utilize the hardware of the system efficiently and make it faster and smarter. This paper highlights some core issues that if dealt with in the operating system level would make use of the full potential of the computer hardware and provide an excellent user experience.
Globally reasoning about localised security policies in distributed systems
Venue: arXiv cs.CR 2012
Year: 2012

In this report, we aim at establishing proper ways for model checking the global security of distributed systems, which are designed consisting of set of localised security policies that enforce specific issues about the security expected. The systems are formally specified following a syntax, defined in detail in this report, and their behaviour is clearly established by the Semantics, also defined in detail in this report. The systems include the formal attachment of security policies into their locations, whose intended interactions are trapped by the policies, aiming at taking access control decisions of the system, and the Semantics also takes care of this. Using the Semantics, a Labelled Transition System (LTS) can be induced for every particular system, and over this LTS some model checking tasks could be done. We identify how this LTS is indeed obtained, and propose an alternative way of model checking the not-yet-induced LTS, by using the system design directly. This may lead to over-approximation thereby producing imprecise, though safe, results. We restrict ourselves to finite systems, in the sake of being certain about the decidability of the proposed method. To illustrate the usefulness and validity of our proposal, we present 2 small case-study-like examples, where we show how the system can be specified, which policies could be added to it, and how to decide if the desired global security property is met. Finally, an Appendix is given for digging deeply into how a tool for automatically performing this task is being built, including some implementation issues. The tool takes advantage of the proposed method, and given some system and some desired global security property, it safely (i.e. without false positives) ensures satisfaction of it.
A Brief Summary of Dictionary Learning Based Approach for Classification (revised)
Venue: arXiv cs.CV 2012
Year: 2012

This note presents some representative methods which are based on dictionary learning (DL) for classification. We do not review the sophisticated methods or frameworks that involve DL for classification, such as online DL and spatial pyramid matching (SPM), but rather, we concentrate on the direct DL-based classification methods. Here, the "so-called direct DL-based method" is the approach directly deals with DL framework by adding some meaningful penalty terms. By listing some representative methods, we can roughly divide them into two categories, i.e. (1) directly making the dictionary discriminative and (2) forcing the sparse coefficients discriminative to push the discrimination power of the dictionary. From this taxonomy, we can expect some extensions of them as future researches.
Characterization of Negabent Functions and Construction of Bent-Negabent Functions with Maximum Algebraic Degree
Venue: arXiv cs.IT 2012
Year: 2012

We present necessary and sufficient conditions for a Boolean function to be a negabent function for both even and odd number of variables, which demonstrate the relationship between negabent functions and bent functions. By using these necessary and sufficient conditions for Boolean functions to be negabent, we obtain that the nega spectrum of a negabent function has at most 4 values. We determine the nega spectrum distribution of negabent functions. Further, we provide a method to construct bent-negabent functions in $n$ variables ($n$ even) of algebraic degree ranging from 2 to $\frac{n}{2}$, which implies that the maximum algebraic degree of an $n$-variable bent-negabent function is equal to $\frac{n}{2}$. Thus, we answer two open problems proposed by Parker and Pott and by Stǎnicǎ \textit{et al.} respectively.
Efficient Subgraph Matching on Billion Node Graphs
Venue: arXiv cs.DB 2012
Year: 2012

The ability to handle large scale graph data is crucial to an increasing number of applications. Much work has been dedicated to supporting basic graph operations such as subgraph matching, reachability, regular expression matching, etc. In many cases, graph indices are employed to speed up query processing. Typically, most indices require either super-linear indexing time or super-linear indexing space. Unfortunately, for very large graphs, super-linear approaches are almost always infeasible. In this paper, we study the problem of subgraph matching on billion-node graphs. We present a novel algorithm that supports efficient subgraph matching for graphs deployed on a distributed memory store. Instead of relying on super-linear indices, we use efficient graph exploration and massive parallel computing for query processing. Our experimental results demonstrate the feasibility of performing subgraph matching on web-scale graph data.
Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases
Venue: arXiv cs.DB 2012
Year: 2012

Many studies have been conducted on seeking the efficient solution for subgraph similarity search over certain (deterministic) graphs due to its wide application in many fields, including bioinformatics, social network analysis, and Resource Description Framework (RDF) data management. All these works assume that the underlying data are certain. However, in reality, graphs are often noisy and uncertain due to various factors, such as errors in data extraction, inconsistencies in data integration, and privacy preserving purposes. Therefore, in this paper, we study subgraph similarity search on large probabilistic graph databases. Different from previous works assuming that edges in an uncertain graph are independent of each other, we study the uncertain graphs where edges' occurrences are correlated. We formally prove that subgraph similarity search over probabilistic graphs is #P-complete, thus, we employ a filter-and-verify framework to speed up the search. In the filtering phase,we develop tight lower and upper bounds of subgraph similarity probability based on a probabilistic matrix index, PMI. PMI is composed of discriminative subgraph features associated with tight lower and upper bounds of subgraph isomorphism probability. Based on PMI, we can sort out a large number of probabilistic graphs and maximize the pruning capability. During the verification phase, we develop an efficient sampling algorithm to validate the remaining candidates. The efficiency of our proposed solutions has been verified through extensive experiments.
Minuet: A Scalable Distributed Multiversion B-Tree
Venue: arXiv cs.DB 2012
Year: 2012

Data management systems have traditionally been designed to support either long-running analytics queries or short-lived transactions, but an increasing number of applications need both. For example, online games, socio-mobile apps, and e-commerce sites need to not only maintain operational state, but also analyze that data quickly to make predictions and recommendations that improve user experience. In this paper, we present Minuet, a distributed, main-memory B-tree that supports both transactions and copy-on-write snapshots for in-situ analytics. Minuet uses main-memory storage to enable low-latency transactional operations as well as analytics queries without compromising transaction performance. In addition to supporting read-only analytics queries on snapshots, Minuet supports writable clones, so that users can create branching versions of the data. This feature can be quite useful, e.g. to support complex "what-if" analysis or to facilitate wide-area replication. Our experiments show that Minuet outperforms a commercial main-memory database in many ways. It scales to hundreds of cores and TBs of memory, and can process hundreds of thousands of B-tree operations per second while executing long-running scans.
Système d'aide à l'accès lexical : trouver le mot qu'on a sur le bout de la langue
Venue: arXiv cs.CL 2012
Year: 2012

The study of the Tip of the Tongue phenomenon (TOT) provides valuable clues and insights concerning the organisation of the mental lexicon (meaning, number of syllables, relation with other words, etc.). This paper describes a tool based on psycho-linguistic observations concerning the TOT phenomenon. We've built it to enable a speaker/writer to find the word he is looking for, word he may know, but which he is unable to access in time. We try to simulate the TOT phenomenon by creating a situation where the system knows the target word, yet is unable to access it. In order to find the target word we make use of the paradigmatic and syntagmatic associations stored in the linguistic databases. Our experiment allows the following conclusion: a tool like SVETLAN, capable to structure (automatically) a dictionary by domains can be used sucessfully to help the speaker/writer to find the word he is looking for, if it is combined with a database rich in terms of paradigmatic links like EuroWordNet.
AirSync: Enabling Distributed Multiuser MIMO with Full Spatial Multiplexing
Venue: arXiv cs.NI 2012
Year: 2012

The enormous success of advanced wireless devices is pushing the demand for higher wireless data rates. Denser spectrum reuse through the deployment of more access points per square mile has the potential to successfully meet the increasing demand for more bandwidth. In theory, the best approach to density increase is via distributed multiuser MIMO, where several access points are connected to a central server and operate as a large distributed multi-antenna access point, ensuring that all transmitted signal power serves the purpose of data transmission, rather than creating "interference." In practice, while enterprise networks offer a natural setup in which distributed MIMO might be possible, there are serious implementation difficulties, the primary one being the need to eliminate phase and timing offsets between the jointly coordinated access points. In this paper we propose AirSync, a novel scheme which provides not only time but also phase synchronization, thus enabling distributed MIMO with full spatial multiplexing gains. AirSync locks the phase of all access points using a common reference broadcasted over the air in conjunction with a Kalman filter which closely tracks the phase drift. We have implemented AirSync as a digital circuit in the FPGA of the WARP radio platform. Our experimental testbed, comprised of two access points and two clients, shows that AirSync is able to achieve phase synchronization within a few degrees, and allows the system to nearly achieve the theoretical optimal multiplexing gain. We also discuss MAC and higher layer aspects of a practical deployment. To the best of our knowledge, AirSync offers the first ever realization of the full multiuser MIMO gain, namely the ability to increase the number of wireless clients linearly with the number of jointly coordinated access points, without reducing the per client rate.
Tighter Worst-Case Bounds on Algebraic Gossip
Venue: arXiv cs.DS 2012
Year: 2012

Gossip and in particular network coded algebraic gossip have recently attracted attention as a fast, bandwidth-efficient, reliable and distributed way to broadcast or multicast multiple messages. While the algorithms are simple, involved queuing approaches are used to study their performance. The most recent result in this direction shows that uniform algebraic gossip disseminates k messages in O(Δ(D + k + log n)) rounds where D is the diameter, n the size of the network and Δ the maximum degree. In this paper we give a simpler, short and self-contained proof for this worst-case guarantee. Our approach also allows to reduce the quadratic ΔD term to min{3n, ΔD}. We furthermore show that a simple round robin routing scheme also achieves min{3n, ΔD} + Δk rounds, eliminating both randomization and coding. Lastly, we combine a recent non-uniform gossip algorithm with a simple routing scheme to get a O(D + k + log^{O(1)}) gossip information dissemination algorithm. This is order optimal as long as D and k are not both polylogarithmically small.
The Porosity of Additive Noise Sequences
Venue: arXiv cs.IT 2012
Year: 2012

Consider a binary additive noise channel with noiseless feedback. When the noise is a stationary and ergodic process $\mathbf{Z}$, the capacity is $1-\mathbb{H}(\mathbf{Z})$ ($\mathbb{H}(\cdot)$ denoting the entropy rate). It is shown analogously that when the noise is a deterministic sequence $z^\infty$, the capacity under finite-state encoding and decoding is $1-\barρ(z^\infty)$, where $\barρ(\cdot)$ is Lempel and Ziv's finite-state compressibility. This quantity is termed the \emph{porosity} $\underlineσ(\cdot)$ of an individual noise sequence. A sequence of schemes are presented that universally achieve porosity for any noise sequence. These converse and achievability results may be interpreted both as a channel-coding counterpart to Ziv and Lempel's work in universal source coding, as well as an extension to the work by Lomnitz and Feder and Shayevitz and Feder on communication across modulo-additive channels. Additionally, a slightly more practical architecture is suggested that draws a connection with finite-state predictability, as introduced by Feder, Gutman, and Merhav.
BPA Bisimilarity is EXPTIME-hard
Venue: arXiv cs.FL 2012
Year: 2012

Given a basic process algebra (BPA) and two stack symbols, the BPA bisimilarity problem asks whether the two stack symbols are bisimilar. We show that this problem is EXPTIME-hard.
Robust Model Predictive Control via Scenario Optimization
Venue: arXiv cs.SY 2012
Year: 2012

This paper discusses a novel probabilistic approach for the design of robust model predictive control (MPC) laws for discrete-time linear systems affected by parametric uncertainty and additive disturbances. The proposed technique is based on the iterated solution, at each step, of a finite-horizon optimal control problem (FHOCP) that takes into account a suitable number of randomly extracted scenarios of uncertainty and disturbances, followed by a specific command selection rule implemented in a receding horizon fashion. The scenario FHOCP is always convex, also when the uncertain parameters and disturbance belong to non-convex sets, and irrespective of how the model uncertainty influences the system's matrices. Moreover, the computational complexity of the proposed approach does not depend on the uncertainty/disturbance dimensions, and scales quadratically with the control horizon. The main result in this paper is related to the analysis of the closed loop system under receding-horizon implementation of the scenario FHOCP, and essentially states that the devised control law guarantees constraint satisfaction at each step with some a-priori assigned probability p, while the system's state reaches the target set either asymptotically, or in finite time with probability at least p. The proposed method may be a valid alternative when other existing techniques, either deterministic or stochastic, are not directly usable due to excessive conservatism or to numerical intractability caused by lack of convexity of the robust or chance-constrained optimization problem.
General Bindings and Alpha-Equivalence in Nominal Isabelle
Venue: arXiv cs.LO 2012
Year: 2012

Nominal Isabelle is a definitional extension of the Isabelle/HOL theorem prover. It provides a proving infrastructure for reasoning about programming language calculi involving named bound variables (as opposed to de-Bruijn indices). In this paper we present an extension of Nominal Isabelle for dealing with general bindings, that means term constructors where multiple variables are bound at once. Such general bindings are ubiquitous in programming language research and only very poorly supported with single binders, such as lambda-abstractions. Our extension includes new definitions of alpha-equivalence and establishes automatically the reasoning infrastructure for alpha-equated terms. We also prove strong induction principles that have the usual variable convention already built in.
Rapid Feature Extraction for Optical Character Recognition
Venue: arXiv cs.CV 2012
Year: 2012

Feature extraction is one of the fundamental problems of character recognition. The performance of character recognition system is depends on proper feature extraction and correct classifier selection. In this article, a rapid feature extraction method is proposed and named as Celled Projection (CP) that compute the projection of each section formed through partitioning an image. The recognition performance of the proposed method is compared with other widely used feature extraction methods that are intensively studied for many different scripts in literature. The experiments have been conducted using Bangla handwritten numerals along with three different well known classifiers which demonstrate comparable results including 94.12% recognition accuracy using celled projection.
Detection Performance in Balanced Binary Relay Trees with Node and Link Failures
Venue: arXiv cs.IT 2012
Year: 2012

We study the distributed detection problem in the context of a balanced binary relay tree, where the leaves of the tree correspond to $N$ identical and independent sensors generating binary messages. The root of the tree is a fusion center making an overall decision. Every other node is a relay node that aggregates the messages received from its child nodes into a new message and sends it up toward the fusion center. We derive upper and lower bounds for the total error probability $P_N$ as explicit functions of $N$ in the case where nodes and links fail with certain probabilities. These characterize the asymptotic decay rate of the total error probability as $N$ goes to infinity. Naturally, this decay rate is not larger than that in the non-failure case, which is $\sqrt N$. However, we derive an explicit necessary and sufficient condition on the decay rate of the local failure probabilities $p_k$ (combination of node and link failure probabilities at each level) such that the decay rate of the total error probability in the failure case is the same as that of the non-failure case. More precisely, we show that $\log P_N^{-1}=Θ(\sqrt N)$ if and only if $\log p_k^{-1}=Ω(2^{k/2})$.
Defect Management Using Depth of Inspection and the Inspection Performance Metric
Venue: arXiv cs.SE 2012
Year: 2012

Advancement in fundamental engineering aspects of software development enables IT enterprises to develop a more cost effective and better quality product through aptly organized defect management strategies. Inspection continues to be the most effective and efficient technique of defect management. To have an appropriate measurement of the inspection process, the process metric, Depth of Inspection (DI) and the people metric, Inspection Performance Metric (IPM) are introduced. The introduction of these pair of metrics can yield valuable information from a company in relation to the inspection process.