In summary, the viewpoint of random graphs indeed provides us an opportunity of improving some existing machine learning algorithms. / In this thesis, we establish three machine learning models on random graphs: Heat Diffusion Models on Random Graphs, Predictive Random Graph Ranking, and Random Graph Dependency. The heat diffusion models on random graphs lead to Graph-based Heat Diffusion Classifiers (G-HDC) and a novel ranking algorithm on Web pages called DiffusionRank. For G-HDC, a random graph is constructed on data points. The generated random graph can be considered as the representation of the underlying geometry, and the heat diffusion model on them can be considered as the approximation to the way that heat flows on a geometric structure. Experiments show that G-HDC can achieve better performance in accuracy in some benchmark datasets. For DiffusionRank, theoretically we show that it is a generalization of PageRank when the heat diffusion coefficient tends to infinity, and empirically we show that it achieves the ability of anti-manipulation. / Predictive Random Graph Ranking (PRGR) incorporates DiffusionRank. PRGR aims to solve the problem that the incomplete information about the Web structure causes inaccurate results of various ranking algorithms. The Web structure is predicted as a random graph, on which ranking algorithms are expected to be improved in accuracy. Experimental results show that the PRGR framework can improve the accuracy of the ranking algorithms such as PageRank and Common Neighbor. / Three special forms of the novel Random Graph Dependency measure on two random graphs are investigated. The first special form can improve the speed of the C4.5 algorithm, and can achieve better results on attribute selection than gamma used in Rough Set Theory. The second special form of the general random graph dependency measure generalizes the conditional entropy because it becomes equivalent to the conditional entropy when the random graphs take their special form-equivalence relations. Experiments demonstrates that the second form is an informative measure, showing its success in decision trees on small sample size problems. The third special form can help to search two parameters in G-HDC faster than the cross-validation method. / Yang, haixuan. / "August 2007." / Advisers: Irwin King; Michael R. Lyu. / Source: Dissertation Abstracts International, Volume: 69-02, Section: B, page: 1125. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (p. 184-197). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract in English and Chinese. / School code: 1307.

This research is describing a novel method to generate realism improved synthetic images while preserving annotation information and the eye gaze direction. Furthermore, it describes how the perceptual loss can be utilized while introducing basic features and techniques from adversarial networks for better results.

Chow Kai Tik = 支援矢量回歸法之影像表示式及其影像處理與分析 / 周啓迪. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 380-383). / Text in English; abstracts in English and Chinese. / Chow Kai Tik = Zhi yuan shi liang hui gui fa zhi ying xiang biao shi shi ji qi ying xiang chu li yu fen xi / Zhou Qidi. / Abstract in English / Abstract in Chinese / Acknowledgement / Content / List of figures / Chapter Chapter 1 --- Introduction --- p.1-11 / Chapter 1.1 --- Introduction --- p.2 / Chapter 1.2 --- Road Map --- p.9 / Chapter Chapter 2 --- Review of Support Vector Machine --- p.12-124 / Chapter 2.1 --- Structural Risk Minimization (SRM) --- p.13 / Chapter 2.1.1 --- Introduction / Chapter 2.1.2 --- Structural Risk Minimization / Chapter 2.2 --- Review of Support Vector Machine --- p.21 / Chapter 2.2.1 --- Review of Support Vector Classification / Chapter 2.2.2 --- Review of Support Vector Regression / Chapter 2.2.3 --- Review of Support Vector Clustering / Chapter 2.2.4 --- Summary of Support Vector Machines / Chapter 2.3 --- Implementation of Support Vector Machines --- p.60 / Chapter 2.3.1 --- Kernel Adatron for Support Vector Classification (KA-SVC) / Chapter 2.3.2 --- Kernel Adatron for Support Vector Regression (KA-SVR) / Chapter 2.3.3 --- Sequential Minimal Optimization for Support Vector Classification (SMO-SVC) / Chapter 2.3.4 --- Sequential Minimal Optimization for Support Vector Regression (SMO-SVR) / Chapter 2.3.5 --- Lagrangian Support Vector Classification (LSVC) / Chapter 2.3.6 --- Lagrangian Support Vector Regression (LSVR) / Chapter 2.4 --- Applications of Support Vector Machines --- p.117 / Chapter 2.4.1 --- Applications of Support Vector Classification / Chapter 2.4.2 --- Applications of Support Vector Regression / Chapter Chapter 3 --- Image Representation by Support Vector Regression --- p.125-183 / Chapter 3.1 --- Introduction of SVR Representation --- p.116 / Chapter 3.1.1 --- Image Representation by SVR / Chapter 3.1.2 --- Implicit Smoothing of SVR representation / Chapter 3.1.3 --- "Different Insensitivity, C value, Kernel and Kernel Parameters" / Chapter 3.2 --- Variation on Encoding Method [Training Process] --- p.154 / Chapter 3.2.1 --- Training SVR with Missing Data / Chapter 3.2.2 --- Training SVR with Image Blocks / Chapter 3.2.3 --- Training SVR with Other Variations / Chapter 3.3 --- Variation on Decoding Method [Testing pr Reconstruction Process] --- p.171 / Chapter 3.3.1 --- Reconstruction with Different Portion of Support Vectors / Chapter 3.3.2 --- Reconstruction with Different Support Vector Locations and Lagrange Multiplier Values / Chapter 3.3.3 --- Reconstruction with Different Kernels / Chapter 3.4 --- Feature Extraction --- p.177 / Chapter 3.4.1 --- Features on Simple Shape / Chapter 3.4.2 --- Invariant of Support Vector Features / Chapter Chapter 4 --- Mathematical and Physical Properties of SYR Representation --- p.184-243 / Chapter 4.1 --- Introduction of RBF Kernel --- p.185 / Chapter 4.2 --- Mathematical Properties: Integral Properties --- p.187 / Chapter 4.2.1 --- Integration of an SVR Image / Chapter 4.2.2 --- Fourier Transform of SVR Image (Hankel Transform of Kernel) / Chapter 4.2.3 --- Cross Correlation between SVR Images / Chapter 4.2.4 --- Convolution of SVR Images / Chapter 4.3 --- Mathematical Properties: Differential Properties --- p.219 / Chapter 4.3.1 --- Review of Differential Geometry / Chapter 4.3.2 --- Gradient of SVR Image / Chapter 4.3.3 --- Laplacian of SVR Image / Chapter 4.4 --- Physical Properties --- p.228 / Chapter 4.4.1 --- 7Transformation between Reconstructed Image and Lagrange Multipliers / Chapter 4.4.2 --- Relation between Original Image and SVR Approximation / Chapter 4.5 --- Appendix --- p.234 / Chapter 4.5.1 --- Hankel Transform for Common Functions / Chapter 4.5.2 --- Hankel Transform for RBF / Chapter 4.5.3 --- Integration of Gaussian / Chapter 4.5.4 --- Chain Rules for Differential Geometry / Chapter 4.5.5 --- Derivation of Gradient of RBF / Chapter 4.5.6 --- Derivation of Laplacian of RBF / Chapter Chapter 5 --- Image Processing in SVR Representation --- p.244-293 / Chapter 5.1 --- Introduction --- p.245 / Chapter 5.2 --- Geometric Transformation --- p.241 / Chapter 5.2.1 --- "Brightness, Contrast and Image Addition" / Chapter 5.2.2 --- Interpolation or Resampling / Chapter 5.2.3 --- Translation and Rotation / Chapter 5.2.4 --- Affine Transformation / Chapter 5.2.5 --- Transformation with Given Optical Flow / Chapter 5.2.6 --- A Brief Summary / Chapter 5.3 --- SVR Image Filtering --- p.261 / Chapter 5.3.1 --- Discrete Filtering in SVR Representation / Chapter 5.3.2 --- Continuous Filtering in SVR Representation / Chapter Chapter 6 --- Image Analysis in SVR Representation --- p.294-370 / Chapter 6.1 --- Contour Extraction --- p.295 / Chapter 6.1.1 --- Contour Tracing by Equi-potential Line [using Gradient] / Chapter 6.1.2 --- Contour Smoothing and Contour Feature Extraction / Chapter 6.2 --- Registration --- p.304 / Chapter 6.2.1 --- Registration using Cross Correlation / Chapter 6.2.2 --- Registration using Phase Correlation [Phase Shift in Fourier Transform] / Chapter 6.2.3 --- Analysis of the Two Methods for Registrationin SVR Domain / Chapter 6.3 --- Segmentation --- p.347 / Chapter 6.3.1 --- Segmentation by Contour Tracing / Chapter 6.3.2 --- Segmentation by Thresholding on Smoothed or Sharpened SVR Image / Chapter 6.3.3 --- Segmentation by Thresholding on SVR Approximation / Chapter 6.4 --- Appendix --- p.368 / Chapter Chapter 7 --- Conclusion --- p.371-379 / Chapter 7.1 --- Conclusion and contribution --- p.372 / Chapter 7.2 --- Future work --- p.378 / Reference --- p.380-383

Tse, Ming Fun. / Thesis submitted in: December 2001. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2002. / Includes bibliographical references (leaves 142-146). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problem Definition --- p.2 / Chapter 1.2 --- Contributions --- p.3 / Chapter 1.3 --- Thesis Outline --- p.4 / Chapter 2 --- Literature Review --- p.6 / Chapter 2.1 --- Representing Inexact Knowledge --- p.7 / Chapter 2.1.1 --- Nature of Inexact Knowledge --- p.7 / Chapter 2.1.2 --- Probability Based Reasoning --- p.8 / Chapter 2.1.3 --- Certainty Factor Algebra --- p.11 / Chapter 2.1.4 --- Fuzzy Logic --- p.13 / Chapter 2.2 --- Machine Learning Paradigms --- p.13 / Chapter 2.2.1 --- Classifications --- p.14 / Chapter 2.2.2 --- Neural Networks and Gradient Descent --- p.15 / Chapter 2.3 --- Related Learning Systems --- p.21 / Chapter 2.3.1 --- Relational Concept Learning --- p.21 / Chapter 2.3.2 --- Learning of Fuzzy Concepts --- p.24 / Chapter 2.4 --- Fuzzy Logic --- p.26 / Chapter 2.4.1 --- Fuzzy Set --- p.27 / Chapter 2.4.2 --- Basic Notations in Fuzzy Logic --- p.29 / Chapter 2.4.3 --- Basic Operations on Fuzzy Sets --- p.29 / Chapter 2.4.4 --- "Fuzzy Relations, Projection and Cylindrical Extension" --- p.31 / Chapter 2.4.5 --- Fuzzy First Order Logic and Fuzzy Prolog --- p.34 / Chapter 3 --- Knowledge Representation and Learning Algorithm --- p.43 / Chapter 3.1 --- Knowledge Representation --- p.44 / Chapter 3.1.1 --- Fuzzy First-order Logic ´ؤ A Powerful Language --- p.44 / Chapter 3.1.2 --- Literal Forms --- p.48 / Chapter 3.1.3 --- Continuous Variables --- p.50 / Chapter 3.2 --- System Architecture --- p.61 / Chapter 3.2.1 --- Data Reading --- p.61 / Chapter 3.2.2 --- Preprocessing and Postprocessing --- p.67 / Chapter 4 --- Global Evaluation of Literals --- p.71 / Chapter 4.1 --- Existing Closeness Measures between Fuzzy Sets --- p.72 / Chapter 4.2 --- The Error Function and the Normalized Error Functions --- p.75 / Chapter 4.2.1 --- The Error Function --- p.75 / Chapter 4.2.2 --- The Normalized Error Functions --- p.76 / Chapter 4.3 --- The Nodal Characteristics and the Error Peaks --- p.79 / Chapter 4.3.1 --- The Nodal Characteristics --- p.79 / Chapter 4.3.2 --- The Zero Error Line and the Error Peaks --- p.80 / Chapter 4.4 --- Quantifying the Nodal Characteristics --- p.85 / Chapter 4.4.1 --- Information Theory --- p.86 / Chapter 4.4.2 --- Applying the Information Theory --- p.88 / Chapter 4.4.3 --- Upper and Lower Bounds of CE --- p.89 / Chapter 4.4.4 --- The Whole Heuristics of FF99 --- p.93 / Chapter 4.5 --- An Example --- p.94 / Chapter 5 --- Partial Evaluation of Literals --- p.99 / Chapter 5.1 --- Importance of Covering in Inductive Learning --- p.100 / Chapter 5.1.1 --- The Divide-and-conquer Method --- p.100 / Chapter 5.1.2 --- The Covering Method --- p.101 / Chapter 5.1.3 --- Effective Pruning in Both Methods --- p.102 / Chapter 5.2 --- Fuzzification of FOIL --- p.104 / Chapter 5.2.1 --- Analysis of FOIL --- p.104 / Chapter 5.2.2 --- Requirements on System Fuzzification --- p.107 / Chapter 5.2.3 --- Possible Ways in Fuzzifing FOIL --- p.109 / Chapter 5.3 --- The α Covering Method --- p.111 / Chapter 5.3.1 --- Construction of Partitions by α-cut --- p.112 / Chapter 5.3.2 --- Adaptive-α Covering --- p.112 / Chapter 5.4 --- The Probabistic Covering Method --- p.114 / Chapter 6 --- Results and Discussions --- p.119 / Chapter 6.1 --- Experimental Results --- p.120 / Chapter 6.1.1 --- Iris Plant Database --- p.120 / Chapter 6.1.2 --- Kinship Relational Domain --- p.122 / Chapter 6.1.3 --- The Fuzzy Relation Domain --- p.129 / Chapter 6.1.4 --- Age Group Domain --- p.134 / Chapter 6.1.5 --- The NBA Domain --- p.135 / Chapter 6.2 --- Future Development Directions --- p.137 / Chapter 6.2.1 --- Speed Improvement --- p.137 / Chapter 6.2.2 --- Accuracy Improvement --- p.138 / Chapter 6.2.3 --- Others --- p.138 / Chapter 7 --- Conclusion --- p.140 / Bibliography --- p.142 / Chapter A --- C4.5 to FOIL File Format Conversion --- p.147 / Chapter B --- FF99 example --- p.150

This thesis investigates the problem of visual learning using a robotic platform. Given a set of objects the robots task is to autonomously manipulate, observe, and learn. This allows the robot to recognise objects in a novel scene and pose, or separate them into distinct visual categories. The main focus of the work is in autonomously acquiring object models using robotic manipulation. Autonomous learning is important for robotic systems. In the context of vision, it allows a robot to adapt to new and uncertain environments, updating its internal model of the world. It also reduces the amount of human supervision needed for building visual models. This leads to machines which can operate in environments with rich and complicated visual information, such as the home or industrial workspace; also, in environments which are potentially hazardous for humans. The hypothesis claims that inducing robot motion on objects aids the learning process. It is shown that extra information from the robot sensors provides enough information to localise an object and distinguish it from the background. Also, that decisive planning allows the object to be separated and observed from a variety of dierent poses, giving a good foundation to build a robust classication model. Contributions include a new segmentation algorithm, a new classication model for object learning, and a method for allowing a robot to supervise its own learning in cluttered and dynamic environments.

The use of forward-looking information from option prices attracted a lot of attention after the 2008 financial crisis, which highlighting the difficulty of using historical data to predict extreme events. Although a considerable number of papers investigate extraction of forward-information from cross-sectional option prices, Figlewski (2008) argues that it is still an open question and none of the techniques is clearly superior. This thesis focuses on getting information from option prices and investigates two broad topics: applying machine learning in extracting state price density and recovering natural probability from option prices. The estimation of state price density (often described as risk-neutral density in the option pricing litera- ture) is of considerable importance since it contains valuable information about investors' expectations and risk preferences. However, this is a non-trivial task due to data limitation and complex arbitrage-free constraints. In this thesis, I develop a more efficient linear programming support vector machine (L1-SVM) estimator for state price density which incorporates no-arbitrage restrictions and bid-ask spread. This method does not depend on a particular approximation function and framework and is, therefore, universally applicable. In a parallel empirical study, I apply the method to options on the S&P 500, showing it to be comparatively accurate and smooth. In addition, since the existing literature has no consensus about what information is recovered from The Recovery Theorem, I empirically examine this recovery problem in a continuous diffusion setting. Using the market data of S&P 500 index option and synthetic data generated by Ornstein-Uhlenbeck (OU) process, I show that the recovered probability is not the real-world probability. Finally, to further explain why The Recovery Theorem fails and show the existence of associated martingale component, I demonstrate a example bivariate recovery.

Space-based communications systems to be employed by future artificial satellites, or spacecraft during exploration missions, can potentially benefit from software-defined radio adaptation capabilities. Multiple communication requirements could potentially compete for radio resources, whose availability of which may vary during the spacecraft's operational life span. Electronic components are prone to failure, and new instructions will eventually be received through software updates. Consequently, these changes may require a whole new set of near-optimal combination of parameters to be derived on-the-fly without instantaneous human interaction or even without a human in-the-loop. Thus, achieving a sufficiently set of radio parameters can be challenging, especially when the communication channels change dynamically due to orbital dynamics as well as atmospheric and space weather-related impairments. This dissertation presents an analysis and discussion regarding novel algorithms proposed in order to enable a cognition control layer for adaptive communication systems operating in space using an architecture that merges machine learning techniques employing wireless communication principles. The proposed cognitive engine proof-of-concept reasons over time through an efficient accumulated learning process. An implementation of the conceptual design is expected to be delivered to the SDR system located on the International Space Station as part of an experimental program. To support the proposed cognitive engine algorithm development, more realistic satellite-based communications channels are proposed along with rain attenuation synthesizers for LEO orbits, channel state detection algorithms, and multipath coefficients function of the reflector's electrical characteristics. The achieved performance of the proposed solutions are compared with the state-of-the-art, and novel performance benchmarks are provided for future research to reference.

"Statistical inference plays an increasingly important role in science, finance and industry. Despite the extensive research and wide application of statistical inference, most of the efforts focus on uniform models. This thesis considers the statistical inference in models with abrupt changes instead. The task is to estimate change-points where the underlying models change. We first study low dimensional linear regression problems for which the underlying model undergoes multiple changes. Our goal is to estimate the number and locations of change-points that segment available data into different regions, and further produce sparse and interpretable models for each region. To address challenges of the existing approaches and to produce interpretable models, we propose a sparse group Lasso (SGL) based approach for linear regression problems with change-points. Then we extend our method to high dimensional nonhomogeneous linear regression models. Under certain assumptions and using a properly chosen regularization parameter, we show several desirable properties of the method. We further extend our studies to generalized linear models (GLM) and prove similar results. In practice, change-points inference usually involves high dimensional data, hence it is prone to tackle for distributed learning with feature partitioning data, which implies each machine in the cluster stores a part of the features. One bottleneck for distributed learning is communication. For this implementation concern, we design communication efficient algorithm for feature partitioning data sets to speed up not only change-points inference but also other classes of machine learning problem including Lasso, support vector machine (SVM) and logistic regression."

"Autonomous vehicle is an engineering technology that can improve transportation safety, alleviate traffic congestion and reduce carbon emissions. Research on autonomous vehicles can be categorized by functionality, for example, object detection or recognition, path planning, navigation, lane keeping, speed control and driver status monitoring. The research topics can also be categorized by the equipment or techniques used, for example, image processing, computer vision, machine learning, and localization. This dissertation primarily reports on computer vision and machine learning algorithms and their implementations for autonomous vehicles. The vision-based system can effectively detect and accurately recognize multiple objects on the road, such as traffic signs, traffic lights, and pedestrians. In addition, an autonomous lane keeping system has been proposed using end-to-end learning. In this dissertation, a road simulator is built using data collection and augmentation, which can be used for training and evaluating autonomous driving algorithms. The Graphic Processing Unit (GPU) based traffic sign detection and recognition system can detect and recognize 48 traffic signs. The implementation has three stages: pre-processing, feature extraction, and classification. A highly optimized and parallelized version of Histogram of Oriented Gradients (HOG) and Support Vector Machine (SVM) is used. The system can process 27.9 frames per second with the active pixels of a 1,628 by 1,236 resolution, and with the minimal loss of accuracy. In an evaluation using the BelgiumTS dataset, the experimental results indicate that the detection rate is about 91.69% with false positives per window of 3.39e-5, and the recognition rate is about 93.77%. We report on two traffic light detection and recognition systems. The first system detects and recognizes red circular lights only, using image processing and SVM. Its performance is better than that of traditional detectors and it achieves the best performance with 96.97% precision and 99.43% recall. The second system is more complicated. It detects and classifies different types of traffic lights, including green and red lights in both circular and arrow forms. In addition, it employs image processing techniques, such as color extraction and blob detection to locate the candidates. Subsequently, a pre-trained PCA network is used as a multi-class classifier for obtaining frame-by-frame results. Furthermore, an online multi-object tracking technique is applied to overcome occasional misses and a forecasting method is used to filter out false positives. Several additional optimization techniques are employed to improve the detector performance and to handle the traffic light transitions. A multi-spectral data collection system is implemented for pedestrian detection, which includes a thermal camera and a pair of stereo color cameras. The three cameras are first aligned using trifocal tensor, and the aligned data are processed by using computer vision and machine learning techniques. Convolutional channel features (CCF) and the traditional HOG+SVM approach are evaluated over the data captured from the three cameras. Through the use of trifocal tensor and CCF, training becomes more efficient. The proposed system achieves only a 9% log-average miss rate on our dataset. Autonomous lane keeping system employs an end- to-end learning approach for obtaining the proper steering angle for maintaining a car in a lane. The convolutional neural network (CNN) model uses raw image frames as input, and it outputs the steering angles corresponding to the input frames. Unlike the traditional approach, which manually decomposes the problem into several parts, such as lane detection, path planning, and steering control, the model learns to extract useful features on its own and learns to steer from human behavior. More importantly, we find that having a simulator for data augmentation and evaluation is important. We then build the simulator using image projection, vehicle dynamics, and vehicle trajectory tracking. The test results reveal that the model trained with augmented data using the simulator has better performance and achieves about a 98% autonomous driving time on our dataset. Furthermore, a vehicle data collection system is developed for building our own datasets from recorded videos. These datasets are used in the above studies and have been released to the public for autonomous vehicle research. The experimental datasets are available at http://computing.wpi.edu/Dataset.html."

A common problem when running Web-based applications is how to scale-up the database. The solution to this problem usually involves having a smart Database Administrator determine how to spread the database tables out amongst computers that will work in parallel. Laying out database tables across multiple machines so they can act together as a single efficient database is hard. Automated methods are needed to help eliminate the time required for database administrators to create optimal configurations. There are four operators that we consider that can create a search space of possible database layouts: 1) denormalizing, 2) horizontally partitioning, 3) vertically partitioning, and 4) fully replicating. Textbooks offer general advice that is useful for dealing with extreme cases - for instance you should fully replicate a table if the level of insert to selects is close to zero. But even this seemingly obvious statement is not necessarily one that will lead to a speed up once you take into account that some nodes might be a bottle neck. There can be complex interactions between the 4 different operators which make it even more difficult to predict what the best thing to do is. Instead of using best practices to do database layout, we need a system that collects empirical data on when these 4 different operators are effective. We have implemented a state based search technique to try different operators, and then we used the empirically measured data to see if any speed up occurred. We recognized that the costs of creating the physical database layout are potentially large, but it is necessary since we want to know the "Ground Truth" about what is effective and under what conditions. After creating a dataset where these four different operators have been applied to make different databases, we can employ machine learning to induce rules to help govern the physical design of the database across an arbitrary number of computer nodes. This learning process, in turn, would allow the database placement algorithm to get better over time as it trains over a set of examples. What this algorithm calls for is that it will try to learn 1) "What is a good database layout for a particular application given a query workload?" and 2) "Can this algorithm automatically improve itself in making recommendations by using machine learned rules to try to generalize when it makes sense to apply each of these operators?" There has been considerable research done in parallelizing databases where large amounts of data are shipped from one node to another to answer a single query. Sometimes the costs of shipping the data back and forth might be high, so in this work we assume that it might be more efficient to create a database layout where each query can be answered by a single node. To make this assumption requires that all the incoming query templates are known beforehand. This requirement can easily be satisfied in the case of a Web-based application due to the characteristic that users typically interact with the system through a web interface such as web forms. In this case, unseen queries are not necessarily answerable, without first possibly reconstructing the data on a single machine. Prior knowledge of these exact query templates allows us to select the best possible database table placements across multiple nodes. But in the case of trying to improve the efficiency of a Web-based application, a web site provider might feel that they are willing to suffer the inconvenience of not being able to answer an arbitrary query, if they are in turn provided with a system that runs more efficiently.