Profile-Driven Data Management

Mitch Cherniack
Brandeis University

A pervasive computing environment can be characterized by the following properties [NIST01]:

•	Scale:   Pervasive computing environments deploy a large number of limited-capability devices (e.g., sensors)

•	Mobility:  Frequently these devices are mobile, and

•	Ubiquity:  The devices are connected to an ubiquitous network structure.

If devices are treated as data sources (of potentially infinite streams of data), query support is possible provided that the data generated by devices is intelligently managed.

Traditional data management consists of techniques (indexing, clustering, replication etc.) that can improve the efficiency of data access when these techniques are applied in a manner consistent with the semantics of the data and the querying applications.   Due to the scale of pervasive environments (as measured by both the number of data sources and the number of querying applications), it is clear that data management techniques are desirable in this context also.

An example serves to illustrate.  Suppose that in the year 2005, all vehicles are equipped with GPS sensors and transmitters that broadcast the vehicle’s serial number, current time and current position in some periodic fashion.  Every vehicle, then, is a data source in this pervasive environment.  Given the number of vehicles that can be on the road at a given time (e.g., Route 128 averages well over 175,000 vehicles in the Waltham, MA stretch near Brandeis on any given day), it is clear that the number of data sources far and away exceeds the number of data sources found in traditional database applications.

The number of querying applications requiring access to this data might also be very large.  Consider the following examples:

1.	Vehicle Tracking:  The Acme Trucking company wants to know the positions of all of its vehicles at all times.

2.	Bottleneck Detection:  Radio station WXYZ wants to monitor traffic at well-known bottleneck locations to determine when to broadcast detour recommendations.

3.	Accident Detection:  Police, fire department and ambulance services want to know about vehicle collisions (which occur when 2 or more vehicles have the exact same position at the exact same time).

4.	City Planning:  City planners wish to maintain historical traffic flow information to determine new transportation needs (e.g., new traffic lights, widened highways).

5.	Convoy Monitoring:  A straying car from a convoy wants to know where rest of the convoy has gone.

6.	Speeding Detection:  State patrollers want to track positions of a random set of cars that are on a given highway over fixed time intervals so as to estimate their speed.

Also, every vehicle may itself run a querying application (accident avoidance) that alerts the driver when other vehicles are within 50 feet and traveling in a trajectory that could result in a collision.

What is Data Management in this Context?

The querying applications described above offer many opportunities for data management.   Applications #4 (city planning) and #6 (speeding detection) require access to historical data (i.e., data transmitted from a vehicle prior to the most recent transmission).  Therefore, data management decisions must be made to choose what streamed data should be stored, where it gets stored, and when it gets discarded.    Data management also figures into decisions about how to organize stored data.  For example, application #2 (bottleneck detection) might benefit from having vehicle position data clustered by position and time, rather than by vehicle id and time (which is the more “natural” clustering policy).  And during bursty periods of data generation and querying (e.g., rush hour), a data management decision must be made to choose how data requested by querying applications can be acceptably approximated.  For example, application #2 (bottleneck detection) might be able to tolerate a 10% loss of accuracy (from missed vehicle reports) and application #4 (city planning) might be able to tolerate a 24 hour delay in receiving answers to its query.  But application #3 (accident detection) likely cannot tolerate any inaccuracies or delay.

Regardless of the data management techniques chosen for use in a pervasive environment, two architectural requirements for data management in pervasive environments are evident:

1.	Brokers:  There is a need for one or more “brokers” to arbitrate between data sources and clients, and to implement data management policies according to client needs.  If for nothing else, brokers are required to track and record historical data, as data recording by devices is usually impossible (e.g., sensors are memoryless, or at best, severely memory-impaired), and data recording by applications is wasteful (e.g., both accident detection and accident avoidance require the same preprocessing of data)

2.	Automatic Data Management:  Due to the large scale of pervasive environments, it is necessary for data management decisions to be made by brokers automatically, rather than as a result of human intervention.  

How Should Data Management Policies Be Determined?  

Traditional data management is driven by the semantics of applications and data.  Application and data semantics are determined by a database administrator in consultation with clients that write querying applications.  In a setting where automatic data management is required, this model cannot work.  Instead, data management should be driven by user profiles that specify the data needs of querying applications. 

The traditional view of a user profile stems from the publish/subscribe world, where it is defined as a filter query that specifies a user subscription.  But user profiles that are used to drive data management must be far more than queries; they must also specify the relative utility of data to a given application.  For example, a user profile for application #2 (bottleneck detection) might specify that the first 90% of vehicle position reports from a given location are extremely important, but that the remaining 10%, or any reports beyond those required to determine that there is a bottleneck are less important.  Similarly, a user profile for application #4 (city planning) might specify that data that is no more than a day old is extremely important, but stale data has a utility value that decays over time.

There are two models for user profiles found in systems today that are relevant to profile-driven data management.  Quality of Service (QoS) profiles are multi-dimensional graphs that plot a “mirth factor” (typically a value between 0 and 1) as a function of delay or accuracy of data [St96, CSS+97].  Such profiles are used in multimedia systems to determine how to compromise video or audio content (e.g., by lowering video resolution or dropping frames) when contention in the system demands that client requests be compromised.   QoS-style profiles could be used similarly in a pervasive data management setting to specify how satisfied is an application when the data it requests is incomplete or delayed.   On the other hand, QoS-style profiles make no distinctions between different types of data.   Application #2 (bottleneck detection) might prefer that inaccuracies in traffic data be confined to select stretches of highway (e.g., those that are of least interest to its audience) and not spread across all bottleneck areas.   QoS-style profiles do not make distinctions of this kind.

Digital Video Recording (DVR) profiles are used by television content management systems such as Tivo [Tivo] and ReplayTV [ReplayTV] to guide the personalized, automatic recording of television content.   An owner of a Tivo or ReplayTV “box” generates a profile that specifies the television content that should be recorded on a continual basis.  This profile combines a query (identifying television shows of interest) with a priority specification (identifying the relative importance of the shows identified as interesting).  The query portion of a DVR profile can identify television shows of interest either explicitly or declaratively.  A television show can be identified explicitly in the following ways:

•	by the date, time and channel of a television show;

•	by the time and channel for a television show (for shows that are aired weekly); and

•	by name (for shows that are aired at multiple times and/or on multiple stations).

The user can also identify shows declaratively using keywords that might be found in the title, list of actors or show description.  For example, the keyword phrase “Guess Who” matches all television shows that have “Guess Who” in the title (e.g., “Guess Who’s Coming to Dinner”), the list of actors (as in a show starring members of the musical group, the Guess Who), or the description.
 
DVR profiles also identify the relative priorities of television content.  A user can specify that a particular show have “hard” or ‘soft” priority. (Hard priority reserves space on the disk for the identified show.  Soft priority records the show only if there is enough room left on the disk.)  As well, users can specify “thresholds” (e.g., keep only the three most recent episodes of Seinfeld) and “resolution” (e.g., ReplayTV offers three grades of video quality).

In short, a DVR-style profile differs from a QoS-style profile in that it identifies the relative worth of data, whereas a QoS-style profile specifies the satisfaction a user gets from a partial result to his query.   Both features are of use for driving data management, and one key issue in profile-driven data management is how to express profiles in such a way as to combine the information that can be gleaned from QoS-style and DVR-style profiles.

What are the Key Issues for Profile-Driven Data Management?

My position is that the three most important issues for profile-driven data management in pervasive environments are as follows:

1.  Architecture:  What should be the underlying architecture for a profile-driven data management system for pervasive environments?   Should a given environment have one or many brokers?  If the latter, how should brokers be organized and how should they communicate/cooperate with each other?

2.  Data Management Techniques:   What kinds of data management decisions can be made on the basis of profile specifications?  We have seen how profiles can influence the result of a query, but how can profiles be used to make other data management decisions such as which streamed data to store, where to store it, and when to discard it, what indexes to build over stored data, how to organize stored data, when data should be replicated etc.

3.  Expressing Profiles:  how should profiles be expressed to combine the features of QoS and DVR-style profiles?  Who should compose profiles?  Should they be authored by users (perhaps with the assistance of a GUI, as with DVR-style profiles) or should they be learned from user activities? (or some combination of the two).

References

[CSS+97]  S. Chatterjee, J. Sydir, B. Sabata and T. Lawrence.  Modeling applications for adaptive QoS-based resource management.  In Proceedings of the 2nd IEEE High-Assurance System Engineering Workshop (HASE97), Bethesda, MD, 1997.

[NIST01]  National Institute of Standards and Technology (NIST), Pervasive Computing 2001: Major IT Conference, May 1-2, 2001.  http://www.nist.gov/pc2001.

[ReplayTV]  Replay TV.  http://www.replaytv.com.

[Tivo]  TIVO.  http://www.tivo.com

[St96]  Richard A. Staehli.  Quality of Service Specification for Resource Management in Multimedia Systems.  PhD. Thesis, Oregon Graduate Institute of Science and Technology, January 1996.