Advances in geographic information extraction have exposed previously untapped resources, such as many travel itineraries found in HTML tables and spreadsheets on the Web. In the general sense, itineraries differ from the related concepts of routes and trajectories in that the precise paths between stopping points are of far less importance than the locations of the stopping points and their order. This characteristic allows for some flexibility when visualizing itineraries. A method for automatically generating itinerary visualizations is presented, which utilizes principles from graph-drawing and map labeling, along with additional criteria designed specifically for the itinerary visualization task. We describe a system based on this method that can perform automated layout for arbitrary itineraries at varying scales.

Given the increasing prevalence of streaming spatially-referenced datasets resulting from sensor networks usually consisting of text objects of varying length (termed labels) as well as streaming spatially oriented queries leads to closer scrutiny of mapping interfaces to present the data to users. These interfaces must cope with the fact that the labels associated with each location are constantly changing and that there are too many objects to display clearly within the interface. An algorithm meeting these challenges is presented. It differs from classical methods by avoiding expensive pre-computation steps, thereby allowing different labels to be associated with locations without needing to completely recompute the layout. In other words, we are addressing a write-many read-many setting instead of the conventional write-once read-many setting. Our experiments show consistent sub-second query times for query windows that contain as many as 11 million data objects, with only slight differences in the set of displayed labels when compared to an exhaustive baseline algorithm. This enables the algorithm to be used in a mapping application that involves both streaming data and streaming queries such as windowing realized by real-time, continuous zooming and panning operations.

Many spatial applications require the ability to display locations of geographic data entries on an online map. For example, an online photo-sharing service may wish to display photos (as thumbnails) according to where they were taken. Since displaying geographic data entries as thumbnails or icons on a map requires some amount of space, displayed entries can overlap each other. As a result, we may wish to discard less popular or older entries (based on a given measure of importance) so that these more popular or newer entries become more distinct. A straightforward solution is to apply a spatial database extension such as PostGIS (i) to retrieve entries within a given display window; (ii) to discard entries in proximity of a more important one. In this paper, we demonstrate our method for efficiently selecting distinct entries from a large geographical point set. Specifically, our demonstration software presents a voting system built upon an ensemble of interrelated indexes, which is the main novelty of our query processing method. This allows us to efficiently determine the degree of distinctiveness of all entries within a query window using simple index traversal operations rather than expensive spatial operations. The effectiveness of our method in comparison to a traditional spatial query is shown by our experimental results using a real dataset of over 9 million locations. These experimental results show that our proposed method is capable of consistently producing subsecond response times, while the spatial query-based method takes more than 10 seconds on average in a low spatial selectivity setting.

Determining geographic interpretations for place names, or toponyms, involves resolving multiple types of ambiguity. Place names commonly occur within lists and data tables, whose authors frequently omit qualifications (such as city or state containers) for place names because they expect the meaning of individual place names to be obvious from context. GeoWhiz is a system that demonstrates a novel technique for place name disambiguation (also known as toponym resolution). The system uses Bayesian inference to assign categories to user-specified lists of place names, then interprets individual toponyms based on the most likely category assignments. The categories are defined along three orthogonal dimensions: place types (e.g., cities, capitals, rivers, etc.), geographic containers, and prominence (e.g., based on population). A map interface enables users to explore possible interpretations and compare the interpretations that are most likely based on selected categories.

Tabular data is an abundant source of information on the Web, but remains mostly isolated from the latter's interconnections since tables lack links and computer-accessible descriptions of their structure. In other words, the schemas of these tables -- attribute names, values, data types, etc. -- are not explicitly stored as table metadata. Consequently, the structure that these tables contain is not accessible to the crawlers that power search engines and thus not accessible to user search queries. We address this lack of structure with a new method for leveraging the principles of table construction in order to extract table schemas. Discovering the schema by which a table is constructed is achieved by harnessing the similarities and differences of nearby table rows through the use of a novel set of features and a feature processing scheme. The schemas of these data tables are determined using a classification technique based on conditional random fields in combination with a novel feature encoding method called logarithmic binning, which is specifically designed for the data table extraction task. Our method provides considerable improvement over the well-known WebTables schema extraction method. In contrast with previous work that focuses on extracting individual relations, our method excels at correctly interpreting full tables, thereby being capable of handling general tables such as those found in spreadsheets, instead of being restricted to HTML tables as is the case with the WebTables method. We also extract additional schema characteristics, such as row groupings, which are important for supporting information retrieval tasks on tabular data.

PhotoStand enables the use of a map query interface to retrieve news photos associated with news articles that are in turn associated with the principal locations that they mention collected as a result of monitoring the output of over 10,000 RSS news feeds, made available within minutes of publication, and stored in a PostgreSQL database. The news photos are ranked according to their relevance to the clusters of news articles associated with locations at which they are displayed. This work differs from traditional work in this field as the associated locations and topics (by virtue of the cluster with which the articles containing the news photos are associated) are generated automatically without any human intervention such as tagging, and that photos are retrieved by location instead of just by keyword as is the case for many existing systems. In addition, the clusters provide a filtering step for detecting near-duplicate news photos.

Many spatial applications require the ability to display locations of data entries on an online map. For example, an online photo-sharing service may wish to display photos according to where they were taken. Since many photos can occupy the same area and overlap each other within a display window, less popular or older images (based on a given measure of importance) can be discarded so that these more popular or newer photos become more distinct. A straightforward solution to this problem is (i) to use a window query to retrieve data entries within a given display window; (ii) to discard data entries in proximity of a more important one. This method works well in a high spatial selectivity setting, e.g., when the window query returns a small number of entries, but the performance drastically degrades as the spatial selectivity decreases. We consider this problem as selecting distinct data entries from a given dataset, where the "distinctiveness" of a data entry depends on its relative importance in comparison to that of other data entries in proximity. In this paper, we propose a new query type called the multi-resolution select-distinct (MRSD) query. The main novelty of our query processing method is a voting system built upon an ensemble of interrelated indexes, which allows us to efficiently determine the degree of distinctiveness of all points within a query window. Using a real dataset of over 9 million locations, our experimental results show that our proposed method is capable of consistently producing subsecond response times, while the window query-based method takes more than 10 seconds on average in a low spatial selectivity setting.

Spatial applications often require the ability to perform similarity search over a collection of point sets. For example, given a geographical distribution of a disease outbreak, find k historical outbreaks with similar spatial distributions from a data collection D. In this paper, we study the problem of similarity search over a collection of point sets using the Hausdorff distance, which is a measure commonly used to determine the maximum discrepancy between two point sets. To avoid computing the Hausdorff distance for all point sets S in D, one may compute an optimistic estimate (i.e., lower bound value) of the actual Hausdorff distance HausDist(Q,S) for each S to rule out sets that are obviously dissimilar to Q. In our investigation, we observed that a commonly used method (called BscLB) to compute an estimate may not produce a result which is indicative of the actual Hausdorff distance. Consequently, we propose a method (called EnhLB) which produces a tighter estimate than the existing one. We then formulate a similarity search algorithm which uses a combination of BscLB and EnhLB to find similar point sets efficiently. In addition, we also extend our method to support an outlier-resistant variant of the Hausdorff distance called the modified Hausdorff distance. We compare our proposed algorithm with an algorithm using only BscLB. The results of our experiments show a reduction in computation time of 72% for searches using the Hausdorff distance and a reduction of 53% using the modified Hausdorff distance.

A geographic search system named GeoXLS is presented, which enables users to submit a set of locations as a query object Q and to find documents containing locations similar to those in Q. Search results come from a collection of geotagged web documents, specifically a vast collection of spreadsheets obtained from the Web. The results are ranked according to their similarity to Q, using one of several user-selected similarity measures related to the Hausdorff distance. GeoXLS allows users to answer queries such as "I know the locations of n entities of type X. What sets of data contain points similar to my query points?" For example, given a set Q of known impact craters, find documents that contain locations similar to those in Q and beyond. In essence, this allows someone to "complete the set" by identifying sets containing similar locations. GeoXLS provides capabilities analogous to a standard keyword search engine, but with keywords specified geographically. In contrast to a search engine that handles only text queries, our geographic search system is capable of returning search result documents that are not exact matches to the query. For example, searching with query points in "Washington, DC", "Denver, Colorado", and "Chicago, Illinois" could return documents related to colleges with actual locations in "College Park, Maryland", "Boulder, Colorado", and "Evanston, Illinois", which are similar spatially, but not textually. GeoXLS can be useful in a wide variety of knowledge domains where the data can be represented as a collection of point sets.

NewsStand is a Web-based mapping application that we have developed to enable searching for spatially-referenced information by using a map query interface. Previously, we adapted the Web version to execute on mobile devices such as smartphones where the main issue that was confronted was how to deal with the considerably smaller display screen while retaining access to the application through the browser. In the current work we discuss the issues that we encountered in converting the Web-based application to a native App primarily on the iPhone and iPod Touch. These issues involve how to compensate for the absence of a hovering action as well as how to integrate an interaction restriction to one hand coupled with use of the thumb as the pointing mechanism. In addition, a significant effort is devoted to the implementation of an intuitive mechanism for undoing the most recent actions. Other issues include the formulation of navigation shortcuts to avoid excessive traffic with the supporting database.

Ontuition, a system for mapping ontologies, is presented. Transforming data to a usable format for Ontuition involves recognizing and resolving data values corresponding to concepts in multiple ontological domains. In particular, for datasets with a geographic component an attempt is made to identify and extract enough spatio-textual data that specific lat/long values to dataset entries can be assigned. Next, a gazetteer is used to transform the textually-specified locations into lat/long values that can be displayed on a map. Non-spatial ontological concepts are also discovered. This methodology is applied to the National Library of Medicine's very popular clinical trials website (http://clinicaltrials.gov/) whose users are generally interested in locating trials near where they live. The trials are specified using XML files. The location data is extracted and coupled with a disease ontology to enable general queries on the data with the result being of use to a very large group of people. The goal is to do this automatically for such ontology datasets with a locational component.