This work is part of a joint project between IBM Almaden Research Center and the Ohio State University. The goal of the project is to facilitate the querying and browsing of multimedia databases over a wide spectrum of networks and media. In this paper, we focus on the related issues of data abstraction, navigation and presentation. We are proposing an integrated form of querying and hierarchical navigation that is similar to the methods used by data analysis systems to allow drill down operations on statistical data. We have applied our solution to hypertext style database publishing and developed a user customizable database query facility. The data visualization is interactive and enables users, even ones who have minimal familiarity with the database contents and schema, to easily pinpoint data in which they are interested. A pilot implementation for the project, using a web interface, is already operational. It provides access to tourist related data of the Greek National Tourist Organization, including on-line brochures, slides, video clips and other travel related information. In addition to this web interface, an interactive TV browsing interface is also under development.
The background and expertise of database users has changed in the recent years. Most conventional database applications expect their users to have at least a minimum level of training, a general knowledge of the data contained in the application, and a relatively concise idea about what they want from the application. However, in an increasing number of situations users do not satisfy any of these prerequisites. A common example is the case of electronic store-fronts on the web. A travel agency for example can publish on the web its database of hotels, resorts, cruises, interesting sites, etc. Web users can then navigate through that collection and virtually visit the place that they want to go, check photos of the hotels and facilities, and even see a photo of the view from the specific room they wish to reserve.
While the idea sounds attractive its implementation has many problems. Presenting the database, in a traditional way, by using a combination of forms that allow users to specify what they want, does not work very well. Users will likely not understand many of the data attributes nor how data is distributed over the domain of a given attribute. For example, in a given travel database, there may exist thousands of Greek hotels with fax facilities or none at all. As a result of this uncertainty the user is forced through repeated trial and error attempts. Suppose a specific user requests information about inexpensive Greek hotels with fax facilities, conference rooms and pools. Simply returning the answer that no such hotels exist is not sufficient. The user would have to guess how to relax the query to get hotels that are even close to this description.
Similar problems exist in many consumer applications, for example, catalogs of available real estate properties or applications for locating specific products in an electronic mall. There are also many business applications that present the same challenges. Most corporations have a large number of disparate interfaces to allow their employees to find information about facilities, services, business forms, etc. For example, an employee may be looking for the location of the nearest color postscript printer with the smallest queue or trying to locate the phone number of somebody from the purchasing department responsible for the accounting procedures. Providing a general purpose yellow page directory that offers a unified interface to these multi-platform, heterogeneous databases is an attractive alternative to the haphazard maze of interfaces supported by businesses today. However, in designing such a unified browser, one encounters many of the same problems faced by electronic store fronts:
In this section, we briefly overview work that is related to ours in its goals. We consider two broad areas: hypertext-based systems for navigating data, and data analysis systems.
In order to meet the needs outlined above, many applications offer hierarchical navigation paths to individual pieces of data. When a schema is small, one can afford to manually create all needed links to the data. This approach fixes a set of paths that can be used to access the data. For large schema though, offering a navigational structure flexible enough to satisfy the needs of any user is not easy. In most cases, applications compromise by providing a fixed set of hierarchies that allow data browsing based on fixed groupings of specific attribute values. For our travel agency example, the geographical location is one attribute over which a navigation hierarchy may be constructed. This hierarchy may group attribute values by neighborhood, by city, and by country. A user can then navigate from countries to cities to neighborhoods. Unfortunately, such a solution is not flexible: for example, geography may not be the differentiating factor for some data sets or for some users, while price may be. Furthermore, the hierarchy divides into groups and subgroups the whole content of the database, not the specific set of data in which a user is interested. The compromise that most of the applications choose is to offer simple forms of querying based on keyword search as an alternative method to access the data. However, the two retrieval paradigms are not well integrated. Many web sites, for example the well known Yahoo site, support only this type of loose integration.
The area of On Line Analytical Processing (OLAP), which includes data analysis and decision support systems along with multidimensional databases, also deals with many of the problems we are addressing. [GBLP95,CC94] These systems group together subsets of the database and present aggregates and common features of the data items in each group. A user may drill down into a set of data by successively restricting one or more of the attributes, while the system presents aggregates and summaries of the underlying data at each step.
Both hypertext and data analysis systems have provided significant advances into the development of flexible navigation and presentation tools. However, many problems remain to be solved. In the next section, we describe our solutions that address the following important problems.
In this section, we describe the principles that underlie our approach to querying and browsing. We begin with a brief example illustrating our basic model. We then examine the principle concepts upon which our approach is based. In developing an integrated query and navigation model, we have built upon techniques from declarative query languages (including visual query languages [Cru94,VAO93] ) along with paradigms for navigating, summarizing and understanding data which are drawn largely from the arena of data analysis applications including multidimensional databases [CC94,GBLP95] and hypertext query interfaces [CT89]. Our approach permits both the use of conventional declarative queries and the use of navigational techniques, including drill down and roll up operators (explained below). The novelty of our approach stems from the seamless integration of these different data navigation paradigms and the incorporation of techniques for handling multimedia data.
Our navigation model permits users to interactively explore and analyze potentially unfamiliar data. For a novice user, this might involve the initial specification of an imprecise, high level query and the incremental refinement of the query using summary and aggregate information provided about the requested data. This style of interaction has been called drilling down in the data analysis literature [CC94]. As a simple example, suppose the initial query is specified declaratively through a simple visual query language. [3] For our travel application, a user may begin by entering a query requesting inexpensive hotels in Greece. To be effective, the result of this high level query cannot be a simple listing of the thousands of inexpensive Greek hotels contained in the database. Rather the answer is a summary of relevant information about inexpensive Greek hotels contained in the database. The summary information is designed to provide enough information to permit users to refine their requests to obtain the data of interest to them.
The presentation of summary information makes use of navigation hierarchies defined on domain values that can be used to aggregate information. In our example, a hierarchy may be defined over the location domain. This hierarchy may reflect a political division of locations into hierarchically structured regions such as cities, counties and countries. Summary information may then be organized according to some hierarchies that are of interest to the user. In our example, the query answer may indicate that there are 1,000 Greek hotels of which 500 are located in Athens, 100 in the Dodecanese Islands, 15 in Crete, etc. To provide this information, the query that is executed is not the user's original query, but rather an automatically rewritten query that returns appropriate aggregate and summary information.
Continuing the above example, a user may examine the node corresponding to the Dodecanese Islands, then examine one of these islands, Rhodes, in more detail. This style of navigation is very similar to traditional hypertext applications, and relies on the use of interactive visual metaphors for presenting the summary information. Summary information is used as a pointer for further navigation. The Rhodes node within the Dodecanese query page is a virtual link to more detailed summary information about hotels within Rhodes. In contrast to static hypertext applications, the structure of pages and links is not fixed. Rather, a query is issued to create the Rhodes page. This query is determined by the system using information about the current hierarchies as well as the user's interest. The query determines what summary information is presented and how it is organized.
In addition to this drill down style of navigation, a user may relax an over-specified query or incrementally change the requirements of a query. This mode of operation is similar to the roll up operators described in the data analysis literature [CC94]. In our example, after determining that the hotels in Rhodes are not of interest, the user may backup in the navigation to a higher level of abstraction - either in the same hierarchy used to drill down or in another hierarchy. For example, the user may indicate that she wishes to backup and see all inexpensive hotels in the Dodecanese, grouped not by geography, but by the type of the hotel. In general, a user may change hierarchies at any point. Changing a hierarchy, corresponds to altering one's perspective on the summarized data. This permits the user to gain additional insight into the available data.
The way in which information is ordered for presentation is particularly important within our navigational paradigm. Continuing the above example, suppose a user does not find any satisfactory hotels in Rhodes. Rather than returning to the last visited abstraction level, which presented information about all inexpensive hotels in the Dodecanese Islands, the user may want to see hotels in Greece that are close to Rhodes. Distance from Rhodes may be viewed an an alternative hierarchy with the special property that items within the various levels of the hierarchy are totally ordered. This hierarchy should then be used in presenting query answers and summary information.
Multimedia query operations in particular may introduce orderings that should be preserve when presenting information. In Greece, many hotels are Cycladic, that is, they have bright white exterior walls with windows and door frames painted in a single bright color --- often blue or green. A user may use an image operator to find Cycladic hotels, either by searching for pictures that closely match a canonical picture in color composition or by searching for pictures that have a specific percentage and special positioning of various colors. [4] Such operators return lists of answers ordered by the closeness of the match. Clearly, such orderings should be preserved when presenting query answers.
Given this basic style of interaction, we now describe in more detail the components of our approach.
As illustrated in our example, and as borne out by many multidimensional data analysis products, hierarchies specified over data domains can provide an effective mechanism for collecting and summarizing information about sets of data items. Our use of such domain abstractions differs from many standard techniques in the following ways.
Our interaction paradigm requires the ability to rewrite a user query into an incremental summary query. This entails: selection of appropriate summary information; selection of hierarchies for displaying information; and selection of appropriate levels with these hierarchies.
Navigation hierarchies may be selected by the user or automatically chosen by the system. A user may know that she wants hotels presented by geographic regions and ordered by price within each region. However, if the user does not have a preference on how data is to be aggregated and presented (or is unfamiliar with available hierarchies), the system may automatically select hierarchies that best characterize (or separate) the data. This functionality is imperative to permit the use of the interface by novice users.
Summary information may be presented for any group of hierarchies. For example, a user may wish to view information about a set of hotels according to both geography and price. For a given abstraction level within the geography and price hierarchies, a two-dimensional display may be used to present this information. Similarly, visual techniques for displaying n-dimensional spaces may be employed to present summary information along n different hierarchies. [5] The summary information itself may be information about the number of data items (count), or arbitrary aggregates applied to the data items. For example, a summary may include the number of total hotels in a given location within a given price range. Additional information, such as the number of Cycladic hotels, the average distance of the hotels from a beach, etc., may also be displayed for each grouping of hotels.
The navigation, structuring and presentation techniques are implemented as a set of Web server programs (CGI scripts) that communicate with a heterogeneous multimedia database. The programs translate user input into the appropriate navigational operation. This translation includes the query rewriting mentioned in Section 3.3. Rewriting may involve the invocation of a data mining module that determines appropriate hierarchies and summary information and formulates an optimal query rewriting. The rewritten query is eventually submitted to the database.
The database itself consists of several data repositories. An SQL server maintains all of the conventional record-oriented data about the application (for example, information about hotels, regions and sites of interest). Images, video clips and large passages of text are stored as files in the Shark video server [Has93]. The Shark server offers appropriate quality of service guarantees for real time video display and also doubles as a generic high performance BLOB (Binary Large Object) server. The image files stored in the Shark server may be processed using operators provided by QBIC [LBN+94]. These operators can be used to extract image features and query images by content, for example by shape, color and texture. Hierarchies, user-defined functions, and metadata may be characterized by a complicated structure and behavior. For example, a transitive closure operator must be available for querying stored hierarchies. ObjectStore [LLOW91], an object-oriented database management system has been chosen to store and manipulate this data.
The database management systems used in our implementation are inherently heterogeneous. Trying to manually handle such heterogeneity would be overwhelming [MIR93]. We rely on the Garlic [CHS+95] system to permit integrated querying and retrieval of data over these various databases and platforms. Garlic permits the development of a unified database schema and offers an OMG compatible interface capable of handling our complex and diverse data types. Garlic hides completely the multi-platform, heterogeneous nature of our databases and database management systems.
We are also developing an interactive TV (ITV) browser which is able to communicate with the web server just like a conventional web browser. The expected technical naivete of ITV users implies that ITV applications will be in need of effective and flexible navigation and presentation mechanisms such as those we are developing.
[2] Note that several data analysis systems do offer interactive visualizations, in order to facilitate the task of displaying alternative groupings. The difference is that for our applications every visualization has to be interactive.
[3] This type of interaction is not required. A user may use exclusively the navigational interface if desired.
[5] We have not developed any new visual metaphors, rather we have made use of many known visualization techniques.