Historical geologic maps contain rich geospatial information—such as rock units, faults, folds, and bedding planes—that is critical for assessing mineral resources essential to renewable energy, electric vehicles, and national security. However, digitizing maps remains a labor-intensive and time-consuming task. We present DIGMAPPER, a modular, scalable system developed in collaboration with the United States Geological Survey (USGS) to automate the digitization of geologic maps. DIGMAPPER features a fully dockerized, workflow-orchestrated architecture that integrates state-of-the-art deep learning models for map layout analysis, feature extraction, and georeferencing. To overcome challenges such as limited training data and complex visual content, our system employs innovative techniques, including in-context learning with large language models, synthetic data generation, and transformer-based models. Evaluations on over 100 annotated maps from the DARPA-USGS dataset demonstrate high accuracy across polygon, line, and point feature extraction, and reliable georeferencing performance. Deployed at USGS, DIGMAPPER significantly accelerates the creation of analysis-ready geospatial datasets, supporting national-scale critical mineral assessments and broader geoscientific applications.

Historical maps often suffer from coloring errors caused by artifacts during map production or scanning. These errors result in color mismatches between important map features (e.g., polygon layers) and their corresponding map keys, which hinders both human interpretation and automated feature extraction. This paper targets the problem of automatically correcting polygon coloring errors in historical maps using only in-map information, such as the map keys. The challenge lies in the diverse visual representations of map keys and variations in coloring errors, which differ significantly both within and across maps. We propose a machine-learning model that automatically identifies and corrects color inconsistencies between map polygon layers and their visual appearances defined by the map keys on the same map. Our approach leverages polygon metadata, such as map keys describing the visual and semantic properties of each polygon on maps, to detect mismatches in color histograms and representations and recolor the incorrect areas in the map content accordingly. We evaluate our approach on USGS geological maps; it outperforms comparative methods by at least 7.5%. In addition, our approach improves the downstream automated polygon-extraction task by 18.0% in precision.

Black-and-white draft geological maps, produced during fieldwork, often contain dense handwritten annotations overlaid on monochromatic contour basemaps. Although interpretable in grayscale, the lack of color makes it difficult to visually distinguish overlapping or adjacent geological units, especially when boundaries are unclear and annotation styles vary. However, colorizing these draft maps is labor-intensive but essential, as they may be the only source of detailed geological information for certain regions. This hinders both human interpretation and downstream tasks such as map digitization and critical mineral resource assessment. We target the problem of automated colorization of draft geological maps. The challenge lies in interpreting noisy visual cues from uncolored sketches and assigning appropriate colors according to their geological categories. We propose a novel machine learning approach that exploits polygon metadata, including map keys that explicitly define geological units and implicitly suggest their intended colors, along with the semantic interpretation of the sketch content in the maps, to assign colors to the draft maps accordingly. We evaluate our method on USGS draft geological maps; it outperforms comparative methods by 15.7%. In addition, our approach improves downstream polygon-extraction performance by 9% in F1 score.

Understanding the semantic structure of tabular data is essential for data integration and discovery. Specifically, the goal is to annotate columns in a tabular source with types and relationships between them using classes and predicates of a target ontology. Previous work either requires trained labeled data or exploits the overlapping data between the table data and a knowledge graph to predict types and relationships. However, these approaches cannot be used in a new domain with limited labeled data. To address this issue, we propose a novel domain-independent approach to estimate a score reflecting the semantic relatedness between a table column and an ontology class or property using the table metadata and data. Our empirical evaluation demonstrates that our approach significantly outperforms strong baselines based on large language models.

With the rapid development of electric vehicles that facilitate sustainable transportation, the need to ensure their accessibility has increased. Determining the optimal locations for extending an existing charging station network is crucial to addressing rising infrastructure needs and reducing environmental impacts. The 13th ACM SIGSPATIAL Cup competition (GISCUP 2024) targets the problem of optimal minimum charging station deployment within an existing network. The recommendation of station locations aims to maximize accessibility over long-distance travel and ensure both coverage and proximity to points of interest or areas with high vehicle usage, while minimizing traffic congestion and reducing impacts on the power grid and the existing charging network. We leverage the categorical Voronoi diagram with hierarchical reconciliation to recommend stations that dovetail with the existing charging network under zero access to historical data. Our approach maximizes station deployment in high-demand areas with equitable distribution. Meanwhile, it complements the existing network to minimize unfavorable impacts on the power grid. Qualitative evaluation on a large-scale real-world dataset shows that our approach effectively balances objectives across areas with diverse geographical and demographic characteristics. In addition, our approach ranked in the top five among all participants in the GISCUP 2024.

Road inspection and cleaning are crucial to securing driving safety. Deploying a fleet of robots that run through a city can inspect and clean pavements without causing road closure. To achieve high coverage, one has to prevent robots from going through a road segment more than once. However, robots may need more than one visit to a particular road segment to inspect a defect. The uncertain success rate of defect inspection and the unknown maximum number of defects hinder the efficacy. Such uncertainty and constraints in objectives can also be seen in security patrolling, trip planning, and network maintenance. We target the problem of multi-agent scheduling with bounded objectives. The scheduling aims for maximum road network coverage while ensuring sufficient visits to particular road segments for defect identification of an uncertain subject, such as potholes and faded markings during road inspection or crimes and parking violations during security patrolling. We leverage an approximate bi-objective algorithm and propose a hierarchical circular route-planning algorithm. Our approach maximizes the road coverage among robots and decreases the search space when maximizing defect identification. Evaluation on a real-world dataset shows that our approach achieves the Pareto optimal among comparative methods, outperforming existing methods by at least one optimization objective.

Tables can contain various types of errors, including both syntactic and semantic errors. Semantic errors relate to the meaning of the data and can be detrimental for downstream applications. The existing approaches for semantic error detection use structured knowledge sources such as Wikidata and DBpedia, but the coverage of such sources is quite limited. There is much more information available in free text to validate the contents of tables. In this paper, we present a novel semantic-error-detection approach that exploits open-domain textual data to verify the semantic correctness of tables. Our approach leverages contrastive learning, table linearization, and pre-trained language models to implement the error detection process. We implement our approach in a system called SEED and show in the evaluation that it significantly outperforms the other competing approaches.

Private vehicles are a direct means to bring people from one place to their desired destinations. However, no omniscient dispatcher is handling the origin-destination of vehicles and the availability of stationary resources, such as parking spaces or charging stations. Competitive cruising for stationary resources leads to environmental pollution and is a waste of drivers' time. We focus on the problem of distributed stationary-resource searching with predefined destinations under a multi-agent scenario. It is a distributed route planning problem with global optimization objectives. We present a probabilistic approach to achieving indirect resource coordination and latent agent cooperation in a distributed manner. Our approach treats the estimated availability of stationary resources as a reference and guides each agent based on their preferences. We evaluate our approach on four real-world datasets. Our approach outperforms state-of-the-art methods by 5% in multi-criteria optimization.

Locating undiscovered deposits of critical minerals requires accurate geological data. However, most of the 100,000 historical geological maps of the United States Geological Survey (USGS) are in raster format. This hinders critical mineral assessment. We target the problem of extracting geological features represented as polygons from raster maps. We exploit the polygon metadata that provides information on the geological features, such as the map keys indicating how the polygon features are represented, to extract the features. We present a metadata-driven machine-learning approach that encodes the raster map and map key into a series of bitmaps and uses a convolutional model to learn to recognize the polygon features. We evaluated our approach on USGS geological maps; our approach achieves a median F1 score of 0.809 and outperforms state-of-the-art methods by 4.52%.

The increasing availability and accessibility of numerous overhead images allows us to estimate and assess the spatial arrangement of groups of geospatial target objects, which can benefit many applications, such as traffic monitoring and agricultural monitoring. Spatial arrangement estimation is the process of identifying the areas which contain the desired objects in overhead images. Traditional supervised object detection approaches can estimate accurate spatial arrangement but require large amounts of bounding box annotations. Recent semi-supervised clustering approaches can reduce manual labeling but still require annotations for all object categories in the image. This paper presents the target-guided generative model (TGGM), under the Variational Auto-encoder (VAE) framework, which uses Gaussian Mixture Models (GMM) to estimate the distributions of both hidden and decoder variables in VAE. Modeling both hidden and decoder variables by GMM reduces the required manual annotations significantly for spatial arrangement estimation. Unlike existing approaches that the training process can only update the GMM as a whole in the optimization iterations (e.g., a "minibatch"), TGGM allows the update of individual GMM components separately in the same optimization iteration. Optimizing GMM components separately allows TGGM to exploit the semantic relationships in spatial data and requires only a few labels to initiate and guide the generative process. Our experiments shows that TGGM achieves results comparable to the state-of-the-art semi-supervised methods and outperformes unsupervised methods by 10% based on the F1scores, while requiring significantly fewer labeled data.

Thousands of scanned historical topographic maps contain valuable information covering long periods of time, such as how the hydrography of a region has changed over time. Efficiently unlocking the information in these maps requires training a geospatial objects recognition system, which needs a large amount of annotated data. Overlapping geo-referenced external vector data with topographic maps according to their coordinates can annotate the desired objects’ locations in the maps automatically. However, directly overlapping the two datasets causes misaligned and false annotations because the publication years and coordinate projection systems of topographic maps are different from the external vector data. We propose a label correction algorithm, which leverages the color information of maps and the prior shape information of the external vector data to reduce misaligned and false annotations. The experiments show that the precision of annotations from the proposed algorithm is 10% higher than the annotations from a state-of-the-art algorithm. Consequently, recognition results using the proposed algorithm’s annotations achieve 9% higher correctness than using the annotations from the state-of-the-art algorithm.

Historical maps contain detailed geographic information difficult to find elsewhere covering long-periods of time (e.g., 125 years for the historical topographic maps in the US). However, these maps typically exist as scanned images without searchable metadata. Existing approaches making historical maps searchable rely on tedious manual work (including crowd-sourcing) to generate the metadata (e.g., geolocations and keywords). Optical character recognition (OCR) software could alleviate the required manual work, but the recognition results are individual words instead of location phrases (e.g., "Black'' and "Mountain'' vs. "Black Mountain''). This paper presents an end-to-end approach to address the real-world problem of finding and indexing historical map images. This approach automatically processes historical map images to extract their text content and generates a set of metadata that is linked to large external geospatial knowledge bases. The linked metadata in the RDF (Resource Description Framework) format support complex queries for finding and indexing historical maps, such as retrieving all historical maps covering mountain peaks higher than 1,000 meters in California. We have implemented the approach in a system called mapKurator. We have evaluated mapKurator using historical maps from several sources with various map styles, scales, and coverage. Our results show significant improvement over the state-of-the-art methods. The code has been made publicly available as modules of the Kartta Labs project at https://github.com/kartta-labs/Project.

With large amounts of digital map archives becoming available, automatically extracting information from scanned historical maps is needed for many domains that require long-term historical geographic data. Convolutional Neural Networks (CNN) are powerful techniques that can be used for extracting locations of geographic features from scanned maps if sufficient representative training data are available. Existing spatial data can provide the approximate locations of corresponding geographic features in historical maps and thus be useful to annotate training data automatically. However, the feature representations, publication date, production scales, and spatial reference systems of contemporary vector data are typically very different from those of historical maps. Hence, such auxiliary data cannot be directly used for annotation of the precise locations of the features of interest in the scanned historical maps. This research introduces an automatic vector-to-raster alignment algorithm based on reinforcement learning to annotate precise locations of geographic features on scanned maps. This paper models the alignment problem using the reinforcement learning framework, which enables informed, efficient searches for matching features without pre-processing steps, such as extracting specific feature signatures (e.g. road intersections). The experimental results show that our algorithm can be applied to various features (roads, water lines, and railroads) and achieve high accuracy.

Data collected from heterogeneous sources often have inconsistencies in data format and thus require transformation before the data can be used. A major issue of existing approaches is their dependency on parallel input-output data to learn the transformations. However, parallel data are not always available, and annotation requires excessive human interaction because of format diversity. Therefore, these approaches have limitations when applied to large-scale real-world problems. To address this issue, we introduce UDATA, a novel unsupervised system for non-parallel data transformation. Because the transforming data usually share common syntactic patterns, UDATA discovers common syntactic patterns from input/output examples and synthesizes the transformations between the patterns. Moreover, in UDATA, transformation results are verified by an active learning model and ambiguous results are reported to users for labeling. UDATA achieves accuracy close to other state-of-the-art supervised systems without the need for any labeled data.

Publishing data sources to knowledge graphs is a complicated and laborious process as data sources are often heterogeneous, hierarchical and interlinked. As an example, food price datasets may contain product prices of various units at different markets and times, and different providers can have many choices of formats such as CSV, JSON or spreadsheet. Beyond data formats, these datasets may have differing layout, where one dataset may be organized as a row-based table or relational table (prices are in one column), while another may use a matrix table (prices are in one matrix). To address these problems, we present a novel data description language for mapping datasets to RDF. In particular, our language supports specifying the locations of source attributes in the sources, mapping of the attributes to ontologies, and simple rules to join the data of these attributes to output final RDF triples. Unlike existing approaches, our language is not restricted to specific data layouts such as the Nested Relational Model, or to specific data formats, such as spreadsheet. Our broad data description language presents a format-independent solution, allowing interlinking among multiple heterogeneous sources and representing many diverse data structures that existing tools are unable to handle.

A semantic model of a data source is a representation of the concepts and relationships contained in the data. Building semantic models is a prerequisite to automatically publishing data to a knowledge graph. However, creating these semantic models is a complex process requiring considerable manual effort and can be error-prone. In this paper, we present a novel approach that efficiently searches over the combinatorial space of possible semantic models, and applies a probabilistic graphical model to identify the most probable semantic model for a data source. Probabilistic graphical models offer many advantages over existing methods: they are robust to noisy inputs and provide a straightforward approach for exploiting relationships within the data. Our solution uses a conditional random field (CRF) to encode structural patterns and enforce conceptual consistency within the semantic model. In an empirical evaluation, our approach outperforms state of the art systems by an average 8.4% of F1 score, even with noisy input data.

No abstract available.

Map labels provide valuable geographic information by annotating geographic phenomenona with text descriptions. However, many interesting and useful maps are only available as images and hence this information is not readily accessible in a Geographic Information System (GIS). Previous work on text recognition in maps considers maps as a special type of image to be processed using Optical Character Recognition (OCR) techniques and does not pay attention to the typical workflows in a GIS. As a result, to convert map labels into machine-readable text, a user has to switch between OCR and GIS software, transform the detected text locations from the image coordinates (in OCR) to the map coordinates (in GIS), and apply data import/export procedures. This tedious process limits the opportunity to access text information in maps. This paper presents ArcStrabo, an integration of our previous text recognition work and a GIS, which uses a GIS user interface, workflows, and data types to enable efficient training of text recognition algorithms for converting map labels to a table of geographic names. We show that ArcStrabo facilitates map digitization processes, eliminates the need for GIS users to learn additional OCR tools, and does not require manual data export/import procedures between GIS and OCR software.

A significant challenge in handling geographic datasets is that the datasets can come from heterogeneous sources with various data qualities and formats. Before these datasets can be used in a Geographic Information System (GIS) for spatial analysis or to create maps, a typical task is to clean the attribute data and transform the data into a uniform format. However, conventional GIS products focus on manipulating the spatial component of geographic features and only offer basic tools for editing the attribute data (e.g., one row at a time). This limits the capability for handling large datasets in a GIS since manually editing and transforming attribute data between different formats is not practical for thousands of geographic features. In this demo, we present ArcKarma, which is built on our previous work on data transformation, to efficiently clean and transform data attributes in a GIS. ArcKarma generates transformation programs from a few user-provided examples and applies these programs to transform individual attribute columns into the desired formats. We show that ArcKarma produces accurate results and eliminates the need for laborious manual data cleaning and scripting tasks.

Given the increasing popularity and availability of location tracking devices, large quantities of spatiotemporal data are available from many different sources. Quick interactive analysis of such data is important in order to understand the data, identify patterns, and eventually make a marketable product. Since the data do not necessarily follow the relational model and may require flexible processing possibly using advanced machine learning techniques, spatial databases or similar query tools do not make the best means for such analysis. Moreover, the high complexity of geometric operations makes the quick interactive analysis very difficult. In this paper, we present a highly flexible functional query engine that 1) works with multiple schema types, 2) provides fast response times by spatiotemporal indexing and parallelization, 3) helps understand the data using visualizations and 4) is highly extensible to easily add complex functionality. To demonstrate its usefulness, we use our tool to solve a real world problem of crime pattern analysis in Los Angeles County and compare the process with other well known tools.

Text recognition is difficult from documents that contain multi-oriented, curved text lines of various character sizes. This is because layout analysis techniques, which most optical character recognition (OCR) approaches rely on, do not work well on unstructured documents with non-homogeneous text. Previous work on recognizing non-homogeneous text typically handles specific cases, such as horizontal and/or straight text lines and single-sized characters. In this paper, we present a general text recognition technique to handle non-homogeneous text by exploiting dynamic character grouping criteria based on the character sizes and maximum desired string curvature. This technique can be easily integrated with classic OCR approaches to recognize non-homogeneous text. In our experiments, we compared our approach to a commercial OCR product using a variety of raster maps that contain multi-oriented, curved and straight text labels of multi-sized characters. Our evaluation showed that our approach produced accurate text recognition results and outperformed the commercial product at both the word and character level accuracy.

The latest generation of WWW tools and services enables Web users to generate applications that combine content from multiple sources. This type of Web application is referred to as a mashup. Many of the tools for constructing mashups rely on a widget paradigm, where users must select, customize, and connect widgets to build the desired application. While this approach does not require programming, the users must still understand programming concepts to successfully create a mashup. As a result, they are put off by the time, effort, and expertise needed to build a mashup. In this article, we describe our programming-by-demonstration approach to building mashup by example. Instead of requiring a user to select and customize a set of widgets, the user simply demonstrates the integration task by example. Our approach addresses the problems of extracting data from Web sources, cleaning and modeling the extracted data, and integrating the data across sources. We implemented these ideas in a system called Karma, and evaluated Karma on a set of 23 users. The results show that, compared to other mashup construction tools, Karma allows more of the users to successfully build mashups and makes it possible to build these mashups significantly faster compared to using a widget-based approach.

Raster maps contain valuable road information, which is especially important for the areas where road vector data are otherwise not readily accessible. However, converting the road information in raster maps to road vector data usually requires significant user effort to achieve high accuracy. In this demo, we present Strabo, which is a system that extracts road vector data from heterogeneous raster maps. We demonstrate Strabo's fully automatic technique for extracting road vector data from raster maps with good image quality and the semi-automatic technique for handling raster maps with poor image quality. We show that Strabo requires minimal user input for extracting road vector data from raster maps with varying map complexity (i.e., overlapping features in maps) and image quality.

Raster maps are widely available and contain useful geographic features such as labels and road lines. To extract the geographic features, most research work relies on a manual step to first extract the foreground pixels from the maps using the distinctive colors or grayscale intensities of the pixels. This strategy requires user interaction for each map to select a set of thresholds. In this paper, we present a map classification technique that uses an image comparison feature called the luminance-boundary histogram and a nearest-neighbor classifier to identify raster maps with similar grayscale intensity usage. We can then apply previously learned thresholds to separate the foreground pixels from the raster maps that are classified in the same group instead of manually examining each map. We show that the luminance-boundary histogram achieves 95% accuracy in our map classification experiment compared to 13.33%, 86.67%, and 88.33% using three traditional image comparison features. The accurate map classification results make it possible to extract geographic features from previously unseen raster maps.

To exploit the road network in raster maps, the first step is to extract the pixels that constitute the roads and then vectorize the road pixels. Identifying colors that represent roads in raster maps for extracting road pixels is difficult since raster maps often contain numerous colors due to the noise introduced during the processes of image compression and scanning. In this paper, we present an approach that minimizes the required user input for identifying the road colors representing the road network in a raster map. We can then use the identified road colors to extract road pixels from the map. Our approach can be used on scanned and compressed maps that are otherwise difficult to process automatically and tedious to process manually. We tested our approach with 100 maps from a variety of sources, which include 90 scanned maps with various compression levels and 10 computer generated maps. We successfully identified the road colors and extracted the road pixels from all test maps with fewer than four user labels per map on average.

The road network is one of the most important types of information on raster maps. In particular, the set of road intersection templates, which consists of the road intersection positions, the road connectivities, and the road orientations, represents an abstraction of the road network and is more accurate and easier to extract than the extraction of the entire road network. To extract the road intersection templates from raster maps, the thinning operator is commonly used to find the basic structure of the road lines (i.e., to extract the skeletons of the lines). However, the thinning operator produces distorted lines near line intersections, especially at the T-shaped intersections. Therefore, the extracted position of the road intersection and the road orientations are not accurate. In this paper, we utilize our previous work on automatically extracting road intersection positions to identify the road lines that intersect at the intersections and then trace the road orientations and refine the positions of the road intersections. We compare the proposed approach with the usage of the thinning operator and show that our proposed approach extracts more accurate road intersection positions and road orientations than the previous approach.

The building identification (BID) problem is based on a pro-cess that uses publicly available information to automati-cally assign addresses to buildings in satellite imagery. In previous work, we have shown the advantages of casting the BID problem as a Constraint Satisfaction Problem (CSP) using the same generic constraint-model to represent all problem instances. However, a generic model is unable to represent with the necessary precision the addressing varia-tions throughout the world, limiting the applicability of our previous approach. In this paper, we describe the end-to-end process used to solve the BID with a new model-generation technique that uses instance-specific information to auto-matically infer a representative constraint model of the BID. This inferred model is used by our custom constraint solver to identify buildings in satellite imagery more efficiently and with higher precision than using a single model. We evalu-ate our approach on El Segundo California, and empirically demonstrate its effectiveness for geographic areas larger than previously tested. We conclude with a discussion of the gen-erality of our approach, and present directions for future work.

Accurate and efficient integration of geospatial data is an important problem with applications in areas such as emergency response and urban planning. Some of the key challenges in supporting large-scale geospatial data integration are automatically computing the quality of the data provided by a large number of geospatial sources and dynamically providing high quality answers to the user queries based on a quality criteria supplied by the user. We describe a framework called the Quality-driven Geospatial Mediator (QGM) that supports efficient and accurate integration of geospatial data from a large number of sources. The key contributions of our framework are: (1) the ability to automatically estimate the quality of data provided by a source by using the information from another source of known quality, (2) representing the quality of data provided by the sources in a declarative data integration framework, and (3) a query answering technique that exploits the quality information to provide high quality geospatial data in response to user queries. Our experimental evaluation using over 1200 real-world sources shows that QGM can accurately estimate the quality of geospatial sources. Moreover, QGM provides better quality data in response to the user queries compared to the traditional data integration systems and does so with lower response time.

In order to combine data from various heterogeneous sources, software agents must first understand the semantics of the sources, expressed in the source model. Currently, source modeling is manual, but as large numbers of sources come online, it is impractical to expect users to continue modeling them by hand. We describe two machine learning techniques for automatically modeling information sources: one that uses source’s metadata, contained in a Web Service Definition file, and one that uses the source’s content, to classify the semantics of the data it uses. We go beyond previous works and verify predictions by invoking the source with sample data of the predicted type. We provide performance results of both methods and validate our approach on several live Web sources. In addition, we describe the application of semantic modeling within the CALO project.

Record linkage is the process of determining that two records refer to the same entity. A key subprocess is evaluating how well the individual fields, or attributes, of the records match each other. One approach to matching fields is to use hand-written domain-specific rules. This "expert systems" approach may result in good performance for specific applications, but it is not scalable. This paper describes a new machine learning approach that creates expert-like rules for field matching. In our approach, the relationship between two field values is described by a set of heterogeneous transformations. Previous machine learning methods used simple models to evaluate the distance between two fields. However, our approach enables more sophisticated relationships to be modeled, which better capture the complex domain specific, common-sense phenomena that humans use to judge similarity. We compare our approach to methods that rely on simpler homogeneous models in several domains. By modeling more complex relationships we produce more accurate results.

Many Web sites, especially those that dynamically generate HTML pages to display the results of a user's query, present information in the form of list or tables. Current tools that allow applications to programmatically extract this information rely heavily on user input, often in the form of labeled extracted records. The sheer size and rate of growth of the Web make any solution that relies primarily on user input is infeasible in the long term. Fortunately, many Web sites contain much explicit and implicit structure, both in layout and content, that we can exploit for the purpose of information extraction. This paper describes an approach to automatic extraction and segmentation of records from Web tables. Automatic methods do not require any user input, but rely solely on the layout and content of the Web source. Our approach relies on the common structure of many Web sites, which present information as a list or a table, with a link in each entry leading to a detail page containing additional information about that item. We describe two algorithms that use redundancies in the content of table and detail pages to aid in information extraction. The first algorithm encodes additional information provided by detail pages as constraints and finds the segmentation by solving a constraint satisfaction problem. The second algorithm uses probabilistic inference to find the record segmentation. We show how each approach can exploit the web site structure in a general, domain-independent manner, and we demonstrate the effectiveness of each algorithm on a set of twelve Web sites.

As product prices become increasingly available on the World Wide Web, consumers attempt to understand how corporations vary these prices over time. However, corporations change prices based on proprietary algorithms and hidden variables (e.g., the number of unsold seats on a flight). Is it possible to develop data mining techniques that will enable consumers to predict price changes under these conditions?This paper reports on a pilot study in the domain of airline ticket prices where we recorded over 12,000 price observations over a 41 day period. When trained on this data, Hamlet --- our multi-strategy data mining algorithm --- generated a predictive model that saved 341 simulated passengers $198,074 by advising them when to buy and when to postpone ticket purchases. Remarkably, a clairvoyant algorithm with complete knowledge of future prices could save at most $320,572 in our simulation, thus HAMLET's savings were 61.8% of optimal. The algorithm's savings of $198,074 represents an average savings of 23.8% for the 341 passengers for whom savings are possible. Overall, HAMLET saved 4.4% of the ticket price averaged over the entire set of 4,488 simulated passengers. Our pilot study suggests that mining of price data available over the web has the potential to save consumers substantial sums of money per annum.

With the rapid growth of the World Wide Web, more and more people rely on the online services to acquire and integrate information. However, it is time consuming to find the online services that are perfectly suited for a given task. First, the users might not have enough information to fill in the required input fields for querying an online service. Second, the online service might generate only partial information. Third, the user might only find the inverse version of the desired service. We propose a framework to develop flexible Web agents that handle these imperfect situations. In this framework we exploit a search engine as a general information discovery tool to assist finding and pruning information. To demonstrate this framework, we implemented two Web agents: the Internet inverse geocoder and the address lookup module.

The task of object identification occurs when integrating information from multiple websites. The same data objects can exist in inconsistent text formats across sites, making it difficult to identify matching objects using exact text match. Previous methods of object identification have required manual construction of domain-specific string transformations or manual setting of general transformation parameter weights for recognizing format inconsistencies. This manual process can be time consuming and error-prone. We have developed an object identification system called Active Atlas [18], which applies a set of domain-independent string transformations to compare the objects' shared attributes in order to identify matching objects. In this paper, we discuss extensions to the Active Atlas system, which allow it to learn to tailor the weights of a set of general transformations to a specific application domain through limited user input. The experimental results demonstrate that this approach achieves higher accuracy and requires less user involvement than previous methods across various application domains.

There is currently great interest in building information mediators that can integrate information from multiple data sources such as databases or Web sources. The query response time for such mediators is typically quite high, mainly due to the time spent in retrieving data from remote sources. We present an approach for optimizing the performance of information mediators by selectively materializing data. We first present our overall framework for materialization in a mediator environment. The data is materialized selectively. We outline the factors that are considered in selecting data to materialize. We present an algorithm for identifying classes of data to materialize by analyzing one of the factors which is the distribution of user queries. We present results with an implemented version of our optimization system for the Ariadne information mediator, which show the effectiveness of our algorithm in extracting patterns of frequently accessed classes from user queries. We also demonstrate the effectiveness of approach in optimizing mediator performance by materializing such classes.

While the information resources on the Web are vast, the sources are often hard to nd, painful to use, and dicult to integrate. Wehavedeveloped the Heracles framework for building Web-based information assistants. This framework provides the infrastructure to rapidly construct new applications that extract information from multiple Web sources and interactively integrate the data using a dynamic, hierarchical constraint network. This paper describes the core technologies that comprise the framework, including information extraction, hierarchical template representation, and constraint propagation. In addition, we present an application of this framework, the ###### #########, which is an interactivetravel planning system. We also briey describe our experience using the same framework to build a second application, the ######### #########, which extracts and integrates geographic-related data about countries thorughout the world. We believe these types of information assistants provide a signicant step forward in fully exploiting the information available on the Internet. 1.

The Web is based on a browsing paradigm that makes it difficult to retrieve and integrate data from multiple sites. Today, the only way to do this is to build specialized applications, which are time-consuming to develop and difficult to maintain. We have addressed this problem by creating the technology and tools for rapidly constructing information agents that extract, query, and integrate data from web sources. Our approach is based on a uniform representation that makes it simple and efficient to integrate multiple sources. Instead of building specialized algorithms for handling web sources, we have developed methods for mapping web sources into this uniform representation. This approach builds on work from knowledge representation, databases, machine learning and automated planning. The resulting system, called Ariadne, makes it fast and easy to build new information agents that access existing web sources. Ariadne also makes it easy to maintain these agents and incorporate new sources as they become available.

Although much has been written about various information integration technologies, little has been said regarding how to combine these technologies together to build an entire application. We demonstrate TheaterLoc, an information integration application that allows users to retrieve information about theatres and restaurants for various U.S. cities, including an interactive map depicting their relative locations. The data retrieved by TheaterLoc comes from five distinct heterogeneous and distributed sources. The enabling technology used to achieve the integration includes: the Ariadne information mediator, a Web site wrapper learning tool, the Theseus execution system, and a mechanism for distributed spatial query planning. Our system is novel because it demonstrates how "virtual applications" can be rapidly built from a set of integration tools and existing online data sources.

New applications of information systems need to integrate a large number of heterogeneous databases over computer networks. Answering a query in these applications usually involves selecting relevant information sources and generating a query plan to combine the data automatically. As significant progress has been made in source selection and plan generation, the critical issue has been shifting to query optimization. This paper presents a semantic query optimization (SQO) approach to optimizing query plans of heterogeneous multidatabase systems. This approach provides global optimization for query plans as well as local optimization for subqueries that retrieve data from individual database sources. An important feature of our local optimization algorithm is that we prove necessary and sufficient conditions to eliminate an unnecessary join in a conjunctive query of arbitrary join topology. This feature allows our optimizer to utilize more expressive relational rules to provide a wider range of possible optimizations than previous work in SQO. The local optimization algorithm also features a new data structure called AND-OR implication graphs to facilitate the search for optimal queries. These features allow the global optimization to effectively use semantic knowledge to reduce the data transmission cost. We have implemented this approach in the PESTO (Plan Enhancement by SemanTic Optimization) query plan optimizer as a part of the SIMS information mediator. Experimental results demonstrate that PESTO can provide significant savings in query execution cost over query plan execution without optimization.

The Web is based on a browsing paradigm that makes it difficult to retrieve and integrate data from multiple sites. Today, the only way to achieve this integration is by building specialized applications, which are time-consuming to develop and difficult to maintain. We are addressing this problem by creating the technology and tools for rapidly constructing information mediators that extract, query, and integrate data from web sources. The resulting system, called Ariadne, makes it feasible to rapidly build information mediators that access existing web sources.

Accessing information sources to retrieve data requested by a user can be expensive, especially when dealing with distributed information sources. One way to reduce this cost is to cache the results of queries, or related classes of data. This paper presents an approach to caching and addresses the issues of which information to cache, how to describe what has been cached, and how to use the cached information to answer future queries. We consider these issues in the context of the SIMS information server, which is a system for retrieving information from multiple heterogeneous and distributed information sources. The design of this information server is ideal for representing and reusing cached information since each class of cached information is simply viewed as another information source that is available for answering future queries.

A practical heterogeneous, distributed multidatabase system must answer queries efficiently. Conventional query optimization techniques are not adequate here because these techniques are dependent on the database structure, and rely on limited information which is not sufficient in complicated multidatabase queries. This paper presents an automated approach to reformulating query plans to improve the efficiency of multidatabase queries. This approach uses database abstractions, the knowledge about the contents of databases, to reformulate a query plan into less expensive but semantically equivalent one. We present two algorithms. The first algorithm reformulates subqueries to individual databases, the second algorithm extends the first one and reformulates the entire query plan. Empirical results show that the reformulations can provide significant savings with minimal overhead. The reformulation approach provides a global reduction in the amount of the intermediate data as well as loc...

With the current explosion of data, retrieving and integrating information from various sources is a critical problem. Work in multidatabase systems has begun to address this problem, but it has primarily focused on methods for communicating between databases and requires significant effort for each new database added to the system. This paper describes a more general approach that exploits a semantic model of a problem domain to integrate the information from various information sources. The information sources handled include both databases and knowledge bases, and other information sources (e.g. programs) could potentially be incorporated into the system. This paper describes how both the domain and the information sources are modeled, shows how a query at the domain level is mapped into a set of queries to individual information sources, and presents algorithms for automatically improving the efficiency of queries using knowledge about both the domain and the information sources. This work is implemented in a system called SIMS and has been tested in a transportation planning domain using nine Oracle databases and a Loom knowledge base.