Navneet Potti

Many modern applications deal with exponentially increasing data volumes and aid business-critical decisions in near real-time. Particularly in exploratory data analysis, the focus is on interactive querying and some degree of error in estimated results is tolerable. A common response to this challenge is approximate query processing, where the user is presented with a quick confidence interval estimate based on a sample of the data. In this work, we highlight some of the problems that are associated with this probabilistic approach when extended to more complex queries, both in semantic interpretation and the lack of a formal algebra. As an alternative, we propose deterministic approximate querying (DAQ) schemes, formalize a closed deterministic approximation algebra, and outline some design principles for DAQ schemes. We also illustrate the utility of this approach with an example deterministic online approximation scheme which uses a bitsliced index representation and computes the most significant bits of the result first. Our prototype scheme delivers speedups over exact aggregation and predicate evaluation, and outperforms sampling-based schemes for extreme value aggregations.

Database-as-a-service providers typically use replication to meet the performance and availability guarantees demanded by their customers. A crucial problem in this context is that of placing the replicas on machines in such a way as to meet these guarantees while optimally utilizing the available resources, despite having incomplete or erroneous a priori knowledge of the workload characteristics. In contrast to previous work, we incorporate this uncertainty by proposing online algorithms that make little or no assumptions about workload characteristics. In this work, we provide a formal definition of variants of the replica placement problem, as well as a wide spectrum of criteria to evaluate proposed solutions. We also designed and evaluated a number of new algorithms for the online replica placement problem. We show that one of our algorithms, RkC, which is based on the notion of the "power of two random choices", outperforms others with respect to these evaluation criteria.