2. Our Innovations in Detail

In this section we present the two approaches in more detail. We also compare the two new approaches in terms of their space and time utilization.

2.1. The Post-Fetch Approach

There is only a finite number of queries that can be formulated over a given Query Preview Panel. Hence, we can compute the answers for each one of these queries before the actual query formulation time and submit the pre-calculated results upon request. For the Query Preview Panel, the desired results are the new settings of the bars.

First, the users click on bars indicating that they want to include those bar values (or exclude) to their selection. This, in return, changes the set of selected bars. Using the selections, the Query Preview Panel displays the new settings and the histogram information for the rest of the bars. If we calculate the answers for each one of these queries the update operation can be transferred into a table look up operation from a set of pre-calculated answers (instead of a query over the database). Therefore we fulfill the need for not computing the answers for queries at run-time. Instead, the pre-calculations can be done off-line and stored on a secondary storage device. On the other hand, the number of possible queries can become so enormous that it might become unwise to download all the possible answers. The reason for this is that the number of possible queries is proportional to the granularity of the attributes of the Query Preview Panel with an exponentially growing function (i.e., for each bar of each attribute, we have to duplicate and reformulate all the previously calculated bar settings).

Therefore, only the queries that users make should be downloaded at run-time. This approach is named as the post-fetch approach. In this approach, when a new query is formulated a request from the server for the new bar settings is made. Then the server sends the settings for only the current query. Therefore, we only communicate from selection to selection with this scheme. The set of all possible queries and answers are stored as a look up table on the server. The selections of the bars are used to address this table. Figure 3 shows the communication scheme for this approach. We assume that the server has the secondary storage capacity for storing all the pre-calculated answers.



Figure 3: The communication scheme for the post-fetch approach.

2.2. The Pre-Fetch Approach

The pre-fetch approach uses the same idea of pre-calculating the answers for all the queries that can be asked on a preview panel. On the other hand, it uses a different communication scheme.

We have noticed in our early studies that the designers of the Query Preview Panel can bring some restrictions to the possible number of bar selections with out altering the usage of the user interface beyond a certain extent. In many cases, restricting the number of areas selectable from a map might not effect the system usability. But, these restrictions will decrease the total number of pre-calculated answers for that preview panel.

Hence, we propose a new approach for the case where the number of selections is restricted. The pre-fetch approach takes advantage of the reduced number of selections and downloads the set of all possible bar settings for all the possible bar selections before users start querying on the Query Preview Panel. The communication scheme for this approach is given in Figure 4.



Figure 4: The communication scheme for the pre-fetch approach.

Obviously, there are advantages and disadvantages for both of these approaches. We recommend the usage of these approaches under different circumstances. The following section compares these two approaches theoretically in terms of their time and space utilization.

2.3. Comparison of the New Approaches

Depending on the bandwidth of the network between the server and the client the performance of the two approaches might vary a lot. Figure 5 displays the comparison of the two approaches in terms of their time and space utilization along with the previous implementations.

Previous methods do not pre-calculate bar settings and can not transform any multi-valued data set into any form of an n-dimensional array. Instead, they transfer the data itself over the network. The bar settings for a given query are found during the execution time with a query that is run over the database.

Previous

Approaches

Post-Fetch

Approach

Pre-Fetch

Approach

Querying

Time

Cost of

Searching the

Database

Answer is Known

(Needs Connection

to the Server)

Answer is Known

(Kept in the Main-

Memory of Client)

Client

Main-Memory

Utilization

Keeps the

Data in Main-

Memory

Nothing is

Stored in the

Main-Memory

Keeps the

Pre-Calculated

Answers

Setup

Time

Transfer Time of the

Data Set

No Setup

Required

Transfer Time of the

Pre-Calculations

Server

Disk

Utilization

Keeps

Data on

Disks

Keeps

Pre-Calculations and

Data on Disks

Keeps

Pre-Calculations and

Data on Disks

Data

Preparation

Time

None

All the

Selections are Used

(Lengthy

Pre-Calculations)

Some of the

Selections are Used

(Shorter

Pre-Calculations)

Restrictivity

Level of the

Preview Panel

None

None

Some

(Designers Choice)

Figure 5: Comparison of the approaches (previous, post-fetch, and pre-fetch).