Compressed Data Cube for Approximate OLAP Query Processing

Approximate query processing has emerged as an approach to dealing with the huge data volume and complex queries in the environment of data warehouse.In this paper,we present a novel method that provides approximate answers to OLAP queries.Our method is based on building a compressed (approximate) data cube by a clustering technique and using this compressed data cube to provide answers to queries directly,so it improves the performance of the queries.We also provide the algorithm of the OLAP queries and the confidence intervals of query results.An extensive experimental study with the OLAP council benchmark shows the effectiveness and scalability of our cluster-based approach compared to sampling.     

A Geometric Approach for Regularization of the Data Term in Stereo-Vision

Every stereovision application must cope with the correspondence problem. The space of the matching variables, often consisting of spatial coordinates, intensity and disparity, is commonly referred as the data term (space). Since the data is often noisy a-priori, preference is required to result a smooth disparity (or piecewise smooth). To this end, each local method (e.g. window correlation techniques) performs a regularization of the data space. In this paper we propose a geometric framework for anisotropic regularization of the data space seeking to preserve the discontinuities in this space when filtering out the noise. On the other hand, the global methods consider a non-regularized data term with a smoothing constraint imposed directly on the disparity. This paper also proposes a new idea where the data space is regularized in a global method prior to the disparity evaluation. The idea is implemented on the state of the art variational method. Experimental results on the Middlebury real images demonstrate the advantages of the proposed approach.

Compressed Indexes for Approximate String Matching

We revisit the problem of indexing a string S[1..n] to support finding all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m ^k ) time for searching. Motivated by the indexing of DNA, we investigate space efficient indexes that occupy only O(n) space. For k=1, we give an index to support matching in O(m+occ+log nlog log n) time. The previously best solution achieving this time complexity requires an index of O(nlog n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog nlog log n+occ) time, and k-error matching, for any k>2, in O(m ^k−1log nlog log n+occ) time.     

Improved Approximate String Matching Using Compressed Suffix Data Structures

Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper we present a space efficient data structure to solve the 1-mismatch and 1-difference problems. Given a text T of length n over an alphabet A, we can preprocess T and give an -bit space data structure so that, for any query pattern P of length m, we can find all 1-mismatch (or 1-difference) occurrences of P in O(|A|mlog log n+occ) time, where occ is the number of occurrences. This is the fastest known query time given that the space of the data structure is o(nlog ² n) bits. The space of our data structure can be further reduced to O(nlog |A|) with the query time increasing by a factor of log  ^ε n, for 0<ε≤1. Furthermore, our solution can be generalized to solve the k-mismatch (and the k-difference) problem in O(|A| ^k m ^k (k+log log n)+occ) and O(log  ^ε n(|A| ^k m ^k (k+log log n)+occ)) time using an -bit and an O(nlog |A|)-bit indexing data structures, respectively. We assume that the alphabet size |A| is bounded by for the -bit space data structure.     

A Solution of Data Inconsistencies in Data Integration ——- Designed for Pervasive Computing Environment

New challenges including how to share information on heterogeneous devices appear in data-intensive pervasive computing environments. Data integration is a practical approach to these applications. Dealing with inconsistencies is one of the important problems in data integration. In this paper we motivate the problem of data inconsistency solution for data integration in pervasive environments. We define data quality criteria and expense quality criteria for data sources to solve data inconsistency. In our ...     

Hierarchical Sampling from Sketches: Estimating Functions over Data Streams

We present a randomized procedure named Hierarchical Sampling from Sketches (Hss) that can be used for estimating a class of functions over the frequency vector f of update streams of the form . We illustrate this by applying the Hss technique to design nearly space-optimal algorithms for estimating the pth moment of the frequency vector, for real p≥2 and for estimating the entropy of a data stream. Preliminary version of this paper appeared as the following conference publications. “Simpler algorithm for estimating frequency moments of data streams,” Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh and Chandan Saha, Proceedings of the ACM Symposium on Discrete Algorithms, 2006, pp. 708–713 and “Estimating entropy over data streams,” Lakshminath Bhuvanagiri and Sumit Ganguly, Proceedings of the European Symposium on Algorithms, LNCS, vol. 4168, pp. 148–159, Springer, 2006.     

A Level-Set Method for Computing the Eigenvalues of Elliptic Operators Defined on Compact Hypersurfaces

We demonstrate, through separation of variables and estimates from the semi-classical analysis of the Schrödinger operator, that the eigenvalues of an elliptic operator defined on a compact hypersurface in ? ⁿ can be found by solving an elliptic eigenvalue problem in a bounded domain Ω?? ⁿ . The latter problem is solved using standard finite element methods on the Cartesian grid. We also discuss the application of these ideas to solving evolution equations on surfaces, including a new proof of a result due to Greer (J. Sci. Comput. 29(3):321–351, 2006).     

Scalable Data Assignment Algorithm of Parallel I/O for Distributed Heterogeneous Computing

In order to improve the efficiency of storing files to disks and meet the demands of,high availability and scalability on distributed heterogeneous computing environment, two new file assignment strategies are proposed. One is named the available percent decision-making, and the other is the combination of subsection select and awailable percent decision-making. Experimental results show the advantages of new algorithms.     

Occurrence Counting Analysis for the π-calculus

We propose an abstract interpretation-based analysis for automatically proving non-trivial properties of mobile systems of processes. We focus on properties relying on the number of occurrences of processes during computation sequences, such as mutual exclusion and non-exhaustion of resources.We design a non-standard semantics for the π-calculus in order to explicitly trace the origin of channels and to solve efficiently problems set by α-conversion and non-deterministic choices. We abstract this semantics into an approximate one. The use of a relational domain for counting the occurrences of processes allows us to prove quickly and efficiently properties such as mutual exclusion and non-exhaustion of resources. At last, dynamic partitioning allows us to detect some configurations by which no infinite computation sequences can pass.     

Detection of Edges in Spectral Data III—Refinement of the Concentration Method

Edge detection from Fourier spectral data is important in many applications including image processing and the post-processing of solutions to numerical partial differential equations. The concentration method, introduced by Gelb and Tadmor in 1999, locates jump discontinuities in piecewise smooth functions from their Fourier spectral data. However, as is true for all global techniques, the method yields strong oscillations near the jump discontinuities, which makes it difficult to distinguish true discontinuities from artificial oscillations. This paper introduces refinements to the concentration method to reduce the oscillations. These refinements also improve the results in noisy environments. One technique adds filtering to the concentration method. Another uses convolution to determine the strongest correlations between the waveform produced by the concentration method and the one produced by the jump function approximation of an indicator function. A zero crossing based concentration factor, which creates a more localized formulation of the jump function approximation, is also introduced. Finally, the effects of zero-mean white Gaussian noise on the refined concentration method are analyzed. The investigation confirms that by applying the refined techniques, the variance of the concentration method is significantly reduced in the presence of noise. This work was partially supported by NSF grants CNS 0324957, DMS 0510813, DMS 0652833, and NIH grant EB 025533-01 (AG).     

Efficient Computation of κ-Medians over Data Streams Under Memory Constraints

In this paper, we study the problem of efficiently computing k-medians over high-dimensional and high speed data streams. The focus of this paper is on the issue of minimizing CPU time to handle high speed data streams on top of the requirements of high accuracy and small memory. Our work is motivated by the following observation: the existing algorithms have similar approximation behaviors in practice, even though they make noticeably different worst case theoretical guarantees. The underlying reason is that in order to achieve high approximation level with the smallest possible memory, they need rather complex techniques to maintain a sketch, along time dimension, by using some existing off-line clustering algorithms. Those clustering algorithms cannot guarantee the optimal clustering result over data segments in a data stream but accumulate errors over segments, which makes most algorithms behave the same in terms of approximation level, in practice. We propose a new grid-based approach which divides the entire data set into cells (not along time dimension). We can achieve high approximation level based on a novel concept called (1-∈)-dominant. We further extend the method to the data stream context, by leveraging a density-based heuristic and frequent item mining techniques over data streams. We only need to apply an existing clustering once to computing k-medians, on demand, which reduces CPU time significantly. We conducted extensive experimental studies, and show that our approaches outperform other well-known approaches.     

A High Order Compact Scheme for the Pure-Streamfunction Formulation of the Navier-Stokes Equations

In this paper we continue the study, which was initiated in (Ben-Artzi et al. in Math. Model. Numer. Anal. 35(2):313–303, 2001; Fishelov et al. in Lecture Notes in Computer Science, vol. 2667, pp. 809–817, 2003; Ben-Artzi et al. in J. Comput. Phys. 205(2):640–664, 2005 and SIAM J. Numer. Anal. 44(5):1997–2024, 2006) of the numerical resolution of the pure streamfunction formulation of the time-dependent two-dimensional Navier-Stokes equation. Here we focus on enhancing our second-order scheme, introduced in the last three afore-mentioned articles, to fourth order accuracy. We construct fourth order approximations for the Laplacian, the biharmonic and the nonlinear convective operators. The scheme is compact (nine-point stencil) for the Laplacian and the biharmonic operators, which are both treated implicitly in the time-stepping scheme. The approximation of the convective term is compact in the no-leak boundary conditions case and is nearly compact (thirteen points stencil) in the case of general boundary conditions. However, we stress that in any case no unphysical boundary condition was applied to our scheme. Numerical results demonstrate that the fourth order accuracy is actually obtained for several test-cases.     

Polylogarithms and the Asymptotic Formula for the Moments of Lebesgue’s Singular Function

Recall that Lebesgue’s singular function L(t) is defined as the unique solution to the equation L(t) = qL(2t) + pL(2t ? 1), where p, q > 0, q = 1 ? p, p ≠ q. The variables M _n = ∫₀¹t ⁿ dL(t), n = 0,1,… are called the moments of the function The principal result of this work is \({M_n} = {n^{{{\log }_2}p}}{e^{ - \tau (n)}}(1 + O({n^{ - 0.99}}))\), where the function τ(x) is periodic in log₂x with the period 1 and is given as \(\tau (x) = \frac{1}{2}1np + \Gamma '(1)lo{g_2}p + \frac{1}{{1n2}}\frac{\partial }{{\partial z}}L{i_z}( - \frac{q}{p}){|_{z = 1}} + \frac{1}{{1n2}}\sum\nolimits_{k \ne 0} {\Gamma ({z_k})L{i_{{z_k} + 1}}( - \frac{q}{p})} {x^{ - {z_k}}}\), \({z_k} = \frac{{2\pi ik}}{{1n2}}\), k ≠ 0. The proof is based on poissonization and the Mellin transform.     

Frequency response method for terrain classification in autonomous ground vehicles

Many autonomous ground vehicle (AGV) missions, such as those related to agricultural applications, search and rescue, or reconnaissance and surveillance, require the vehicle to operate in difficult outdoor terrains such as sand, mud, or snow. To ensure the safety and performance of AGVs on these terrains, a terrain-dependent driving and control system can be implemented. A key first step in implementing this system is autonomous terrain classification. It has recently been shown that the magnitude of the spatial frequency response of the terrain is an effective terrain signature. Furthermore, since the spatial frequency response is mapped by an AGV’s vibration transfer function to the frequency response of the vibration measurements, the magnitude of the latter frequency responses also serve as a terrain signature. Hence, this paper focuses on terrain classification using vibration measurements. Classification is performed using a probabilistic neural network, which can be implemented online at relatively high computational speeds. The algorithm is applied experimentally to both an ATRV-Jr and an eXperimental Unmanned Vehicle (XUV) at multiple speeds. The experimental results show the efficacy of the proposed approach.

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.     

Discrete Dynamical System Framework for Construction of Connections between Critical Regions in Lattice Height Data

We define a new mathematical model for the topological study of lattice height data. A discrete multivalued dynamical system framework is used to establish discrete analogies of a Morse function, its gradient field, and its stable and unstable manifolds in order to interpret functions numerically given on finite sets of pixels. We present efficient algorithms detecting critical components of a height function f and displaying connections between them by means of a graph, called the Morse connections graph whose nodes represent the critical components of f and edges show the existence of connecting trajectories between nodes. This graph encodes efficiently the topological structure of the data and makes it easy to manipulate for subsequent processing.

Computing differential invariants of hybrid systems as fixedpoints

We introduce a fixedpoint algorithm for verifying safety properties of hybrid systems with differential equations whose right-hand sides are polynomials in the state variables. In order to verify nontrivial systems without solving their differential equations and without numerical errors, we use a continuous generalization of induction, for which our algorithm computes the required differential invariants. As a means for combining local differential invariants into global system invariants in a sound way, our fixedpoint algorithm works with a compositional verification logic for hybrid systems. With this compositional approach we exploit locality in system designs. To improve the verification power, we further introduce a saturation procedure that refines the system dynamics successively with differential invariants until safety becomes provable. By complementing our symbolic verification algorithm with a robust version of numerical falsification, we obtain a fast and sound verification procedure. We verify roundabout maneuvers in air traffic management and collision avoidance in train control and car control.     

A High Order Numerical Method for Computing Physical Observables in the Semiclassical Limit of the One-Dimensional Linear Schrödinger Equation with Discontinuous Potentials

We develop a fourth order numerical method for the computation of multivalued physical observables (density, momentum, etc.) in the semiclassical limit of the one-dimensional linear Schrödinger equation in the case of discontinuous potentials. We adopt the level set framework developed in (Jin et al. in J. Comput. Phys. 210:497–518, 2005) which allows one to compute the multivalued physical observables via solving the classical Liouville equation with bounded initial data and approximating delta function integrals. We achieve high order accuracy for our method by studying two issues. The first is to highly accurately compute the solution and its derivatives of the Liouville equation with bounded initial data and discontinuous potentials. The second is to design high order numerical methods to evaluate one-dimensional delta function integrals with discontinuous kernel functions. Numerical examples are presented to verify that our method achieves the fourth order L ¹-norm accuracy for computing multivalued physical observables of the one-dimensional linear Schrödinger equation with general discontinuous potentials.     

Approaches to Solve the Problem of Determining the Moments of the Beginning and End of an Object’s Movement Using the Data of a Strapdown Inertial Navigation System

Journal of Computer and Systems Sciences International - The problem of autonomous determination using primary and/or secondary data of a strapdown inertial navigation system of two events is...