Location tracking has several applications in mobile (cellular or ad hoc) networks, such as location-based routing algorithms and consumer services. It is often difficult to compute the location of a node precisely because of the infrastructure costs and the errors inherent in most tracking techniques. Furthermore, this accuracy differs amongst nodes based on the scattered availability of equipment such as GPS. We focus on heterogeneous mobile networks, wherein some nodes know their locations more precisely than others and there is a short-range peer-to-peer communication channel such as Bluetooth or 802.11. We consider a generalized notion of location, called vicinity, which is the set of potential locations for a node. We formulate a hierarchy of distance constraints that can be applied in a network and devise efficient distributed techniques for computing the most optimal (smallest) vicinities under various constraint classes. In particular, our algorithms use both proximity and non-proximity relationships between the nodes. We present simulation results establishing the effectiveness of using these different types of constraints.

Network design tools are routinely used in practice to design optical networks that can carry a given set of traffic demands at the least cost The criteria used to route demands during design are often different from those used while routing in the operational network. As a result, the routes computed may be different during design and operations, leading to over- or under- utilization of portions of the network and even failure to route some demands. In this paper, we propose a general solution for this problem, which handles any combination of routing criteria. It works by enhancing the designed network with minimal additional capacity such that it can carry the demands during operations. We also provide experimental results evaluating the performance of this technique and the operational effectiveness of various design algorithms.

Fast shared restoration is critical to the success of WDM mesh networking. A restricted form of sharing called K-sharing was recently proposed, which allows rapid, signaling-free restoration. However, the routing and design algorithms used for traditional shared restoration do not work for this scheme. Also, K-sharing can potentially increase capacity requirements in the network because it limits sharing. In this paper, we present novel routing and design algorithms for K-shared networks. We also show that a practical version of the routing problem is NP-hard and present heuristics to solve it. We also summarize experimental results demonstrating that the additional capacity requirements imposed by K-sharing are in fact minimal in practice.

Many commercial database systems maintain histograms to summarize the contents of large relations and permit efficient estimation of query result sizes for use in query optimizers. Delaying the propagation of database updates to the histogram often introduces errors into the estimation. This article presents new sampling-based approaches for incremental maintenance of approximate histograms. By scheduling updates to the histogram based on the updates to the database, our techniques are the first to maintain histograms effectively up to date at all times and avoid computing overheads when unnecessary. Our techniques provide highly accurate approximate histograms belonging to the equidepth and Compressed classes. Experimental results show that our new approaches provide orders of magnitude more accurate estimation than previous approaches.An important aspect employed by these new approaches is a backing sample , an up-to-date random sample of the tuples currently in a relation. We provide efficient solutions for maintaining a uniformly random sample of a relation in the presence of updates to the relation. The backing sample techniques can be used for any other application that relies on random samples of data.

In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex decision support queries using precomputed summary statistics, such as samples. Decision support queries routinely segment the data into groups and then aggregate the information in each group (group-by queries). Depending on the data, there can be a wide disparity between the number of data items in each group. As a result, approximate answers based on uniform random samples of the data can result in poor accuracy for groups with very few data items, since such groups will be represented in the sample by very few (often zero) tuples.

Many emerging environments are increasingly facing the problem where the requirements of applications easily outstrip the system resources. This is particularly acute in the World Wide Web (WWW) and many data-intensive applications like OLAP and multimedia databases. We address this problem in the Web context via systematic multiresolution, i.e., a framework for providing responses at different qualities (resolutions) and costs. We validate our conceptual contributions by implementing NetBlitz a multiresolution-based proxy server on the WWW. NetBlitz addresses two key problems facing the Web: high latencies and heterogeneity of client resources and requirements. It solves these problems by dynamically generating the "required version" of a Web object based on client preferences and capabilities. We also propose novel multiresolution-aware caching techniques that further improve performance. Finally we experimentally demonstrate the utility of multiresolution and the caching enhancements proposed.

Summary form only given. The last few years have witnessed a significant increase in the use of databases for complex data analysis (OLAP) applications. These applications often require very quick responses from the DBMS. However, they also involve complex queries on large volumes of data. Despite significant improvement in database support for OLAP over the last few years, most DBMSs still fall short of providing quick enough responses. We present a novel solution to this problem: we use small amounts of precomputed summary statistics of the data to answer the queries quickly, albeit approximately. Our hypothesis is that many OLAP applications can tolerate approximations in query results in return for huge response time reductions. The work is part of our efforts to build an efficient data analysis system called AQUA. We describe some of the technical problems addressed in this effort.

In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex aggregate queries based on statistical summaries of the full data. In this paper, we demonstrate the difficulty of providing good approximate answers for join-queries using only statistics (in particular, samples) from the base relations. We propose join synopses as an effective solution for this problem and show how precomputing just one join synopsis for each relation suffices to significantly improve the quality of approximate answers for arbitrary queries with foreign key joins. We present optimal strategies for allocating the available space among the various join synopses when the query work load is known and identify heuristics for the common case when the work load is not known. We also present efficient algorithms for incrementally maintaining join synopses in the presence of updates to the base relations. Our extensive set of experiments on the TPC-D benchmark database show the effectiveness of join synopses and various other techniques proposed in this paper.

Selectivity estimation of queries is an important and well-studied problem in relational database systems. In this paper, we examine selectivity estimation in the context of Geographic Information Systems, which manage spatial data such as points, lines, poly-lines and polygons. In particular, we focus on point and range queries over two-dimensional rectangular data. We propose several techniques based on using spatial indices, histograms, binary space partitionings (BSPs), and the novel notion of spatial skew. Our techniques carefully partition the input rectangles into subsets and approximate each partition accurately. We present a detailed experimental study comparing the proposed techniques and the best known sampling and parametric techniques. We evaluate them using synthetic as well as real-life TIGER datasets. Based on our experiments, we identify a BSP based partitioning that we call Min-Skew which consistently provides the most accurate selectivity estimates for spatial queries. The Min-Skew partitioning can be constructed efficiently, occupies very little space, and provides accurate selectivity estimates over a broad range of spatial queries.

Modern decision support systems require very quick (interactive) responses from the DBMS, but pose complex queries on large volumes of data. In this paper, we present a novel solution to this problem: we precompute concise histogram statistics on the data to answer the queries quickly but approximately. Our hypothesis is that many decision support applications can tolerate small errors in query results in return for large reductions in response times. In particular, we propose the use of multiple histograms to approximate the data cube and answer aggregate queries approximately using this summarized data. We enhance histograms to estimate the quality of the approximate answers. We primarily explore the interaction among various histograms on the data cube in order to minimize the space needed when an upper bound on the errors is given. Our main contribution in this paper is an efficient technique for selecting a provably near-optimal set of histograms on the data cube. Extensive experiments show that our technique results in very accurate and concise statistics. Our technique is general in nature and can also be used for selecting a set of histograms (or other statistics) on a relation for the purpose of selectivity estimation.

Many commercial database systems maintain histograms to summarize the contents of relations and permit efficient estimation of query result sizes and access plan costs. Although several types of histograms have been proposed in the past, there has never been a systematic study of all histogram aspects, the available choices for each aspect, and the impact of such choices on histogram effectiveness. In this paper, we provide a taxonomy of histograms that captures all previously proposed histogram types and indicates many new possibilities. We introduce novel choices for several of the taxonomy dimensions, and derive new histogram types by combining choices in effective ways. We also show how sampling techniques can be used to reduce the cost of histogram construction. Finally, we present results from an empirical study of the proposed histogram types used in selectivity estimation of range predicates and identify the histogram types that have the best overall performance. 1 Introduction...

Many current database systems use histograms to approximate the frequency distribution of values in the attributes of relations and based on them estimate query result sizes and access plan costs. In choosing among the various histograms, one has to balance between two conflicting goals: optimality, so that generated estimates have the least error, and practicality, so that histograms can be constructed and maintained efficiently. In this paper, we present both theoretical and experimental results on several issues related to this trade-off. Our overall conclusion is that the most effective approach is to focus on the class of histograms that accurately maintain the frequencies of a few attribute values and assume the uniform distribution for the rest, and choose for each relation the histogram in that class that is optimal for a self-join query.