OpenRaiser/Intern-Atlas huggingface dataset:
The steepest watershed: from graphs to images
Venue: arXiv cs.CV 2012
Year: 2012

The watershed is a powerful tool for segmenting objects whose contours appear as crest lines on a gradient image. The watershed transform associates to a topographic surface a partition into catchment basins, defined as attraction zones of a drop of water falling on the relief and following a line of steepest descent. Unfortunately, catchment basins may overlap and do not form a partition. Moreover, current watershed algorithms, being shortsighted, do not correctly estimate the steepness of the downwards trajectories and overestimate the overlapping zones of catchment basins. An arbitrary division of these zones between adjacent catchment basin results in a poor localization of the contours. We propose an algorithm without myopia, which considers the total length of a trajectory for estimating its steepness. We first consider topographic surfaces defined on node weighted graphs. The graphs are pruned in order to eliminate all downwards trajectories which are not the steepest. An iterative algorithm with simple neighborhood operations performs the pruning and constructs the catchment basins. The algorithm is then adapted to gray tone images. The graph structure itself is encoded as an image thanks to the fixed neighborhood structure of grids. A pair of adaptative erosions and dilations prune the graph and extend the catchment basins. As a result one obtains a precise detection of the catchment basins and a graph of the steepest trajectories. A last iterative algorithm allows to follow selected downwards trajectories in order to detect particular structures such as rivers or thalweg lines of the topographic surface.
The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy
Venue: arXiv cs.DS 2012
Year: 2012

This paper proves that an "old dog", namely -- the classical Johnson-Lindenstrauss transform, "performs new tricks" -- it gives a novel way of preserving differential privacy. We show that if we take two databases, $D$ and $D'$, such that (i) $D'-D$ is a rank-1 matrix of bounded norm and (ii) all singular values of $D$ and $D'$ are sufficiently large, then multiplying either $D$ or $D'$ with a vector of iid normal Gaussians yields two statistically close distributions in the sense of differential privacy. Furthermore, a small, deterministic and \emph{public} alteration of the input is enough to assert that all singular values of $D$ are large. We apply the Johnson-Lindenstrauss transform to the task of approximating cut-queries: the number of edges crossing a $(S,\bar S)$-cut in a graph. We show that the JL transform allows us to \emph{publish a sanitized graph} that preserves edge differential privacy (where two graphs are neighbors if they differ on a single edge) while adding only $O(|S|/ε)$ random noise to any given query (w.h.p). Comparing the additive noise of our algorithm to existing algorithms for answering cut-queries in a differentially private manner, we outperform all others on small cuts ($|S| = o(n)$). We also apply our technique to the task of estimating the variance of a given matrix in any given direction. The JL transform allows us to \emph{publish a sanitized covariance matrix} that preserves differential privacy w.r.t bounded changes (each row in the matrix can change by at most a norm-1 vector) while adding random noise of magnitude independent of the size of the matrix (w.h.p). In contrast, existing algorithms introduce an error which depends on the matrix dimensions.
Construction of Community Web Directories based on Web usage Data
Venue: arXiv cs.OH 2012
Year: 2012

This paper support the concept of a community Web directory, as a Web directory that is constructed according to the needs and interests of particular user communities. Furthermore, it presents the complete method for the construction of such directories by using web usage data. User community models take the form of thematic hierarchies and are constructed by employing clustering approach. We applied our methodology to the ODP directory and also to an artificial Web directory, which was generated by clustering Web pages that appear in the access log of an Internet Service Provider. For the discovery of the community models, we introduced a new criterion that combines a priori thematic informativeness of the Web directory categories with the level of interest observed in the usage data. In this context, we introduced and evaluated new clustering method. We have tested the methodology using access log files which are collected from the proxy servers of an Internet Service Provider and provided results that indicates the usability of the community Web directories. The proposed clustering methodology is evaluated both on a specialized artificial and a community Web directory, indicating its value to the user of the web.
Investigating Keyphrase Indexing with Text Denoising
Venue: arXiv cs.DL 2012
Year: 2012

In this paper, we report on indexing performance by a state-of-the-art keyphrase indexer, Maui, when paired with a text extraction procedure called text denoising. Text denoising is a method that extracts the denoised text, comprising the content-rich sentences, from full texts. The performance of the keyphrase indexer is demonstrated on three standard corpora collected from three domains, namely food and agriculture, high energy physics, and biomedical science. Maui is trained using the full texts and denoised texts. The indexer, using its trained models, then extracts keyphrases from test sets comprising full texts, and their denoised and noise parts (i.e., the part of texts that remains after denoising). Experimental findings show that against a gold standard, the denoised-text-trained indexer indexing full texts, performs either better than or as good as its benchmark performance produced by a full-text-trained indexer indexing full texts.
Performance Enhancement of Ad Hoc Networks with Janitor Based Routing
Venue: arXiv cs.NI 2012
Year: 2012

We propose and analyze a new on the fly strategy that discovers, repairs and maintains routes in hierarchical and distributed fashion called Janitor Based Routing (JBR). The main motivation behind our JBR protocol is to decrease flooding and routing overhead and increase efficiencies in packet movement. An analytical model for the proposed JBR is presented and detailed simulation is used to observe the performance of JBR. This route discovery and maintenance protocol clearly achieved improvement in terms of reduction of flooding, routing overhead, and, hence, provides enhanced reliability.
Optimal tree for Genetic Algorithms in the Traveling Salesman Problem (TSP)
Venue: arXiv cs.OH 2012
Year: 2012

In this paper, the author proposes optimal tree as a "gauge" for the generation of the initial population at random in the Genetic Algorithms (GA) to benchmark against the good and the bad parent tours. Thus, without having the so-called bad parent tours in the initiate population, it will speed up the GA. The characteristics of the gauge (algorithm, complexity time, trade-off, etc.) will be discussed in this paper as well.
Quantifier-Free Interpolation of a Theory of Arrays
Venue: arXiv cs.LO 2012
Year: 2012

The use of interpolants in model checking is becoming an enabling technology to allow fast and robust verification of hardware and software. The application of encodings based on the theory of arrays, however, is limited by the impossibility of deriving quantifier- free interpolants in general. In this paper, we show that it is possible to obtain quantifier-free interpolants for a Skolemized version of the extensional theory of arrays. We prove this in two ways: (1) non-constructively, by using the model theoretic notion of amalgamation, which is known to be equivalent to admit quantifier-free interpolation for universal theories; and (2) constructively, by designing an interpolating procedure, based on solving equations between array updates. (Interestingly, rewriting techniques are used in the key steps of the solver and its proof of correctness.) To the best of our knowledge, this is the first successful attempt of computing quantifier- free interpolants for a variant of the theory of arrays with extensionality.
Employing Subsequence Matching in Audio Data Processing
Venue: arXiv cs.SD 2012
Year: 2012

We overview current problems of audio retrieval and time-series subsequence matching. We discuss the usage of subsequence matching approaches in audio data processing, especially in automatic speech recognition (ASR) area and we aim at improving performance of the retrieval process. To overcome the problems known from the time-series area like the occurrence of implementation bias and data bias we present a Subsequence Matching Framework as a tool for fast prototyping, building, and testing similarity search subsequence matching applications. The framework is build on top of MESSIF (Metric Similarity Search Implementation Framework) and thus the subsequence matching algorithms can exploit advanced similarity indexes in order to significantly increase their query processing performance. To prove our concept we provide a design of query-by-example spoken term detection type of application with the usage of phonetic posteriograms and subsequence matching approach.
A Novel Framework using Elliptic Curve Cryptography for Extremely Secure Transmission in Distributed Privacy Preserving Data Mining
Venue: arXiv cs.DB 2012
Year: 2012

Privacy Preserving Data Mining is a method which ensures privacy of individual information during mining. Most important task involves retrieving information from multiple data bases which is distributed. The data once in the data warehouse can be used by mining algorithms to retrieve confidential information. The proposed framework has two major tasks, secure transmission and privacy of confidential information during mining. Secure transmission is handled by using elliptic curve cryptography and data distortion for privacy preservation ensuring highly secure environment.
Efficient Iterative Decoding of LDPC in the Presence of Strong Phase Noise
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we propose a new efficient message passing algorithm for decoding LDPC transmitted over a channel with strong phase noise. The algorithm performs approximate bayesian inference on a factor graph representation of the channel and code joint posterior. The approximate inference is based on an improved canonical model for the messages of the Sum & Product Algorithm, and a method for clustering the messages using the directional statistics framework. The proposed canonical model includes treatment for phase slips which can limit the performance of tracking algorithms. We show simulation results and complexity analysis for the proposed algorithm demonstrating its superiority over some of the current state of the art algorithms.
A practical approach to language complexity: a Wikipedia case study
Venue: arXiv cs.CL 2012
Year: 2012

In this paper we present statistical analysis of English texts from Wikipedia. We try to address the issue of language complexity empirically by comparing the simple English Wikipedia (Simple) to comparable samples of the main English Wikipedia (Main). Simple is supposed to use a more simplified language with a limited vocabulary, and editors are explicitly requested to follow this guideline, yet in practice the vocabulary richness of both samples are at the same level. Detailed analysis of longer units (n-grams of words and part of speech tags) shows that the language of Simple is less complex than that of Main primarily due to the use of shorter sentences, as opposed to drastically simplified syntax or vocabulary. Comparing the two language varieties by the Gunning readability index supports this conclusion. We also report on the topical dependence of language complexity, e.g. that the language is more advanced in conceptual articles compared to person-based (biographical) and object-based articles. Finally, we investigate the relation between conflict and language complexity by analyzing the content of the talk pages associated to controversial and peacefully developing articles, concluding that controversy has the effect of reducing language complexity.
Non-sparse Linear Representations for Visual Tracking with Online Reservoir Metric Learning
Venue: arXiv cs.CV 2012
Year: 2012

Most sparse linear representation-based trackers need to solve a computationally expensive L1-regularized optimization problem. To address this problem, we propose a visual tracker based on non-sparse linear representations, which admit an efficient closed-form solution without sacrificing accuracy. Moreover, in order to capture the correlation information between different feature dimensions, we learn a Mahalanobis distance metric in an online fashion and incorporate the learned metric into the optimization problem for obtaining the linear representation. We show that online metric learning using proximity comparison significantly improves the robustness of the tracking, especially on those sequences exhibiting drastic appearance changes. Furthermore, in order to prevent the unbounded growth in the number of training samples for the metric learning, we design a time-weighted reservoir sampling method to maintain and update limited-sized foreground and background sample buffers for balancing sample diversity and adaptability. Experimental results on challenging videos demonstrate the effectiveness and robustness of the proposed tracker.
Diversity versus Channel Knowledge at Finite Block-Length
Venue: arXiv cs.IT 2012
Year: 2012

We study the maximal achievable rate R*(n, ε) for a given block-length n and block error probability εover Rayleigh block-fading channels in the noncoherent setting and in the finite block-length regime. Our results show that for a given block-length and error probability, R*(n, ε) is not monotonic in the channel's coherence time, but there exists a rate maximizing coherence time that optimally trades between diversity and cost of estimating the channel.
Tractable Answer-Set Programming with Weight Constraints: Bounded Treewidth is not Enough
Venue: arXiv cs.LO 2012
Year: 2012

Cardinality constraints or, more generally, weight constraints are well recognized as an important extension of answer-set programming. Clearly, all common algorithmic tasks related to programs with cardinality or weight constraints - like checking the consistency of a program - are intractable. Many intractable problems in the area of knowledge representation and reasoning have been shown to become linear time tractable if the treewidth of the programs or formulas under consideration is bounded by some constant. The goal of this paper is to apply the notion of treewidth to programs with cardinality or weight constraints and to identify tractable fragments. It will turn out that the straightforward application of treewidth to such class of programs does not suffice to obtain tractability. However, by imposing further restrictions, tractability can be achieved.
The Rank of Tree-Automatic Linear Orderings
Venue: arXiv cs.LO 2012
Year: 2012

We generalise Delhommé's result that each tree-automatic ordinal is strictly below ω^ω^ω by showing that any tree-automatic linear ordering has FC-rank strictly below ω^ω. We further investigate a restricted form of tree-automaticity and prove that every linear ordering which admits a tree-automatic presentation of branching complexity at most k has FC-rank strictly below ω^k.
Alternative Tilings for the Fast Multipole Method on the Plane
Venue: arXiv cs.NA 2012
Year: 2012

The fast multipole method (FMM) performs fast approximate kernel summation to a specified tolerance $ε$ by using a hierarchical division of the domain, which groups source and receiver points into regions that satisfy local separation and the well-separated pair decomposition properties. While square tilings and quadtrees are commonly used in 2D, we investigate alternative tilings and associated spatial data structures: regular hexagons (septree) and triangles (triangle-quadtree). We show that both structures satisfy separation properties for the FMM and prove their theoretical error bounds and computational costs. Empirical runtime and error analysis of our implementations are provided.
Reliable communication over non-binary insertion/deletion channels
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of reliable communication over non-binary insertion/deletion channels where symbols are randomly deleted from or inserted in the transmitted sequence and all symbols are corrupted by additive white Gaussian noise. To this end, we utilize the inherent redundancy achievable in non-binary symbol sets by first expanding the symbol set and then allocating part of the bits associated with each symbol to watermark symbols. The watermark sequence, known at the receiver, is then used by a forward-backward algorithm to provide soft information for an outer code which decodes the transmitted sequence. Through numerical results and discussions, we evaluate the performance of the proposed solution and show that it leads to significant system ability to detect and correct insertions/deletions. We also provide estimates of the maximum achievable information rates of the system, compare them with the available bounds, and construct practical codes capable of approaching these limits.
Monografia
Venue: arXiv cs.CR 2012
Year: 2012

Developed structural scheme implementation of an integrated security and formulated principles for the creation and development of an effective system of information security.
Automated synthesis of reliable and efficient systems through game theory: a case study
Venue: arXiv cs.GT 2012
Year: 2012

Reactive computer systems bear inherent complexity due to continuous interactions with their environment. While this environment often proves to be uncontrollable, we still want to ensure that critical computer systems will not fail, no matter what they face. Examples are legion: railway traffic, power plants, plane navigation systems, etc. Formal verification of a system may ensure that it satisfies a given specification, but only applies to an already existing model of a system. In this work, we address the problem of synthesis: starting from a specification of the desired behavior, we show how to build a suitable system controller that will enforce this specification. In particular, we discuss recent developments of that approach for systems that must ensure Boolean behaviors (e.g., reachability, liveness) along with quantitative requirements over their execution (e.g., never drop out of fuel, ensure a suitable mean response time). We notably illustrate a powerful, practically useable algorithm for the automated synthesis of provably safe reactive systems.
Ubiquitous Indoor Localization and Worldwide Automatic Construction of Floor Plans
Venue: arXiv cs.NI 2012
Year: 2012

Although GPS has been considered a ubiquitous outdoor localization technology, we are still far from a similar technology for indoor environments. While a number of technologies have been proposed for indoor localization, they are isolated efforts that are way from a true ubiquitous localization system. A ubiquitous indoor positioning system is envisioned to be deployed on a large scale worldwide, with minimum overhead, to work with heterogeneous devices, and to allow users to roam seamlessly from indoor to outdoor environments. Such a system will enable a wide set of applications including worldwide seamless direction finding between indoor locations, enhancing first responders' safety by providing anywhere localization and floor plans, and providing a richer environment for location-aware social networking applications. We describe an architecture for the ubiquitous indoor positioning system (IPS) and the challenges that have to be addressed to materialize it. We then focus on the feasibility of automating the construction of a worldwide indoor floor plan and fingerprint database which, as we believe, is one of the main challenges that limit the existence of a ubiquitous IPS system. Our proof of concept uses a crowd-sourcing approach that leverages the embedded sensors in today's cell phones as a worldwide distributed floor plan generation tool. This includes constructing the floor plans and determining the areas of interest (corridors, offices, meeting rooms, elevators, etc). The cloud computing concepts are also adopted for the processing and storage of the huge amount of data generated and requested by the system's users. Our results show the ability of the system to construct an accurate floor plan and identify the areas of interest with more than 90% accuracy. We also identify different research directions for addressing the challenges of realizing a true ubiquitous IPS system.
What "Crowdsourcing" Obscures: Exposing the Dynamics of Connected Crowd Work during Disaster
Venue: arXiv cs.SI 2012
Year: 2012

The aim of this paper is to demonstrate that the current understanding of crowdsourcing may not be broad enough to capture the diversity of crowd work during disasters, or specific enough to highlight the unique dynamics of information organizing by the crowd in that context. In making this argument, this paper first unpacks the crowdsourcing term, examining its roots in open source development and outsourcing business models, and tying it to related concepts of human computation and collective intelligence. The paper then attempts to characterize several examples of crowd work during disasters using current definitions of crowdsourcing and existing models for human computation and collective intelligence, exposing a need for future research towards a framework for understanding crowd work.
Crowdsourcing Gaze Data Collection
Venue: arXiv cs.SI 2012
Year: 2012

Knowing where people look is a useful tool in many various image and video applications. However, traditional gaze tracking hardware is expensive and requires local study participants, so acquiring gaze location data from a large number of participants is very problematic. In this work we propose a crowdsourced method for acquisition of gaze direction data from a virtually unlimited number of participants, using a robust self-reporting mechanism (see Figure 1). Our system collects temporally sparse but spatially dense points-of-attention in any visual information. We apply our approach to an existing video data set and demonstrate that we obtain results similar to traditional gaze tracking. We also explore the parameter ranges of our method, and collect gaze tracking data for a large set of YouTube videos.
Cloudpress 2.0: A MapReduce Approach for News Retrieval on the Cloud
Venue: arXiv cs.DC 2012
Year: 2012

In this era of the Internet, the amount of news articles added every minute of everyday is humongous. As a result of this explosive amount of news articles, news retrieval systems are required to process the news articles frequently and intensively. The news retrieval systems that are in-use today are not capable of coping up with these data-intensive computations. Cloudpress 2.0 presented here, is designed and implemented to be scalable, robust and fault tolerant. It is designed in such a way that, all the processes involved in news retrieval such as fetching, pre-processing, indexing, storing and summarizing, exploit MapReduce paradigm and use the power of the Cloud computing. It uses novel approaches for parallel processing, for storing the news articles in a distributed database and for visualizing them as a 3D visual. It uses Lucene-based indexing for efficient and faster retrieval. It also includes a novel query expansion feature for searching the news articles. Cloudpress 2.0 also allows on-the-fly, extractive summarization of news articles based on the input query.