The Alexandria Digital Library (ADL) is one of the six digital library projects funded by NSF, DARPA, and NASA. ADL's collection and services focus on information containing georeferences: maps, images, data sets, text, and other information sources with links to geographic locations. During this study period, three different user interfaces were developed and tested by user groups. User feedback was collected through various formal and informal approaches and the results fed back into the design and implementation cycle. This article describes the evolution of the ADL system and the effect of user evaluation on that evolution. ADL is an ongoing project; user feedback and evaluation plans for the remainder of the project are described.

Summarization of intermediary query result sets plays an important role when users browse through digital library collections. Summarization enables users to quickly digest the results of their queries, and provides users with important information they can use to narrow their search interactively. Techniques from the field of data analysis may be applied to the problem of generating summaries of query results efficiently. Such techniques should permit the incorporation of classification hierarchies in order to provide powerful browsing environments for digital library users.

Range sum queries on data cubes are a powerful tool for analysis. A range sum query applies an aggregation operation (e.g., SUM) over all selected cells in a data cube, where the selection is specified by providing ranges of values for numeric dimensions. Many application domains require that information provided by analysis tools be current or "near-current." Existing techniques for range sum queries on data cubes, however, can incur update costs on the order of the size of the data cube. Since the size of a data cube is exponential in the number of its dimensions, rebuilding the entire data cube can be very costly. We present an approach that achieves constant time range sum queries while constraining update costs. Our method reduces the overall complexity of the range sum problem.

This paper investigates load balancing strategies for clustered Alexandria digital library (ADL) servers. The ADL system, which provides on-line information searching and browsing of spatially-referenced materials through the World Wide Web, involves intensive database I/O and heterogeneous CPU activities. Clustering servers can improve the scalability of the ADL system in response to a large number of simultaneous access requests. One difficulty addressed is that clustered workstation nodes may be non-uniform in terms of CPU and I/O speeds. An optimization scheme is proposed in this paper to dynamically monitor the resource availability, use a low-cost communication strategy for updating load information among nodes, and schedule requests based on both I/O and computation load indices. Since the accurate cost estimation for processing database-searching requests is difficult, a sampling and prediction scheme is used to identify the relative efficiency of nodes for satisfying I/O and CPU demands of these requests. A set of experiments using the ADL traces have been conducted to verify the effectiveness of the proposed strategies.

No abstract available.

The Alexandria project has been initiated to build a digital library for map and satellite images.Designed for content-based retrieval, the relevant information in each image is encoded in the form of a multi-dimensional feature vector.Though representing images by feature vectors ~eatly facilitates user queries, indexing these vectors degrades performance when the number of dimensions is large.We consider 2 popular techniques (DFT and SVD) to reduce the dimension of feature vectors, and study their retrieval performance with respect to recall and precision.We End that though SVD generally out-performs DFT, DFT compares favorably in a limited range suitable for browsing large image databases.

A simple, exemplary system is described that performs reasoning about the spatial relationships between members of a set of spatial objects. The main problem of interest is to make sound and complete inferences about the set of all spatial relationships that hold between the objects, given prior information about a subset of the relationships. The spatial inferences are formalized within the framework of relation algebra and procedurally implemented in terms of constraint satisfaction procedures. Although the approach is general, the particular example employs a new ‘complete’ set of topological relationships that have been published elsewhere. In particular, a relation algebra for these topological relations is developed and a computational implementation of this algebra is described. Systems with such reasoning capabilities have many applications in geographical analysis and could be usefully incorporated into geographical information systems and related systems.

This paper provides a brief survey of the history, structure and functions of ‘traditional’ geographic information systems (GIS), and then suggests a set of requirements that large-scale GIS should satisfy, together with a set of principles for their satisfaction. These principles, which include the systematic application of techniques from several sub-fields of computer science to the design and implementation of GIS and the integration of techniques from computer vision and image processing into standard GIS technology, are discussed in some detail. In particular, the paper provides a detailed discussion of questions relating to appropriate data models, data structures and computational procedures for the efficient storage, retrieval and analysis of spatially-indexed data.

This paper describes the architecture and working of a recently implemented knowledge-based GIS (KBGIS-II) that was designed to satisfy several general criteria for GIS. The system has four major functions, query-answering, learning, editing and training. The main query finds constrained locations for spatial objects that are describable in a predicate-calculus based spatial object language. The main search procedures include a family of constraint-satisfaction procedures that use a spatial object knowledge base to search efficiently for complex spatial objects in large, multi-layered spatial data bases. These data bases are represented in quadtree form. The search strategy is designed to reduce the computational cost of search in the average case. The learning capabilities of the system include the addition of new locations of complex spatial objects to the knowledge base as queries are answered, and the ability to learn inductively definitions of new spatial objects from examples. The new definitions are added to the knowledge base by the system. The system is currently performing all its designated tasks successfully, although currently implemented on inadequate hardware.