11230966
Robust Aggregation in Sensor Networks
In the emerging area of sensor-based systems, a significant challenge is to develop scalable, fault-tolerant methods to extract useful information from the data the sensors collect. An approach to this data management problem is the use of sensor “database” systems, which allow users to perform aggregation queries on the readings of a sensor network. Due to power and range constraints, centralized approaches are generally impractical, so most systems use in-network aggregation to reduce network traffic. However, these aggregation strategies become bandwidthintensive when combined with the fault-tolerant, multi-path routing methods often used in these environments. In order to avoid this expense, we investigate the use of approximate in-network aggregation using small sketches and we survey robust and scalable methods for computing duplicate-sensitive aggregates.
8773045
Characterizing and Exploiting Reference Locality in Data Stream Applications
In this paper, we investigate a new approach to process queries in data stream applications. We show that reference locality characteristics of data streams could be exploited in the design of superior and flexible data stream query processing techniques. We identify two different causes of reference locality: popularity over long time scales and temporal correlations over shorter time scales. An elegant mathematical model is shown to precisely quantify the degree of those sources of locality. Furthermore, we analyze the impact of locality-awareness on achievable performance gains over traditional algorithms on applications such asMAX-subset approximate sliding window join and approximate count estimation. In a comprehensive experimental study, we compare several existing algorithms against our locality-aware algorithms over a number of real datasets. The results validate the usefulness and efficiency of our approach.
17450841
An information concierge for the Web
WWW Information Collection, Collaging and Programming (WICCAP) system is a software system for the generation of logical views of web resources, and the extraction of desired information in the form of a structured document. It is designed to enable people to obtain information of interests in a simple and effective manner as well as to make information from the WWW accessible to applications so as to afford automation, inter-operation and Web-awareness among services. A key factor in making this system useful in practice is that it provides tools to automate and facilitate the process of constructing logical representation of websites, to identify and define information of interest, and to retrieving them. In this paper we present the design of the WICCAP system and its two main components, namely Mapping Wizard and Network Extraction Agent.
6484880
Spatio-temporal aggregation using sketches
Several spatio-temporal applications require the retrieval of summarized information about moving objects that lie in a query region during a query interval (e.g., the number of mobile users covered by a cell, traffic volume in a district, etc.). Existing solutions have the distinct counting problem: if an object remains in the query region for several timestamps during the query interval, it will be counted multiple times in the result. We solve this problem by integrating spatio-temporal indexes with sketches, traditionally used for approximate query processing. The proposed techniques can also be applied to reduce the space requirements of conventional spatio-temporal data and to mine spatio-temporal association rules.
3002704
Approximate aggregation techniques for sensor databases
In the emerging area of sensor-based systems, a significant challenge is to develop scalable, fault-tolerant methods to extract useful information from the data the sensors collect. An approach to this data management problem is the use of sensor database systems, exemplified by TinyDB and Cougar, which allow users to perform aggregation queries such as MIN, COUNT and AVG on a sensor network. Due to power and range constraints, centralized approaches are generally impractical, so most systems use in-network aggregation to reduce network traffic. However, these aggregation strategies become bandwidth-intensive when combined with the fault-tolerant, multipath routing methods often used in these environments. For example, duplicate-sensitive aggregates such as SUM cannot be computed exactly using substantially less bandwidth than explicit enumeration. To avoid this expense, we investigate the use of approximate in-network aggregation using small sketches. Our contributions are as follows: 1) we generalize well known duplicate-insensitive sketches for approximating COUNT to handle SUM, 2) we present and analyze methods for using sketches to produce accurate results with low communication and computation overhead, and 3) we present an extensive experimental validation of our methods.
3455572
On Trip Planning Queries in Spatial Databases
In this paper we discuss a new type of query in Spatial Databas es, called the Trip Planning Query (TPQ). Given a set of points of interestP in space, where each point belongs to a specific category, a star ting pointS and a destinationE, TPQ retrieves thebesttrip that starts at S, passes through at least one point from each category, and ends at E. For example, a driver traveling from Boston to Providence might want to stop to a gas station, a ban k and a post office on his way, and the goal is to provide him with the best possibl e route (in terms of distance, traffic, road conditions, etc.). The difficulty of this query lies in the existence of multiple choices per category. In this paper, w study fast approximation algorithms for TPQ in a metric space. We provide a numb er of approximation algorithms with approximation ratios that depend o either the number of categories, the maximum number of points per category or b oth. Therefore, for different instances of the problem, we can choose the alg orithm with the best approximation ratio, since they all run in polynomial time. Furthermore, we use some of the proposed algorithms to derive efficient heuristi cs for large datasets stored in external memory. Finally, we give an experimental ev luation of the proposed algorithms using both synthetic and real datasets .
6487445
Incremental rendering of deformable trimmed NURBS surfaces
Trimmed NURBS surfaces are often used to model smooth and complex objects. Unfortunately, most existing hardware graphics accelerators cannot render them directly. Although there are a lot of methods proposed to accelerate the rendering of such surfaces, majority of them are based on tessellation, which is developed primarily for handling non-deforming objects. For an object that may deform in run-time, such as clothing, facial expression, human and animal character, the tessellation process will need to be performed repeatedly while the object is deforming. However, as the tessellation process is very time consuming, interactive display of deforming objects is difficult. This explains why deformable objects are rarely used in virtual reality applications. In this paper, we present a efficient method for incremental rendering of deformable trimmed NURBS surfaces. This method can handle both trimmed surface deformation and trimming curve deformation. Experimental results show that our method performs significantly faster than the method used in OpenGL.
14081654
Real-time rendering of deformable parametric free-form surfaces
Deformable objects are required to improve the realism of virtual reality applications. They are particularly useful in modeling clothes, facial expression, human and animal characters. A common method to render these objects is by tessellation. However, the tessellation process is computationally very expensive. If the object deforms, we need to retessellate the surface every frame, as its shape changes from one frame to the next. This computational burden poses a significant challenge to the real-time rendering of deformable objects. Consequently, deformable objects are seldom incorporated in existing virtual reality systems. In this paper, we present an incremental method for rendering deformable objects modeled by parametric free-form surfaces. We also introduce two new frame coherence techniques for crack prevention and parameter caching. Finally, we present a single hierarchical data structure which provides a multi-resolution representation of the object model.
2888187
Asynchronous collaboration around multimedia and its application to on-demand training
Multimedia content is a central component of on-demand training and education delivered over the World Wide Web. Supporting asynchronous collaboration around educational multimedia is a key requirement for making the online educational environment effective. A multimedia annotation system tightly integrated with email provides a powerful platform on which to base such functionality. Building on our earlier work with multimedia annotations, we present user interface and system extensions to support asynchronous collaboration for on-demand training. We report results from a study of the effectiveness of the system, including student experience, instructor experience, and user interface appropriateness. Overall, the student experience was positive: they appreciated the flexibility of on-demand delivery and benefited from the collaborative features.
2691860
Design and Management of 3D Chip Multiprocessors Using Network-in-Memory
Long interconnects are becoming an increasingly important problem from both power and performance perspectives. This motivates designers to adopt on-chip network-based communication infrastructures and three-dimensional (3D) designs where multiple device layers are stacked together. Considering the trends towards increasing use of chip multiprocessing, it is timely to consider 3D chip multiprocessor design and memory networking issues, especially in the context of data management in large L2 caches. The overall goal of this paper is to study the challenges for L2 design and management in 3D chip multiprocessors. Our first contribution is to propose a router architecture and a topology design that makes use of a network architecture embedded into the L2 cache memory. Our second contribution is to demonstrate, through extensive experiments, that a 3D L2 memory architecture generates much better results than the conventional two-dimensional (2D) designs under different number of layers and vertical (inter-wafer) connections. In particular, our experiments show that a 3D architecture with no dynamic data migration generates better performance than a 2D architecture that employs data migration. This also helps reduce power consumption in L2 due to a reduced number of data movements
16010739
Compiler-directed proactive power management for networks
Increasing use of parallel computation platforms (both off-chip and on-chip) makes communication analysis and optimization an important target. While there have been numerous studies that target network performance of parallel architectures, the efforts that target network power consumption (in terms of both modeling and optimization) are relatively new. One of the common characteristics of most of the prior approaches to network power management is that they are hardware-based and reactive in the sense that they manage power consumption of the network as a response to observed message traffic. Consequently, they can miss important opportunities for saving power and can incur performance penalties due to inaccuracies in predicting future idle and active times of communication links. Motivated by this observation, this paper proposes a compiler-directed proactive approach to network power management for the class of loop-intensive applications running on small-sized networks used exclusively by a single embedded application at a time.As compared to hardware-based approaches, the proposed compiler-directed approach has two potential benefits. First, based on high-level communication analysis, it determines the points at which a given communication link is idle and can be turned off (i.e., powered down) to save power. Therefore, an idle link can be put in the low-power state without waiting for a certain period of time to make sure that the link has really become idle (as in the case of hardware schemes). Second, since the compiler can also determine the point at which a turned-off link will be needed in the future, it can pre-activate it (i.e., before it is actually needed) to eliminate the turn on (reactivation) performance penalty. Our simulations with seven array-intensive applications and an embedded on-chip network clearly show that the proposed compiler-directed approach is better than a hardware-based scheme from both power and performance perspectives.