OpenRaiser/Intern-Atlas huggingface dataset:
A Compositional Distributional Semantics, Two Concrete Constructions, and some Experimental Evaluations
Venue: arXiv cs.CL 2011
Year: 2011

We provide an overview of the hybrid compositional distributional model of meaning, developed in Coecke et al. (arXiv:1003.4394v1 [cs.CL]), which is based on the categorical methods also applied to the analysis of information flow in quantum protocols. The mathematical setting stipulates that the meaning of a sentence is a linear function of the tensor products of the meanings of its words. We provide concrete constructions for this definition and present techniques to build vector spaces for meaning vectors of words, as well as that of sentences. The applicability of these methods is demonstrated via a toy vector space as well as real data from the British National Corpus and two disambiguation experiments.
Analysis of Alternative Metrics for the PAPR Problem in OFDM Transmission
Venue: arXiv cs.IT 2011
Year: 2011

The effective PAPR of the transmit signal is the standard metric to capture the effect of nonlinear distortion in OFDM transmission. A common rule of thumb is the log$(N)$ barrier where $N$ is the number of subcarriers which has been theoretically analyzed by many authors. Recently, new alternative metrics have been proposed in practice leading potentially to different system design rules which are theoretically analyzed in this paper. One of the main findings is that, most surprisingly, the log$(N)$ barrier turns out to be much too conservative: e.g. for the so-called amplifier-oriented metric the scaling is rather $\log[ \log(N)]$. To prove this result, new upper bounds on the PAPR distribution for coded systems are presented as well as a theorem relating PAPR results to these alternative metrics.
User Mode Memory Page Management: An old idea applied anew to the memory wall problem
Venue: arXiv cs.OS 2011
Year: 2011

It is often said that one of the biggest limitations on computer performance is memory bandwidth (i.e."the memory wall problem"). In this position paper, I argue that if historical trends in computing evolution (where growth in available capacity is exponential and reduction in its access latencies is linear) continue as they have, then this view is wrong - in fact we ought to be concentrating on reducing whole system memory access latencies wherever possible, and by "whole system" I mean that we ought to look at how software can be unnecessarily wasteful with memory bandwidth due to legacy design decisions. To this end I conduct a feasibility study to determine whether we ought to virtualise the MMU for each application process such that it has direct access to its own MMU page tables and the memory allocated to a process is managed exclusively by the process and not the kernel. I find under typical conditions that nearly scale invariant performance to memory allocation size is possible such that hundreds of megabytes of memory can be allocated, relocated, swapped and deallocated in almost the same time as kilobytes (e.g. allocating 8Mb is 10x quicker under this experimental allocator than a conventional allocator, and resizing a 128Kb block to 256Kb block is 4.5x faster). I find that first time page access latencies are improved tenfold; moreover, because the kernel page fault handler is never called, the lack of cache pollution improves whole application memory access latencies increasing performance by up to 2x. Finally, I try binary patching existing applications to use the experimental allocation technique, finding almost universal performance improvements without having to recompile these applications to make better use of the new facilities.
Emerging multidisciplinary research across database management systems
Venue: arXiv cs.DB 2011
Year: 2011

The database community is exploring more and more multidisciplinary avenues: Data semantics overlaps with ontology management; reasoning tasks venture into the domain of artificial intelligence; and data stream management and information retrieval shake hands, e.g., when processing Web click-streams. These new research avenues become evident, for example, in the topics that doctoral students choose for their dissertations. This paper surveys the emerging multidisciplinary research by doctoral students in database systems and related areas. It is based on the PIKM 2010, which is the 3rd Ph.D. workshop at the International Conference on Information and Knowledge Management (CIKM). The topics addressed include ontology development, data streams, natural language processing, medical databases, green energy, cloud computing, and exploratory search. In addition to core ideas from the workshop, we list some open research questions in these multidisciplinary areas.
Brain-like infrastructure for embedded SoC diagnosis
Venue: arXiv cs.AR 2011
Year: 2011

This article describes high-speed multiprocessor architecture for the concurrent analyzing information represented in analytic, graph- and table forms of associative relations to search, recognize and make a decision in n-dimensional vector discrete space. Vector-logical process models of actual applications,for which the quality of solution is estimated by the proposed integral non-arithmetical metric of the interaction between Boolean vectors, are described.
Approximation Algorithms for Submodular Multiway Partition
Venue: arXiv cs.DS 2011
Year: 2011

We study algorithms for the Submodular Multiway Partition problem (SubMP). An instance of SubMP consists of a finite ground set $V$, a subset of $k$ elements $S = \{s_1,s_2,...,s_k\}$ called terminals, and a non-negative submodular set function $f:2^V\rightarrow \mathbb{R}_+$ on $V$ provided as a value oracle. The goal is to partition $V$ into $k$ sets $A_1,...,A_k$ such that for $1 \le i \le k$, $s_i \in A_i$ and $\sum_{i=1}^k f(A_i)$ is minimized. SubMP generalizes some well-known problems such as the Multiway Cut problem in graphs and hypergraphs, and the Node-weighed Multiway Cut problem in graphs. SubMP for arbitrarysubmodular functions (instead of just symmetric functions) was considered by Zhao, Nagamochi and Ibaraki \cite{ZhaoNI05}. Previous algorithms were based on greedy splitting and divide and conquer strategies. In very recent work \cite{ChekuriE11} we proposed a convex-programming relaxation for SubMP based on the Lovász-extension of a submodular function and showed its applicability for some special cases. In this paper we obtain the following results for arbitrary submodular functions via this relaxation. (i) A 2-approximation for SubMP. This improves the $(k-1)$-approximation from \cite{ZhaoNI05} and (ii) A $(1.5-1/k)$-approximation for SubMP when $f$ is symmetric. This improves the $2(1-1/k)$-approximation from \cite{Queyranne99,ZhaoNI05}.
Scalar Quantization with Random Thresholds
Venue: arXiv cs.IT 2011
Year: 2011

The distortion-rate performance of certain randomly-designed scalar quantizers is determined. The central results are the mean-squared error distortion and output entropy for quantizing a uniform random variable with thresholds drawn independently from a uniform distribution. The distortion is at most 6 times that of an optimal (deterministically-designed) quantizer, and for a large number of levels the output entropy is reduced by approximately (1-gamma)/(ln 2) bits, where gamma is the Euler-Mascheroni constant. This shows that the high-rate asymptotic distortion of these quantizers in an entropy-constrained context is worse than the optimal quantizer by at most a factor of 6 exp(-2(1-gamma)).
Distributed Semantic Web Data Management in HBase and MySQL Cluster
Venue: arXiv cs.DB 2011
Year: 2011

Various computing and data resources on the Web are being enhanced with machine-interpretable semantic descriptions to facilitate better search, discovery and integration. This interconnected metadata constitutes the Semantic Web, whose volume can potentially grow the scale of the Web. Efficient management of Semantic Web data, expressed using the W3C's Resource Description Framework (RDF), is crucial for supporting new data-intensive, semantics-enabled applications. In this work, we study and compare two approaches to distributed RDF data management based on emerging cloud computing technologies and traditional relational database clustering technologies. In particular, we design distributed RDF data storage and querying schemes for HBase and MySQL Cluster and conduct an empirical comparison of these approaches on a cluster of commodity machines using datasets and queries from the Third Provenance Challenge and Lehigh University Benchmark. Our study reveals interesting patterns in query evaluation, shows that our algorithms are promising, and suggests that cloud computing has a great potential for scalable Semantic Web data management.
Science Models as Value-Added Services for Scholarly Information Systems
Venue: arXiv cs.DL 2011
Year: 2011

The paper introduces scholarly Information Retrieval (IR) as a further dimension that should be considered in the science modeling debate. The IR use case is seen as a validation model of the adequacy of science models in representing and predicting structure and dynamics in science. Particular conceptualizations of scholarly activity and structures in science are used as value-added search services to improve retrieval quality: a co-word model depicting the cognitive structure of a field (used for query expansion), the Bradford law of information concentration, and a model of co-authorship networks (both used for re-ranking search results). An evaluation of the retrieval quality when science model driven services are used turned out that the models proposed actually provide beneficial effects to retrieval quality. From an IR perspective, the models studied are therefore verified as expressive conceptualizations of central phenomena in science. Thus, it could be shown that the IR perspective can significantly contribute to a better understanding of scholarly structures and activities.
Computer certified efficient exact reals in Coq
Venue: arXiv cs.LO 2011
Year: 2011

Floating point operations are fast, but require continuous effort on the part of the user in order to ensure that the results are correct. This burden can be shifted away from the user by providing a library of exact analysis in which the computer handles the error estimates. We provide an implementation of the exact real numbers in the Coq proof assistant. This improves on the earlier Coq-implementation by O'Connor in two ways: we use dyadic rationals built from the machine integers and we optimize computation of power series by using approximate division. Moreover, we use type classes for clean mathematical interfaces. This appears to be the first time that type classes are used in heavy computation. We obtain over a 100 times speed up of the basic operations and indications for improving the Coq system.
Improving Performance of Speaker Identification System Using Complementary Information Fusion
Venue: arXiv cs.SD 2011
Year: 2011

Feature extraction plays an important role as a front-end processing block in speaker identification (SI) process. Most of the SI systems utilize like Mel-Frequency Cepstral Coefficients (MFCC), Perceptual Linear Prediction (PLP), Linear Predictive Cepstral Coefficients (LPCC), as a feature for representing speech signal. Their derivations are based on short term processing of speech signal and they try to capture the vocal tract information ignoring the contribution from the vocal cord. Vocal cord cues are equally important in SI context, as the information like pitch frequency, phase in the residual signal, etc could convey important speaker specific attributes and are complementary to the information contained in spectral feature sets. In this paper we propose a novel feature set extracted from the residual signal of LP modeling. Higher-order statistical moments are used here to find the nonlinear relationship in residual signal. To get the advantages of complementarity vocal cord based decision score is fused with the vocal tract based score. The experimental results on two public databases show that fused mode system outperforms single spectral features.
View subspaces for indexing and retrieval of 3D models
Venue: arXiv cs.CV 2011
Year: 2011

View-based indexing schemes for 3D object retrieval are gaining popularity since they provide good retrieval results. These schemes are coherent with the theory that humans recognize objects based on their 2D appearances. The viewbased techniques also allow users to search with various queries such as binary images, range images and even 2D sketches. The previous view-based techniques use classical 2D shape descriptors such as Fourier invariants, Zernike moments, Scale Invariant Feature Transform-based local features and 2D Digital Fourier Transform coefficients. These methods describe each object independent of others. In this work, we explore data driven subspace models, such as Principal Component Analysis, Independent Component Analysis and Nonnegative Matrix Factorization to describe the shape information of the views. We treat the depth images obtained from various points of the view sphere as 2D intensity images and train a subspace to extract the inherent structure of the views within a database. We also show the benefit of categorizing shapes according to their eigenvalue spread. Both the shape categorization and data-driven feature set conjectures are tested on the PSB database and compared with the competitor view-based 3D shape retrieval algorithms
Salient Local 3D Features for 3D Shape Retrieval
Venue: arXiv cs.CV 2011
Year: 2011

In this paper we describe a new formulation for the 3D salient local features based on the voxel grid inspired by the Scale Invariant Feature Transform (SIFT). We use it to identify the salient keypoints (invariant points) on a 3D voxelized model and calculate invariant 3D local feature descriptors at these keypoints. We then use the bag of words approach on the 3D local features to represent the 3D models for shape retrieval. The advantages of the method are that it can be applied to rigid as well as to articulated and deformable 3D models. Finally, this approach is applied for 3D Shape Retrieval on the McGill articulated shape benchmark and then the retrieval results are presented and compared to other methods.
Face Recognition using 3D Facial Shape and Color Map Information: Comparison and Combination
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we investigate the use of 3D surface geometry for face recognition and compare it to one based on color map information. The 3D surface and color map data are from the CAESAR anthropometric database. We find that the recognition performance is not very different between 3D surface and color map information using a principal component analysis algorithm. We also discuss the different techniques for the combination of the 3D surface and color map information for multi-modal recognition by using different fusion approaches and show that there is significant improvement in results. The effectiveness of various techniques is compared and evaluated on a dataset with 200 subjects in two different positions.
Retrieval and Clustering from a 3D Human Database based on Body and Head Shape
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, we describe a framework for similarity based retrieval and clustering from a 3D human database. Our technique is based on both body and head shape representation and the retrieval is based on similarity of both of them. The 3D human database used in our study is the CAESAR anthropometric database which contains approximately 5000 bodies. We have developed a web-based interface for specifying the queries to interact with the retrieval system. Our approach performs the similarity based retrieval in a reasonable amount of time and is a practical approach.
Pattern avoidance with involution
Venue: arXiv cs.FL 2011
Year: 2011

We give the avoidance indices (morphic and antimorphic) for all unary patterns with involution.
Multi-Amdahl: Optimal Resource Sharing with Multiple Program Execution Segments
Venue: arXiv cs.AR 2011
Year: 2011

This paper presents Multi-Amdahl, a resource allocation analytical tool for heterogeneous systems. Our model includes multiple program execution segments, where each one is accelerated by a specific hardware unit. The acceleration speedup of the specific hardware unit is a function of a limited resource, such as the unit area, power, or energy. Using the Lagrange theorem we discover the optimal resource distribution between all specific units. We then illustrate this general Multi-Amdahl technique using several examples of area and power allocation among several cores and accelerators.
Anatomy of a Bit: Information in a Time Series Observation
Venue: arXiv cs.IT 2011
Year: 2011

Appealing to several multivariate information measures---some familiar, some new here---we analyze the information embedded in discrete-valued stochastic time series. We dissect the uncertainty of a single observation to demonstrate how the measures' asymptotic behavior sheds structural and semantic light on the generating process's internal information dynamics. The measures scale with the length of time window, which captures both intensive (rates of growth) and subextensive components. We provide interpretations for the components, developing explicit relationships between them. We also identify the informational component shared between the past and the future that is not contained in a single observation. The existence of this component directly motivates the notion of a process's effective (internal) states and indicates why one must build models.
A Novel Method for Calculating Demand Not Served for Transmission Expansion Planning
Venue: arXiv cs.OH 2011
Year: 2011

Restructuring of the power market introduced demand uncertainty in transmission expansion planning (TEP), which in turn also requires an accurate estimation of demand not served (DNS). Unfortunately, the graph theory based minimum-cut maximum-flow (MCMF) approach does not ensure that electrical laws are followed. Nor can it be used for calculating DNS at individual buses. In this letter, we propose a generalized load flow based methodology for calculating DNS. This procedure is able to calculate simultaneously generation not served (GNS) and wheeling loss (WL). Importantly, the procedure is able to incorporate the effect of I2R losses, excluded in MCMF approach. Case study on a 5-bus IEEE system shows the effectiveness of the proposed approach over existing method.
Hierarchies in Dependence Logic
Venue: arXiv cs.LO 2011
Year: 2011

We study fragments of dependence logic defined either by restricting the number k of universal quantifiers or the width of dependence atoms in formulas. We find the sublogics of existential second-order logic corresponding to these fragments of dependence logic. We also show that these both ways of defining fragments of dependence logic give rise to a hierarchy in expressive power with respect to k.
Relating Weight Constraint and Aggregate Programs: Semantics and Representation
Venue: arXiv cs.LO 2011
Year: 2011

Weight constraint and aggregate programs are among the most widely used logic programs with constraints. In this paper, we relate the semantics of these two classes of programs, namely the stable model semantics for weight constraint programs and the answer set semantics based on conditional satisfaction for aggregate programs. Both classes of programs are instances of logic programs with constraints, and in particular, the answer set semantics for aggregate programs can be applied to weight constraint programs. We show that the two semantics are closely related. First, we show that for a broad class of weight constraint programs, called strongly satisfiable programs, the two semantics coincide. When they disagree, a stable model admitted by the stable model semantics may be circularly justified. We show that the gap between the two semantics can be closed by transforming a weight constraint program to a strongly satisfiable one, so that no circular models may be generated under the current implementation of the stable model semantics. We further demonstrate the close relationship between the two semantics by formulating a transformation from weight constraint programs to logic programs with nested expressions which preserves the answer set semantics. Our study on the semantics leads to an investigation of a methodological issue, namely the possibility of compact representation of aggregate programs by weight constraint programs. We show that almost all standard aggregates can be encoded by weight constraints compactly. This makes it possible to compute the answer sets of aggregate programs using the ASP solvers for weight constraint programs. This approach is compared experimentally with the ones where aggregates are handled more explicitly, which show that the weight constraint encoding of aggregates enables a competitive approach to answer set computation for aggregate programs.
Xapagy: a cognitive architecture for narrative reasoning
Venue: arXiv cs.AI 2011
Year: 2011

We introduce the Xapagy cognitive architecture: a software system designed to perform narrative reasoning. The architecture has been designed from scratch to model and mimic the activities performed by humans when witnessing, reading, recalling, narrating and talking about stories.
Face Shape and Reflectance Acquisition using a Multispectral Light Stage
Venue: arXiv cs.CV 2011
Year: 2011

In this thesis, we discuss the design and calibration (geometric and radiometric) of a novel shape and reflectance acquisition device called the "Multispectral Light Stage". This device can capture highly detailed facial geometry (down to the level of skin pores detail) and Multispectral reflectance map which can be used to estimate biophysical skin parameters such as the distribution of pigmentation and blood beneath the surface of the skin. We extend the analysis of the original spherical gradient photometric stereo method to study the effects of deformed diffuse lobes on the quality of recovered surface normals. Based on our modified radiance equations, we develop a minimal image set method to recover high quality photometric normals using only four, instead of six, spherical gradient images. Using the same radiance equations, we explore a Quadratic Programming (QP) based algorithm for correction of surface normals obtained using spherical gradient photometric stereo. Based on the proposed minimal image sets method, we present a performance capture sequence that significantly reduces the data capture requirement and post-processing computational cost of existing photometric stereo based performance geometry capture methods. Furthermore, we explore the use of images captured in our Light Stage to generate stimuli images for a psychology experiment exploring the neural representation of 3D shape and texture of a human face.