Vast majority of the data warehouses have less than few terabytes of data and their performance for complex queries on traditional database systems are often not very satisfactory. Data warehouse appliances have been announced by vendors (HP Oracle Exadata Storage server, HP Neoview, Neteeza etc.) to address this burgeoning need. Most of these involve creating a large parallel database systems using scale-out of commodity machines and/or pushing filters into disk retrieval system to reduce the data coming to memory; these done along the lines pioneered by research projects such as Gamma, Bubba and other prior database machine research. These approaches deliver performance by deploying many CPUs, large amount of memory, large number of disk-heads & disk space and in effect extracting performance by under utilizing the resources -- albeit very inexpensive commodity resources.

We consider applications using depth-based image-based rendering (IBR), where the synthesis of arbitrary views occur at a remote location, necessitating the compression and transmission of depth maps. Traditional image compression has been designed to provide maximum perceived visual quality, and a direct application is sub-optimal for depth-map compression, since depth-maps are not directly viewed. In other words, the sensitivity of the rendering error depends on the image content as well as on the depth map, we propose two improvements to take this into account. Firstly, we consider region-of-interest (ROI) coding, where we identify those regions of the image where accurate depth is most crucial. Secondly, we reshape the dynamic range of the depth map. Our experiments show a significant improvement in coding gain (1.1 dB) and rendering quality when we integrated these two improvements into a standard JPEG-2000 coder.

We consider the problems of motion-compensated frame interpolation (MCFI) and bidirectional prediction in a video coding environment. These applications generally require good motion estimates at the decoder. We use a multiscale optical-flow-based motion estimator that provides smooth, natural motion fields under bit-rate constraints. These motion estimates scale well with change in temporal resolution and provide considerable flexibility in the design and operation of coders and decoders. In the MCFI application, this estimator provides excellent interpolated frames that are superior to those of conventional motion estimators, both visually and in terms of peak signal-to-noise ratio (PSNR). We also consider the effect of occlusions in the bidirectional prediction application and introduce a dense label field that complements our motion estimator. This label field enables us to adaptively weight the forward and backward predictions and gives us substantial visual and PSNR improvements in the covered/uncovered regions of the sequence.

Considers the problem of querying the data in applications such as spreadsheets and word processors. This problem has several motivations from the perspective of data integration, interoperability and OLAP. We provide an architecture for realizing interoperability among such diverse applications and address the challenges that arise specifically in the context of querying data stored in spreadsheet applications. A fundamental challenge is the lack of a well-defined schema. We propose a framework in which the user can specify the layout of data in a spreadsheet, based on his perception of the important concepts underlying that data. Layout specifications can be viewed as the "physical schema" of a spreadsheet. We motivate the concept of an abstract database machine (ADM) that uses the layout specifications to provide a relational view of the data in spreadsheet applications and, similar to a DBMS, supports efficient querying of the spreadsheet data. We develop a methodology for building ADMs for spreadsheets and describe our implementation of an ADM for Microsoft Excel applications, based on the above methodology. Our implementation platform is IBM PCs running Windows NT, Microsoft Office and OLE 2.0. We demonstrate the generality and practicality of our approach by developing a formal characterization of the class of spreadsheets that can be handled in our framework. Our results show that the approach is capable of handling a broad class of naturally occurring spreadsheet applications. This work is part of an office tool integration project.

article Free Access Share on Picture programming project Authors: Nita Goyal Hewlett-Packard Laboratories, Palo Alto, CA Hewlett-Packard Laboratories, Palo Alto, CAView Profile , Charles Hoch Hewlett-Packard Laboratories, Palo Alto, CA Hewlett-Packard Laboratories, Palo Alto, CAView Profile , Ravi Krishnamurthy Hewlett-Packard Laboratories, Palo Alto, CA Hewlett-Packard Laboratories, Palo Alto, CAView Profile , Brian Meckler Hewlett-Packard Laboratories, Palo Alto, CA Hewlett-Packard Laboratories, Palo Alto, CAView Profile , Michael Suchow Hewlett-Packard Laboratories, Palo Alto, CA Hewlett-Packard Laboratories, Palo Alto, CAView Profile , Moshe Zloof Hewlett-Packard Laboratories, Palo Alto, CA Hewlett-Packard Laboratories, Palo Alto, CAView Profile Authors Info & Claims ACM SIGMOD RecordVolume 26Issue 2June 1997 pp 514–516https://doi.org/10.1145/253262.253377Online:01 June 1997Publication History 1citation267DownloadsMetricsTotal Citations1Total Downloads267Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a systematic approach to forward-motion-compensated predictive video coding. The first step is the definition of a flexible model that compactly represents motion fields. The inhomogeneity and spatial coherence properties of motion fields are captured using linear multiscale models. One possible design is based on linear finite elements and yields a multiscale extension of the triangle motion compensation (TMC) method. The second step is the choice of a computational technique that identifies the coefficients of the linear model. We study a modified optical flow technique and minimize a cost function closely related to Horn and Schunck's (1981) criterion. The cost function balances accuracy and complexity of the motion compensated predictor and is viewed as a measure of goodness of the motion field. It determines not only the coefficients of the model, but also the quantization method. We formulate the estimation and quantization problems jointly as a discrete optimization problem and solve it using a fast multiscale relaxation algorithm. A hierarchical extension of the algorithm allows proper handling of large displacements. Simulations on a variety of video sequences have produced improvements over TMC and over the half-pel-accuracy, full-search block matching algorithm, in excess of 0.5 dB in average. The results are visually superior as well. In particular, the reconstructed video is entirely free of blocking artifacts.

Motion estimation is an important component of video coding systems because it enables us to exploit the temporal redundancy in the sequence. The popular block-matching algorithms (BMAs) produce unnatural, piecewise constant motion fields that do not correspond to "true" motion. In contrast, our focus here is on high-quality motion estimates that produce a video representation that is less dependent on the specific frame-rate or resolution. To this end, we present an iterated registration algorithm that extends previous work on multiscale motion models and gradient-based estimation for coding applications. We obtain improved motion estimates and higher overall coding performance. Promising applications are found in temporally-scalable video coding with motion-compensated frame interpolation at the decoder. We obtain excellent interpolation performance and video quality; in contrast, BMA leads to annoying artifacts near moving image edges.

Programming nontrivial GUI applications is currently an arduous task. Just as the use of a declarative language simplified the programming of database applications, we ask whether we can do the same for GUI programming? Can we then import a large body of knowledge from database research? We answer these questions by describing our experience in building nontrivial GUI applications initially using C++ programming and subsequently using Logic++, a higher order Horn clause logic language on complex objects with object-oriented features. We abstract a GUI application as a set of event handlers. Each event handler can be conceptualized as a transition from the old screen/program state to a new screen/program state. We use a data centric view of the screen/program state (i.e., every entity on the screen corresponds to proxy datum in the program) and express each event handler as a query dependent update, albeit a complicated one. To express such complicated updates we use Logic++. The proxy data are expressed as derived views that are materialized on the screen. Therefore, the system must be active in maintaining these materialized views. Consequently, each event handler is conceptually an update followed by a fixpoint computation of the proxy data. Based on our experience in building the GUI system, we observe that many database techniques such as view maintenance, active DB, concurrency control, recovery, optimization as well as language concepts such as higher order logic are useful in the context of GUI programming.

We consider the adaptive restoration of inhomogeneous textured images, where the individual regions are modeled using a Wold-like decomposition. A generalized Wiener filter is developed to accommodate mixed spectra, and unsupervised restoration is achieved by using the expectation-maximization (EM) algorithm to estimate the degradation parameters. This algorithm yields superior results when compared with supervised Wiener filtering using autoregressive (AR) image models.

While much work has addressed the problem of maintaining materialized views, the important question of optimizing queries in the presence of materialised views has not been resolved. In this paper, we analyze the optimization question and provide a comprehensive and efficient solution. Our solution has the desirable property that it is a simple generalization of the traditional query optimization algorithm.>

Rendering is defined to be a customized presentation of data in such a way that allows users to subsequently interact with the presented data. Traditionally such a user interface would be a custom application written using conventional programming languages; in contrast we propose an application-independent, declarative (i.e., what-you-want) language that we call Rendering By Example, RBE, with the capability to specify a wide variety of renderings. RBE is a domain calculus language over user interface widgets. Most previous domain calculus database languages (e.g., QBE, LDL, Datalog) mainly addressed the data processing problem. The main contribution in developing RBE is to model semantics of user interactions in a declarative way. This declarative specification not only allows quick and ad-hoc specification of renderings (i.e., user interfaces) but also provides a framework to understand renderings as an abstract concept, independent of the application. Further, such a linguistic abstraction provides the basis for user-interface research. RBE is part of the ICBE language that is being prototyped in the Picture Programming project at HP Labs.>

Motion estimation is an important part of most video coding schemes because it enables us to exploit the high degree of temporal redundancy present. Though block matching algorithms (BMA) yield coarse and piecewise-constant fields, they are very popular due to their simplicity and low bit overhead. In this paper, we propose to use a more advanced gradient-based technique to overcome the disadvantages of BMA. A dense motion field is estimated and compressed using a hierarchical finite element (HFE) representation, leading to an efficient, highly parallel, iterative, multiresolution optimization algorithm. The scheme also uses multiresolution measurements and a coarse-to-fine strategy to estimate large displacements. At comparable bit rates, the motion fields are much smoother and more natural than those produced by BMA. Coding gains of about 0.6 dB were obtained on Claire. More importantly, substantial visual improvements were obtained, mainly due to improved performance near the edges.

We consider the adaptive restoration of inhomogeneous textured images degraded by linear blur and additive white Gaussian noise. The method consists of segmenting the image into individual homogeneous textures and restoring each texture separately. The individual textures are assumed to be realizations of 2-D Wold-decomposition based regular, homogeneous random fields which may possess deterministic components. The conventional Wiener filter assumes that the spectral distribution of the signal is absolutely continuous and, therefore, cannot be directly used to restore the individual textures. A generalized Wiener filter accommodates the unified texture model and is shown to yield minimum mean-squared error estimates for fields with discontinuous spectral distributions. Texture discrimination is performed by obtaining maximum a posteriori estimates for the label field using simulated annealing. The performance of our segmentation algorithm is investigated in the presence of noise.

The decreasing cost of computing makes it economically viable to reduce the response time of decision support queries by using parallel execution to exploit inexpen-sive resources. This goal poses the following query op-timization problem: Mzntmzze response ttme subject to constraints on throughput, which we motivate as the dual of the traditional DBMS problem, We address this novel problem in the context of Select-Project-Join queries by extending the execution space, cost model and search al-gorithm that are widely used in commercial DBItlSs. We incorporate the sources and deterrents of parallelism in the traditional execution space. We show that a cost model can predict response time while accounting for the new aspects due to parallelism, We observe that the response time optimization metric violates a fundamen-tal assumption in the dynamic programming algorithm that is the linchpin in the optimizers of most commer-cial DBMSS. We extend dynamic programming and show how optimization metrics which correctly predict response time may be designed. 1

A novel experimental procedure, based on a standard statistical estimation procedure, is presented to estimate the performance of transitive closure algorithms. This experimental procedure has been exemplified in three contexts: (1) comparison of a suite of algorithms: (2) analysis of one particular algorithm; and (3) analysis of the transitive closure problem itself. It is shown that the number of duplicate edges generated (by most algorithms) can be more than ten times the size of the transitive closure, even for small graphs. The majority of these duplicates are due to the existence of strongly connected components in the graph. This experimental approach can be generalized to estimate various performance metrics for a large class of database queries. It is both simple and general and provides the necessary ingredients for a guess-and-verify paradigm of testing hypotheses.>

The logic data language (LDL) system provides a declarative logic-based language and integrates relational database and logic programming technologies so as to support advanced data and knowledge-based applications. A comprehensive overview of the system and a description of LDL language and the compilation techniques employed to translate LDL queries into target query execution plans on the stored data are presented. The architecture and runtime environment of the system and the optimization techniques employed in order to improve the performance and assure the safety of the compiled queries are given. The experience gained so far with the system and application areas where the LDL approach appears to be particularly effective are discussed.>

We present techniques for optimizing queries in memory-resident database systems. Optimization techniques in memory-resident database systems differ significantly from those in conventional disk-resident database systems. In this paper we address the following aspects of query optimization in such systems and present specific solutions for them: (1) a new approach to developing a CPU-intensive cost model; (2) new optimization strategies for main-memory query processing; (3) new insight into join algorithms and access structures that take advantage of memory residency of data; and (4) the effect of the operating system's scheduling algorithm on the memory-residency assumption. We present an interesting result that a major cost of processing queries in memory-resident database systems is incurred by evaluation of predicates. We discuss optimization techniques using the Office-by-Example (OBE) that has been under development at IBM Research. We also present the results of performance measurements, which prove to be excellent in the current state of the art. Despite recent work on memory-resident database systems, query optimization aspects in these systems have not been well studied. We believe this paper opens the issues of query optimization in memory-resident database systems and presents practical solutions to them.

The need for control in logic programs is now being recognized. This is particularly evident when one focuses on allowing updates in logic programs. In this paper we propose a language DatalogA which is an extension of Datalog with updates to base relations. We define some procedural constructs to allow update programs to be written in an easy manner. The (W,p) scheme of Dynamic Logic fits nicely into the semantics of DatalogA programs in which W is taken to be the set of all possible states of the program and p is the accessibility relation between states. We give declarative semantics and equivalent constructed model semantics for DatalogA programs. We show that in the absence of updates our semantics reduce to the classical semantics of Datalog. Finally, we show some examples of non-stratified programs expressed in DatalogA.

The problem of pushing projections in recursive rules has received little attention. The objective of this paper is to motivate this problem and present some (partial) solutions. We consider programs with function-free rules, also known as Datalog programs. After formally defining existential subqueries, we present a syntactic criterion for detecting them and then consider optimization in three areas 1) We identify the existential subqueries and make them explicit by rewriting the rules. This, in effect, automatically captures some aspects of Prolog's cut operator that are appropriate to the bottom-up model of computation 2) We eliminate argument positions in recursive rules by “pushing projections” 3) We observe that “pushing projections” in rules also has the effect of making some rules (even recursive rules) redundant and try to (identify and) discard them

This paper presents a methodology for testing a general logic program containing function symbols and built-in predicates for safety and effective computability. Safety is the property that the set of answers for a given query is finite. A related issues is whether the evaluation strategy can effectively compute all answers and terminate. We consider these problems under the assumption that queries are evaluated using a bottom-up fixpoint computation. We also approximate the use of function symbols by considering Datalog programs with infinite base relations over which finiteness constraints and monotonicity constraints are considered. One of the main results of this paper is a recursive algorithm, check_clique, to test the safety and effective computability of predicates in arbitrarily complex cliques. This algorithm takes certain procedures as parameters, and its applicability can be strengthened by making these procedures more sophisticated. We specify the properties required of these procedures precisely, and present a formal proof of correctness for algorithm check_clique. This work provides a framework for testing safety and effective computability of recursive programs, and is based on a clique by clique analysis. The results reported here form the basis of the safety testing for the LDL language, being implemented at MCC.

Office-by-Example (OBE) is an integrated office information system that has been under development at IBM Research. OBE, an extension of Query-by-Example, supports various office features such as database tables, word processing, electronic mail, graphics, images, and so forth. These seemingly heterogeneous features are integrated through a language feature called example elements . Applications involving example elements are processed by the database manager, an integrated part of the OBE system. In this paper we describe the facilities and architecture of the OBE system and discuss the techniques for integrating heterogeneous objects.

We present a novel preprocessing technique for distributed query optimization which achieves nearly all of the benefits that full database reduction by semijoin achieves, but for a small fraction of the cost. Most previous researchers have approached the problem of distributed query optimization with the idea of achieving maximum database reduction at any cost. We take an engineering approach — that, past a point of diminishing returns, database reduction is not cost-effective. We introduce a technique called "partial reduction", which uses a sequence of "bucket semijoins" to eliminate nearly all of the irrelevant tuples eliminated by a fully reducing sequence of semijoins. We provide a performance analysis for a simple binary semijoin compared to a bucket semijoin, and show that a bucket semijoin can achieve, say, 90% of the reduction that a semijoin can, but for, say, 10% of the cost. Although we used some simplifying assumptions in our analysis, we argue that relaxing these assumptions does not diminish our results in any way. We discuss the sensitivity of our technique to its parameters, and we show that our results improve for multiple join and inequality join queries.

Distributed algorithms tend to be difficult to understand and even more difficult to prove correct. Using distributed dead-lock detection as a running example this paper presents a framework for stating, understanding, and proving the correctness of distributed algorithms for decision problems. The framework consists of a series of complexity levels. To simplify the initial levels, we treat the data structure of the algorithm as a database, and use the database notions of views and transaction atomicity. For each complexity level, we state theorems that need to be proved for each algorithm. The framework is illustrated using several existing deadlock detection algorithms. Finally, it is shown that the framework suggests new algorithms using the best features of several existing algorithms.

In this paper we present a parallel program schema model of a transaction system and generalize the concept of serializability from the sequential two-step model to a parallel multi-step model. We define two classes of serializable executions, and for each class we discuss two problems: recognition and scheduling. It is shown that the results for the recognition and online scheduling problems for the sequential model generalize to the parallel model. But it is argued that online scheduling is not suitable for a parallel execution environment. Therefore, batch schedulers are defined and a minimal set of precedence constraints is derived. Finally, it is shown that any optimal batch scheduler that uses syntactic information alone cannot be efficient.