OpenRaiser/Intern-Atlas huggingface dataset:
On the Convergence Speed of Turbo Demodulation with Turbo Decoding
Venue: arXiv cs.IT 2012
Year: 2012

Iterative processing is widely adopted nowadays in modern wireless receivers for advanced channel codes like turbo and LDPC codes. Extension of this principle with an additional iterative feedback loop to the demapping function has proven to provide substantial error performance gain. However, the adoption of iterative demodulation with turbo decoding is constrained by the additional implied implementation complexity, heavily impacting latency and power consumption. In this paper, we analyze the convergence speed of these combined two iterative processes in order to determine the exact required number of iterations at each level. Extrinsic information transfer (EXIT) charts are used for a thorough analysis at different modulation orders and code rates. An original iteration scheduling is proposed reducing two demapping iterations with reasonable performance loss of less than 0.15 dB. Analyzing and normalizing the computational and memory access complexity, which directly impact latency and power consumption, demonstrates the considerable gains of the proposed scheduling and the promising contributions of the proposed analysis.
Analysing Temporally Annotated Corpora with CAVaT
Venue: arXiv cs.CL 2012
Year: 2012

We present CAVaT, a tool that performs Corpus Analysis and Validation for TimeML. CAVaT is an open source, modular checking utility for statistical analysis of features specific to temporally-annotated natural language corpora. It provides reporting, highlights salient links between a variety of general and time-specific linguistic features, and also validates a temporal annotation to ensure that it is logically consistent and sufficiently annotated. Uniquely, CAVaT provides analysis specific to TimeML-annotated temporal information. TimeML is a standard for annotating temporal information in natural language text. In this paper, we present the reporting part of CAVaT, and then its error-checking ability, including the workings of several novel TimeML document verification methods. This is followed by the execution of some example tasks using the tool to show relations between times, events, signals and links. We also demonstrate inconsistencies in a TimeML corpus (TimeBank) that have been detected with CAVaT.
Kernel Density Feature Points Estimator for Content-Based Image Retrieval
Venue: arXiv cs.CV 2012
Year: 2012

Research is taking place to find effective algorithms for content-based image representation and description. There is a substantial amount of algorithms available that use visual features (color, shape, texture). Shape feature has attracted much attention from researchers that there are many shape representation and description algorithms in literature. These shape image representation and description algorithms are usually not application independent or robust, making them undesirable for generic shape description. This paper presents an object shape representation using Kernel Density Feature Points Estimator (KDFPE). In this method, the density of feature points within defined rings around the centroid of the image is obtained. The KDFPE is then applied to the vector of the image. KDFPE is invariant to translation, scale and rotation. This method of image representation shows improved retrieval rate when compared to Density Histogram Feature Points (DHFP) method. Analytic analysis is done to justify our method, which was compared with the DHFP to prove its robustness.
A Reduction-Preserving Completion for Proving Confluence of Non-Terminating Term Rewriting Systems
Venue: arXiv cs.LO 2012
Year: 2012

We give a method to prove confluence of term rewriting systems that contain non-terminating rewrite rules such as commutativity and associativity. Usually, confluence of term rewriting systems containing such rules is proved by treating them as equational term rewriting systems and considering E-critical pairs and/or termination modulo E. In contrast, our method is based solely on usual critical pairs and it also (partially) works even if the system is not terminating modulo E. We first present confluence criteria for term rewriting systems whose rewrite rules can be partitioned into a terminating part and a possibly non-terminating part. We then give a reduction-preserving completion procedure so that the applicability of the criteria is enhanced. In contrast to the well-known Knuth-Bendix completion procedure which preserves the equivalence relation of the system, our completion procedure preserves the reduction relation of the system, by which confluence of the original system is inferred from that of the completed system.
A New Low-Complexity Selected Mapping Scheme Using Cyclic Shifted IFFT for PAPR Reduction in OFDM Systems
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, a new peak-to-average power ratio (PAPR) reduction scheme for orthogonal frequency division multiplexing (OFDM) is proposed based on the selected mapping (SLM) scheme. The proposed SLM scheme generates alternative OFDM signal sequences by cyclically shifting the connections in each subblock at an intermediate stage of inverse fast Fourier transform (IFFT). Compared with the conventional SLM scheme, the proposed SLM scheme achieves similar PAPR reduction performance with much lower computational complexity and no bit error rate (BER) degradation. The performance of the proposed SLM scheme is verified through numerical analysis. Also, it is shown that the proposed SLM scheme has the lowest computational complexity among the existing low-complexity SLM schemes exploiting the signals at an intermediate stage of IFFT.
Semi-Automatically Extracting FAQs to Improve Accessibility of Software Development Knowledge
Venue: arXiv cs.SE 2012
Year: 2012

Frequently asked questions (FAQs) are a popular way to document software development knowledge. As creating such documents is expensive, this paper presents an approach for automatically extracting FAQs from sources of software development discussion, such as mailing lists and Internet forums, by combining techniques of text mining and natural language processing. We apply the approach to popular mailing lists and carry out a survey among software developers to show that it is able to extract high-quality FAQs that may be further improved by experts.
Market-Oriented Cloud Computing and the Cloudbus Toolkit
Venue: arXiv cs.DC 2012
Year: 2012

Cloud computing has penetrated the Information Technology industry deep enough to influence major companies to adopt it into their mainstream business. A strong thrust on the use of virtualization technology to realize Infrastructure-as-a-Service (IaaS) has led enterprises to leverage subscription-oriented computing capabilities of public Clouds for hosting their application services. In parallel, research in academia has been investigating transversal aspects such as security, software frameworks, quality of service, and standardization. We believe that the complete realization of the Cloud computing vision will lead to the introduction of a virtual market where Cloud brokers, on behalf of end users, are in charge of selecting and composing the services advertised by different Cloud vendors. In order to make this happen, existing solutions and technologies have to be redesigned and extended from a market-oriented perspective and integrated together, giving rise to what we term Market-Oriented Cloud Computing. In this paper, we will assess the current status of Cloud computing by providing a reference model, discuss the challenges that researchers and IT practitioners are facing and will encounter in the near future, and present the approach for solving them from the perspective of the Cloudbus toolkit, which comprises of a set of technologies geared towards the realization of Market Oriented Cloud Computing vision. We provide experimental results demonstrating market-oriented resource provisioning and brokering within a Cloud and across multiple distributed resources. We also include an application illustrating the hosting of ECG analysis as SaaS on Amazon IaaS (EC2 and S3) services.
ASR Context-Sensitive Error Correction Based on Microsoft N-Gram Dataset
Venue: arXiv cs.CL 2012
Year: 2012

At the present time, computers are employed to solve complex tasks and problems ranging from simple calculations to intensive digital image processing and intricate algorithmic optimization problems to computationally-demanding weather forecasting problems. ASR short for Automatic Speech Recognition is yet another type of computational problem whose purpose is to recognize human spoken speech and convert it into text that can be processed by a computer. Despite that ASR has many versatile and pervasive real-world applications,it is still relatively erroneous and not perfectly solved as it is prone to produce spelling errors in the recognized text, especially if the ASR system is operating in a noisy environment, its vocabulary size is limited, and its input speech is of bad or low quality. This paper proposes a post-editing ASR error correction method based on MicrosoftN-Gram dataset for detecting and correcting spelling errors generated by ASR systems. The proposed method comprises an error detection algorithm for detecting word errors; a candidate corrections generation algorithm for generating correction suggestions for the detected word errors; and a context-sensitive error correction algorithm for selecting the best candidate for correction. The virtue of using the Microsoft N-Gram dataset is that it contains real-world data and word sequences extracted from the web which canmimica comprehensive dictionary of words having a large and all-inclusive vocabulary. Experiments conducted on numerous speeches, performed by different speakers, showed a remarkable reduction in ASR errors. Future research can improve upon the proposed algorithm so much so that it can be parallelized to take advantage of multiprocessor and distributed systems.
Social Media and the Social Good: How Nonprofits Use Facebook to Communicate with the Public
Venue: arXiv cs.CY 2012
Year: 2012

In this study, we examine the social networking practices of the 100 largest nonprofit organizations in the United States. More specifically, we develop a comprehensive classification scheme to delineate these organizations' use of Facebook as a stakeholder engagement tool. We find that there are 5 primary categories of Facebook "statuses", which can be aggregated into three key dimensions - "information", "community", and "action". Our analysis reveals that, though the "informational" use of Facebook is still significant, nonprofit organizations are better at using Facebook to strategically engage their stakeholders via "dialogic" and "community-building" practices than they have been with traditional websites. The adoption of social media seems to have engendered new paradigms of public engagement.
Improving an Hybrid Literary Book Recommendation System through Author Ranking
Venue: arXiv cs.IR 2012
Year: 2012

Literary reading is an important activity for individuals and choosing to read a book can be a long time commitment, making book choice an important task for book lovers and public library users. In this paper we present an hybrid recommendation system to help readers decide which book to read next. We study book and author recommendation in an hybrid recommendation setting and test our approach in the LitRec data set. Our hybrid book recommendation approach purposed combines two item-based collaborative filtering algorithms to predict books and authors that the user will like. Author predictions are expanded in to a book list that is subsequently aggregated with the former list generated through the initial collaborative recommender. Finally, the resulting book list is used to yield the top-n book recommendations. By means of various experiments, we demonstrate that author recommendation can improve overall book recommendation.
Distributed, Cross-Platform, and Regression Testing Architecture for Service-Oriented Architecture
Venue: arXiv cs.SE 2012
Year: 2012

As per leading IT experts, today's large enterprises are going through business transformations. They are adopting service-based IT models such as SOA to develop their enterprise information systems and applications. In fact, SOA is an integration of loosely-coupled interoperable components, possibly built using heterogeneous software technologies and hardware platforms. As a result, traditional testing architectures are no more adequate for verifying and validating the quality of SOA systems and whether they are operating to specifications. This paper first discusses the various state-of-the-art methods for testing SOA applications, and then it proposes a novel automated, distributed, cross-platform, and regression testing architecture for SOA systems. The proposed testing architecture consists of several testing units which include test engine, test code generator, test case generator, test executer, and test monitor units. Experiments conducted showed that the proposed testing architecture managed to use parallel agents to test heterogeneous web services whose technologies were incompatible with the testing framework. As future work, testing non-functional aspects of SOA applications are to be investigated so as to allow the testing of such properties as performance, security, availability, and scalability.
A Regularization Approach for Prediction of Edges and Node Features in Dynamic Graphs
Venue: arXiv cs.LG 2012
Year: 2012

We consider the two problems of predicting links in a dynamic graph sequence and predicting functions defined at each node of the graph. In many applications, the solution of one problem is useful for solving the other. Indeed, if these functions reflect node features, then they are related through the graph structure. In this paper, we formulate a hybrid approach that simultaneously learns the structure of the graph and predicts the values of the node-related functions. Our approach is based on the optimization of a joint regularization objective. We empirically test the benefits of the proposed method with both synthetic and real data. The results indicate that joint regularization improves prediction performance over the graph evolution and the node features.
Transfer Learning, Soft Distance-Based Bias, and the Hierarchical BOA
Venue: arXiv cs.NE 2012
Year: 2012

An automated technique has recently been proposed to transfer learning in the hierarchical Bayesian optimization algorithm (hBOA) based on distance-based statistics. The technique enables practitioners to improve hBOA efficiency by collecting statistics from probabilistic models obtained in previous hBOA runs and using the obtained statistics to bias future hBOA runs on similar problems. The purpose of this paper is threefold: (1) test the technique on several classes of NP-complete problems, including MAXSAT, spin glasses and minimum vertex cover; (2) demonstrate that the technique is effective even when previous runs were done on problems of different size; (3) provide empirical evidence that combining transfer learning with other efficiency enhancement techniques can often yield nearly multiplicative speedups.
Optimal Private Halfspace Counting via Discrepancy
Venue: arXiv cs.DS 2012
Year: 2012

A range counting problem is specified by a set $P$ of size $|P| = n$ of points in $\mathbb{R}^d$, an integer weight $x_p$ associated to each point $p \in P$, and a range space ${\cal R} \subseteq 2^{P}$. Given a query range $R \in {\cal R}$, the target output is $R(\vec{x}) = \sum_{p \in R}{x_p}$. Range counting for different range spaces is a central problem in Computational Geometry. We study $(ε, δ)$-differentially private algorithms for range counting. Our main results are for the range space given by hyperplanes, that is, the halfspace counting problem. We present an $(ε, δ)$-differentially private algorithm for halfspace counting in $d$ dimensions which achieves $O(n^{1-1/d})$ average squared error. This contrasts with the $Ω(n)$ lower bound established by the classical result of Dinur and Nissim [PODS 2003] for arbitrary subset counting queries. We also show a matching lower bound on average squared error for any $(ε, δ)$-differentially private algorithm for halfspace counting. Both bounds are obtained using discrepancy theory. For the lower bound, we use a modified discrepancy measure and bound approximation of $(ε, δ)$-differentially private algorithms for range counting queries in terms of this discrepancy. We also relate the modified discrepancy measure to classical combinatorial discrepancy, which allows us to exploit known discrepancy lower bounds. This approach also yields a lower bound of $Ω((\log n)^{d-1})$ for $(ε, δ)$-differentially private orthogonal range counting in $d$ dimensions, the first known superconstant lower bound for this problem. For the upper bound, we use an approach inspired by partial coloring methods for proving discrepancy upper bounds, and obtain $(ε, δ)$-differentially private algorithms for range counting with polynomially bounded shatter function range spaces.
Breaking a novel colour image encryption algorithm based on chaos
Venue: arXiv cs.CR 2012
Year: 2012

Recently, a colour image encryption algorithm based on chaos was proposed by cascading two position permutation operations and one substitution operation, which are all determined by some pseudo-random number sequences generated by iterating the Logistic map. This paper evaluates the security level of the encryption algorithm and finds that the position permutation-only part and the substitution part can be separately broken with only $\lceil (\log_2(3MN))/8 \rceil$ and 2 chosen plain-images, respectively, where $MN$ is the size of the plain-image. Concise theoretical analyses are provided to support the chosen-plaintext attack, which are verified by experimental results also.
Memory Hierarchy Sensitive Graph Layout
Venue: arXiv cs.DS 2012
Year: 2012

Mining large graphs for information is becoming an increasingly important workload due to the plethora of graph structured data becoming available. An aspect of graph algorithms that has hitherto not received much interest is the effect of memory hierarchy on accesses. A typical system today has multiple levels in the memory hierarchy with differing units of locality; ranging across cache lines, TLB entries and DRAM pages. We postulate that it is possible to allocate graph structured data in main memory in a way as to improve the spatial locality of the data. Previous approaches to improving cache locality have focused only on a single unit of locality, either the cache line or virtual memory page. On the other hand cache oblivious algorithms can optimise layout for all levels of the memory hierarchy but unfortunately need to be specially designed for individual data structures. In this paper we explore hierarchical blocking as a technique for closing this gap. We require as input a specification of the units of locality in the memory hierarchy and lay out the input graph accordingly by copying its nodes using a hierarchy of breadth first searches. We start with a basic algorithm that is limited to trees and then extend it to arbitrary graphs. Our most efficient version requires only a constant amount of additional space. We have implemented versions of the algorithm in various environments: for C programs interfaced with macros, as an extension to the Boost object oriented graph library and finally as a modification to the traversal phase of the semispace garbage collector in the Jikes Java virtual machine. Our results show significant improvements in the access time to graphs of various structure.
Building Custom Term Suggestion Web Services with OAI-Harvested Open Data
Venue: arXiv cs.DL 2012
Year: 2012

The problem that the same information need can be expressed in a variety of ways is especially true for scientific literature. Each scientific discipline has its own domain-specific language and vocabulary. This language is coded into documentary tools like thesauri or classifications that are used to document and describe scientific documents. When we think of information retrieval as "fundamentally a linguistic process" (Blair, 2003) users have to be aware of the most relevant search terms - which are the controlled thesauri terms the documents are described with. This can be achieved with so-called search-term-recommenders (STR) that map free search terms of a lay user to controlled vocabulary terms which can then be used as a term suggestion or to do an automatic query expansion (Hienert, Schaer, Schaible, & Mayr, 2011). State-of-the-art repository software systems like DSpace or EPrints already offer some kind of term suggestion features in search or input forms but these implementations only work as simple auto completion mechanisms that don't incorporate any kind of semantic mapping. Such software systems would gain a lot in terms of usability and data consistency if tools like the proposed domain-specific STRs would be freely available. We aim to implement a rich toolbox of web services (like the mentioned domain-specific STRs) to support users and providers of online Digital Library (DL) or repository systems.
Compressed Sensing for Moving Imagery in Medical Imaging
Venue: arXiv cs.MM 2012
Year: 2012

Numerous applications in signal processing have benefited from the theory of compressed sensing which shows that it is possible to reconstruct signals sampled below the Nyquist rate when certain conditions are satisfied. One of these conditions is that there exists a known transform that represents the signal with a sufficiently small number of non-zero coefficients. However when the signal to be reconstructed is composed of moving images or volumes, it is challenging to form such regularization constraints with traditional transforms such as wavelets. In this paper, we present a motion compensating prior for such signals that is derived directly from the optical flow constraint and can utilize the motion information during compressed sensing reconstruction. Proposed regularization method can be used in a wide variety of applications involving compressed sensing and images or volumes of moving and deforming objects. It is also shown that it is possible to estimate the signal and the motion jointly or separately. Practical examples from magnetic resonance imaging has been presented to demonstrate the benefit of the proposed method.
Series Crimes
Venue: arXiv cs.SC 2012
Year: 2012

Puiseux series are power series in which the exponents can be fractional and/or negative rational numbers. Several computer algebra systems have one or more built-in or loadable functions for computing truncated Puiseux series. Some are generalized to allow coefficients containing functions of the series variable that are dominated by any power of that variable, such as logarithms and nested logarithms of the series variable. Some computer algebra systems also have built-in or loadable functions that compute infinite Puiseux series. Unfortunately, there are some little-known pitfalls in computing Puiseux series. The most serious of these is expansions within branch cuts or at branch points that are incorrect for some directions in the complex plane. For example with each series implementation accessible to you: Compare the value of (z^2 + z^3)^(3/2) with that of its truncated series expansion about z = 0, approximated at z = -0.01. Does the series converge to a value that is the negative of the correct value? Compare the value of ln(z^2 + z^3) with its truncated series expansion about z = 0, approximated at z = -0.01 + 0.1i. Does the series converge to a value that is incorrect by 2pi i? Compare arctanh(-2 + ln(z)z) with its truncated series expansion about z = 0, approximated at z = -0.01. Does the series converge to a value that is incorrect by about pi i? At the time of this writing, most implementations that accommodate such series exhibit such errors. This article describes how to avoid these errors both for manual derivation of series and when implementing series packages.