OpenRaiser/Intern-Atlas huggingface dataset:
Multidimensional or Relational? / How to Organize an On-line Analytical Processing Database
Venue: arXiv cs.DB 2011
Year: 2011

In the past few years, the number of OLAP applications increased quickly. These applications use two significantly different DB structures: multidimensional (MD) and table-based. One can show that the traditional model of relational databases cannot make difference between these two structures. Another model is necessary to make the differences visible. One of these is the speed of the system. It can be proven that the multidimensional DB organization results in shorter response times. And it is crucial, since a manager may become impatient, if he or she has to wait say more than 20 seconds for the next screen. On the other hand, we have to pay for the speed with a bigger DB size. Why does the size of MD databases grow so quickly? The reason is the sparsity of data: The MD matrix contains many empty cells. Efficient handling of sparse matrices is indispensable in an OLAP application. One way to handle sparsity is to take the structure closer to the table-based one. Thus the DB size decreases, while the application gets slower. Therefore, other methods are needed. This paper deals with the comparison of the two DB structures and the limits of their usage. The new results of the paper: (1) It gives a constructive proof that all relations can be represented in MD arrays. (2) It also shows when the MD array representation is quicker than the table-based one. (3) The MD representation results in smaller DB size under some conditions. One such sufficient condition is proved in the paper. (4) A variation of the single count header compression scheme is described with an algorithm, which creates the compressed array from the ordered table without materializing the uncompressed array. (5) The speed of the two different database organizations is tested with experiments, as well. The tests are done on benchmark as well as real life data. The experiments support the theoretical results.
Analysis of Randomized Work Stealing with False Sharing
Venue: arXiv cs.DC 2011
Year: 2011

This paper analyzes the cache miss cost of algorithms when scheduled using randomized work stealing (RWS) in a parallel environment, taking into account the effects of false sharing. First, prior analyses (due to Acar et al.) are extended to incorporate false sharing. However, to control the possible delays due to false sharing, some restrictions on the algorithms seem necessary. Accordingly, the class of Hierarchical Tree algorithms is introduced and their performance analyzed. In addition, the paper analyzes the performance of a subclass of the Hierarchical Tree Algorithms, called HBP algorithms, when scheduled using RWS; improved complexity bounds are obtained for this subclass. This class was introduced in a companion paper with efficient resource oblivious computation in mind. Finally, we note that in a scenario in which there is no false sharing the results in this paper match prior bounds for cache misses but with reduced assumptions, and in particular with no need for a bounding concave function for the cost of cache misses as in prior work by Frigo and Strumpen. This allows non-trivial cache miss bounds in this case to be obtained for a larger class of algorithms.
Caching in Multidimensional Databases
Venue: arXiv cs.DB 2011
Year: 2011

One utilisation of multidimensional databases is the field of On-line Analytical Processing (OLAP). The applications in this area are designed to make the analysis of shared multidimensional information fast [9]. On one hand, speed can be achieved by specially devised data structures and algorithms. On the other hand, the analytical process is cyclic. In other words, the user of the OLAP application runs his or her queries one after the other. The output of the last query may be there (at least partly) in one of the previous results. Therefore caching also plays an important role in the operation of these systems. However, caching itself may not be enough to ensure acceptable performance. Size does matter: The more memory is available, the more we gain by loading and keeping information in there. Oftentimes, the cache size is fixed. This limits the performance of the multidimensional database, as well, unless we compress the data in order to move a greater proportion of them into the memory. Caching combined with proper compression methods promise further performance improvements. In this paper, we investigate how caching influences the speed of OLAP systems. Different physical representations (multidimensional and table) are evaluated. For the thorough comparison, models are proposed. We draw conclusions based on these models, and the conclusions are verified with empirical data.
Design and frequency analysis of continuous finite-time-convergent differentiator
Venue: arXiv cs.SY 2011
Year: 2011

In this paper, a continuous finite-time-convergent differentiator is presented based on a strong Lyapunov function. The continuous differentiator can reduce chattering phenomenon sufficiently than normal sliding mode differentiator, and the outputs of signal tracking and derivative estimation are all smooth. Frequency analysis is applied to compare the continuous differentiator with sliding mode differentiator. The beauties of the continuous finite-time-convergent differentiator include its simplicity, restraining noises sufficiently, and avoiding the chattering phenomenon.
MDP Optimal Control under Temporal Logic Constraints
Venue: arXiv cs.RO 2011
Year: 2011

In this paper, we develop a method to automatically generate a control policy for a dynamical system modeled as a Markov Decision Process (MDP). The control specification is given as a Linear Temporal Logic (LTL) formula over a set of propositions defined on the states of the MDP. We synthesize a control policy such that the MDP satisfies the given specification almost surely, if such a policy exists. In addition, we designate an "optimizing proposition" to be repeatedly satisfied, and we formulate a novel optimization criterion in terms of minimizing the expected cost in between satisfactions of this proposition. We propose a sufficient condition for a policy to be optimal, and develop a dynamic programming algorithm that synthesizes a policy that is optimal under some conditions, and sub-optimal otherwise. This problem is motivated by robotic applications requiring persistent tasks, such as environmental monitoring or data gathering, to be performed.
Interference Alignment with Partially Coordinated Transmit Precoding
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we introduce an efficient interference alignment (IA) algorithm exploiting partially coordinated transmit precoding to improve the number of concurrent interference-free transmissions, i.e., the multiplexing gain, in multicell downlink. The proposed coordination model is such that each base-station simultaneously transmits to two users and each user is served by two base-stations. First, we show in a K-user system operating at the information theoretic upper bound of degrees of freedom (DOF), the generic IA is proper when $K \leq 3$, whereas the proposed partially coordinated IA is proper when $K \leq 5$. Then, we derive a non-iterative, i.e., one shot, IA algorithm for the proposed scheme when $K \leq 5$. We show that for a given latency, the backhaul data rate requirement of the proposed method grows linearly with K. Monte-Carlo simulation results show that the proposed one-shot algorithm offers higher system throughput than the iterative IA at practical SNR levels.
Information Theoretic Bounds for Tensor Rank Minimization over Finite Fields
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of noiseless and noisy low-rank tensor completion from a set of random linear measurements. In our derivations, we assume that the entries of the tensor belong to a finite field of arbitrary size and that reconstruction is based on a rank minimization framework. The derived results show that the smallest number of measurements needed for exact reconstruction is upper bounded by the product of the rank, the order and the dimension of a cubic tensor. Furthermore, this condition is also sufficient for unique minimization. Similar bounds hold for the noisy rank minimization scenario, except for a scaling function that depends on the channel error probability.
Clustered regression with unknown clusters
Venue: arXiv cs.LG 2011
Year: 2011

We consider a collection of prediction experiments, which are clustered in the sense that groups of experiments ex- hibit similar relationship between the predictor and response variables. The experiment clusters as well as the regres- sion relationships are unknown. The regression relation- ships define the experiment clusters, and in general, the predictor and response variables may not exhibit any clus- tering. We call this prediction problem clustered regres- sion with unknown clusters (CRUC) and in this paper we focus on linear regression. We study and compare several methods for CRUC, demonstrate their applicability to the Yahoo Learning-to-rank Challenge (YLRC) dataset, and in- vestigate an associated mathematical model. CRUC is at the crossroads of many prior works and we study several prediction algorithms with diverse origins: an adaptation of the expectation-maximization algorithm, an approach in- spired by K-means clustering, the singular value threshold- ing approach to matrix rank minimization under quadratic constraints, an adaptation of the Curds and Whey method in multiple regression, and a local regression (LoR) scheme reminiscent of neighborhood methods in collaborative filter- ing. Based on empirical evaluation on the YLRC dataset as well as simulated data, we identify the LoR method as a good practical choice: it yields best or near-best prediction performance at a reasonable computational load, and it is less sensitive to the choice of the algorithm parameter. We also provide some analysis of the LoR method for an asso- ciated mathematical model, which sheds light on optimal parameter choice and prediction performance.
Hardness of discrepancy computation and epsilon-net verification in high dimension
Venue: arXiv cs.CG 2011
Year: 2011

Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. There are two notions of discrepancy, namely continuous discrepancy and combinatorial discrepancy. Depending on the ranges, several possible variants arise, for example star discrepancy, box discrepancy, and discrepancy of half-spaces. In this paper, we investigate the hardness of these problems with respect to the dimension d of the underlying space. All these problems are solvable in time {n^O(d)}, but such a time dependency quickly becomes intractable for high-dimensional data. Thus it is interesting to ask whether the dependency on d can be moderated. We answer this question negatively by proving that the canonical decision problems are W[1]-hard with respect to the dimension. This is done via a parameterized reduction from the Clique problem. As the parameter stays linear in the input parameter, the results moreover imply that these problems require {n^Ω(d)} time, unless 3-Sat can be solved in {2^o(n)} time. Further, we derive that testing whether a given set is an ε-net with respect to half-spaces takes {n^Ω(d)} time under the same assumption. As intermediate results, we discover the W[1]-hardness of other well known problems, such as determining the largest empty star inside the unit cube. For this, we show that it is even hard to approximate within a factor of {2^n}.
The Topology of Wireless Communication
Venue: arXiv cs.DS 2011
Year: 2011

In this paper we study the topological properties of wireless communication maps and their usability in algorithmic design. We consider the SINR model, which compares the received power of a signal at a receiver against the sum of strengths of other interfering signals plus background noise. To describe the behavior of a multi-station network, we use the convenient representation of a \emph{reception map}. In the SINR model, the resulting \emph{SINR diagram} partitions the plane into reception zones, one per station, and the complementary region of the plane where no station can be heard. We consider the general case where transmission energies are arbitrary (or non-uniform). Under that setting, the reception zones are not necessarily convex or even connected. This poses the algorithmic challenge of designing efficient point location techniques as well as the theoretical challenge of understanding the geometry of SINR diagrams. We achieve several results in both directions. We establish a form of weaker convexity in the case where stations are aligned on a line. In addition, one of our key results concerns the behavior of a $(d+1)$-dimensional map. Specifically, although the $d$-dimensional map might be highly fractured, drawing the map in one dimension higher "heals" the zones, which become connected. In addition, as a step toward establishing a weaker form of convexity for the $d$-dimensional map, we study the interference function and show that it satisfies the maximum principle. Finally, we turn to consider algorithmic applications, and propose a new variant of approximate point location.
Linearizable Implementations Do Not Suffice for Randomized Distributed Computation
Venue: arXiv cs.DC 2011
Year: 2011

Linearizability is the gold standard among algorithm designers for deducing the correctness of a distributed algorithm using implemented shared objects from the correctness of the corresponding algorithm using atomic versions of the same objects. We show that linearizability does not suffice for this purpose when processes can exploit randomization, and we discuss the existence of alternative correctness conditions.
Cyclic and Inductive Calculi are equivalent
Venue: arXiv cs.LO 2011
Year: 2011

Brotherston and Simpson [citation] have formalized and investigated cyclic reasoning, reaching the important conclusion that it is at least as powerful as inductive reasoning (specifically, they showed that each inductive proof can be translated into a cyclic proof). We add to their investigation by proving the converse of this result, namely that each inductive proof can be translated into an inductive one. This, in effect, establishes the equivalence between first order cyclic and inductive calculi.
Computer Modelling of 3D Geological Surface
Venue: arXiv cs.CE 2011
Year: 2011

The geological surveying presently uses methods and tools for the computer modeling of 3D-structures of the geographical subsurface and geotechnical characterization as well as the application of geoinformation systems for management and analysis of spatial data, and their cartographic presentation. The objectives of this paper are to present a 3D geological surface model of Latur district in Maharashtra state of India. This study is undertaken through the several processes which are discussed in this paper to generate and visualize the automated 3D geological surface model of a projected area.
Lost in translation: data integration tools meet the Semantic Web (experiences from the Ondex project)
Venue: arXiv cs.SE 2011
Year: 2011

More information is now being published in machine processable form on the web and, as de-facto distributed knowledge bases are materializing, partly encouraged by the vision of the Semantic Web, the focus is shifting from the publication of this information to its consumption. Platforms for data integration, visualization and analysis that are based on a graph representation of information appear first candidates to be consumers of web-based information that is readily expressible as graphs. The question is whether the adoption of these platforms to information available on the Semantic Web requires some adaptation of their data structures and semantics. Ondex is a network-based data integration, analysis and visualization platform which has been developed in a Life Sciences context. A number of features, including semantic annotation via ontologies and an attention to provenance and evidence, make this an ideal candidate to consume Semantic Web information, as well as a prototype for the application of network analysis tools in this context. By analyzing the Ondex data structure and its usage, we have found a set of discrepancies and errors arising from the semantic mismatch between a procedural approach to network analysis and the implications of a web-based representation of information. We report in the paper on the simple methodology that we have adopted to conduct such analysis, and on issues that we have found which may be relevant for a range of similar platforms
Full-Rate Full-Diversity Achieving MIMO Precoding with Partial CSIT
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider a $n_t\times n_r$ multiple-input multiple-output (MIMO) channel subjected to block fading. Reliability (in terms of achieved diversity order) and rate (in number of symbols transmitted per channel use) are of interest in such channels. We propose a new precoding scheme which achieves both full diversity ($n_tn_r$th order diversity) as well as full rate ($n_t$ symbols per channel use) using partial channel state information at the transmitter (CSIT), applicable in MIMO systems including $n_r<n_t$ asymmetric MIMO. The proposed scheme achieves full diversity and improved coding gain through an optimization over the choice of constellation sets. The optimization maximizes $d_{min}^2$ for our precoding scheme subject to an energy constraint. The scheme requires feedback of $n_t-1$ angle parameter values, compared to $2n_tn_r$ real coefficients in case of full CSIT. Error rate performance results for $3\times 1$, $3\times 2$, $4\times 1$, $8\times 1$ precoded MIMO systems (with $n_t=3,3,4,8$ symbols per channel use, respectively) show that the proposed precoding achieves 3rd, 6th, 4th and 8th order diversities, respectively. These performances are shown to be better than other precoding schemes in the literature; the better performance is due to the choice of the signal sets and the feedback angles in the proposed scheme.
Formal and Computational Properties of the Confidence Boost of Association Rules
Venue: arXiv cs.DB 2011
Year: 2011

Some existing notions of redundancy among association rules allow for a logical-style characterization and lead to irredundant bases of absolutely minimum size. One can push the intuition of redundancy further and find an intuitive notion of interest of an association rule, in terms of its "novelty" with respect to other rules. Namely: an irredundant rule is so because its confidence is higher than what the rest of the rules would suggest; then, one can ask: how much higher? We propose to measure such a sort of "novelty" through the confidence boost of a rule, which encompasses two previous similar notions (confidence width and rule blocking, of which the latter is closely related to the earlier measure "improvement"). Acting as a complement to confidence and support, the confidence boost helps to obtain small and crisp sets of mined association rules, and solves the well-known problem that, in certain cases, rules of negative correlation may pass the confidence bound. We analyze the properties of two versions of the notion of confidence boost, one of them a natural generalization of the other. We develop efficient algorithmics to filter rules according to their confidence boost, compare the concept to some similar notions in the bibliography, and describe the results of some experimentation employing the new notions on standard benchmark datasets. We describe an open-source association mining tool that embodies one of our variants of confidence boost in such a way that the data mining process does not require the user to select any value for any parameter.
Latent Capacity Region: A Case Study on Symmetric Broadcast With Common Messages
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of broadcast with common messages, and focus on the case that the common message rate $R_{\mathcal{A}}$, i.e., the rate of the message intended for all the receivers in the set $\mathcal{A}$, is the same for all the set $\mathcal{A}$ of the same cardinality. Instead of attempting to characterize the capacity region of general broadcast channels, we only consider the structure of the capacity region that any broadcast channel should bear. The concept of latent capacity region is useful in capturing these underlying constraints, and we provide a complete characterization of the latent capacity region for the symmetric broadcast problem. The converse proof of this tight characterization relies on a deterministic broadcast channel model. The achievability proof generalizes the familiar rate transfer argument to include more involved erasure correction coding among messages, thus revealing an inherent connection between broadcast with common message and erasure correction codes.
Robust Distributed Routing in Dynamical Flow Networks - Part II: Strong Resilience, Equilibrium Selection and Cascaded Failures
Venue: arXiv cs.SY 2011
Year: 2011

Strong resilience properties of dynamical flow networks are analyzed for distributed routing policies. The latter are characterized by the property that the way the inflow at a non-destination node gets split among its outgoing links is allowed to depend only on local information about the current particle densities on the outgoing links. The strong resilience of the network is defined as the infimum sum of link-wise flow capacity reductions under which the network cannot maintain the asymptotic total inflow to the destination node to be equal to the inflow at the origin. A class of distributed routing policies that are locally responsive to local information is shown to yield the maximum possible strong resilience under such local information constraints for an acyclic dynamical flow network with a single origin-destination pair. The maximal strong resilience achievable is shown to be equal to the minimum node residual capacity of the network. The latter depends on the limit flow of the unperturbed network and is defined as the minimum, among all the non-destination nodes, of the sum, over all the links outgoing from the node, of the differences between the maximum flow capacity and the limit flow of the unperturbed network. We propose a simple convex optimization problem to solve for equilibrium limit flows of the unperturbed network that minimize average delay subject to strong resilience guarantees, and discuss the use of tolls to induce such an equilibrium limit flow in transportation networks. Finally, we present illustrative simulations to discuss the connection between cascaded failures and the resilience properties of the network.
Generating contour lines using different elevation data file formats
Venue: arXiv cs.OH 2011
Year: 2011

In terrain mapping, there are so many ways to measure and estimate the terrain measurements like contouring, vertical profiling, hill shading, hypsometric tinting, perspective view, etc. Here in this paper we are using the contouring techniques to generate the contours for the different digital elevation data like DEM, HGT, IMG etc. The elevation data is captured in dem, hgt and img formats of the same projected area and the contour is generated using the existing techniques and applications. The exact differences, errors of elevation (contour) intervals, slopes and heights are analyzed and recovered.