Spatial Web Navigation with Perl

Kostas Pentikousis and Robert Rothenberg
Summer, 2002

Navigation is about wayfinding... It's about looking at the whole.
-- Clement Mok

In the year that Web Services become the latest IT catch phrase, discussing "merely" delivering dynamic Web pages might seem old-fashioned. Dynamic Web content is ubiquitous today. In fact, it is relatively easy to create Web pages that are based on frequently updated databases using, for example, the CGI and DBI Perl modules. Sometimes, though, the site's content has some underlying characteristics or relationships that are not sufficiently illustrated using solely a textual representation.

Consider, for example, the case of construction projects. Knowing that there is some major construction in a particular area, say at the intersection of Abbey Road with Alphabet Street, can be sufficient for people who are familiar with the region, but it is far less useful to many who are simply passing by the area. Construction at the aforementioned intersection may, for example, interfere with traffic on Mullholland Drive, and this information is not conveyed using solely a text-based presentation. In this case, Web developers can deliver more information by providing a map of the area along with the construction details. This article illustrates how such dynamic maps can be created using Perl. However, the essence of this work is about how Web architects can enhance the navigation of a site by capitalizing on spatial characteristics or attributes of the site's content, and use images to deliver additional information.

Hard Hat Required

The Stony Brook University campus has been undergoing fervent construction since its establishment more than four decades ago. There are scores of major projects ranging from office and classroom rehabilitations to new building construction to landscape improvements. A list of these projects used to be published on the Web by the department managing them, but it soon became clear that this list did not reveal the whole picture. Our clients were interested in presenting not only what was under construction but where as well. Of course, any solution should permit the user, regardless of her familiarity with the campus geography, to navigate in an intuitive manner and easily determine which areas are undergoing construction.

The trivial solution to this problem is to use some image manipulation software to edit a campus map, manually overlay project indications on it, and use a static image map to link areas affected by construction to pages with further project information. There are several problems with this approach. First, it is a maintenance nightmare, because any updates require changing the projects map, the associated image map, and the corresponding pages containing the project details. Second, due to the size of the campus a reasonably detailed map is not possible to fit within a single "screen" (that is, without requiring the user to scroll horizontally or vertically). Therefore, a static solution would require us to crop a more detailed map and create a relatively large subset of possible zoomed-in views of the campus map that could then be associated with locations on the less detailed campus map. It quickly became obvious that this process would be too convoluted and a better solution was needed.

Given a database with all the required information about the projects (see "The Projects Database" section), including the location, description, and timeline for each project, we can associate project locations to coordinates on the map and dynamically place "under construction" icons on the map. This way, changes in the database (e.g., the addition of new projects) are automatically reflected on the map. Moreover, because the creation of the map is done dynamically, the map size is no longer an issue; the user can zoom in from a smaller and less detailed (overview) version of the map to a more detailed one. The remainder of this article explains how this can be done using Perl.

Web Site Overview

The Web site front page is built around a small map, an aerial view of the Stony Brook campus. The page also shows other project-related information including a dynamically updated "featured projects" list (Figure 1). Notice that the dimensions of this overview map are chosen so that it fits in a single "screen".

The aerial map of the campus (overview map) on the front page is a server-side image map. Clicking on any point on the map allows the user to designate an area of interest, which will be "searched" for campus construction projects. The point coordinates (on the image map) are sent to the Web server, where they are processed by a script called zoomIn.cgi. Figure 2 illustrates this process in terms of HTTP requests and replies between the user's browser and the Web server that relate to this discussion. It does not include requests and replies for other, peripheral images of the returned page.

After parsing the browser's request, the script returns a page that contains a more finely detailed map with distinct "under construction" (UC) icons overlaid on it (see Figure 3). These icons play a dual role. On one hand, they pinpoint project locations on the map, and on the other, they form clickable, "hot" areas in the client-side image map. A sidebar with the corresponding project descriptions is also included in the page. The user can click either on an icon on the map or the description of the project within the sidebar to see more project details.

As mentioned already, the list of projects in the sidebar and the icons on the map are produced based on the Cartesian vector (X, Y) on the overview map (the point on which the user clicked). This list must include all projects with locations inside a rectangle (called a bounding box or frame) with its center at (X, Y). To create this list, we must determine which projects have locations in the frame. This must be done in two different scripts: a) in zoomIn.cgi to generate the client-side image map, and b) in crop.cgi to overlay the icons on the detailed aerial view.

Note that it is considered a good practice to add extra path information containing the proper file extension when generating images dynamically (e.g., "/crop.cgi?160,160/dynamap.jpg") to accommodate Web browsers that use the file extension instead of the MIME type to determine which type of image is being transferred (Guelich, Gundavaram, & Birznieks 2000). However, this may not work on some Web servers such as IIS and current versions of popular browsers interpret image MIME types correctly.

A Note on Client-Side and Server-Side Image Maps

Client-side image maps are defined so that all the information needed to define clickable areas is sent to the browser. In general, client-side image maps are preferred over server-side image maps, because there is no need to communicate with the Web server to figure out whether a given area of the image map is "hot". Client-side image maps can lead to faster response times and bandwidth savings, especially if the user fails to click on a hot area of a server-side image map; this cannot be the case with client-side image maps (Wallace 1999).

Furthermore, client-side image maps can be created so that they appear more user friendly. For example, after parsing the (client-side) image map created by zoomIn.cgi, a browser becomes aware of all the clickable areas (UC icons) and can display visual cues with the project name/location when the user hovers with the mouse on top of them. Some browsers will pop up a small window ("balloon help"), which will display the project description. This cannot be the case with server-side image maps because the definitions of the clickable areas are stored only at the Web server.

However, client-side image maps are not always the solution. The front page utilizes a server-side image map because every single point on the map is a "hot" area. This functionality cannot be achieved in an efficient manner with a client-side image map. Note that this is not the case with the detailed view of the campus (Figure 3) where only certain parts of the map contain projects. An additional benefit from using the server-side image map is that certain areas of interest can be bookmarked for future visits, because the URL contains all the information needed to locate projects in a particular region (e.g., http://some.site.net/zoomIn.cgi?160,160).

Design and Implementation

One of the first choices we made while designing the Web site was the kind of map to use. We decided that an aerial photograph was preferred over, say, a line drawing (e.g. produced by CADD software). The main advantage of an aerial map is that it can easily be resized while still being readable, whereas scaled down line drawings tend to become cluttered and difficult to read. Moreover, an aerial map has many geographic features (such as wooded and landscaped areas, fields and plazas, etc.) not available on the line drawings; features like these make user navigation easier.

Our programs use the Perl DBI module (Descartes & Bunce 2000), to get the information from the projects database, and the GD graphics module to create the images. GD offers the basic building blocks for manipulating images and is well-suited for our purposes because it introduces lower overhead than other, more powerful but more resource-hungry, image manipulation Perl modules (such as Image::Magick).

Looking Closer (a.k.a. Zooming In)

The application we present has at its cornerstone a single, large (1950 x 2380 pixels), relatively high-detail aerial photograph of the Stony Brook University campus. We have resized this photograph to create a smaller version (sized at 400 x 488 pixels), which is used as the overview map on the front page. The method we use is illustrated in Figure 4, which presents the transformation needed to zoom in from an overview map of New York State to a specific area (Eastern Long Island) on the large map.

To share some common code and data among the different scripts used in the Web site, we wrote a small Perl module for this application. (Alternatively, we could have implemented the same functionality using one larger script with several input parameters, but we found this less elegant.) Among other things, the module defines some constants such as the aerial photograph sizes (see Listing 1). Although the GD module provides the means for reading image sizes dynamically, we opted not to use them. Aerial photographs of the campus are not produced more often than once per year, so we felt that it would be wasteful to open these images solely for reading their sizes every single time the scripts are run. Using constants, instead, saves CPU cycles and leads to improved performance. Given these constants, we calculate the relative aspect ratios between the two images so we can project from the small map to the larger one (as illustrated in Figure 4).

The transformation illustrated in Figure 4 is performed as follows. First, the coordinates from the image map are extracted from the HTTP request using the getImageMapCoords() subroutine (Listing 2), and then the function named getZoomedInCoords() transforms this pair of coordinates from the small image to a quadruple containing the top-left and bottom-right coordinates of the bounding box (or frame) in the larger image (Listing 3). This frame contains the area of the large image that is to be cropped (and is indicated with a red line in Figure 4). This cropped part of the large image is later used as the basis for creating the image map included in Figure 3.

Then, using the top-left point coordinates returned by getZoomedInCoords() and the image crop size constants, we crop the part of the map that is of interest to the user. To accomplish this, we first create a new GD image object and copy there the contents of the bounding box (Listing 4).

The Projects Database

After cropping the image, we need to determine which projects are located in the area under consideration. We implement this by querying our projects database using the DBI module. The ER (Entity Relationship) diagram of the projects database is shown in Figure 5. The Map table contains several campus locations; it is not exhaustive, but can easily be extended as needed. Given the high resolution of the detailed map, we are able to assign unique (X, Y) coordinates to all meaningful locations to avoid overlapping UC icons. The ProjectsList table contains project-related information, such as the project name, description, status, etc.

Extracting Project Information from the Database

We use getIconLocationsByCoords() which, given a set of defining coordinates of a bounding box, returns a list of map locations within the bounding box that are associated with projects marked as "active" (Listing 5). This list of locations is used to overlay the UC icons on the zoomed-in version of the map and to generate the HTML code defining the active areas on the image map.

Adding the Icons

After calling getIconLocationsByCoords() in crop.cgi to get the list of projects in the region, we overlay the UC icons on top of the cropped image produced by Listing 4 as shown in Listing 6.

Creating the Image Map

Finally, we call getIconLocationsByCoords() in zoomIn.cgi to get the list of projects and create the HTML code for the client-side image map (Listing 7); the code to create the sidebar is straightforward and is, therefore, omitted.

Performance Considerations

Our aerial views are photographs, which are stored, in general, more efficiently using the JPEG format as opposed to, say, PNG. Note that the GD module no longer supports GIF due to patent issues. Therefore, it was clear that the images sent to the user's browser (i.e., the output of crop.cgi) should be in JPEG encoding to allow for shorter download times. On the other hand, it was not so clear whether we should store the detailed aerial view in JPEG, too. In terms of file sizes, JPEG proves the most efficient format while maintaining high image quality. For example, the detailed aerial photograph stored in GD2 "native" format is eight times larger than in JPEG. GD2 is a newer native, optimized format of the GD module that uses compression (as opposed to the older GD format). Table 1 presents the file sizes produced by different image encoding schemes. The smaller file size, which provided a good image quality, was produced using JPEG with a Paint Shop Pro compression factor (CF) of 65%. Higher CFs reduced image quality, and lower CFs increased file sizes.

Smaller Ain't Better

Since JPEG proved the most economical in terms of file sizes, we thought we had a winner. But what about the cost of decompressing the JPEG image to manipulate it within crop.cgi, you ask. Several tests during the summer of 2000, when the first version of the site was released, showed that the JPEG version of the detailed aerial view led to better user-perceived response times -- at least under our hardware and software configuration. Our guess, at that time, was that the cost of reading larger files from the disk outweighed the effort to decode the file on our Web server, and this was reflected in the server logs.

We had this impression until we began writing this article. In fact, we were about to gloss over this issue, because we thought it was self-evident, an undeniable truth, that JPEG was much better. But when we once again took real measurements of the time needed to run crop.cgi, we were shocked: crop.cgi was performing much worse when the detailed map was stored in JPEG than when it was stored in GD2 format. More rigorous benchmarking proved that decompressing the JPEG image took a high toll on performance: crop.cgi needed 289% (!) more time to successfully complete a browser's request if the detailed image was stored in JPEG than in GD2.

To measure with relative accuracy the performance of crop.cgi, we copied the part of the code responsible for loading the detailed image (see Listing 3) to another file and executed batches of 100 runs. Figure 6 presents the averages calculated based on these runs. We ran the benchmark on three different machines during off-peak hours, storing the detailed image on a local hard disk. System A is the newest one, and is not currently used in production. System B is an older machine, and was used while developing the original application code. System C is a relatively busy internal server, which is probably why its performance lags behind that of System B, despite the fact that it is a higher class machine.

Note that the averages presented in Figure 6 were calculated based on execution times measured with the Time::HiRes module. Single runs and batches of 10 runs were also performed, and the averages were very close to the ones presented in the figure. This leads us to conclude that the I/O penalty for the larger images is not as severe as the cost of JPEG decompression.

We are not sure why our two-year-old measurements could not be revalidated. Although we did not then perform the rigorous benchmarking we did this time, the crop.cgi total execution times were reversed in tests conducted while preparing for this article. Of course, we are currently using a newer version of the GD module (and a different Perl version as well), so maybe that's where the gains come from. Or, maybe it's because we are now running background disk defragmentation software on our servers, which, in fact, are running more applications and serve more users than two years ago. Or, maybe, because a new Monachus monachus baby was born (Monachus monachus is a Mediterranean seal that has, unfortunately, made it to the endangered species list). The truth is, we are not sure why JPEG is now performing so badly, but we are very happy we found out!

Improving Performance

The image manipulation done by crop.cgi is the most computationally intensive part of our application. In fact, a large part of the total execution time of crop.cgi is due to loading of the detailed image. Using the GD2 format proves to be the most efficient format in terms of execution time, across three different system configurations, despite the fact that it leads to much larger file sizes.

Moreover, as it can be surmised from Figure 6, without accounting for image loading, the rest of the code in crop.cgi requires about 1.3s to execute (on System B). Faster processors, larger memory sizes, and faster, unfragmented hard disks can improve performance by up to 250% (System A vs. System B). Alternatively, we can use a secondary Web server that delivers only the cropped images -- a technique referred to as image farming (Wallace 1999). If the secondary server is not required to perform other heavy duty tasks, performance can improve by almost four times (System A vs. System C).

User-Perceived Performance

A design choice that can affect performance significantly involves which images are created dynamically and which are static. For example, we could have used a single, highly detailed, aerial image for both the front page and in crop.cgi. Using this image, the script on the front page could dynamically resize the image before sending it to the browser. We thought this was not a sound choice and preferred to create a smaller version of the aerial photograph off-line, thereby saving an image resize operation every time the front page is requested. Keeping the overview map static allows Web browsers and proxy cache servers (if any) to cache the image, thereby saving system and network resources and leading to smaller response times. Of course, we do have this "luxury" because, as mentioned previously, the campus aerial photograph does not change over the course of several months. Other applications may require a different approach.

As a last note, it is fundamental to use the WIDTH and HEIGHT attributes of the <IMG> element in the HTML code produced by zoomIn.cgi. Doing so allows browsers to allocate the space needed to layout the image and display the rest of the page while the cropped image is being downloaded.

Summary and Future Work

This article illustrates how to use Perl to create dynamic spatial navigation systems, and in particular, geographical representations of (on-going) construction and rehab projects. Our database-driven application conveys not only textual and visual information about projects, but spatial as well. It requires minimal maintenance by the support staff (that's us!), because updates in the projects database are automatically reflected on the site. Last but not least, we believe it's very user friendly, enabling the user to virtually navigate the projects database without even realizing it.

Although it may seem that the particular application was in and of itself well suited for spatial navigation, we feel that the same design principles apply to many other applications. For example, an application that lends itself very well to spatial Web navigation is a network management site. Code similar to the one presented in this article can be interconnected with a database and network monitoring tools, such as MRTG, to create a Web interface to monitor large networks in a intuitive way. Other applications are only limited by the reader's imagination.

Future enhancements include: a) the use of different icons to indicate the status, type, and scale of each project; b) the addition of more media-rich information about a project, including still pictures, live Web cameras covering construction sites, links to Web sites maintained by other agencies with more project details; and c) connecting the projects database with the project management system in real time.

Acknowledgements

We thank Yimeng Sheng for assistance in developing the Web site prototype and Thanasis Kokkinos for proposing a more efficient way to query the projects database (Listing 5).

References

Descartes, A., and Bunce, T. Programming the Perl DBI. O' Reilly and Asssociates, 2000.

Guelich, S., Gundavaram, S., and Birznieks, G. CGI Programming with Perl. 2nd Ed., O' Reilly and Asssociates, 2000.

Wallace, S. P. Programming Web Graphics with Perl and GNU Software. O' Reilly and Asssociates, 1999.

Kostas is a computer scientist who fell in love with Perl in the summer of 2000, while working for Systems Management and Support, Stony Brook University. He thinks that this is the appropriate place to thank his co-author for introducing him to Perl. You can reach him via the Web at http://www.cs.sunysb.edu/~kostas.

Robert is a computer programmer with Systems and Management Support, Stony Brook University. He was first corrupted with the joys of Perl programming in 1995. He has written several modules that are available on CPAN. You can reach him via email at Robert.Rothenberg@StonyBrook.edu.