The following is a Java applet demo of the TRAPP algorithm as presented in the SIGMOD 2001 paper Adaptive Precision Setting for Cached Approximate Values
by Chris Olston, Boon Thau Loo, and Jennifer Widom. Select a data set for viewing the demo, or read the instructions below. Brief descriptions of the data sets are also available.
| Data Set |
| Random Walk |
| Ocean Buoy Data (2 data objects) |
Overview
This demo simulates a situation in which a cache has multiple data sources whose value it is tracking. Simple aggregate queries, such as a sum over all values or the average of all values, are issued to the cache, each with a given precision requirement. The cache then uses its cached values to answer the query within the required precision, requesting more up-to-date data from the sources if it is unable to meet the query requirements.
Each source has a given precision window associated with it. This window is a guarentee from the source that its data value is within the window boundaries. For example, if the source has the window [4,8], the cache knows that the value at the source falls somewhere in that interval: it could be 5 or 7, but not 9. Having a window associated with the value means that the source does nto need to refresh its value to the cache as long as the value stays within the window. Whenever the data value at a source exceeds the window boundary, it transmits (refreshes) its new value to the cache. Whenever the cache receives a query which has a precision window smaller than the cache can answer with its current estimates, it probes sources for their values, continuing to do so until it can satisfy the query with sufficient precision. Each refresh and probe on a source causes the precision window for that source to change. For this demo, every probe cuts the window in half, and every refresh doubles the window. In this manner, the precision for each source is adaptively set.
Display
Each of the moving graphs on the display plots the data value (blue line) and the precision window width (gray box). Every time the cache receives a query, a vertical gray line is plotted on the display. Probes (query-initiated refresh) are shown as green highlights in the plot, and refreshes (source-initiated) are shown as red bars.
The bar graph at the right of the display shows the cost of TRAPP (TRP) when compared to several alternative methods of maintiaining cached values: Adaptive Data Replication (ADR), Exact Caching (Exa) in which data values are transmitted to the cache every time the data value changes, and No Caching (NC) in which data values are fetched from the source on every query. The cost graphs show the total cost of each algorithm over the window visible on screen, with each message sent contributing one unit to the cost.
Controls
The sliders below the graphs allow the user to control three parameters. The top slider controls the average query frequency, in terms of queries per window. The middle slider sets the percision requirement; making the requirement larger allows the precision window to grow without requiring a refresh. The bottom slider controls the speed at which the graphs travel across the screen (but does not affect the algorithm).
Note
This demo is a Java Applet which uses AWT. If you are using Netscape 4.x for the Mac or Unix, the default JRE may not have AWT support, which will cause the demo not to work.
Random Walk: At each time step an item in this data set will transition to another value with a certain probability. If an item is selected to transition it will either transition to a value one higher or one lower with equal probability.
Ocean Buoy Data: This data set is a subset of real-world data collected from ocean buoys monitoring wind speed.