OpenRaiser/Intern-Atlas huggingface dataset:
DBMSs Should Talk Back Too
Venue: arXiv cs.DB 2009
Year: 2009

Natural language user interfaces to database systems have been studied for several decades now. They have mainly focused on parsing and interpreting natural language queries to generate them in a formal database language. We envision the reverse functionality, where the system would be able to take the internal result of that translation, say in SQL form, translate it back into natural language, and show it to the initiator of the query for verification. Likewise, information extraction has received considerable attention in the past ten years or so, identifying structured information in free text so that it may then be stored appropriately and queried. Validation of the records stored with a backward translation into text would again be very powerful. Verification and validation of query and data input of a database system correspond to just one example of the many important applications that would benefit greatly from having mature techniques for translating such database constructs into free-flowing text. The problem appears to be deceivingly simple, as there are no ambiguities or other complications in interpreting internal database elements, so initially a straightforward translation appears adequate. Reality teaches us quite the opposite, however, as the resulting text should be expressive, i.e., accurate in capturing the underlying queries or data, and effective, i.e., allowing fast and unique interpretation of them. Achieving both of these qualities is very difficult and raises several technical challenges that need to be addressed. In this paper, we first expose the reader to several situations and applications that need translation into natural language, thereby, motivating the problem. We then outline, by example, the research problems that need to be solved, separately for data translations and query translations.
Paired approximation problems and incompatible inapproximabilities
Venue: arXiv cs.DS 2009
Year: 2009

This paper considers pairs of optimization problems that are defined from a single input and for which it is desired to find a good approximation to either one of the problems. In many instances, it is possible to efficiently find an approximation of this type that is better than known inapproximability lower bounds for either of the two individual optimization problems forming the pair. In particular, we find either a $(1+ε)$-approximation to $(1,2)$-TSP or a $1/ε$-approximation to maximum independent set, from a given graph, in linear time. We show a similar paired approximation result for finding either a coloring or a long path. However, no such tradeoff exists in some other cases: for set cover and hitting set problems defined from a single set family, and for clique and independent set problems on the same graph, it is not possible to find an approximation when both problems are combined that is better than the best approximation for either problem on its own.
Using Ellipsoidal Domains to Analyze Control Systems Software
Venue: arXiv cs.PL 2009
Year: 2009

We propose a methodology for the automatic verification of safety properties of controllers based on dynamical systems, such as those typically used in avionics. In particular, our focus is on proving stability properties of software implementing linear and some non-linear controllers. We develop an abstract interpretation framework that follows closely the Lyapunov methods used in proofs at the model level and describe the corresponding abstract domains, which for linear systems consist of ellipsoidal constraints. These ellipsoidal domains provide abstractions for the values of state variables and must be combined with other domains that model the remaining variables in a program. Thus, the problem of automatically assigning the right type of abstract domain to each variable arises. We provide an algorithm that solves this classification problem in many practical cases and suggest how it could be generalized to more complicated cases. We then find a fixpoint by solving a matrix equation, which in the linear case is just the discrete Lyapunov equation. Contrary to most cases in software analysis, this fixpoint cannot be reached by the usual iterative method of propagating constraints until saturation and so numerical methods become essential. Finally, we illustrate our methodology with several examples.
A Lightweight Distributed Solution to Content Replication in Mobile Networks
Venue: arXiv cs.NI 2009
Year: 2009

Performance and reliability of content access in mobile networks is conditioned by the number and location of content replicas deployed at the network nodes. Facility location theory has been the traditional, centralized approach to study content replication: computing the number and placement of replicas in a network can be cast as an uncapacitated facility location problem. The endeavour of this work is to design a distributed, lightweight solution to the above joint optimization problem, while taking into account the network dynamics. In particular, we devise a mechanism that lets nodes share the burden of storing and providing content, so as to achieve load balancing, and decide whether to replicate or drop the information so as to adapt to a dynamic content demand and time-varying topology. We evaluate our mechanism through simulation, by exploring a wide range of settings and studying realistic content access mechanisms that go beyond the traditional assumptionmatching demand points to their closest content replica. Results show that our mechanism, which uses local measurements only, is: (i) extremely precise in approximating an optimal solution to content placement and replication; (ii) robust against network mobility; (iii) flexible in accommodating various content access patterns, including variation in time and space of the content demand.
Back analysis based on SOM-RST system
Venue: arXiv cs.AI 2009
Year: 2009

This paper describes application of information granulation theory, on the back analysis of Jeffrey mine southeast wall Quebec. In this manner, using a combining of Self Organizing Map (SOM) and rough set theory (RST), crisp and rough granules are obtained. Balancing of crisp granules and sub rough granules is rendered in close-open iteration. Combining of hard and soft computing, namely finite difference method (FDM) and computational intelligence and taking in to account missing information are two main benefits of the proposed method. As a practical example, reverse analysis on the failure of the southeast wall Jeffrey mine is accomplished.
Towards a General Definition of Biometric Systems
Venue: arXiv cs.OH 2009
Year: 2009

A foundation for closing the gap between biometrics in the narrower and the broader perspective is presented trough a conceptualization of biometric systems in both perspectives. A clear distinction between verification, identification and classification systems is made as well as shown that there are additional classes of biometric systems. In the end a Unified Modeling Language model is developed showing the connections between the two perspectives.
Global Heuristic Search on Encrypted Data (GHSED)
Venue: arXiv cs.CR 2009
Year: 2009

Important document are being kept encrypted in remote servers. In order to retrieve these encrypted data, efficient search methods needed to enable the retrieval of the document without knowing the content of the documents In this paper a technique called a global heuristic search on encrypted data (GHSED) technique will be described for search in an encrypted files using public key encryption stored on an untrusted server and retrieve the files that satisfy a certain search pattern without revealing any information about the original files. GHSED technique would satisfy the following: (1) Provably secure, the untrusted server cannot learn anything about the plaintext given only the cipher text. (2) Provide controlled searching, so that the untrusted server cannot search for a word without the user's authorization. (3) Support hidden queries, so that the user may ask the untrusted server to search for a secret word without revealing the word to the server. (4) Support query isolation, so the untrusted server learns nothing more than the search result about the plaintext.
Comprehensive Security Framework for Global Threads Analysis
Venue: arXiv cs.CR 2009
Year: 2009

Cyber criminality activities are changing and becoming more and more professional. With the growth of financial flows through the Internet and the Information System (IS), new kinds of thread arise involving complex scenarios spread within multiple IS components. The IS information modeling and Behavioral Analysis are becoming new solutions to normalize the IS information and counter these new threads. This paper presents a framework which details the principal and necessary steps for monitoring an IS. We present the architecture of the framework, i.e. an ontology of activities carried out within an IS to model security information and User Behavioral analysis. The results of the performed experiments on real data show that the modeling is effective to reduce the amount of events by 91%. The User Behavioral Analysis on uniform modeled data is also effective, detecting more than 80% of legitimate actions of attack scenarios.
Similarity Matching Techniques for Fault Diagnosis in Automotive Infotainment Electronics
Venue: arXiv cs.AI 2009
Year: 2009

Fault diagnosis has become a very important area of research during the last decade due to the advancement of mechanical and electrical systems in industries. The automobile is a crucial field where fault diagnosis is given a special attention. Due to the increasing complexity and newly added features in vehicles, a comprehensive study has to be performed in order to achieve an appropriate diagnosis model. A diagnosis system is capable of identifying the faults of a system by investigating the observable effects (or symptoms). The system categorizes the fault into a diagnosis class and identifies a probable cause based on the supplied fault symptoms. Fault categorization and identification are done using similarity matching techniques. The development of diagnosis classes is done by making use of previous experience, knowledge or information within an application area. The necessary information used may come from several sources of knowledge, such as from system analysis. In this paper similarity matching techniques for fault diagnosis in automotive infotainment applications are discussed.
Geometric and Signal Strength Dilution of Precision (DoP)Wi-Fi
Venue: arXiv cs.NI 2009
Year: 2009

The democratization of wireless networks combined to the emergence of mobile devices increasingly autonomous and efficient lead to new services. Positioning services become overcrowded. Accuracy is the main quality criteria in positioning. But to better appreciate this one a coefficient is needed. In this paper we present Geometric and Signal Strength Dilution of Precision (DOP) for positioning systems based on Wi-Fi and Signal Strength measurements.
End User Computing in AIB Capital Markets: A Management Summary
Venue: arXiv cs.HC 2009
Year: 2009

This paper is a management summary of how the area of End User Computing (EUC) has been addressed by AIB Capital Markets. The development of an effective policy is described, as well as the process by which a register of critical EUC applications was assembled and how those applications were brought into a controlled environment. A number of findings are included as well as recommendations for others who would seek to run a similar project.
Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs
Venue: arXiv cs.DS 2009
Year: 2009

In this paper we study the problem of existence of a crossing-free acyclic hamiltonian path completion (for short, HP-completion) set for embedded upward planar digraphs. In the context of book embeddings, this question becomes: given an embedded upward planar digraph $G$, determine whether there exists an upward 2-page book embedding of $G$ preserving the given planar embedding. Given an embedded $st$-digraph $G$ which has a crossing-free HP-completion set, we show that there always exists a crossing-free HP-completion set with at most two edges per face of $G$. For an embedded $N$-free upward planar digraph $G$, we show that there always exists a crossing-free acyclic HP-completion set for $G$ which, moreover, can be computed in linear time. For a width-$k$ embedded planar $st$-digraph $G$, we show that we can be efficiently test whether $G$ admits a crossing-free acyclic HP-completion set.
Vers la reconnaissance de mini-messages manuscrits
Venue: arXiv cs.CL 2009
Year: 2009

Handwriting is an alternative method for entering texts which composed Short Message Services. However, a whole new language features the texts which are produced. They include for instance abbreviations and other consonantal writing which sprung up for time saving and fashion. We have collected and processed a significant number of such handwritten SMS, and used various strategies to tackle this challenging area of handwriting recognition. We proposed to study more specifically three different phenomena: consonant skeleton, rebus, and phonetic writing. For each of them, we compare the rough results produced by a standard recognition system with those obtained when using a specific language model to take care of them.
A Random Variable Substitution Lemma With Applications to Multiple Description Coding
Venue: arXiv cs.IT 2009
Year: 2009

We establish a random variable substitution lemma and use it to investigate the role of refinement layer in multiple description coding, which clarifies the relationship among several existing achievable multiple description rate-distortion regions. Specifically, it is shown that the El Gamal-Cover (EGC) region is equivalent to the EGC* region (an antecedent version of the EGC region) while the Venkataramani-Kramer-Goyal (VKG) region (when specialized to the 2-description case) is equivalent to the Zhang-Berger (ZB) region. Moreover, we prove that for multiple description coding with individual and hierarchical distortion constraints, the number of layers in the VKG scheme can be significantly reduced when only certain weighted sum rates are concerned. The role of refinement layer in scalable coding (a special case of multiple description coding) is also studied.
FPT Algorithms for Connected Feedback Vertex Set
Venue: arXiv cs.DS 2009
Year: 2009

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists a subset F of V, of size at most k, such that G[V F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time $O(2^{O(k)}n^{O(1)})$ on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses as subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it will be useful for obtaining parameterized algorithms for other connectivity problems.
Analyse en dépendances à l'aide des grammaires d'interaction
Venue: arXiv cs.CL 2009
Year: 2009

This article proposes a method to extract dependency structures from phrase-structure level parsing with Interaction Grammars. Interaction Grammars are a formalism which expresses interactions among words using a polarity system. Syntactical composition is led by the saturation of polarities. Interactions take place between constituents, but as grammars are lexicalized, these interactions can be translated at the level of words. Dependency relations are extracted from the parsing process: every dependency is the consequence of a polarity saturation. The dependency relations we obtain can be seen as a refinement of the usual dependency tree. Generally speaking, this work sheds new light on links between phrase structure and dependency parsing.
Grouping Synonyms by Definitions
Venue: arXiv cs.CL 2009
Year: 2009

We present a method for grouping the synonyms of a lemma according to its dictionary senses. The senses are defined by a large machine readable dictionary for French, the TLFi (Trésor de la langue française informatisé) and the synonyms are given by 5 synonym dictionaries (also for French). To evaluate the proposed method, we manually constructed a gold standard where for each (word, definition) pair and given the set of synonyms defined for that word by the 5 synonym dictionaries, 4 lexicographers specified the set of synonyms they judge adequate. While inter-annotator agreement ranges on that task from 67% to at best 88% depending on the annotator pair and on the synonym dictionary being considered, the automatic procedure we propose scores a precision of 67% and a recall of 71%. The proposed method is compared with related work namely, word sense disambiguation, synonym lexicon acquisition and WordNet construction.
ODMRP with Quality of Service and local recovery with security Support
Venue: arXiv cs.NI 2009
Year: 2009

In this paper we focus on one critical issue in mobile ad hoc networks that is multicast routing and propose a mesh based on demand multicast routing protocol for Ad-Hoc networks with QoS (quality of service) support. Then a model was presented which is used for create a local recovering mechanism in order to joining the nodes to multi sectional groups at the minimized time and method for security in this protocol we present .
Extension of Path Probability Method to Approximate Inference over Time
Venue: arXiv cs.LG 2009
Year: 2009

There has been a tremendous growth in publicly available digital video footage over the past decade. This has necessitated the development of new techniques in computer vision geared towards efficient analysis, storage and retrieval of such data. Many mid-level computer vision tasks such as segmentation, object detection, tracking, etc. involve an inference problem based on the video data available. Video data has a high degree of spatial and temporal coherence. The property must be intelligently leveraged in order to obtain better results. Graphical models, such as Markov Random Fields, have emerged as a powerful tool for such inference problems. They are naturally suited for expressing the spatial dependencies present in video data, It is however, not clear, how to extend the existing techniques for the problem of inference over time. This thesis explores the Path Probability Method, a variational technique in statistical mechanics, in the context of graphical models and approximate inference problems. It extends the method to a general framework for problems involving inference in time, resulting in an algorithm, \emph{DynBP}. We explore the relation of the algorithm with existing techniques, and find the algorithm competitive with existing approaches. The main contribution of this thesis are the extended GBP algorithm, the extension of Path Probability Methods to the DynBP algorithm and the relationship between them. We have also explored some applications in computer vision involving temporal evolution with promising results.
Large-girth roots of graphs
Venue: arXiv cs.DS 2009
Year: 2009

We study the problem of recognizing graph powers and computing roots of graphs. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r+3, thus improving a bound conjectured by Farzad et al. (STACS 2009). Our algorithm also finds all r-th roots of a given graph that have girth at least 2r+3 and no degree one vertices, which is a step towards a recent conjecture of Levenshtein that such root should be unique. On the negative side, we prove that recognition becomes an NP-complete problem when the bound on girth is about twice smaller. Similar results have so far only been attempted for r=2,3.
Personal Information Databases
Venue: arXiv cs.DB 2009
Year: 2009

One of the most important aspects of security organization is to establish a framework to identify security significant points where policies and procedures are declared. The (information) security infrastructure comprises entities, processes, and technology. All are participants in handling information, which is the item that needs to be protected. Privacy and security information technology is a critical and unmet need in the management of personal information. This paper proposes concepts and technologies for management of personal information. Two different types of information can be distinguished: personal information and nonpersonal information. Personal information can be either personal identifiable information (PII), or nonidentifiable information (NII). Security, policy, and technical requirements can be based on this distinction. At the conceptual level, PII is defined and formalized by propositions over infons (discrete pieces of information) that specify transformations in PII and NII. PII is categorized into simple infons that reflect the proprietor s aspects, relationships with objects, and relationships with other proprietors. The proprietor is the identified person about whom the information is communicated. The paper proposes a database organization that focuses on the PII spheres of proprietors. At the design level, the paper describes databases of personal identifiable information built exclusively for this type of information, with their own conceptual scheme, system management, and physical structure.
Clustering with Obstacles in Spatial Databases
Venue: arXiv cs.DB 2009
Year: 2009

Clustering large spatial databases is an important problem, which tries to find the densely populated regions in a spatial area to be used in data mining, knowledge discovery, or efficient information retrieval. However most algorithms have ignored the fact that physical obstacles such as rivers, lakes, and highways exist in the real world and could thus affect the result of the clustering. In this paper, we propose CPO, an efficient clustering technique to solve the problem of clustering in the presence of obstacles. The proposed algorithm divides the spatial area into rectangular cells. Each cell is associated with statistical information used to label the cell as dense or non-dense. It also labels each cell as obstructed (i.e. intersects any obstacle) or nonobstructed. For each obstructed cell, the algorithm finds a number of non-obstructed sub-cells. Then it finds the dense regions of non-obstructed cells or sub-cells by a breadthfirst search as the required clusters with a center to each region.
Algorithm for Spatial Clustering with Obstacles
Venue: arXiv cs.DB 2009
Year: 2009

In this paper, we propose an efficient clustering technique to solve the problem of clustering in the presence of obstacles. The proposed algorithm divides the spatial area into rectangular cells. Each cell is associated with statistical information that enables us to label the cell as dense or non-dense. We also label each cell as obstructed (i.e. intersects any obstacle) or non-obstructed. Then the algorithm finds the regions (clusters) of connected, dense, non-obstructed cells. Finally, the algorithm finds a center for each such region and returns those centers as centers of the relatively dense regions (clusters) in the spatial area.