8490960
Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams
As computer systems are essential components of many critical commercial services, the need for secure online transactions is now becoming evident. The demand for such applications, as the market grows, exceeds the capacity of individual businesses to provide fast and reliable services, making outsourcing technologies a key player in alleviating issues of scale. Consider a stock broker that needs to provide a real-time stock trading monitoring service to clients. Since the cost of multicasting this information to a large audience might become prohibitive, the broker could outsource the stock feed to third-party providers, who are in turn responsible for forwarding the appropriate sub-feed to clients. Evidently, in critical applications the integrity of the third-party should not be taken for granted. In this work we study a variety of authentication algorithms for selection and aggregation queries over sliding windows. Our algorithms enable the end-users to prove that the results provided by the third-party are correct, i.e., equal to the results that would have been computed by the original provider. Our solutions are based on Merkle hash trees over a forest of space partitioning data structures, and try to leverage key features, like update, query, signing, and authentication costs. We present detailed theoretical analysis for our solutions and empirically evaluate the proposed techniques.
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 .
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.
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.
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.
17571347
A multi-server architecture for distributed virtual walkthrough
CyberWalk is a distributed virtual walkthrough system that we have developed. It allows users at different geographical locations to share information and interact within a common virtual environment (VE) via a local network or through the Internet. In this paper, we illustrate that when the number of users exploring the VE increases, the server will quickly become the bottleneck. To enable good performance, CyberWalk utilizes multiple servers and employs an adaptive data partitioning techniques to dynamically partition the whole VE into regions. All objects within each region will be managed by one server. Under normal circumstances, when a viewer is exploring a region, the server of that region will be responsible for serving all requests from the viewer. When a viewer is crossing the boundary of two or more regions, the servers of all the regions involved will be serving requests from the viewer since the viewer might be able to view objects within all those regions. We evaluate the performance of this multi-server architecture of CyberWalk via a detail simulation model.
41742727
Efficient rendering of deformable objects for real-time applications
Deformable objects can be used to model soft objects such as clothing, human faces and animal characters. They are important as they can improve the realism of the applications. However, most existing hardware accelerators cannot render deformable objects directly. A tessellation process is often used to convert a deformable object into polygons so that the hardware graphics accelerator may render them. Unfortunately, this tessellation process is computationally very expensive. While the object is deforming, the tessellation process needs to be performed repeatedly to convert the deforming objects into polygons. As a result, deformable objects are seldom used in real-time applications such as virtual environments and computer games. Since trimmed NURBS surfaces are often used to represent deformable objects, in this paper we present an efficient method for incremental rendering of deformable trimmed NURBS surfaces. A trimmed NURBS surface typically deforms through the deformation of the trimmed NURBS surface and/or the trimming curve. Our method handles both trimmed surface deformation as well as trimming curve deformation. Experimental results show that our method performs significantly faster than the method used in OpenGL and can be used in real-time applications, such as computer games. Copyright © 2006 John Wiley & Sons, Ltd.
16124997
GameOD: an internet based game-on-demand framework
Multiplayer online 3D games are becoming very popular in recent years. However, existing games require the complete game content to be installed prior to game playing. Since the content is usually large in size, it may be difficult to run these games on a PDA or other handheld devices. It also pushes game companies to distribute their games as CDROMs/DVDROMs rather than online downloading. On the other hand, due to network latency, players may perceive discrepant status of some dynamic game objects. In this paper, we present a game-on-demand (GameOD) framework to distribute game content progressively in an on-demand manner. It allows critical contents to be available at the players' machines in a timely fashion. We present a simple distributed synchronization method to allow concurrent players to synchronize their perceived game status. Finally, we show some performance results of the proposed framework.
17088807
Reducing NoC energy consumption through compiler-directed channel voltage scaling
While scalable NoC (Network-on-Chip) based communication architectures have clear advantages over long point-to-point communication channels, their power consumption can be very high. In contrast to most of the existing hardware-based efforts on NoC power optimization, this paper proposes a compiler-directed approach where the compiler decides the appropriate voltage/frequency levels to be used for each communication channel in the NoC. Our approach builds and operates on a novel graph based representation of a parallel program and has been implemented within an optimizing compiler and tested using 12 embedded benchmarks. Our experiments indicate that the proposed approach behaves better - from both performance and power perspectives - than a hardwarebased scheme and the energy savings it achieves are very close to the savings that could be obtained from an optimal, but hypothetical voltage/frequency scaling scheme.
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.