NSF Program: CISE (IRIS), NSF 03-141
Award Number: IRI94-11330
PI Name: Terence R. Smith
Period Covered By This Report: 08/01/97-10/31/97
PI Institution: UCSB
Date: November 1st, 1997
PI Address: Department of Computer Science, UCSB, Santa Barbara, CA 93106
1.0 Summary of Overall Progress - The Information Systems Team continued its work on multi-dimensional indexing, with a focus on concurrency control as it relates to enhancing index performance in a multi-user environment. Its proposed a new scheme Copy-based Concurrent Update Sche me increases throughput by 50% compared with the CGiST technique. In relation to content-based retrieval of images, dimensionality reduction techniques using SVD were found to be 45% more accurate than those using DFT and the team has incorporated SVD in a dynamic index structure, which reduces re-computation overheads by a factor of 25. The team has successfully developed new disk allocation policies for two-dimensional data which are superior to existing approaches. The image processing team has continued its investigation of efficient implementation of lossless multiresolution image compression schemes; extensions to color and multispectral imagery; and digital watermarking and data hiding using wavelet transforms. The Parallel Processing Te am has conducted research using the CONVEX shared memory machine of the US Navy. A strategy was developed to monitor the performance of subcomplexes and perform load balancing between subcomplexes. The team's experiments also show that resource mo nitoring is important to gain performance. The Geospatial Information team has implemented it fuzzy geographic footprints for on-the-fly registration of geospatial objects in a variety of clients, including clients mounted in moving vehicles.
In preparation for the impending Fall Release of the ADL system, the Evaluation Team continued to work with the Interface Development Team in the development of the new user interface. A second internal evaluation period during the week of October 20th was held and new scenarios were designed that ran twenty-one testers through the new features of the interface and the expanded collections available. New features include user registration and an exit poll to find out more about how the session went.
The ADL Advisory Board met on October 6, 1997 and the ADL project held a two-day system design review in which seven participants from academia and industry reviewed the ADL system architecture.
2.0 Management Issues
2.1 Alexandria Advisory Board - A meeting of the Alexandria Digital Library Advisory Board, chaired by Jeff Dozier, took place on October 6, 1997. ADL staff gave presentations of the status of their research and development of the ADL operational system. The board gave the follo wing recommendations regarding the focus of ADL research efforts:
In addition, the board made the following recommendations regarding development of an operational ADL system:
2.2 Personnel - Dan Andresen continues to work with the Parallel Processing Team while he began an appointment at KSU as an assistant professor. Students who worked on the team were Huican Zhu and David Watson.
3.0 Research Progress and plans
3.1 Information Systems Team - The team continued its work on multi-dimensional indexing, with a focus on concurrency control as it relates to enhancing index performance in a multi-user environment. Current work on R-link trees and concurrency control in GiST (CGiST)structures ha ve the drawback that multiple index nodes are locked during updates. Such locking limits the concurrency in the system and lower index throughput. We proposed a new scheme, called Copy-based Concurrent Update, to reduce such blocking overheads. Experi ments on a shared memory multi-processor on image texture data indicated 50% higher throughput using the proposed technique in comparison to the CGiST technique.
Content-based retrieval of images is an important application of high-dimensional indexing. Indexing high-dimensional data using conventional multi-dimensional structures such as the R*-trees and the SS-trees suffer from the drawback that query perf ormance degrades due to (1) overlapping index regions, and, (2) high dimensionality of the data. Dimensionality reduction has been proposed as a solution to this problem. Although such reduction improves query performance, it introduces a loss of acc uracy in query results. The team examined two different dimensionality reduction techniques one using SVD and the other using DFT. The team observed that the query results using SVD are 45% more accurate than those using DFT. Based on these results, t he team has developed novel techniques to incorporate SVD in a dynamic index structure. The main idea is to approximately estimate SVD-transform using the index regions in an index structure instead of using the entire data. This reduces the overheads of re-computation without compromising on query accuracy. In our experiments on real image data, the approximate techniques reduced the re-computation overheads by a factor of 25.
In relation to the development of new disk allocation policies for two-dimensional data, it has been shown that strictly optimal solutions to the problem of declustering two-dimensionally tiled data onto multiple I/O devices (possibly disks) in orde r to achieve maximum parallelism for rectangular queries, do not exist, except for some special cases. We have developed new allocation techniques that achieve very good performance in a general setting. These techniques are superior to the existing a pproaches especially for the cases where no strictly optimal solution exists. In relation to impact of media exchanges in robotic storage libraries, we tested an assumption made in an earlier paper (Scheduling Tertiary I/O in Database Applications) th at since the cost of exchanging media (tapes or disks) in robotic libraries is so high, it would be beneficial to eliminate exchanges as far as possible. We showed that though the assumption is not valid all the time, it is so most of the time. Also t he gains obtained by not making the assumption are small whereas the resulting computation is much more intense. This paper was submitted to IOPADS 97.
In relation to interoperability and distributed processing, the team has been developing tools and frameworks to distribute processing of objects across a network. The StratOSphere distributed object system permits applications to be relocated and migrated to remote sites. The team has defined several layers of interoperability, and developed the interfaces at each level.
In relation to a new generic indexing technology for digital library support, a new, three-year NSF-funded research project began on the above topic with P.I. Michael Freeston and Co P.I. Terence Smith. The objective of the project is to develop, di sseminate and exploit a series of recent advances in database index design by the project's P.I. The technology is potentially applicable in a wide variety of contexts, but the immediate application focus of the project will be ADL. The relationship w ith ADL is highly synergistic: we aim to use ADL as a testbed for the technology, and to use the technology to improve the performance of ADL. ADL provides a challenging testbed for any attempt to improve indexing methods, since it involves very large data sets, composed predominantly of geo-spatial data and images, but also demands efficient text retrieval techniques.
The project has begun with a new implementation of BANG indexing - a multi-dimensional tree-structured indexing technique based on a design developed by Freeston ten years ago. The motivation for the original design was the need for an indexing tec hnique to support the integration of deduction rules into large-scale relational database systems. Since then it has been theoretically generalized to the indexing of any complex structures which can be expressed as directed graphs; and a new tree stru cture has been developed (the BV-tree) which makes B-tree like worst-case performance characteristics possible in n dimensions. It is our intention to test these theoretical advances in practice, with the overall aim of developing a new, generalized i ndexing technology. However, the current implementation is based on a conventional balanced tree, so that it can be used as a yardstick by which to measure the performance of a later implementation based on the BV-tree.
3.1.1 Research Plans of Team for Next Three Months - With respect to multi-dimensional indexing, the team will investigate SR-trees, which are hypothesized to combine the merits of the SS-trees and the R*-trees for indexing high-dimensional data. It has been shown that this combination outperforms bot h SS-trees and R*-trees, despite its higher storage costs. Since the storage cost -- specifically the capacity of tree nodes -- has a direct impact on query performance, we are examining how to increase node capacity thereby improving query performa nce. Most reported work on concurrency control in index structures assume a mixture of updates and range queries. For high-dimensional index structures, however, nearest-neighbor queries may be more appropriate than range queries. The team is examining how to efficiently support nearest-neighbor queries along with concurrent updates in high-dimensional index structures. To our knowledge, there is no work reported on this problem. The team will spend 3 months designing an optimized index structure fo r high-dimensional data and 6 months investigating concurrency control techniques for update and nearest-neighbor queries in high-dimensional index structures.
In relation to disk allocation policies, the team will evaluate the performance of declustering schemes with real disks. In relation to interoperability and distributed processing, the team will continue to develop further programs to process and disp lay the Alexandria collection of geographical data and produce a testbed that demonstrates the benefits of distributing processing and extending functionality of Alexandria objects. The team will also develop a new generic indexing technology for DL support, concentrating on spatial point and object indexing, since this is a functionality of key importance to ADL. We are currently engaged in preparing benchmark tests to compare the performance of this new version of BANG indexing with that of B- trees and R*-trees.
The team is also building an interactive website for the project, where it will publish
3.2 The Image Processing Team - The image processing team has continued its investigation of efficient implementation of lossless multiresolution image compression schemes using average interpolation filter banks. Extensions to color and multispectral imagery is also being studied. Digital watermarking and data hiding using wavelet transforms is being investigated as well. Both watermarking and data hiding are important issues when digital media is distributed over the internet. In collaboration with a local DSP company, the image segmentation algorithm based on edgeflow technique developed at UCSB is being ported to a DSP environment. UCSB has filed for a provisional patent on this algorithm. On request the code is also being distributed to other researchers in computer vision (th ese include JPL, UCSD, and Stanford University). JPL researchers have reported encouraging results on some of the recently acquired MARS imagery. The edgeflow based segmentation is now being extended to spatio-temporal segmentation of video images.
3.3 The Parallel Processing Team - The team has conducted research in the Navy CONVEX shared memory machine. For the shared memory machine, CPUs can be partitioned as subcomplexes and normally different users access different subcomplexes based on the work load needs. A strategy was developed to monitor the performance of subcomplexes and perform load balancing between subcomplexes. If all CPUs are clustered as one subcomplex, then OS scheduling will dominate the optimization. Our analysis shows that our scheduling outperforms the CONVEX OS process auto-scheduler substantially if we partition the system into several subcomplexes. Load balancing issues have been previously studied extensively, but we think many of previous work are not fully implemented, and experiment re sults are conducted mainly using simulation. Our analysis based on real-world experiments motivates us to develop new techniques that work in practice. Our experiments also show that resource monitoring is important to gain performance.
The team has installed the ADL server on our local Ultra-SPARC SCI cluster. Our goal is to evaluate the performance of ADL in the presence of a large number of concurrent accesses and improve the performance using SWEB. Currently the team is in the process of gathering test data and simulating the real workload. Different WEB servers are being profiled, and the impact of caching and fast I/O is being examined. The team expects to develop some reasonable evaluation results after this fall.
3.3.1 Research Plans of Team for Next Three Months - The team will evaluate the performance of an ADL server in responding the selected workload. Develop a workstation cluster environment as a cooperative ADL server farm. Incorporate/extend scheduling and caching techniques for such an environment.
3.4 Geospatial Information Team - Research continues on the definition of fuzzy geographic footprints for both information objects and queries. A paper on ADL work in this area is nearing completion.
Problems associated with on-the-fly registration of geospatial data sets, required for successful integration of data in ADL, are being studied, in part under a new grant from NIMA, and in part through funding from Caltrans and the US Department of Transportation. These methods are being studied and implemented in a variety of clients, including clients mounted in moving vehicles, where retrieval of information from distributed sources is essential to effective navigation.
The sponsorship of a study of the concept of a "geolibrary" by the Mapping Science Committee of the National Research Council is confirmed. Goodchild and Buttenfield are members of the core planning group. The objectives of the effort are to define a vision for future dissemination of geospatial and related data, and to identify the associated research and development issues. A workshop of 50-100 people will be convened early in 1998, and the effort will lead to a published report of the NRC.
3.4.1 Research Plans of Team for Next Three Months - The team will continue work with on-the-fly registration of geospatial data sets, required for successful integration of data in ADL.
3.5 User Interface Evaluation Team - The UCSB Evaluation Team continued to work with the Interface Development Team in the development of the new interface; the interface was reviewed at weekly meetings and comments given to the Interface Development Team.
A second internal evaluation period during the week of October 20th was held and new scenarios were designed that ran testers through the new features of the interface and the expanded collections available. New features include user registration an d an exit poll to find out more about how the session went. Twenty-one people participate in the evaluation in one-hour sessions. A report of the results of the evaluation was prepared and made available to the Implementation Team.
The Colorado team ran a focus group session in September, to evaluate the new interface design. Results of the focus group were submitted and will be integrated with the UCSB results quickly. The staff intend to run another focus group session in N ovember. We have been approached by Professor Clayton Lewis, an internationally recognized interface design and HCI researcher, about running focus groups on the new interface with his graduate students, who have formal training in think-aloud/talk-al oud protocols. System designers at UCSB asked that these focus group sessions be delayed until November, and Clayton Lewis is still willing to run the evaluation.
3.5.1 Research Plans of Team for Next Three Months - The Colorado team plans to follow on the user pattern modeling, we will continue the disaggregation analysis, which continues to progress. Reitsma, Tsou, and Buttenfield will work on this effort.
In preparation for monitoring transaction logs for the new JAVA-based interface, the UCSB system developers have implemented JAVA based transaction logs. Following release of the new interface, Tsou and Buttenfield plan to spend a week at UCSB workin g out final strategic details.
To follow on the georeferencing project with the Denver Public Library, GPS positioning of individual photographs for the pilot group is complete. GIPSY is operational, and probabilistic coordinates will be generated before the end of the year.
4.0 ADL System Development Progress and Plans
4.1 ADL system design review - The Alexandria Digital Library System Design Review was held October 7-8, 1997. The purpose of this design review was to (1) evaluate the ADL system architecture (e.g., does it meet our objectives? is it scalable? is it distributable?), and (2) eva luate the ADL architecture's current implementation (e.g., our COTS selections.) This review did NOT address system requirements, user interface design or usability, or ADL's information content. The intent was to focus on the ADL system architecture , making the most of the reviewer's expertise in large-scale, distributed information systems.
4.1.1 ADL Design Review Participants -
Chaitanya Baru - San Diego Supercomputing Center
Jim Davidson - Digital Cities
Bob Evans - U. Miami
Jim Gallager - Consultant to URI (DODS)
Thor Heinrichs-Wolpert - Oracle
Steve Marley - EOSL (EOSDIS)
Bill Weibel - UCLA
4.1.2 Summary of Design Review comments/recommendations: - ADL project research focus should be on issues related to DL interoperability (for example, ADL could contribute to Dublin Core development by providing clarification of coordinate attribute).
Technical focus of ADL system development should be:
1) Pursue spatial data indexing and result ranking (classes of spatial data: point, etc)
2) Query language semantics (Seek out complementary research on query languages rather than reinvent wheel)
3) Exploration of "crawler model" (i.e., ADL as geospatial "AltaVista")
4) Explore spatial extensions to text search, instead of reinventing the wheel, work with existing vendors, such as the PLS group.
5) Define success criteria for ADL fall release and subsequent releases.
Possible architectural trouble spots include:
-security
-performance
-distributability
-query language
Winning aspects of the architecture include:
-"Search Buckets" approach
-Asynchronous searches (buffering between client and server)
Attention needs to be paid to potential productization of ADL components,
including:
-GUI
-map browser
-catalog
-gazetteer
-or potential replacement w/ vendor equivalents
ADL scope/users should be more precisely defined in order to properly evaluate
the architectural components and extensibility, including:
-define the end product
-who are we optimizing for
-what is partners incentive to be involved
-prototyping is different from research - define scope of each and
intersections
Formalize prototype feedback and documentation:
-object design - document use cases
-use that info for a re-definition of requirements
-document external API
-formalize query semantics
4.2 Testbed Developments Involving Other R&D Teams - In relation to interoperability and distributed processing, the Information Systems Team has written and developed Java program objects to read Aerial photographs stored as TIFF files in the Alexandria collection. The Parallel Processing team is cu rrently documenting the JAVA implementation of the wavelet color image browsing scheme. The code will be available publicly in the late Fall of 1997.
5.0 Partnerships and Resources
5.1 Interactions with Partners - A white Paper authored by Mike Freeston comparing the capabilities of various commercially available DBMS products with spatial extensions was submitted to DEC in fulfillment of a deliverable. The Parallel Processing team interacted with Navy NRaD f or implementing adaptive client-server scheduling code on their Convex machine with applications in image document browsing.
5.2 Additional Resources to Support Research and Development - Funding has been received to develop a spatial data infrastructure and DL capability in Ecopetrol, the Colombian national petroleum company. It will support graduate students and Colombian researchers in Santa Barbara for a period of two years. The value of the project is approximately $270,000. In addition, the Colorado team has been approached by the Arctic and Alpine LTER site to participate in their next funding cycle, and will meet in November to discuss avenues of common research interest, following the successful Niwot Ridge pilot study.
6.0 Presentations and Promotional Activities - A workshop was held at the National Center for Ecological Analysis and Synthesis in Santa Barbara September 29 - October 1 on the subject of data-related uncertainty in ecological modeling; participants included Goodchild, Beard, and Buttenfield fro m ADL. Many issues of relevance to ADL were discussed, including the representation of uncertainty in metadata. The result of the workshop will be a book, published likely in early 1998. Buttenfield presented at paper at this workshop entitled, "Princ iples for Visual Representations of Metadata". The User Interface Evaluation team's paper on "User Evaluation: Summary of the Methodologies and Results for the Alexandria Digital Library, University of California at Santa Barbara" was presented at th e American Society for Information Science annual meeting in Washington D.C. Buttenfield, B.P. Cartographic Metaphors for Browsing Very Large Data Archives. Presented 17th Annual Meeting of the North American Cartographic Information Society (NACIS), Lexington, Kentucky. Buttenfield, B.P. Pilot Projects in Metadata Ingest to a Digital Library. Colloquium presented to the National Snow and Ice Data Center (NSIDC), University of Colorado-Boulder, 5 Sept 97 Mike Goodchild: "New Directions in the I nformation Sciences", University of Wyoming, September 1997 Mike Goodchild: Invited discussant, "Geographic Information Research at the Millennium", GISDATA Final Conference, Strasbourg, September 1997 Mike Goodchild: "GIS and Geography: Presidential Session", Association of Pacific Coast Geographers, Spokane, WA, September 1997. A new initiative of the National Center for Geographic Information and Analysis, titled "Interoperating GISs", will bring many of the issues faced by ADL to the fore in a combined international conference and workshop planned in Santa Barbara in December 1997. 60 abstracts were received, and a complete program will be defined by mid-October. This effort is being conducted jointly with the Open GIS Consortium, and Terr y Smith and Mike Goodchild are both participating in the organizing committees.
7.0 Publications -
Buttenfield, B.P. "Talking in the Tree House: Communication and Representation in Cartography." Cartographic Perspectives vol. 27(1): 20-23.
Buttenfield. B.P., "Why Don't We Do It on the Web? Distributing Geographic Information Via the Internet." Transactions in GIS, Invited Editorial vol. 2(1).
Chen, H.C., Smith, T.R., Larsgaard, M., and L. Hill, 1997. A Geographic Knowledge Representation System for Multimedia Geospatial Retrieval and Analysis, Journal of Digital Libraries, 1(2), 132-152.
Deng, Y., Manjunath, B.S., "Content-based Search of Video Using Color, Texture, and Motion", to appear in the Proceedings of IEEE International Conference on Image Processing, Santa Barbara, CA, October, 1997.
Dolin, R., Agrawal, D., Dillon, L., El Abbadi, A., "Pharos: A Scalable Distributed Architecture for Locating Heterogeneous Information Sources," Proceedings of the Sixth CIKM Conference, Las Vegas, Nevada, November, 1997.
Ehlschlaeger, C.R., Shortridge, A.M. and M.F. Goodchild, "Visualizing spatial data uncertainty using animation", Computers and Geosciences 23(4): 387-395, 1997.
Fabrikant, S. I. and Buttenfield, B.P. Envisioning User Acess to a Large Data Archive. Proceedings, GIS/LIS '97, Cincinnatti, Ohio, 27-29 November, 1997.
Hill, L.L., Dolin, R., Frew, J., Kemp, R.B., Larsgaard, M., Montello, D.R., Rae, M-A, Simpson, J, "User Evaluation: Summary of the Methodologies and Results for the Alexandria Digital Library, University of California at Santa Barbara," Proceedings of the American Society for Information Science (ASIS) Annual Meeting, Washington D.C., November 1997.
Kanth, K.V. and Ambuj S.. "Efficient Dynamic Range Searching using Data Replication", submitted to Information Processing Letters.
Kanth, K.V., D. F. Serena and A. Singh. "Improved Concurrency Control Techniques for Multi-Dimensional Index Structures", submitted to International Parallel Processing Symposium.
Lee, C. H., Y. F. Wang, and Tao Yang, ``Global Optimization for Mapping Parallel Image Processing Tasks on Distributed Memory Machines,'' Accepted for publication in Journal of Parallel and Distributed Processing.
Liang, P., and Y. F. Wang, ``Local Scale Controlled Anisotropic Diffusion with Local Noise Estimate for Image Smoothing and Edge Detection,'' to appear in International Conference on Computer Vision, Bombay, India, January, 1998.
Ma, W. Y. and B. S. Manjunath, "A pattern thesaurus for browsing large aerial photographs," accepted for publication, Journal of American Society for Information Science, 1997.
Ma, W.Y., Manjunath, B.S., "NETRA: A Toolbox for Navigating Large Image Databases," to appear in the Proceedings of IEEE International Conference on Image Processing, Santa Barbara, CA. October, 1997. A detailed version has been accepted for publi cation in the Multimedia Systems journal.
Poulakidas, A. S., A. Srinivasan, O. Egecioglu, O. Ibarra, T. Yang, "A Compact Storage Scheme for Fast Wavelet-Based Subregion Retrieval," (Journal of Theoretical Computer Science), invited submission, in preparation, 1997.
S. Prabhakar, D. Agrawal, A. El Abbadi, A. Singh and T. Smith, "Browsing and Placement of Multiresolution Images on Multiple Disks", To Appear in 5th Annual Workshop on I/O in Parallel and Distributed Systems, IOPADS 97, San Jose, CA, Nov 17 1997, p ages 102-113.
Prabhakar, S., D. Agrawal, A. El Abbadi and A. Singh "Scheduling Tertiary I/O in Database Applications'', in 8th international workshop on Database and Expert Systems Applications, DEXA '97, Toulouse, France.
Prabhakar, S., A. Abdel-Ghaffar, D. Agrawal and A. El Abbadi ``Cyclic Declustering of Two-Dimensional Data'' to appear in 14th International Conference on Data Engineering, ICDE '98.
Prabhakar, S., D. Agrawal, A. El Abbadi and A. Singh, ``Tertiary Storage Systems: Current Status and Future Directions'' submitted to International Journal of Digital Libraries (IJODL)
Smith, A. and Buttenfield, B.P. Georeferencing Historical Photographs for a Digital Library. Proceedings, GIS/LIS '97, Cincinnatti, Ohio, 27-29 November, 1997. Smith, T.R., 1997. Meta-information in Digital Libraries, Introduction to Special Issu e of Journal of Digital Libraries, Journal of Digital Libraries, 1(2), 105-107.
Strobel, N., Mitra, S.K., Manjunath, B.S., "Model-Based Detection and Correction of Corrupted Wavelet Coefficients," to appear in Proceedings of IEEE International Conference on Image Processing, Santa Barbara, CA, October, 1997.
Strobel, N., Li, C.S., Castelli, V., "Texture-Based Image Segmentation and MMAP for Digital Libraries," to appear in Proceedings of IEEE International Conference on Image Processing, Santa Barbara, CA, October, 1997.
Wang, Y. F., and P. Liang, ``3D Shape and Motion Analysis from Image Blur and Smear: A Unified Approach,'' to appear in International Conference on Computer Vision, Bombay, India, January, 1998.
Wang, Y. F., and Ronald-Bryan O. Alfreze, ``A Unified Framework for Image-Derived Invariants,'' to appear in the 3rd Asian Conference on Computer Vision, Hong Kong, January, 1998.
Wright, D.J. and M.F. Goodchild, "Guest editorial: Data from the deep: implications for the GIS community", International Journal of Geographical Information Science 11(6): 523-528, 1997.
Wu, D., D. Agrawal, A. El Abbadi and A. Singh, "A Java-based Distributed Framework for Distributed Processing" to appear in Proc. of Intl. Conf. on Conceptual Modeling 1997 (ER '97), UCLA, November 3-6, 1997
8.0 Certification - I certify that to the best of my knowledge (1) the statements herein (excluding scientific hypotheses and scientific opinions) are true and complete, and (2) the text and graphics in this report as well as any accompanying publications or other documen ts, unless otherwise indicated, are the original work of the signatories or individuals working under their supervision. I understand that the willful provision of false information or concealing a material fact in this report(s) or any other communicatio n submitted to NSF is criminal offense (U.S. Code, Title 18, Section 1011.)
Terence R. Smith
Director, Alexandria Digital Library Project