Traditional search engines use text-based queries to perform top-k keyword search. However, this approach does not always capture every user intention. For example, pattern-based spatial search can better answer queries involving spatial constraints (i.e. X North of Y). However, pattern-based search usually requires a pictorial query pattern as input, constructed by a user dragging and dropping objects on a canvas in a specialized interface. To bridge the gap between pattern-based spatial search and traditional search engines that require text input, we devise a Natural Language to Pictorial Query (NL2PQ) module that converts natural language queries into pictorial queries that can be refined then resolved using spatial pattern matching algorithms, thus enabling pattern based spatial search via natural language input.

Electric vehicles (EVs) have the potential to serve as energy storage solutions through bidirectional charging technology, which allows them to both draw power from and feed power back into the grid, homes, or other vehicles. This capability enables EVs to reduce emissions, optimize costs, and support the grid by storing energy during periods of high production and supplying it when demand is high. In this vision paper, we focus on unlocking the potential of EVs as energy storage solutions while ensuring they remain readily available for transportation, their primary purpose. A significant research gap exists in that most current studies prioritize energy management, often using simplistic approaches that inadequately address the travel needs of EV owners. We believe the database community can be instrumental in maximizing the dual role of EVs as transportation and energy storage. We present a non-exhaustive list of research directions for various EV stakeholders, including individual EV owners, groups of independent yet cooperative EVs, commercial EV fleets, and autonomous EVs, and hope to inspire the database community for further exploration.

Sun glare during driving poses a significant threat to driver and pedestrian safety. Navigation and route planning typically seeks to minimize the distance or time between the desired origin and destination, accounting for traffic patterns and other heuristics like minimizing the number of stoplights or left turns encountered on a route. However, current navigation methods do not support avoidance of complicated, temporally-dependent safety factors, like adverse road and environmental conditions. We take avoiding incident sun glare to the driver as an example of dynamic safety-aware navigation and lay out potential strategies for addressing this previously unexplored problem. We present a reinforcement learning-based method for computing sun glare-low routes through an elastic function that accounts for the direct angle between the sun and the driving direction. Our preliminary work shows that in some cases it is possible to reduce the sun glare exposure on a route by trading off additional travel distance. We envision future safety-aware navigation approaches that can automatically balance this trade-off and account for additional dynamic spatially and temporally-dependent safety-related environmental factors, like road and weather conditions, to determine the safest and most efficient route between any two given points.

Spatial reasoning is a particularly challenging task that requires inferring implicit information about objects based on their relative positions in space. In an effort to develop general purpose geo-foundation models that can perform a variety of spatial reasoning tasks, preliminary work has explored what kinds of world knowledge and spatial reasoning capabilities Large Language Models (LLMs) naturally inherit from their training data. Recent work suggests that LLMs contain geospatial knowledge in the form of understanding geo-coordinates and associating spatial meaning to the key terms "near" and "far." In this paper, we show that LLMs lack the ability to adapt the meaning of the words "near" and "far" to the appropriate scale when provided contextual reference points. By uncovering biases in how LLMs answer distance-related spatial questions, we set the groundwork for developing new techniques that may enable LLMs to perform accurate spatial reasoning.

In the field of mobility, the focus in the past few years has been on the proverbial last mile connectivity. However this paper, narrows the scope from "miles" to the "last 100 yards" presenting a unique sets of issues that are not seen at other levels. The last 100 yards encompass routing and connectivity issues within confined spaces such as houses, apartment building, office spaces and many others. Some of the challenges in this context include coordinating between traditional delivery services (e.g., Fedex, DHL or Amazon Prime) and specialized pilots authorized to operate within the human dominated spaces of the last 100 yards. Ensuring timely delivery of perishable items, addressing the risks of delivery theft and recipient accuracy, and managing the storage and redelivery of packages when recipient are not present further complicates the process. Despite the challenges, the last 100 yards also present opportunities for novel solutions based on automation, robotic routing, social modelling, and industrial planning. In these confined spaces fully automated robotic solutions become feasible as navigation speed and routes are limited and the area can be easily geofenced.

Spatial Pattern Matching is an important search problem that involves reasoning about the relative position, distance, and orientation of objects with respect to one another. Spatial relationships between objects contain a lot of information about the world, which makes them useful in applications like Point of Interest (POI) retrieval and location-based services. However, spatial pattern matching is an NP-hard problem in the worst case. This paper presents a theoretical comparison of spatial pattern matching approaches, showing how the prominent methods compare for each type of spatial relation they support. We further highlight the common techniques used to gain performance improvements and provide suggestions towards developing approximate solutions to this form of spatial search.

OBJECTIVE: The COVID-19 pandemic emphasized the value of geospatial visual analytics for both epidemiologists and the general public. However, systems struggled to encode temporal and geospatial trends of multiple, potentially interacting variables, such as active cases, deaths, and vaccinations. We sought to ask (1) how epidemiologists interact with visual analytics tools, (2) how multiple, time-varying, geospatial variables can be conveyed in a unified view, and (3) how complex spatiotemporal encodings affect utility for both experts and non-experts. MATERIALS AND METHODS: We propose encoding variables with animated, concentric, hollow circles, allowing multiple variables via color encoding and avoiding occlusion problems, and we implement this method in a browser-based tool called CoronaViz. We conduct task-based evaluations with non-experts, as well as in-depth interviews and observational sessions with epidemiologists, covering a range of tools and encodings. RESULTS: Sessions with epidemiologists confirmed the importance of multivariate, spatiotemporal queries and the utility of CoronaViz for answering them, while providing direction for future development. Non-experts tasked with performing spatiotemporal queries unanimously preferred animation to multi-view dashboards. DISCUSSION: We find that conveying complex, multivariate data necessarily involves trade-offs. Yet, our studies suggest the importance of complementary visualization strategies, with our animated multivariate spatiotemporal encoding filling important needs for exploration and presentation. CONCLUSION: CoronaViz's unique ability to convey multiple, time-varying, geospatial variables makes it both a valuable addition to interactive COVID-19 dashboards and a platform for empowering experts and the public during future disease outbreaks. CoronaViz is open-source and a live instance is freely hosted at http://coronaviz.umiacs.io.

With the advance of the geo-positioning technology, the terrain surface data has become increasingly popular and has drawn much research attention from both academia and industry. Answering a shortest-path query for a given source and a given destination on a terrain surface is a fundamental problem and has many applications including Geographical Information System and 3D virtual games. We observe that all existing exact algorithms are only aware of the position of the source point and is unaware of the information of the destination point. Motivated by this, in this paper, we propose an efficient algorithm, namelydirection-oriented algorithm (DIO Algorithm), for answering shortest-path queries on a terrain surface. The algorithm properly guides the search along a direction towards the destination instead of blindly searching all possible directions from the source point. To this end, we convert the geodesic shortest path problem to a shortest obstacle-free euclidean path problem in the 2D planar unfolding of the terrain surface. Based on this conversion, we derive for each part of the terrain surface a lower bound on the length of the shortest path from the source to the destination passing through the part with a novel method. The lower bounds provide useful information that can be used to decide the visiting order of the parts on the terrain surface and guides the search of finding the destination quickly. Our experiments verified that our algorithm runs faster than the state-of-the-art by more than one order of magnitude.

While the electric vehicle (EV) industry is facing some challenges concerning its refueling, its rapid growth in popularity is increasing these difficulties. In this paper, we demonstrate the gravity of the problems that EVs may experience for charging,both now and in the near future, and show how establishing new charging stations can be challenging. We also present the challenges in optimizing the use of charging stations by EV users. Then, we envisage opportunities for the rise of alternative charging options, such as distributed generation, crowdsourced, wireless and mobile charging stations. Additionally, we explain directions on how route and charging stations' location planning can cater to optimizing the charging infrastructure.

Due to the advance of the geo-spatial positioning and the computer graphics technology, digital terrain data has become increasingly popular nowadays. Query processing on terrain data has attracted considerable attention from both the academic and the industry communities. Proximity queries such as the shortest path/distance query, k nearest/farthest neighbor query, and top- k closest/farthest pairs query are fundamental and important queries in the context of the terrain surfaces, and they have a lot of applications in Geographical Information System, 3D object feature vector construction, and 3D object data mining. In this article, we first study the most fundamental type of query, namely, shortest distance and path query, which is to find the shortest distance and path between two points of interest on the surface of the terrain. As observed by existing studies, computing the exact shortest distance/path is very expensive. Some existing studies proposed ϵ -approximate distance and path oracles, where ϵ is a non-negative real-valued error parameter. However, the best-known algorithm has a large oracle construction time, a large oracle size, and a large query time. Motivated by this, we propose a novel ϵ -approximate distance and path oracle called the S pace E fficient distance and path oracle (SE), which has a small oracle construction time, a small oracle size, and a small distance and path query time, thanks to its compactness of storing concise information about pairwise distances between any two points-of-interest. Then, we propose several algorithms for the k nearest/farthest neighbor and top- k closest/farthest pairs queries with the assistance of our distance and path oracle SE . Our experimental results show that the oracle construction time, the oracle size, and the distance and path query time of SE are up to two, three, and five orders of magnitude faster than the best-known algorithm, respectively. Besides, our algorithms for other proximity queries including k nearest/farthest neighbor queries and top- k closest/farthest pairs queries significantly outperform the state-of-the-art algorithms by up to two orders of magnitude.

COVID-19 has brought about substantial social, economic and health related burdens, motivating different control measures from policy makers worldwide. Contact tracing plays a pivotal role in the COVID-19 era. However, contact tracing is by nature entirely retrospective: it can only identify contacts of known or suspected cases. Our proposed system is prospective, aiming to 'create' networks that will ultimately make contact tracing and pandemic management easier. As contact tracing seeks to reconstruct the underlying interaction network, we can improve the process by reducing the complexity of contact network structure; we introduce a method for reducing contact network complexity through strategic scheduling. The method functions through pairwise comparison of individual trajectories in a coordinate space of activities, locations, and time intervals. We demonstrate the method through a simulated scenario where individuals (students) register for activities using a mobile application in a campus. The application then applies our algorithm to provide individuals with schedules that reduce the complexity of the overall network, without compromising individual privacy.

Music is present in numerous forms in our daily lives and is deemed essential to it. Multiple applications have been proposed to let users check into a location and tag that check-in with the song to which they are listening. This is time-consuming and requires much work in voluntary manual tagging. One of our major goals is to automatically determine the spatial scope of a song. Our research challenge is how to identify locations in unstructured and badly-cased lyric texts (e.g., all caps, camel case, non-cased, studly caps, etc.) that are mostly submitted by volunteers from all over the world. Uncertain casing leads to a severe performance drop when using named entity recognition (NER) and geographical information is often lost due to a failure to correctly identify geographical entities. We overcome this failure by normalizing the lyrics in the sense that the information loss is minimized and propose the MusicStand(http://musicstand.umiacs.io/) framework to process/input lyric text that involves three steps: cleaning, truecasing, and geotagging. MusicStand enables users to explore or search a music collection where the goal is to find and play songs about particular geographic entities (i.e., toponyms) using a map query interface. Note that the collection may be static (e.g., a songbook) or dynamic (e.g., a radio playlist).

User trajectory data is becoming increasingly accessible due to the prevalence of GPS-equipped devices such as smartphones. Many existing studies focus on querying trajectories that are similar to each other in their entirety. We observe that trajectories partially similar to each other contain useful information about users’ travel patterns which should not be ignored. Such partially similar trajectories are critical in applications such as epidemic contact tracing. We thus propose to query trajectories that are within a given distance range from each other for a given period of time. We formulate this problem as a sub-trajectory similarity join query named as the STS-Join. We further propose a distributed index structure and a query algorithm for STS-Join, where users retain their raw location data and only send obfuscated trajectories to a server for query processing. This helps preserve user location privacy which is vital when dealing with such data. Theoretical analysis and experiments on real data confirm the effectiveness and the efficiency of our proposed index structure and query algorithm.

Understanding urban areas of interest (AOIs) is essential in many real-life scenarios, and such AOIs can be computed based on the geographic points that satisfy user queries. In this article, we study the problem of efficient and effective visualization of user-defined urban AOIs in an interactive manner. In particular, we first define the problem of user-defined AOI visualization based on a real estate data visualization scenario, and we illustrate why a novel footprint method is needed to support the visualization. After extensively reviewing existing “footprint” methods, we propose a parameter-free footprint method, named AOI-shapes, to capture the boundary information of a user-defined urban AOI. Next, to allow interactive query refinements by the user, we propose two efficient and scalable algorithms to incrementally generate urban AOIs by reusing existing visualization results. Finally, we conduct extensive experiments with both synthetic and real-world datasets to demonstrate the quality and efficiency of the proposed methods.

Online sources of news have steadily supplanted their paper counterparts alongside the growth of the internet. This growth in online news has led to a surplus of data in the form of the text of news articles published online. While an abundance of data is obviously desirable, it can make it difficult for a human to analyze and find trends in the data without assistance. The application demonstrated in the paper aims to aid users in such analysis by building a spatio-textual and spatiotemporal data visualization based on the existing NewsStand architecture. The application is shown to be applicable to tracking the changing geographic prevalence of a disease (e.g., COVID-19) over time.

Moving objects equipped with location-positioning devices continuously generate a large amount of spatio-temporal trajectory data. An interesting finding over a trajectory stream is a group of objects that are travelling together for a certain period of time. We observe that existing studies on mining co-moving objects do not consider an important correlation between co-moving objects, which is the reoccurrence of the co-moving pattern. In this study, we propose the problem of finding recurrent co-moving patterns from streaming trajectories, enabling us to discover recent co-moving patterns that are repeated within a given time period. Experimental results on real-life trajectory data verify the efficiency and effectiveness of our method.

Recognizing representative living patterns in population is extremely valuable for urban planning and decision making. Thanks to the growing popularity of location-based applications and check-ins on social networking sites, Point of Interest (POI) of a location is quite often available in the trajectory data, which expresses user living semantics. However, adopting trajectory semantics for living pattern recognition is an open and challenging research problem due to three major technical challenges: effective feature representation, suitable granularity selection for habit unit, and reliable habit distance measurement. In this paper, we propose a representation learning based system named habit2vec to represent user trajectory semantics in vector space, which preserves the original user living habit information. We evaluated our proposed system on a large-scale real-world dataset provided by a popular social network operator including 123,803 users for 1.5 months in Beijing. The results justify the representation ability of our system in preserving user habit pattern, and demonstrate the effectiveness of clustering users with similar living patterns.

Air Navigation Service Providers (ANSP) worldwide have been making a considerable effort for the development of a better method to monitor conformance to the planned routes and detect anomalies within a particular airspace. Conformance monitoring and anomaly detection are crucial for a better managed airspace, both strategically and tactically, yielding a higher level of automation and thereby reducing the air traffic controller's workload. Although the prior approaches with limited amount of static air traffic data have been able to address the problem to some extent, data management and query processing of ever-increasing vast volume of streaming air traffic data at high rates for online conformance monitoring and anomaly detection still remain a challenge. In this paper, we present a novel data management and analytics system to continuously conformance monitor flights and accurately detect anomalies within the National Airspace System (NAS). The incoming Traffic Flow Management (TFM) data is streaming, big, uncorrelated and noisy. In the overall data pipeline, the system monitors flights and detects anomalies in 3 steps: In the preprocessing step, the system continuously processes the incoming raw flight data and makes it available for the next step where an interim Key-Value data store is created and maintained for efficient query processing. In the final step, the system learns from historical trajectories and pertinent weather parameters and builds a Long Short-Term Memory (LSTM) model. As the flights progress, the non-conforming trajectory segments as part of the live data stream are raised as anomalies. Evaluations on real air traffic and weather data in the U.S. verify that our system efficiently and accurately detects anomalies.

With online social networks being extended to geographical space, location context plays a key role in many applications such as local event detection and location recommendation. Geotagged tweets in Twitter serve as an invaluable source to understand people's activities in urban space. Analyzing geotagged tweets to identify implicit contexts among location, time and text is an interesting problem. In this paper, we present LeGo-CM, a methodology for Leearning embeddings of Geotagged tweets for Cross-Modal search such as locations, time units (hour-of-day and day-of-week) and textual words in tweets. The resulting compact vector representations of these entities make it easy to perform searches like "find which locations are mostly related to the given topics". In LeGo-CM, we first build a graph of entities extracted from tweets in which each edge carries the weight of co-occurrences between two entities. The embeddings of graph nodes are then learned in the same latent space under the guidance of approximating stationary residing probabilities between nodes which are computed using personalized random walk procedures. We evaluate LeGo-CM on datasets of New York City and Los Angeles, showing that the proposed method generally outperforms competitive baseline approaches.

Moving objects equipped with location-positioning devices continuously generate a large amount of spatio-temporal trajectory data. An interesting finding over a trajectory stream is a group of objects that are travelling together for a certain period of time. Existing studies on mining co-moving objects do not consider an important correlation between co-moving objects, which is the reoccurrence of the movement pattern. In this study, we define a problem of finding recurrent pattern of co-moving objects from streaming trajectories and propose an efficient solution that enables us to discover recent co-moving object patterns repeated within a given time period. Experimental results on a real-life trajectory database show the efficiency of our method.

At the present time, there is no mechanism for Air Navigation Service Providers (ANSPs) to probe new flight plans filed by the Airlines Operation Centers (AOCs) against the existing approved flight plans to see if they are likely to cause conflicts or bring sector traffic densities beyond control. In the current Air Traffic Control (ATC) operations, aircraft conflicts and sector traffic densities are resolved tactically, increasing workload and leading to potential safety risks and loss of capacity and efficiency.

Large analytic applications on road networks including simulations, logistics, location-based advertisement, and transportation planning require shortest distance/time methods that provide high throughput (i.e., distance/time computations per second). Our previous work discussed how to process graph distance computations in a PostgreSQL database on a large road network, e.g., 60K distance computations per second per machine, how to "scale out" by using a Spark cluster to achieve 73.8K distance computations per second per machine, and how to obtain a extremely high-throughput solution in memory for city-sized road networks, e.g., 6.7M distance computations per second. However, there is no solution that could achieve more than 1M throughput for large road networks. In an industrial setting, most state-of-the-art solutions yield 5K - 10K shortest distance computations per second per machine even with multi-threads. In this paper, we propose a new distance oracle system (DOS) for large road networks. It can solve most spatial analytic queries, and its throughput achieves 5M distance computations per second even on the whole USA road network. For example, a 10K × 10K origin-distance (OD) matrix can be computed in 20 seconds.

Computing with trajectories has become an important and practical research topic. In many scenarios, the goal is to find similar trajectories. The Fréchet distance is a very promising metric for measuring trajectory similarity and yet limited in practical applications due to its expensive computing complexity. In this paper, we demonstrate an efcicient approach to retrieve similar trajectories using the Fréchet distance. Essentially, the proposed method builds up a set of R-trees for indexing trajectories and thereby enables multi-level of positive and negative filtering to speed up the similarity queries. For answering 5,000 queries on a dataset of 20,000 trajectories, the experimental results show that the proposed method achieves significant speedups at certain filtering levels while maintaining very high precision and recall in retrieving similar trajectories.

Geotagged tweet streams contain invaluable information about the real-world local events like sports games, protests and traffic accidents. Timely detecting and extracting such events has various applications but yet unsolved challenges. In this paper, we present DeLLe, a methodology for automatically Detecting Latest Local Events from geotagged tweet streams. DeLLe first finds unusual locations which have aggregated unexpected number of tweets, and then ranks the unusual locations to select the top ones that are likely to be local event candidates. We evaluate DeLLe on the city of Seattle, WA as well as a larger city of New York. The results show that the proposed method generally outperforms competitive baseline approaches.

Techniques are reviewed for representing multi-dimensional spatial data geometrically and textually based on sorting it. These ideas are also used for metric data where only a distance function indicating the degree of similarity between all object pairs in the dataset are available.

Unprecedented growth is expected globally in commercial air traffic over the next ten years. To accommodate this increase in volume, a new concept of operations has been implemented in the context of the Next Generation Air Transportation System (NextGen) in the USA and the Single European Sky ATM Research (SESAR) in Europe. However, both of the systems approach airspace capacity and efficiency deterministically, failing to account for external operational circumstances which can directly affect the aircraft's actual flight profile. A major factor in increased airspace efficiency and capacity is accurate prediction of Estimated Time of Arrival (ETA) for commercial flights, which can be a challenging task due to a non-deterministic nature of environmental factors, and air traffic. Inaccurate prediction of ETA can cause potential safety risks and loss of resources for Air Navigation Service Providers (ANSP), airlines and passengers. In this paper, we present a novel ETA Prediction System for commercial flights. The system learns from historical trajectories and uses their pertinent 3D grid points to collect key features such as weather parameters, air traffic, and airport data along the potential flight path. The features are fed into various regression models and a Recurrent Neural Network (RNN) and the best performing models with the most accurate ETA predictions are compared with the ETAs currently operational by the European ANSP, EUROCONTROL. Evaluations on an extensive set of real trajectory, weather, and airport data in Europe verify that our prediction system generates more accurate ETAs with a far smaller standard deviation than those of EUROCONTROL. This translates to smaller prediction windows of flight arrival times, thereby enabling airlines to make more cost-effective ground resource allocation and ANSPs to make more efficient flight schedules.

Abstract In this paper we study the problem of supporting effective and scalable visualization for the rapidly increasing volumes of urban data. From an extensive literature study, we find that the existing solutions suffer from at least one of the drawbacks below: (i) loss of interesting structures/outliers due to sampling; (ii) supporting heatmaps only, which provides limited information; and (iii) no notion of real‐world geography semantics (e.g., country, state, city) is captured in the visualization result as well as the underlying index. Therefore, we propose ConcaveCubes, a cluster‐based data cube to support interactive visualization of large‐scale multidimensional urban data. Specifically, we devise an appropriate visualization abstraction and visualization design based on clusters. We propose a novel concave hull construction method to support boundary based cluster map visualization, where real‐world geographical semantics are preserved without any information loss. Instead of calculating the clusters on demand, ConcaveCubes (re)utilizes existing calculation and visualization results to efficiently support different kinds of user interactions. We conduct extensive experiments using real‐world datasets and show the efficiency and effectiveness of ConcaveCubes by comparing with the state‐of‐the‐art cube‐based solutions.

The k -regret query aims to return a size- k subset S of a database D such that, for any query user that selects a data object from this size- k subset S rather than from database D , her regret ratio is minimized. The regret ratio here is modeled by the relative difference in the optimality between the locally optimal object in S and the globally optimal object in D . The optimality of a data object in turn is modeled by a utility function of the query user. Unlike traditional top- k queries, the k -regret query does not minimize the regret ratio for a specific utility function. Instead, it considers a family of infinite utility functions F , and aims to find a size- k subset that minimizes the maximum regret ratio of any utility function in F . Studies on k -regret queries have focused on the family of additive utility functions, which have limitations in modeling individuals’ preferences and decision-making processes, especially for a common observation called the diminishing marginal rate of substitution (DMRS). We introduce k -regret queries with multiplicative utility functions, which are more expressive in modeling the DMRS, to overcome those limitations. We propose a query algorithm with bounded regret ratios. To showcase the applicability of the algorithm, we apply it to a special family of multiplicative utility functions, the Cobb-Douglas family of utility functions, and a closely related family of utility functions, the Constant Elasticity of Substitution family of utility functions, both of which are frequently used utility functions in microeconomics. After a further study of the query properties, we propose a heuristic algorithm that produces even smaller regret ratios in practice. Extensive experiments on the proposed algorithms confirm that they consistently achieve small maximum regret ratios.

The popular micro-blogging service, Twitter, hides invaluable information about real world events. Extracting such information, especially local news, exerts a measure of influence over various applications such as situation awareness and disaster recovery. Detecting small, local news is very challenging, however, due to the sparsity of publicly available Tweets on a specific area. In this work, we present a Twitter user-based method to mitigate the data sparsity. In essence, for a given geographical area, we aim to find as many Twitter users as possible from it and then track their posts to monitor the news happening in that area. However, only a small fraction of Twitter users provide information about their location, making the location information for most of Twitter users not available. Therefore, we utilize a geotagging procedure to estimate location for unknown-location Twitter users thereby finding more Twitter users in a given geographical area. Tracking the post updates of such Twitter users yields a real-time local live tweet stream and thus alleviates the paucity of local tweet data. On the real-time collected tweet stream, we perform online clustering to group tweets together to report potential news. The evaluation shows that in so doing, our method detects hundreds of more local news in comparison with solely utilizing the existing Twitter's publicly available tweet stream.

Currently, deep neural networks are deployed on low-power portable devices by first training a full-precision model using powerful hardware, and then deriving a corresponding low-precision model for efficient inference on such systems. However, training models directly with coarsely quantized weights is a key step towards learning on embedded platforms that have limited computing resources, memory capacity, and power consumption. Numerous recent publications have studied methods for training quantized networks, but these studies have mostly been empirical. In this work, we investigate training methods for quantized neural networks from a theoretical viewpoint. We first explore accuracy guarantees for training methods under convexity assumptions. We then look at the behavior of these algorithms for non-convex problems, and show that training algorithms that exploit high-precision representations have an important greedy search phase that purely quantized training methods lack, which explains the difficulty of training using low-precision arithmetic.

Some analytic queries on road networks, usually concentrating in a local area spanning several cities, need a high-throughput solution such as performing millions of shortest distance computations per second. However, most existing solutions achieve less than 5, 000 shortest distance computations per second per machine even with multi-threads. We demonstrate a solution, termed City Distance Oracles (CDO), using our previously developed ε-distance oracle to achieve as many as 7 million shortest distance computations per second per commodity machine on a city road network, i.e., 10K × 10K origin-distance (OD) matrix can be finished in 14 seconds.

Pursuing criminal activity is tied with understanding illegal or unlawful actions taken on opportunity within a geographic location. Mapping such activities can aid significantly in determining the health of a region, and the vicissitudes of civilian life. Methods to track crime and criminal activity after the fact by mapping news reports of it to geographic locations using the NewsStand system are discussed. NewsStand provides a map-query interface to monitor over 10,000 RSS news sources and making them available within minutes after publication. NewsStand was designed to collect event data given keywords centered on locations specified textually and mapping these locations to their spatial representation, a procedure called geotagging. The goal is to demonstrate how to detect and classify criminal activity by geotagging keywords pertaining to crime, and, in effect, to enhance the capabilities of NewsStand to explicitly show this category of news. The resulting system is named "CrimeStand".

In the past decades, shortest distance methods for road networks have been developed that focus on how to speed up the latency of a single source-target pair distance query. Large analytical applications on road networks including simulations (e.g., evacuation planning), logistics, and transportation planning require methods that provide high throughput (i.e., distance computations per second) and the ability to “scale out” by using large distributed computing clusters. A framework called SPDO is presented which implements an extremely fast distributed algorithm for computing road network distance queries on Apache Spark. The approach extends our previous work of developing the ε-distance oracle which has now been adapted to use Spark's resilient distributed dataset (RDD). Compared with state-of-the-art methods that focus on reducing latency, the proposed framework improves the throughput by at least an order of magnitude, which makes the approach suitable for applications that need to compute thousands to millions of network distances per second.

Automatic summarization of streaming news images is critical for efficient news browsing. Although image duplicates are redundant for news reading, the number of duplicates of a news image is a good indicator for its importance. We describe the architecture used in a news aggregation system for online streaming news image summarization. Given a sequence of images for a news topic, we first cluster image duplicates based on a two-stage feature matching process, followed by representative image selection inside each cluster. Images with a high importance score are ranked chronologically to generate a timeline summarization. Our timeline summarization is not limited to a fixed size but enables users to zoom in to see more images with more details based on their interests. Experiments on real-world news data demonstrate that the timelines produced by our method can generate accurate and dynamic timeline summarizations.

At the heart of Air Traffic Management (ATM) lies the Decision Support Systems (DST) that rely upon accurate trajectory prediction to determine how the airspace will look like in the future to make better decisions and advisories. Dealing with airspace that is prone to congestion due to environmental factors still remains the challenge especially when a deterministic approach is used in the trajectory prediction process. In this paper, we describe a novel stochastic trajectory prediction approach for ATM that can be used for more efficient and realistic flight planning and to assist airspace flow management, potentially resulting in higher safety, capacity, and efficiency commensurate with fuel savings thereby reducing emissions for a better environment. Our approach considers airspace as a 3D grid network, where each grid point is a location of a weather observation. We hypothetically build cubes around these grid points, so the entire airspace can be considered as a set of cubes. Each cube is defined by its centroid, the original grid point, and associated weather parameters that remain homogeneous within the cube during a period of time. Then, we align raw trajectories to a set of cube centroids which are basically fixed 3D positions independent of trajectory data. This creates a new form of trajectories which are 4D joint cubes, where each cube is a segment that is associated with not only spatio-temporal attributes but also with weather parameters. Next, we exploit machine learning techniques to train inference models from historical data and apply a stochastic model, a Hidden Markov Model (HMM), to predict trajectories taking environmental uncertainties into account. During the process, we apply time series clustering to generate input observations from an excessive set of weather parameters to feed into the Viterbi algorithm. Our experiments use a real trajectory dataset with pertaining weather observations and demonstrate the effectiveness of our approach to the trajectory prediction process for ATM.

Discusses the current state of the journal, reports on current and future areas of exploration and research, and presents new editors.

The NewsStand system enables the use of a map query interface to retrieve news articles 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. NewsStand has been enhanced to allow using the map query interface to access other information associated with the articles such as photos and videos, as well as names of people and diseases mentioned in these articles. Here we report on our efforts to enhance NewsStand to display the names of brands and to the articles mentioning them. The challenges in identifying interesting brand mentions are discussed.

When recording their GPS trajectories or posting geo-tagged content on social networks, people produce social spatio-temporal data that can be stored and shared, namely geosocial data. Much of these spatio-temporal data can be used by organizations and applications, for statistical analysis or to provide services that are based on data. By letting people sell the data they produce, to different consumers, both sides can benefit. Thus, we present here a visionary idea of a geosocial marketplace where people and organizations can sell, buy and exchange geosocial data, that is, trade with spatio-temporal data pertaining people. We discuss the involved challenges, such as how to define supply and demand, pricing data, privacy issues and measuring the amount of data being exchanged. We explain the importance of the approach and its applicability. We believe that the proposed vision could motivate followup research in the area of sharing and exchanging spatio-temporal data as well as determining appropriate price points.

Spatial analytical queries on road networks typically perform hundreds of thousands to several millions of shortest distance computations in the process of producing results. These queries require architectures that can compute a large number of network distances. Two architectures are evaluated on a variety of spatial analytical queries on road networks. The first architecture is a widely used hybrid architecture that uses a database to store spatial datasets, a road network distance computing module, and an analysis tool to tie them together into a single query processing pipeline. The second architecture uses of a distance oracle representation of a road network. This architecture stores the spatial datasets and the distance oracle inside the database, and the query processing is completely handled by the database. A detailed evaluation of the two architectures for a variety of analytical query processing tasks such as region, KNN, distance matrix and trajectory queries is presented and the lessons learned are discussed.

Techniques for the specification and representation of the locational component of multimedia data are reviewed. The focus is on how the locational component is specified and also on how it is represented. For the specification component we also discuss textual specifications. For the representation component, the emphasis is on a sorting approach which yields an index to the locational component where the data includes both points as well as objects with a spatial extent.

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.

In a previous work we showed that the knowledge of the spatial reader scope of a news source, that is the geographical location for which its content has been primarily produced, plays an important role in disambiguating toponyms in news articles. The determination of the spatial reader scope of a news source is based on the notion of a local lexicon, which for a location l is defined as a set of concepts, such as names of people, landmarks and historical events, that are spatially related to l. The automatic determination of a local lexicon for a wide range of locations is key to implementing an efficient geotagged news retrieval system, such as NewsStand and its variants TwitterStand and PhotoStand. The major research challenge here is the measurement of the spatial relatedness of a concept to a location. Our previous work resorted to a similarity measure that used the geographic coordinates attached to the Wikipedia articles to find concepts that are spatially related to a certain location. Clearly, this results in local lexicons that mostly include spatial concepts, although non-spatial concepts, such as people or food specialties, are key elements of the identity of a location. In this paper, we explore a set of graph-based similarity measures to determine a local lexicon of a location from Wikipedia without using any spatial clues, based on the observation that the spatial relatedness of a concept to a location is hidden in the Wikipedia link structure. Our evaluation on the local lexicons of 1,200 locations indicates that our observation is well-founded. Additionally, we provide experiments on standard datasets that show that SynRank, one of the measures that we propose for computing the spatial relatedness of a concept to a location, rivals existing similarity measures in determining the semantic relatedness between wikipedia articles.

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.

Mobile location-based applications rely heavily on network connections. When the mobile devices are offline, such applications become less accessible to users. A cache-based method is proposed to improve the offline accessibility for mobile location-based applications. The central idea is that when users are browsing information, the client program not only submits the current query window to the server, but also attempts to predict the most likely (from a probabilistic standpoint) query windows that would be submitted to the server in the future. The major challenge is the very large number of possible future query windows. This challenge is tackled by proposing a discretization technique that makes predictions over a finite subset of all possible query windows. A probabilistic model is proposed for prediction, which is trained using the query log recorded by the client, so that the prediction can be executed entirely on the client side. The advantage of this technique is that it requires no modification on the existing server side, so it can be adapted by most existing applications easily. The usability of the technique is demonstrated by prototyping it on top the NewsStand system so that the query window is constantly changing as users pan and zoom around the world using a gesturing interface, among others. Evaluation shows the prototype to be effective while decreasing the response time.

Incrementally finding the k nearest neighbors (kNN) in a spatial network is an important problem in location-based services. One method (INE) simply applies Dijkstra's algorithm. Another method (IER) computes the k nearest neighbors using Euclidean distance followed by computing their corresponding network distances, and then incrementally finds the next nearest neighbors in order of increasing Euclidean distance until finding one whose Euclidean distance is greater than the current k nearest neighbor in terms of network distance. The LBC method improves on INE by avoiding the visit of nodes that cannot possibly lead to the k nearest neighbors by using a Euclidean heuristic estimator, and on IER by avoiding the repeated visits to nodes in the spatial network that appear on the shortest paths to different members of the k nearest neighbors by performing multiple instances of heuristic search using a Euclidean heuristic estimator on candidate objects around the query point. LBC's drawback is that the maintenance of multiple instances of heuristic search (called wavefronts) requires k priority queues and the queue operations required to maintain them incur a high in-memory processing cost. A method (SWH) is proposed that utilizes a novel heuristic function which considers objects surrounding the query point together as a single unit, instead of as one destination at a time as in LBC, thereby eliminating the need for multiple wavefronts and needs just one priority queue. These results in a significant reduction in the in-memory processing cost components while having the same reduced cost of the access to the spatial network as LBC. SWH is also extended to support the incremental distance semi-join (IDSJ) query, which is a multiple query point generalization of the kNN query. In addition, SWH is shown to support landmark-based heuristic functions, thereby enabling it to be applied to non-spatial networks/graphs such as social networks. Comparisons of experiments on SWH for kNN queries with INE, the best single-wavefront method, show that SWH is 2.5 times faster, and with LBC, the best existing heuristic search method, show that SWH is 3.5 times faster. For IDSJ queries, SWH-IDSJ is 5 times faster than INE-IDSJ, and 4 times faster than LBC-IDSJ.

Techniques for representing multidimensional, spatial, and metric data for applications in spatial databases, geographic information systems (GIS), and location-based services are reviewed. This includes both geometric and textual representations of spatial data.

Moving object databases arise in numerous applications such as traffic monitoring, crowd tracking, and games. They all require keeping track of objects that move and thus the database of objects must be constantly updated. The cover fieldtree (more commonly known as the loose quadtree and the loose octree, depending on the dimension of the underlying space) is designed to overcome the drawback of spatial data structures that associate objects with their minimum enclosing quadtree (octree) cells which is that the size of these cells depends more on the position of the objects and less on their size. In fact, the size of these cells may be as large as the entire space from which the objects are drawn. The loose quadtree (octree) overcomes this drawback by expanding the size of the space that is spanned by each quadtree (octree) cell c of width w by a cell expansion factor p (p>0) so that the expanded cell is of width (1+p)*w and an object is associated with its minimum enclosing expanded quadtree (octree) cell. It is shown that for an object o with minimum bounding hypercube box b of radius r (i.e., half the length of a side of the hypercube), the maximum possible width w of the minimum enclosing expanded quadtree cell c is just a function of r and p, and is independent of the position of o. Normalizing w via division by 2r enables calculating the range of possible expanded quadtree cell sizes as a function of p. For p >= 0.5 the range consists of just two values and usually just one value for p >= 1.

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.

TweetPhoto utilizes a map query interface to display news photos from news articles that are extracted from the tweets of 2,000 Twitter users who have been determined to post news related content. These articles are then geotagged and clustered so that a set of locations are associated with a cluster and its associated images. For each of these locations, the images are scored based on the terms associated with the location and the image's caption. This work differs from traditional work in this area as all topic and location extraction is automated without the need for user entered content or GPS coordinates.

The database architecture and system design of NewsStand, a database system that analyzes and displays streaming news using a map user interface, is described. Special emphasis is given to NewsStand's pipe server, which coordinates individual, independent analysis modules in a processing pipeline, and NewsStand's relational database schema, designed to accommodate responsive spatial querying and retrieval via NewsStand's user interface. Examples of these spatial queries, which are variants of top-k window queries, are also presented. Experiments on the live NewsStand database system demonstrate its capability for rapidly processing large amounts of streaming news as well as the interactivity of its map user interface as measured by database querying.

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.

News sources around the world generate constant streams of information, but effective streaming news retrieval requires an intimate understanding of the geographic content of news. This process of understanding, known as geotagging, consists of first finding words in article text that correspond to location names (toponyms), and second, assigning each toponym its correct lat/long values. The latter step, called toponym resolution, can also be considered a classification problem, where each of the possible interpretations for each toponym is classified as correct or incorrect. Hence, techniques from supervised machine learning can be applied to improve accuracy. New classification features to improve toponym resolution, termed adaptive context features, are introduced that consider a window of context around each toponym, and use geographic attributes of toponyms in the window to aid in their correct resolution. Adaptive parameters controlling the window's breadth and depth afford flexibility in managing a tradeoff between feature computation speed and resolution accuracy, allowing the features to potentially apply to a variety of textual domains. Extensive experiments with three large datasets of streaming news demonstrate the new features' effectiveness over two widely-used competing methods.

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.

News sources on the Web generate constant streams of information, describing many aspects of the events that shape our world. In particular, geography plays a key role in the news, and enabling geographic retrieval of news articles involves recognizing the textual references to geographic locations (called toponyms) present in the articles, which can be difficult due to ambiguity in natural language. Toponym recognition in news is often accomplished with algorithms designed and tested around small corpora of news articles, but these static collections do not reflect the streaming nature of online news, as evidenced by poor performance in tests. In contrast, a method for toponym recognition is presented that is tuned for streaming news by leveraging a wide variety of recognition components, both rule-based and statistical. An evaluation of this method shows that it outperforms two prominent toponym recognition systems when tested on large datasets of streaming news, indicating its suitability for this domain.

The Hausdorff distance is commonly used as a similarity measure between two point sets. Using this measure, a set X is considered similar to Y iff every point in X is close to at least one point in Y . Formally, the Hausdorff distance HausDist( X, Y ) can be computed as the Max-Min distance from X to Y , i.e., find the maximum of the distance from an element in X to its nearest neighbor (NN) in Y . Although this is similar to the closest pair and farthest pair problems, computing the Hausdorff distance is a more challenging problem since its Max-Min nature involves both maximization and minimization rather than just one or the other. A traditional approach to computing HausDist( X, Y ) performs a linear scan over X and utilizes an index to help compute the NN in Y for each x in X . We present a pair of basic solutions that avoid scanning X by applying the concept of aggregate NN search to searching for the element in X that yields the Hausdorff distance. In addition, we propose a novel method which incrementally explores the indexes of the two sets X and Y simultaneously. As an example application of our techniques, we use the Hausdorff distance as a measure of similarity between two trajectories (represented as point sets). We also use this example application to compare the performance of our proposed method with the traditional approach and the basic solutions. Experimental results show that our proposed method outperforms all competitors by one order of magnitude in terms of the tree traversal cost and total response time.

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.

Information sources on the Internet (e.g., Web versions of newspapers) usually have an implicit spatial reader scope, which is the geographical location for which the content has been primarily produced. Knowledge of the spatial reader scope facilitates the construction of a news search engine that provides readers a set of news sources relevant to the location in which they are interested. In particular, it plays an important role in disambiguating toponyms (e.g., textual specifications of geographical locations) in news articles, as the process of selecting an interpretation for the toponym often reduces to one of selecting an interpretation that seems natural in the context of the spatial reader scope. The key to determining the spatial reader scope of news sources is the notion of local lexicon, which for a location s is a set of concepts such as, but not limited to, names of people, landmarks, and historical events, that are spatially related to s. Techniques to automatically generate the local lexicon of a location by using the link structure of Wikipedia are described and evaluated. A key contribution is the improvement of existing methods used in the semantic relatedness domain to extract concepts spatially related to a given location from the Wikipedia. Results of experiments are presented that indicate that the knowledge of the spatial reader scope significantly improves the disambiguation of textually specified locations in news articles and that using local lexicons is an effective method to determine the spatial reader scopes of news sources.

The successful execution of location-based and feature-based queries on spatial databases requires the construction of spatial indexes on the spatial attributes. This is not simple when the data is unstructured as is the case when the data is a collection of documents such as news articles, which is the domain of discourse, where the spatial attribute consists of text that can be (but is not required to be) interpreted as the names of locations. In other words, spatial data is specified using text (known as a toponym) instead of geometry, which means that there is some ambiguity involved. The process of identifying and disambiguating references to geographic locations is known as geotagging and involves using a combination of internal document structure and external knowledge, including a document-independent model of the audience's vocabulary of geographic locations, termed its spatial lexicon. In contrast to previous work, a new spatial lexicon model is presented that distinguishes between a global lexicon of locations known to all audiences, and an audience-specific local lexicon. Generic methods for inferring audiences' local lexicons are described. Evaluations of this inference method and the overall geotagging procedure indicate that establishing local lexicons cannot be overlooked, especially given the increasing prevalence of highly local data sources on the Internet, and will enable the construction of more accurate spatial indexes.

A system, called News Stand, is introduced that automatically extracts images from news articles. The system takes RSS feeds of news article and applies an online clustering algorithm so that articles belonging to the same news topic can be associated with the same cluster. Using the feature vector associated with the cluster, the images from news articles that form the cluster are extracted. First, the caption text associated with each of the images embedded in the news article is determined. This is done by analyzing the structure of the news article's HTML page. If the caption and feature vector of the cluster are found to contain keywords in common, then the image is added to an image repository. Additional meta-information are now associated with each image such as caption, cluster features, names of people in the news article, etc. A very large repository containing more than 983k images from 12 million news articles was built using this approach. This repository also contained more than 86.8 million keywords associated with the images. The key contribution of this work is that it combines clustering and natural language processing tasks to automatically create a large corpus of news images with good quality tags or meta-information so that interesting vision tasks can be performed on it.

The representation of spatial data is an important issue in game programming, computer graphics, visualization, solid modeling, and related areas including computer vision and geographic information systems (GIS). Many representations are currently used. Recently, there has been much interest in hierarchical representations such as quadtrees, octrees, and pyramids which are based on image hierarchies, as well methods that use bounding boxes which are based on object hierarchies. The key advantage of these representations is that they provide a way to index into space. In fact, they are little more than multidimensional sorts. They are compact and depending on the nature of the spatial data they save space as well as time and also facilitate operations such as search.

Techniques for similarity searching in multimedia databases are reviewed. This includes a discussion of the curse of dimensionality, as well as multidimensional indexing, distance-based indexing, and the actual search process which is realized by nearest neighbor finding.

The popularity of location-based services and the need to do real-time processing on them has led to an interest in performing queries on transportation networks, such as finding shortest paths and finding nearest neighbors. The challenge here is that the efficient execution of spatial operations usually involves the computation of distance along a spatial network instead of "as the crow flies," which is not simple. Techniques are described that enable the determination of the network distance between any pair of points (i.e., vertices) with as little as O(n) space rather than having to store the n2distances between all pairs. This is done by being willing to expend a bit more time to achieve this goal such as O(log n) instead of O(1), as well as by accepting an error ε in the accuracy of the distance that is provided. The strategy that is adopted reduces the space requirements and is based on the ability to identify groups of source and destination vertices for which the distance is approximately the same within some ε. The reductions are achieved by introducing a construct termed a distance oracle that yields an estimate of the network distance (termed the ε-approximate distance) between any two vertices in the spatial network. The distance oracle is obtained by showing how to adapt the well-separated pair technique from computational geometry to spatial networks. Initially, an e-approximate distance oracle of size O(n/(ε2)) is used that is capable of retrieving the approximate network distance in O(log n) time using a B-tree. The retrieval time can be theoretically reduced further to O(1) time by proposing another e-approximate distance oracle of size O((n log n)/(ε2)) that uses a hash table. Experimental results indicate that the proposed technique is scalable and can be applied to sufficiently large road networks. For example, a 10-percentapproximate oracle (ε = 0.1) on a large network yielded an average error of 0.9 percent with 90 percent of the answers having an error of 2 percent or less and an average retrieval time of 68 μ seconds. The fact that the network distance can be approximated by one value is used to show how a number of spatial queries can be formulated using appropriate SQL constructs and a few built-in primitives. The result is that these operations can be executed on almost any modern database with no modifications, while taking advantage of the existing query optimizers and query processing strategies.

The spatio-textual spreadsheet is a conventional spreadsheet where spatial attribute values are specified textually. Techniques are presented to automatically find the textually-specified spatial attributes that are present in spreadsheets. Once the spatial attributes have been identified, an accurate translation of the values of the spatial attributes to their actual geographic locations is needed (known as geotagging). The key observation is that spreadsheets with spatial data exhibit spatial coherence --- that is, cells with spatial data that are nearby in the spreadsheet contain data that share spatial characteristics in the real world. These techniques also allow richer search engine results by returning actual tuples from spreadsheets instead of simply links to the spreadsheets. Moreover, when the search key is a particular location, results in proximity to the query can be provided rather than just exact matches.

Twitter is an electronic medium that allows a large user populace to communicate with each other simultaneously. Inherent to Twitter is an asymmetrical relationship between friends and followers that provides an interesting social network like structure among the users of Twitter. Twitter messages, called tweets, are restricted to 140 characters and thus are usually very focused. We investigate the use of Twitter to build a news processing system, called TwitterStand, from Twitter tweets. The idea is to capture tweets that correspond to late breaking news. The result is analogous to a distributed news wire service. The difference is that the identities of the contributors/reporters are not known in advance and there may be many of them. Furthermore, tweets are not sent according to a schedule: they occur as news is happening, and tend to be noisy while usually arriving at a high throughput rate. Some of the issues addressed include removing the noise, determining tweet clusters of interest bearing in mind that the methods must be online, and determining the relevant locations associated with the tweets.

The popularity of location-based services and the need to do real-time processing on them has led to an interest in performing queries on transportation networks, such as finding shortest paths and finding nearest neighbors. The challenge is that these operations involve the computation of distance along a spatial network rather than "as the crow flies." In many applications an estimate of the distance is sufficient, which can be achieved by use of an oracle. An approximate distance oracle is proposed for spatial networks that exploits the coherence between the spatial position of vertices and the network distance between them. Using this observation, a distance oracle is introduced that is able to obtain the epsiv-approximate network distance between two vertices of the spatial network. The network distance between every pair of vertices in the spatial network is efficiently represented by adapting the well-separated pair technique to spatial networks. Initially, use is made of an epsilon-approximate distance oracle of size O(n/epsivd) that is capable of retrieving the approximate network distance in O(log n) time using a B-tree. The retrieval time can be theoretically reduced further to O(1) time by proposing another epsiv-approximate distance oracle of size O(n log n/epsivd) that uses a hash table. Experimental results indicate that the proposed technique is scalable and can be applied to sufficiently large road networks. A 10%-approximate oracle (epsiv = 0.1) on a large network yielded an average error of 0.9% with 90% of the answers making an error of 2% or less and an average retrieval timeof 68 mu seconds. Finally, a strategy for the integration of the distance oracle into any relational database system as well as using it to perform a variety of spatial queries such as region search, k-nearest neighbor search, and spatial joins on spatial networks is discussed.

The advent of location-based services has led to an increased demand for performing operations on spatial networks in real time. The challenge lies in being able to cast operations on spatial networks in terms of relational operators so that they can be performed in the context of a database. A linear-sized construct termed a path oracle is introduced that compactly encodes the n 2 shortest paths between every pair of vertices in a spatial network having n vertices thereby reducing each of the paths to a single tuple in a relational database and enables finding shortest paths by repeated application of a single SQL SELECT operator. The construction of the path oracle is based on the observed coherence between the spatial positions of both source and destination vertices and the shortest paths between them which facilitates the aggregation of source and destination vertices into groups that share common vertices or edges on the shortest paths between them. With the aid of the Well-Separated Pair (WSP) technique, which has been applied to spatial networks using the network distance measure, a path oracle is proposed that takes O ( s d n ) space, where s is empirically estimated to be around 12 for road networks, but that can retrieve an intermediate link in a shortest path in O (log n ) time using a B-tree. An additional construct termed the path-distance oracle of size O ( n · max( s d , 1/ε d )) (empirically ( n · max(12 2 , 2.5/ε 2 ))) is proposed that can retrieve an intermediate vertex as well as an ε-approximation of the network distances in O (log n ) time using a B-tree. Experimental results indicate that the proposed oracles are linear in n which means that they are scalable and can enable complicated query processing scenarios on massive spatial network datasets.

An index is devised to support position-independent search for images containing quartets of icons. Point quartets exist that do not unambiguously map to quadrilaterals, however, four points do unambiguously determine a set of six interpoint line segments. Values for the “size”, “shape”, and “orientation ” attributes of an icon quartet can be derived as functions of this interpoint line set, and can be used to construct a point-based index, in which each point quartet maps to a single point in the resulting hyperdimensional index space. Orientation can be represented by a single, spatially closed dimension. However, assignment of a reference direction for quartets possessing a k-fold rotational symmetry presents a significant challenge. Methods are described for determining shape and orientation attributes for point quartets, and for mapping these attributes onto a set of attribute axes to form a combined index. The orientation computation supplies, as a byproduct, one component of the shape attribute. All attributes are continuous with respect to small variations in the indexed point quartets. 1.

News articles contain a wealth of implicit geographic content that if exposed to readers improves understanding of today's news. However, most articles are not explicitly geotagged with their geographic content, and few news aggregation systems expose this content to users. A new system named NewsStand is presented that collects, analyzes, and displays news stories in a map interface, thus leveraging on their implicit geographic content. NewsStand monitors RSS feeds from thousands of online news sources and retrieves articles within minutes of publication. It then extracts geographic content from articles using a custom-built geotagger, and groups articles into story clusters using a fast online clustering algorithm. By panning and zooming in NewsStand's map interface, users can retrieve stories based on both topical significance and geographic region, and see substantially different stories depending on position and zoom level.

A similarity join operation A BOWTIEepsivB takes two sets of points A, B and a value epsiv isin Ropf, and outputs pairs of points p isin A,q isin B, such that the distance D(p, q) les epsiv. Similarity joins find use in a variety of fields, such as clustering, text mining, and multimedia databases. A novel similarity join algorithm called LSS is presented that executes on a graphics processing unit (GPU), exploiting its parallelism and high data throughput. As GPUs only allow simple data operations such as the sorting and searching of arrays, LSS uses these two operations to cast a similarity join operation as a GPU sort-and-search problem. It first creates, on the fly, a set of space-filling curves on one of its input datasets, using a parallel GPU sort routine. Next, LSS processes each point p of the other dataset in parallel. For each p, it searches an interval of one of the space-filling curves guaranteed to contain all the pairs in which p participates. Using extensive theoretical and experimental analysis, LSS is shown to offer a good balance between time and work efficiency. Experimental results demonstrate that LSS is suitable for similarity joins in large high-dimensional datasets, and that it performs well when compared against two existing prominent similarity join methods.

An algorithm is presented for finding the k nearest neighbors in a spatial network in a best-first manner using network distance. The algorithm is based on precomputing the shortest paths between all possible vertices in the network and then making use of an encoding that takes advantage of the fact that the shortest paths from vertex u to all of the remaining vertices can be decomposed into subsets based on the first edges on the shortest paths to them from u. Thus, in the worst case, the amount of work depends on the number of objects that are examined and the number of links on the shortest paths to them from q, rather than depending on the number of vertices in the network. The amount of storage required to keep track of the subsets is reduced by taking advantage of their spatial coherence which is captured by the aid of a shortest path quadtree. In particular, experiments on a number of large road networks as well as a theoretical analysis have shown that the storage has been reduced from O(N3) to O(N1.5) (i.e., by an order of magnitude equal to the square root). The precomputation of the shortest paths along the network essentially decouples the process of computing shortest paths along the network from that of finding the neighbors, and thereby also decouples the domain S of the query objects and that of the objects from which the neighbors are drawn from the domain V of the vertices of the spatial network. This means that as long as the spatial network is unchanged, the algorithm and underlying representation of the shortest paths in the spatial network can be used with different sets of objects.

Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These algorithms are generally applicable to any index based on hierarchical clustering. The idea is that the data is partitioned into clusters which are aggregated to form other clusters, with the total aggregation being represented as a tree. These algorithms have traditionally used a lower bound corresponding to the minimum distance at which a nearest neighbor can be found (termed MinDist) to prune the search process by avoiding the processing of some of the clusters as well as individual objects when they can be shown to be farther from the query object q than all of the current k nearest neighbors of q. An alternative pruning technique that uses an upper bound corresponding to the maximum possible distance at which a nearest neighbor is guaranteed to be found (termed MaxNearestDist) is described. The MaxNearestDist upper bound is adapted to enable its use for finding the k nearest neighbors instead of just the nearest neighbor (i.e., k=1) as in its previous uses. Both the depth-first and best-first k-nearest neighbor algorithms are modified to use MaxNearestDist, which is shown to enhance both algorithms by overcoming their shortcomings. In particular, for the depth-first algorithm, the number of clusters in the search hierarchy that must be examined is not increased thereby potentially lowering its execution time, while for the best-first algorithm, the number of clusters in the search hierarchy that must be retained in the priority queue used to control the ordering of processing of the clusters is also not increased, thereby potentially lowering its storage requirements.

Similarity join algorithms find pairs of objects that lie within a certain distance ϵ of each other. Algorithms that are adapted from spatial join techniques are designed primarily for data in a vector space and often employ some form of a multidimensional index. For these algorithms, when the data lies in a metric space, the usual solution is to embed the data in vector space and then make use of a multidimensional index. Such an approach has a number of drawbacks when the data is high dimensional as we must eventually find the most discriminating dimensions, which is not trivial. In addition, although the maximum distance between objects increases with dimension, the ability to discriminate between objects in each dimension does not. These drawbacks are overcome via the introduction of a new method called Quickjoin that does not require a multidimensional index and instead adapts techniques used in distance-based indexing for use in a method that is conceptually similar to the Quicksort algorithm. A formal analysis is provided of the Quickjoin method. Experiments show that the Quickjoin method significantly outperforms two existing techniques.

STEWARD ("Spatio-Textual Extraction on the Web Aiding Retrieval of Documents"), a system for extracting, querying, and visualizing textual references to geographic locations in unstructured text documents, is presented. Methods for retrieving and processing web documents, extracting and disambiguating georeferences, and identifying geographic focus are described. A brief overview of STEWARD's querying capabilities, as well as the design of an intuitive user interface, are provided. Finally, several application scenarios and future extensions to STEWARD are discussed.

Database search for images containing icons with specific mutual spatial relationships can be facilitated by an appropriately structured index. For the case of images containing subsets each of which consist of three icons, the one-to-one correspondence between (distinct) point triples and triangles allows the use of such triangle attributes as position, size, orientation, and "shape" in constructing a point-based index, in which each triangle maps to a single point in a resulting hyperdimensional index space. Size (based on the triangle perimeter) can be represented by a single linear dimension. The abstract "shape" of a triangle induces a space that is inherently two-dimensional, and a number of alternative definitions of a basis for this space are examined. Within a plane, orientation reduces to rotation, and (after assignment of a reference direction for the triangle) can be represented by a single, spatially closed dimension. However, assignment of a reference direction for triangles possessing a k-fold rotational symmetry presents a significant challenge. Methods are described for characterizing shape and orientation of triangles, and for mapping these attributes onto a set of linear axes to form a combined index. The shape attribute is independent of size, orientation, and position, and the characterization of shape and orientation is stable with respect to small variations in the indexed triangles.

A variety of techniques for performing a spatial join are reviewed. Instead of just summarizing the literature and presenting each technique in its entirety, distinct components of the different techniques are described and each is decomposed into an overall framework for performing a spatial join. A typical spatial join technique consists of the following components: partitioning the data, performing internal-memory spatial joins on subsets of the data, and checking if the full polygons intersect. Each technique is decomposed into these components and each component addressed in a separate section so as to compare and contrast similar aspects of each technique. The goal of this survey is to describe the algorithms within each component in detail, comparing and contrasting competing methods, thereby enabling further analysis and experimentation with each component and allowing the best algorithms for a particular situation to be built piecemeal, or, even better, enabling an optimizer to choose which algorithms to use.

An iconic image database is a collection of symbolic images where each image is a collection of labeled point features called icons. A method is presented to support fast position-independent similarity search in an iconic database for symbolic images where the similarity condition involves finding icon pairs that satisfy a specific spatial relationship. This is achieved by introducing an index data structure based on r-θ space, which corresponds to the Cartesian product of separation (i.e., inter-icon distance) and (some representation of) relative spatial orientation. In this space, each pairing of two icons is represented by a single point, and all pairs with the same separation and relative orientation (regardless of absolute position) map to the same point. Similarly, all icon pairs with the same separation but different relative orientations map to points on a line parallel to the θ axis, while all pairs with different separations but the same relative orientation map to points on a line parallel to the r axis. Using such an index, database search for icon pairs with a given spatial relationship or range is accomplished by examining the subarea of the index space into which desired pairs would map. This r-θ index space can be organized using well-known spatial database techniques, such as quadtrees or R-trees. Although the size of such an index grows only linearly with respect to the number of images in the collection, it grows quadratically with the average number of icons in an image. A scheme is described to reduce the size of the index by pruning away a subset of the pairs, at the cost of incurring additional work when searching the database. This pruning is governed by a parameter φ, whose variation provides a continuous range of trade-offs between index size and search time.

The result of a distance join operation on two sets of objects R, S on a spatial network G is a set P of object pairs pq, p É R, q É S such that the distance of an object pair pq is the shortest distance from p to q in G. Several variations to the distance join operation such as UnOrdered, Incremental, topk, Semi-Join impose additional constraints on the distance between the object pairs in P, the ordering of object pairs in P, and on the cardinality of P. A distance join algorithm on spatial networks is proposed that works in conjunction with the SILC framework, which is a new approach to query processing on spatial networks. Experimental results demonstrate up to an order of magnitude speed up when compared with a prominent existing technique.

A system that enables real time query processing on large spatial networks is demonstrated. The system provides functionality for processing a wide range of spatial queries such as nearest neighbor searches and spatial joins on spatial networks of sufficiently large sizes.

Cars, aircraft, mobile cell phones, ships, tanks, and mobile robots all have the common property that they are moving objects. A kinematic representation can be used to describe the location of these objects as a function of time. For example, a moving point can be represented by the function p ( t ) = x → 0 + ( t - t 0 ) v → , where x → 0 is the start location, t 0 is the start time, and v → is its velocity vector. Instead of storing the location of the object at a given time in a database, the coefficients of the function are stored. When an object's behavior changes enough so that the function describing its location is no longer accurate, the function coefficients for the object are updated. Because the location of each object is represented as a function of time, spatial query results can change even when no transactions update the database. We present efficient algorithms to maintain k -nearest neighbor, and spatial join queries in this domain as time advances and updates occur. We assume no previous knowledge of what the updates will be before they occur. We experimentally compare these new algorithms with more straight forward adaptations of previous work to support updates. Experiments are conducted using synthetic uniformly distributed data, and real aircraft flight data. The primary metric of comparison is the number of I/O disk accesses needed to maintain the query results and the supporting data structures.

We describe a distributed quadtree index for enabling more powerful access on complex data over P2P networks. It is based on the Chord method. Methods such as Chord have been gaining usage in P2P settings to facilitate exact-match queries. The Chord method maps both the data keys and peer addresses. Our work can be applied to higher dimensions, to various data types, i.e., other than spatial data, and to different types of quadtrees. Finally, we can use other key-based methods than the Chord method as our base P2P routing protocol and index scale well. The index also benefits from the underlying fault-tolerant hashing-based methods by achieving a nice load distribution among many peers. We can seamlessly execute a single query on multiple branches of the index hosted by a dynamic set of peers.

The size of five trie-based methods of sorting large collections of line segments in a spatial database is investigated analytically using a random lines image model and geometric probability techniques. The methods are based on sorting the line segments with respect to the space that they occupy. Since the space is two-dimensional, the trie is formed by interleaving the bits corresponding to the binary representation of the x and y coordinates of the underlying space and then testing two bits at each iteration. The result of this formulation yields a class of representations that are referred to as quadtrie variants, although they have been traditionally referred to as quadtree variants. The analysis differs from prior work in that it uses a detailed explicit model of the image instead of relying on modeling the branching process represented by the tree and leaving the underlying image unspecified. The analysis provides analytic expressions and bounds on the expected size of these quadtree variants. This enables the prediction of storage required by the representations and of the associated performance of algorithms that rely on them. The results are useful in the following two ways: They reveal the properties of the various representations and permit their comparison using analytic, nonexperimental criteria. Some of the results confirm previous analyses (e.g., that the storage requirement of the MX quadtree is proportional to the total lengths of the line segments). An important new result is that for a PMR and Bucket PMR quadtree with sufficiently high values of the splitting threshold (i.e., $\geq 4$) the number of nodes is proportional to the number of line segments and is independent of the maximum depth of the tree. This provides a theoretical justification for the good behavior and use of the PMR quadtree, which so far has been only of an empirical nature.The random lines model was found to be general enough to approximate real data in the sense that the properties of the trie representations, when used to store real data (e.g., maps), are similar to their properties when storing random lines data. Therefore, by specifying an equivalent random lines model for a real map, the proposed analytical expressions can be applied to predict the storage required for real data. Specifying the equivalent random lines model requires only an estimate of the effective number of random lines in it. Several such estimates are derived for real images, and the accuracy of the implied predictions is demonstrated on a real collection of maps. The agreement between the predictions and real data suggests that they could serve as the basis of a cost model that can be used by a query optimizer to generate an appropriate query evaluation plan.

We consider a recursive decomposition of a four-dimensional hypercube into a hierarchy of nested 4-dimensional simplexes, that we call pentatopes. The paper presents an algorithm for finding the neighbors of a pentatope along its five tetrahedral faces in constant time. To this aim, we develop a labeling technique for nested pentatopes that enables their identification by using location codes. The constant-time behavior is achieved through bit manipulation operations, thus avoiding traversing the simplicial hierarchy via pointer following. We discuss an application of this representation to multi-resolution representations of four-dimensional scalar fields. Extracting adaptive continuous approximations of the scalar field from such a model requires generating conforming meshes, i.e., meshes in which the pentatopes match along their tetrahedral faces. Our neighbor finding algorithm enables computing face-adjacent pentatopes efficiently.

The principle of decoupling the partitioning and grouping processes that form the basis of most spatial indexing methods that use tree directories of buckets is explored. The decoupling is designed to overcome the following drawbacks of traditional solutions:(1) multiple postings in disjoint space decomposition methods that lead to balanced trees such as the hB-tree where a node split in the event of node overflow may be such that one of the children of the node that was split becomes a child of both of the nodes resulting from the split;(2) multiple coverage and nondisjointness of methods based on object hierarchies such as the R-tree which lead to nonunique search paths;(3) directory nodes with similarly-shaped hyper-rectangle bounding boxes with minimum occupancy in disjoint space decomposition methods such as those based on quadtrees and k-d trees that make use of regular decomposition.The first two drawbacks are shown to be overcome by the BV-tree where as a result of decoupling the partitioning and grouping processes, the union of the regions associated with the nodes at a given level of the directory does not necessarily contain all of the data points although all searches take the same amount of time. The BV-tree is not plagued by the third drawback. The third drawback is shown to be overcome by the PK-tree where the grouping process is based on ensuring that every node has at least k objects or blocks. The PK-tree is not plagued by the first two drawbacks as they are inapplicable to it. In both cases, the downside of decoupling the partitioning and grouping processes is that the resulting structure is not necessarily balanced, although, since the nodes have a relatively large fanout, the deviation from a balanced structure is relatively small.

A video is used to demonstrate a set of spatial index JAVA applets that enable users on the worldwide web to experiment with a number of variants of the quadtree spatial data structure for different spatial data types, and, most importantly, enable them to see in an animated manner how a number of basic search operations are executed for them. The spatial data types are points, line segments, rectangles, and regions. The search operations are the window query (i.e., a spatial range query) and a nearest neighbor query that enables ranking spatial objects in the order of their distance from a given query object. The representations and algorithms are visualized and animated in a consistent manner using the same primitives and colors so that the differences between the effects of the representations can be easily understood. The video demonstrates the PR quadtree, PM1 quadtree, and R-tree. The applets can be found at: www.cs.umd.edu/~hjs/quadtree/.

We present a new robust line matching algorithm for solving the model-to-image registration problem. Given a model consisting of 3D lines and a cluttered perspective image of this model, the algorithm simultaneously estimates the pose of the model and the correspondences of model lines to image lines. The algorithm combines softassign for determining correspondences and POSIT for determining pose. Integrating these algorithms into a deterministic annealing procedure allows the correspondence and pose to evolve from initially uncertain values to a joint local optimum. This research extends to line features the SoftPOSIT algorithm proposed recently for point features. Lines detected in images are typically more stable than points and are less likely to be produced by clutter and noise, especially in man-made environments. Experiments on synthetic and real imagery with high levels of clutter, occlusion, and noise demonstrate the robustness of the algorithm.

Moving object databases store and process data for objects that change location frequently. Materialized views maintained over time must be updated to reflect changes due to the motion of objects in their environment. To visualize view query results, displays must be updated to reflect the change. In this paper we present the Internet Spatial Spreadsheet (ISS) as a means to organize, query, and visualize changing spatial data in a network environment such as the Internet.The goal of the ISS is to keep client visualizations of query results up to date with the server state. This is accomplished by pushing the minimal set of spatial data needed for rendering query results on the client. Incremental changes to query results are subsequently transmitted to the client as the database is updated to keep the visualization current. Additional constraints in the network environment such as firewall limitations are also considered.

Complex data types-such as images, documents, DNA sequences, etc.-are becoming increasingly important in modern database applications. A typical query in many of these applications seeks to find objects that are similar to some target object, where (dis)similarity is defined by some distance function. Often, the cost of evaluating the distance between two objects is very high. Thus, the number of distance evaluations should be kept at a minimum, while (ideally) maintaining the quality of the result. One way to approach this goal is to embed the data objects in a vector space so that the distances of the embedded objects approximates the actual distances. Thus, queries can be performed (for the most part) on the embedded objects. We are especially interested in examining the issue of whether or not the embedding methods will ensure that no relevant objects are left out. Particular attention is paid to the SparseMap, FastMap, and MetricMap embedding methods. SparseMap is a variant of Lipschitz embeddings, while FastMap and MetricMap are inspired by dimension reduction methods for Euclidean spaces. We show that, in general, none of these embedding methods guarantee that queries on the embedded objects have no false dismissals, while also demonstrating the limited cases in which the guarantee does hold. Moreover, we describe a variant of SparseMap that allows queries with no false dismissals. In addition, we show that with FastMap and MetricMap, the distances of the embedded objects can be much greater than the actual distances. This makes it impossible (or at least impractical) to modify FastMap and MetricMap to guarantee no false dismissals.

Similarity search is a very important operation in multimedia databases and other database applications involving complex objects, and involves finding objects in a data set S similar to a query object q , based on some similarity measure. In this article, we focus on methods for similarity search that make the general assumption that similarity is represented with a distance metric d . Existing methods for handling similarity search in this setting typically fall into one of two classes. The first directly indexes the objects based on distances (distance-based indexing), while the second is based on mapping to a vector space (mapping-based approach). The main part of this article is dedicated to a survey of distance-based indexing methods, but we also briefly outline how search occurs in mapping-based methods. We also present a general framework for performing search based on distances, and present algorithms for common types of queries that operate on an arbitrary "search hierarchy." These algorithms can be applied on each of the methods presented, provided a suitable search hierarchy is defined.

The key issue in performing spatial joins is finding the pairs of intersecting rectangles. For unindexed data sets, this is usually resolved by partitioning the data and then performing a plane sweep on the individual partitions. The resulting join can be viewed as a two-step process where the partition corresponds to a hash-based join while the plane-sweep corresponds to a sort-merge join. In this article, we look at extending the idea of the sort-merge join for one-dimensional data to multiple dimensions and introduce the Iterative Spatial Join . As with the sort-merge join, the Iterative Spatial Join is best suited to cases where the data is already sorted. However, as we show in the experiments, the Iterative Spatial Join performs well when internal memory is limited, compared to the partitioning methods. This suggests that the Iterative Spatial Join would be useful for very large data sets or in situations where internal memory is a shared resource and is therefore limited, such as with today's database engines which share internal memory amongst several queries. Furthermore, the performance of the Iterative Spatial Join is predictable and has no parameters which need to be tuned, unlike other algorithms. The Iterative Spatial Join is based on a plane sweep algorithm, which requires the entire data set to fit in internal memory. When internal memory overflows, the Iterative Spatial Join simply makes additional passes on the data, thereby exhibiting only a gradual performance degradation. To demonstrate the use and efficacy of the Iterative Spatial Join, we first examine and analyze current approaches to performing spatial joins, and then give a detailed analysis of the Iterative Spatial Join as well as present the results of extensive testing of the algorithm, including a comparison with partitioning-based spatial join methods. These tests show that the Iterative Spatial Join overcomes the performance limitations of the other algorithms for data sets of all sizes as well as differing amounts of internal memory.

We deal with the problem of analyzing and visualizing large-size volume data sets. To this aim, we consider multiresolution representations based on a decomposition of the field domain into tetrahedral cells. We compare two types of multiresolution representations that differ on the rule applied to refine an initial coarse mesh: one is based on tetrahedron bisection, and one based on vertex split. The two representations can be viewed as instances of a common multiresolution model, that we call a multiresolution mesh. Encoding data structures for the two representations are briefly described. An experimental comparison on structured volume data sets is presented.

Techniques are presented for moving between adjacent tetrahedra in a tetrahedral mesh. The tetrahedra result from a recursive decomposition of a cube into six initial congruent tetrahedra. A new technique is presented for labeling the triangular faces. The labeling enables the implementation of a binary-like decomposition of each tetrahedron which is represented using a pointerless representation. Outlines of algorithms are given for traversing adjacent triangular faces of equal size in constant time.

An algorithm is given for processing pictorial query specifications that consist of a query image and a similarity level that must hold between the query image and database images. The similarity level specifies the contextual similarity (how well the content of one image matches that of another) as well as the spatial similarity (the relative locations of the matching symbols in the two images). The algorithm differs from previous approaches in its ability to handle multiple instances of each object in both the query and database images by searching for isomorphic subgraphs. The running time of the algorithm is O(m 2/sup m/) in the worst case where all symbols in both the query and database image are from the same class, but falls far below this bound in the presence of spatial constraints.

Techniques are presented for navigating between adjacent triangles of greater or equal size in a hierarchical triangle mesh where the triangles are obtained by a recursive quadtree-like subdivision of the underlying space into four equilateral triangles. These techniques are useful in a number of applications, including finite element analysis, ray tracing, and the modeling of spherical data. The operations are implemented in a manner analogous to that used in a quadtree representation of data on the two-dimensional plane where the underlying space is tessellated into a square mesh. A new technique is described for labeling the triangles, which is useful in implementing the quadtree triangle mesh as a linear quadtree (i.e., a pointer-less quadtree); the navigation can then take place in this linear quadtree. When the neighbors are of equal size, the algorithms have a worst-case constant time complexity. The algorithms are very efficient, as they make use of just a few bit manipulation operations, and can be implemented in hardware using just a few machine language instructions. The use of these techniques when modeling spherical data by projecting it onto the faces of a regular solid whose faces are equilateral triangles, which are represented as quadtree triangle meshes, is discussed in detail. The methods are applicable to the icosahedron, octahedron, and tetrahedron. The difference lies in the way transitions are made between the faces of the polyhedron. However, regardless of the type of polyhedron, the computational complexity of the methods is the same.

Investigates data structures obtained by a recursive partitioning of the input domain into regions of equal size. One of the most well-known examples of such a structure is the quadtree, which is used in this paper as a basis for more complex data structures; we also provide multidimensional versions of the stratified tree of P. van Emde Boas (1997). We show that, under the assumption that the input points have limited precision (i.e. are drawn from an integer grid of size u), these data structures yield efficient solutions to many important problems. In particular, they allow us to achieve O(log log u) time per operation for finding the dynamic approximate nearest neighbor (under insertions and deletions) and the exact online closest pair (under insertions only) in any constant dimension. They allow O(log log u) point location in a given planar shape or in its expansion (dilation by a ball of a given radius). Finally, we provide a linear-time (optimal) algorithm for computing the expansion of a shape represented by a quadtree. This result shows that the spatial order imposed by this regular data structure is sufficient to optimize the dilation by a ball operation.

We compare two different techniques for browsing through a collection of spatial objects stored in an R-tree spatial data structure on the basis of their distances from an arbitrary spatial query object. The conventional approach is one that makes use of a k -nearest neighbor algorithm where k is known prior to the invocation of the algorithm. Thus if m < k neighbors are needed, the k -nearest neighbor algorithm has to be reinvoked for m neighbors, thereby possibly performing some redundant computations. The second approach is incremental in the sense that having obtained the k nearest neighbors, the k + 1 st neighbor can be obtained without having to calculate the k + 1 nearest neighbors from scratch. The incremental approach is useful when processing complex queries where one of the conditions involves spatial proximity (e.g., the nearest city to Chicago with population greater than a million), in which case a query engine can make use of a pipelined strategy. We present a general incremental nearest neighbor algorithm that is applicable to a large class of hierarchical spatial data structures. This algorithm is adapted to the R-tree and its performance is compared to an existing k -nearest neighbor algorithm for R-trees [Rousseopoulos et al. 1995]. Experiments show that the incremental nearest neighbor algorithm significantly outperforms the k -nearest neighbor algorithm for distance browsing queries in a spatial database that uses the R-tree as a spatial index. Moreover, the incremental nearest neighbor algorithm usually outperforms the k -nearest neighber algorithm when applied to the k -nearest neighbor problem for the R-tree, although the improvement is not nearly as large as for distance browsing queries. In fact, we prove informally that at any step in its execution the incremental nearest neighbor algorithm is optimal with respect to the spatial data structure that is employed. Furthermore, based on some simplifying assumptions, we prove that in two dimensions the number of distance computations and leaf nodes accesses made by the algorithm for finding k neighbors is O ( k + k ).

A method has been developed for overcoming some of the major obstacles of object recognition. It represents both 2D images and 3D models from a database by viewpoint invariant descriptors in the same invariant space. As there is a large number of possible matches between the image and model invariants, there is a crucial need to perform this match efficiently. We answer this need by using an adaptation of spatial sorting based on the octree representation of the model points and image lines in three-dimensional space. We show the advantage of the octree method over the traditional "brute-force" approach and we compare the merits of the two methods. This makes it possible for the recognition task to be performed in a reasonable time for a large number of models.

A method for representing and matching logos based on positive and negative shape features is presented. Negative shape features represent an object that consists of several components enclosed in a simple geometric structure (e.g., a square) based on its interior with the components considered as holes. The goal is to find logos in a database that are most similar to a given sample logo. A border is added around logos that are not enclosed in a simple shape. Logos are segmented. Local and global shape features are computed for each component. Two methods for comparing logos represented by positive and negative components are presented and evaluated.

A technique that enables specifying complex queries in image databases using pictorial query trees is presented. The leaves of a pictorial query tree correspond to individual pictorial queries that specify which objects should appear in the target images as well as how many occurrences of each object are required. In addition, the minimum required certainty of matching between query-image objects and database-image objects, as well as spatial constraints that specify bounds on the distance between objects and the relative direction between them are also specified. Internal nodes in the query tree represent logical operations (AND, OR, XOR) and their negations on the set of pictorial queries (or subtrees) represented by its children. The syntax of query trees is described. Algorithms for processing individual pictorial queries and for parsing and computing the overall result of a pictorial query tree are outlined.

Two new spatial join operations, distance join and distance semi-join, are introduced where the join output is ordered by the distance between the spatial attribute values of the joined tuples. Incremental algorithms are presented for computing these operations, which can be used in a pipelined fashion, thereby obviating the need to wait for their completion when only a few tuples are needed. The algorithms can be used with a large class of hierarchical spatial data structures and arbitrary spatial data types in any dimensions. In addition, any distance metric may be employed. A performance study using R-trees shows that the incremental algorithms outperform non-incremental approaches by an order of magnitude if only a small part of the result is needed, while the penalty, if any, for the incremental processing is modest if the entire join result is required.

A new method termed the vertex representation is presented for approximating the shapes of objects of arbitrary dimensionality d (e.g., 2D, 3D, etc.) with orthogonal (d-1)-dimensional faces using a variable number of vertices. The vertex representation can be viewed as a generalization of boundary codes (i.e., chain codes) to higher dimensions. Techniques are described for using the vertex representation to efficiently perform many operations commonly performed on rasters. The utility of these techniques in image database applications is discussed.

A method for specifying pictorial queries to an image database is introduced. A pictorial query specification consists of a query image, and a similarity level that specifies the required extent of similarity between the query image and database images that are to be retrieved. The query image is constructed by positioning objects so that the desired locational and spatial constraints hold. Two image similarity factors are considered: (1) contextual similarity: how well does the content of one image match that of another; (2) spatial similarity: the relative locations of the matching symbols in the two images. Algorithms for retrieving all database images that conform to a given pictorial query specification are presented and compared.

A system named MARCO (denoting map retrieval by content) that is used for the acquisition, storage, indexing, and retrieval of map images is presented. The input to MARCO are raster images of separate map layers and raster images of map composites. A legend-driven map interpretation system converts map layer images from their physical representation to their logical representation. This logical representation is then used to automatically index both the composite and the layer images. Methods for incorporating logical and physical layer images as well as composite images into the framework of a relational database management system are described. Indices are constructed on both the contextual and the spatial data thereby enabling efficient retrieval of layer and composite images based on contextual as well as spatial specifications. Example queries and query processing strategies using these indices are described. The user interface is demonstrated via the execution of an example query. Results of an experimental study on a large amount of data are presented. The system is evaluated in terms of accuracy and in terms of query execution time.

A system for the acquisition, storage, indexing, and retrieval of map images is presented. The input to this system are raster images of separate map layers and map composites. A legend driven map interpretation system converts layer images from a physical to a logical representation. This logical representation is used to automatically index both the composite and the layer images. Methods for incorporating logical and physical layers as well as composite images into the framework of a relational database management system are described. An example query and a corresponding query processing strategy that uses these indices is presented. The user interface is demonstrated via an example query execution.

Abstract A new algorithm is presented for viewing three‐dimensional objects, represented by an octree, from an arbitrary location. The algorithm generates aperspective view of the objects while eliminating hidden surfaces. The viewer can be located anywhere inside or outside the objects. The algorithm presented in this short notefixes an artifact that is generated by a previously published algorithm due to Meagher when the viewer is located in certain regions in space. The new algorithm traverses the octree in a back‐to‐front order and recursively chooses correct orders for visiting the sons of non‐leaf nodes.

In a spatial database, an object may extend arbitrarily in space. As a result, many spatial data structures (e.g., the quadtree, the cell tree, the R+-tree) represent an object by partitioning it into multiple, yet simple, pieces, each of which is stored separately inside the data structure. Many operations on these data structures are likely to produce duplicate results because of the multiplicity of object pieces. A novel approach for duplicate processing based on proximity of spatial objects is presented. This is different from conventional duplicate elimination in database systems because, with spatial databases, different pieces of the same object can span multiple buckets of the underlying data structure. Example algorithms are presented to perform duplicate processing using proximity for quadtree representation of line segments and arbitrary rectangles. The complexity of the algorithms is seen to depend on a geometric classification of different instances of the spatial objects. By using proximity and the spatial properties of the objects, the number of disk-I/O requests as well as the run-time storage during duplicate processing can be reduced.

Efficient data-parallel spatial join algorithms for bucket PMR quadtrees and R-trees, common spatial data structures, are given. The domain consists of planar line segment data (i.e., Bureau of the Census TIGER/Line files). Parallel algorithms for map intersection and a spatial range query are described. The algorithms are implemented using the scan model of parallel computation on the hypercube architecture of the Connection Machine.

A system is presented that utilizes the symbolic knowledge found in the legend of the map to drive geographic symbol recognition. The geographic symbol layer(s) of the map are first scanned. The legend of the map is located and segmented. The geographic symbols are identified and their semantic meaning is attached to them. The geographical symbols in input maps are classified using statistical pattern recognition. An experimental study was conducted on a large amount of data with recognition rates of over 95%.

Data-parallel algorithms for R-trees, a common spatial data structure are presented, in the domain of planar line segment data (e.g., Bureau of the Census TIGER/Line files). Parallel algorithms for both building the data-parallel R-tree, as well as determining the closed polygons formed by the line segments, are described and implemented using the SAM (Scan-And-Monotonic-mapping) model of parallel computation on the hypercube architecture of the Connection Machine.

A qualitative comparative study is performed of the performance of three popular spatial indexing methods - the R-tree, R+-tree, and the PMR quadtree-in the context of processing spatial queries in large line segment databases. The data is drawn from the TIGER/Line files used by the Bureau of the Census to deal with the road networks in the US. The goal is not to find the best data structure as this is not generally possible. Instead, their comparability is demonstrated and an indication is given as to when and why their performance differs. Tests are conducted with a number of large datasets and performance is tabulated in terms of the complexity of the disk activity in building them, their storage requirements, and the complexity of the disk activity for a number of tasks that include point and window queries, as well as finding the nearest line segment to a given point and an enclosing polygon.

An improved and general approach to connected-component labeling of images is presented. The algorithm presented in this paper processes images in predetermined order , which means that the processing order depends only on the image representation scheme and not on specific properties of the image. The algorithm handles a wide variety of image representation schemes (rasters, run lengths, quadrees, bintrees, etc.). How to adapt the standard UNION-FIND algorithm to permit reuse of temporary labels is shown. This is done using a technique called age balancing , in which, when two labels are merged, the older label becomes the father of the younger label. This technique can be made to coexist with the more conventional rule of weight balancing , in which the label with more descendants becomes the father of the label with fewer descendants. Various image scanning orders are examined and classified. It is also shown that when the algorithm is specialized to a pixel array scanned in raster order, the total processing time is linear in the number of pixels. The linear-time processing time follows from a special property of the UNION-FIND algorithm, which may be of independent interest. This property states that under certain restrictions on the input, UNION-FIND runs in time linear in the number of FIND and UNION operations. Under these restrictions, linear-time performance can be achieved without resorting to the more complicated Gabow-Tarjan algorithm for disjoint set union.

The size of five hierarchical geometric data structures is investigated analytically using random image models. Upper bounds and some lower bounds on the size of the structures are derived. The results are useful in predicting the storage required by the structures as well as the performance of algorithms that rely on them.>

Motion planning is studied in a time-varying environment. Each obstacle is a convex polygon that moves in a fixed direction at a constant speed. The robot is a convex polygon that is subject to a speed bound. A method of determining whether or not there is a translational collision-free motion for a polygonal robot from an initial position to a final position and of planning such a motion, if it exists, is presented. The method makes use of the concept of configuration spaces and accessibility. An algorithm is given for motion planning in such an environment, and its time complexity is analyzed.>

Window operations serve as the basis of a number of queries that can be posed in a spatial database. Examples of these window-based queries include the exist query (i.e., determining whether or not a spatial feature exists inside a window) and the report query, (i.e., reporting the identity of all the features that exist inside a window). Algorithms are described for answering window queries in Ο(n log logT) time for a window of size n x n in a feature space (e.g., an image) of size T x T (e.g., pixel elements). The significance of this result is that even though the window contains n2 pixel elements, the worst-case time complexity of the algorithms is almost linearly proportional (and not quadratic) to the window diameter, and does not depend on other factors. The above complexity bounds are achieved via the introduction of the incomplete pyramid data structure (a variant of the pyramid data structure) as the underlying representation to store spatial features and to answer queries on them.

This paper describes QUILT, a prototype geographic information system (GIS) that uses the quadtree data structure as the underlying representation for cartographic data. While QUILT contains many features typically available in a GIS, its primary purpose is to serve as a testbed for the design and testing of new data structures and algorithms for use in computer cartography. Quadtree variants for region, point and line data are implemented using the linear quadtree, organized on disk by a B-tree. QUILT provides a simple attribute attachment system which associates non-spatial data with geographic objects. The user views QUILT as an augmented LISP environment. QUILT's geographic functions include conversion of rasters to and from quadtrees; subset operations to select specified geographic objects; map editing, display, windowing, intersection and union operations; polygon expansion; and computation of geographic object properties such as the centroid, area, perimeter and bounding rectangle for sets of geographic objects.

A one-pass algorithm that performs region expansion in images represented by quadtrees is presented. The algorithm changes to black those white pixels within a specified distance of any black mode in the image. The algorithm yields a significant improvement over previous approaches by reducing both the number of black nodes that must be considered for expansion and the number of nodes that must be inserted as a result of the expansion. The reductions are achieved by introducing the concepts of a merging cluster and a vertex set. Empirical tests show that the execution time of this algorithm generally decreases as the radius of expansion increases, whereas in previous approaches the execution time generally increased with the radius of expansion.>

Motion planning for a point robot is studied in a two-dimensional time-varying environment. The obstacle is a convex polygon that moves in a fixed direction at a constant speed. The point to be reached (referred to as the destination point) also moves along a known path. The concept of accessibility from a point to a moving object is introduced, and it is used to define a graph on a set of moving obstacles. The graph is shown to exhibit an important property, that is, if the moving point is able to move faster than any of the obstacles, a time-minimal path is given as a sequence of edges in the graph. An algorithm is described for generating a time-minimal path, and its execution time is analyzed.>

A method is presented for planning a path in the presence of moving obstacles. Given a set of polygonal moving obstacles, the authors focus on generating a path for a mobile robot that navigates in the two-dimensional plane. Their methodology is to include time as one of the dimensions of the model world. This enables the authors to regard the moving obstacles as being stationary in the extended world. For a solution to be feasible, the robot must not collide with any other moving obstacles, and, also, it must navigate without exceeding the predetermined range of velocity, acceleration, and centrifugal force. The authors investigate an appropriate model to represent the extend world for the path-planning task, and give a time-optimal solution using this model.>

A study is performed of the problem of planning a collision-free path for a robot in a time-varying environment. It is assumed that an obstacle moves along a known path. The formulation also allows the destination point (the point to be reached) to move along a predetermined path. A concept of 'accessibility' from a point to a moving object is introduced and is used to determine a collision-free path. An environment which contains some uncertainty in which the robot needs to see and possibly plan an alternative path is also considered. The ability to deal with moving obstacles is useful in a variety of visual tasks such as the navigation of an autonomous vehicle and the interaction between robot arms.>

A method is presented for planning a path in the presence of moving obstacles. Given a set of polygonal moving obstacles, a path is generated for a mobile robot that navigates in the two-dimensional plane. Time is included as one of the dimensions of the model world. This allows the moving obstacles to be regarded as stationary in the extended world. For a solution to be feasible, the robot must not collide with any other moving obstacles and must navigate within the predetermined range of velocity, acceleration, and centrifugal force. A spatial index is used to facilitate geometric search for the path-planning task. Computer simulation results are presented to illustrate the feasibility of this approach.>

An algorithm is presented to perform connected-component labeling of images of arbitrary dimension that are represented by a linear bintree. The bintree is a generalization of the quadtree data structure that enables dealing with images of arbitrary dimension. The linear bintree is a pointerless representation. The algorithm uses an active border which is represented by linked lists instead of arrays. This results in a significant reduction in the space requirements, thereby making it feasible to process three- and higher-dimensional images. Analysis of the execution time of the algorithm shows almost linear behavior with respect to the number of leaf nodes in the image, and empirical tests are in agreement. The algorithm can be modified easily to compute a (d-1)-dimensional boundary measure (e.g. perimeter in two dimensions and surface area in three dimensions) with linear performance.>

A new method termed population analysis is presented for approximating the distribution of node occupancies in hierarchical data structures which store a variable number of geometric data items per node. The basic idea is to describe a dynamic data structure as a set of populations which are permitted to transform into one another according to certain rules. The transformation rules are used to obtain a set of equations describing a population distribution which is stable under insertion of additional information into the structure. These equations can then be solved, either analytically or numerically, to obtain the population distribution. Hierarchical data structures are modeled by letting each population represent the nodes of a given occupancy. A detailed analysis of quadtree data structures for storing point data is presented, and the results are compared to experimental data. Two phenomena referred to as aging and phasing are defined and shown to account for the differences between the experimental results and those predicted by the model. The population technique is compared with statistical methods of analyzing similar data structures.

A consistent hierarchical data structure for the representation of vector data is presented. It makes use of a concept termed a line segment fragment to prevent data degradation under splitting or clipping of vector primitives. This means that the insertion and subsequent deletion (and vice versa) of a vector leaves the data unchanged. Vectors are represented exactly and not as digital approximations. The data is dynamically organized by use of simple probabilistic splitting and merging rules. The use of the structure for implementing a geographic information system is described. Algorithms for constructing and manipulating the structure are provided. Results of empirical tests comparing the structure to other representations in the literature are given.

A hidden surface algorithm is presented for viewing constructive solid geometry representations of solids (CSG trees) by converting them implicitly into a 3-d recursive spatial subdivision (bintree). The algorithm prunes the CSG tree to its minimal representation within each bintree block and does not evaluate it in regions of space (bintree nodes) that are totally hidden to the observer.

A discussion is presented of the relationship between two solid representation schemes: constructive solid geometry (CSG trees) and recursive spatial subdivision exemplified by the bintree, a generalization of the quadtree and octree. Detailed algorithms are developed and analyzed for evaluating CSG trees by bintree conversion, i.e., by determining explicitly which parts of space are solid and which empty. These techniques enable the addition of the time dimension and motion to the approximate analysis of CSG trees in a simple manner to solve problems such as dynamic interference detection. For "well-behaved" CSG trees, the execution time of the conversion algorithm is directly related to the spatial complexity of the object represented by the CSG tree (i.e., asymptotically it is proportional to the number of bintree nodes as the resolution increases). The set of well-behaved CSG trees includes all trees that define multidimensional polyhedra in a manner that does not give rise to tangential intersections at CSG tree nodes.

Many standard image processing operations can be implemented using quadtrees as a simple tree traversal where, at each terminal node, a computation is performed involving some of that node's neighbors. Most of this work has involved the use of bottom-up neighbor-finding techniques which search for a nearest common ancestor. Recently, top-down techniques have been proposed which make use of a neighbor vector as the tree is traversed. A simplified version of the top-down method for a quadtree in the context of a general-purpose tree traversal algorithm is presented. It differs, in part, from prior work in its ability to compute diagonally adjacent neighbors rather than just horizontally and vertically adjacent neighbors. It builds a neighbor vector for each node using a minimal amount of information. Analysis of the algorithm shows that its execution time is directly proportional to the number of nodes in the tree. However, it does require some extra storage. Use of the algorithm leads to lower execution time bounds for some common quadtree image processing operations such as connected component labeling.

A natural byproduct of the tree-like nature of the quadtree is that many basic image processing operations can be implemented as tree traversals which differ in the nature of the computation that is performed at each node. Some of these computations involve the inspection of a node's adjacent neighbors (termed neighbor finding). A new model is developed for images represented by quadtrees, and it is used to analyze various neighbor-finding techniques. The model's predicted costs for neighbor finding correlate very closely with empirical results and it is superior to the model that was used previously.

The region quadtree is a hierarchical data structure that finds use in applications such as image processing, computer graphics, pattern recognition, robotics, and cartography. In order to save space, a number of pointerless quadtree representations (termed linear quadtrees) have been proposed. One representation maintains the nodes in a list ordered according to a preorder traversal of the quadtree. Using such an image representation and a graph definition of a quadtree, a general algorithm to compute geometric image properties such as the perimeter, the Euler number, and the connected components of an image is developed and analyzed. The algorithm differs from the conventional approaches to images represented by quadtrees in that it does not make use of neighbor finding methods that require the location of a nearest common ancestor. Instead, it makes use of a staircase-like data structure to represent the blocks that have been already processed. The worst-case execution time of the algorithm, when used to compute the perimeter, is proportional to the number of leaf nodes in the quadtree, which is optimal. For an image of size 2n × 2n, the perimeter algorithm requires only four arrays of 2n positions each for working storage. This makes it well suited to processing linear quadtrees residing in secondary storage. Implementation experience has confirmed its superiority to existing approaches to computing geometric properties for images represented by quadtrees.

An adaptation of the quadtree data structure that represents polygonal maps (i.e., collections of polygons, possibly containing holes) is described ina manner that is also useful for the manipulation of arbitrary collections of straight line segments. The gol is to store these maps without the loss of information that results from digitization, and to obtain a worst-case execution time that is not overly sensitive to the positioning of the map. A regular decomposition variant of the region quadtree is used to organize the vertices and edges of the maps. A number of related data organizations are proposed in an iterative manner until a method is obtained that meets the stated goals. The result is termed a PM (polygonal map) quadtree and is based on a regular decomposition point space quadtree (PR quadtree) that stores additional information about the edges at its terminal nodes. Algorithms are given for inserting and deleting line segments from a PM quadtree. Use of the PM quadtree to perform point location, dynamic line insertion, and map overlay is discussed. The PM quadtree is compared conceptually to the K-structure and the layered dag with respect to typical cartographic data. An empirical comparison of the PM quadtree with other quadtree-based representations for polygonal maps is also provided.

We present experiences and comparisons evaluating a fast algorithm for connected component labeling of quad- and octrees. The algorithm works without loss of efficiency on linear tree representations that may reside in external storage.

We present an algorithm for converting from the boundary representation of a solid to the corresponding octree model. The algorithm utilizes an efficient new connected components labeling technique. A novelty of the method is the demonstration that all processing can be performed directly on linear quad and octree encodings. We illustrate the use of the algorithm by an application to geometric mine modeling and verify its performance by analysis and practical experiments.

The ``line quadtree'' data structure hierarchically represents a region and its boundary. Based on the standard quadtree, each node in this structure stores adjacency information as well. While line quadtrees use the same amount of space as standard qaudtrees, they facilitate several region processing algorithms. In particular, we describe efficient algorithms for boundary and superimposing two maps encoded as line quadtrees.

A judicial systems laboratory has been established and several large-scale information management systems projects have been undertaken within the Federal Judicial Center in Washington, D.C. The newness of the court application area, together with the experimental nature of the initial prototypes, required that the system building tools be as flexible and efficient as possible for effective software design and development. The size of the databases, the expected transaction volumes, and the long-term value of the court records required a data manipulation system capable of providing high performance and integrity. The resulting design criteria, the programming capabilities developed, and their use in system construction are described herein. This database programming facility has been especially designed as a technical management tool for the database administrator, while providing the applications programmer with a flexible database software interface for high productivity. Specifically, a network-type database management system using SAIL as the data manipulation host language is described. Generic data manipulation verb formats using SAIL's macro facilities and dynamic data structuring facilities allowing in-core database representations have been developed to achieve a level of flexibility not usually attained in conventional database systems.

Results of a study are summarized in which quadtrees were used to encode the regions in three map overlays representing a small area in northern California. Programs were then written to perform various analysis and manipulation tasks on the quadtree-encoded regions. Data is provided on the compactness of the encodings and the efficiency of the programs.

The concept of distance used in binary array representations of images is adapted to a quadtree representation. The chessboard distance metric is shown to be particularly suitable for the quadtree. A chessboard distance transform for a quadtree is defined as the minimum distance in the plane from each BLACK node to the border of a WHiTE node. An algorithm is presented which computes this transform by only examining the BLACK node's adjacent and abutting neighbors and their progeny. However, unlike prior work with quadtrees, computation of the distance transform requires a capability of finding neighbors in the diagonal direction rather than merely in the horizontal and vertical directions. The algorithm's average execution time is proportional to the number of leaf nodes in the quadtree.

Code optimization is characterized as a time versus space tradeoff. Space optimizations are further decomposed into static and dynamic categories. Using this characterization, the optimization requirements of a list processing language such as LISP are examined. Scrutiny of the structure of programs written in such a language reveals that traditional code optimization techniques have little benefit. Instead, a collection of low-level time and static space optimizations is seen to lead to a potential decrease in space and execution time. Dynamic space optimization is also examined in the context of reducing the frequency of occurrence of garbage collection. Alternatively, some language extensions are proposed which reduce the amount of storage that needs to be allocated, and hence may result in a decrease in the frequency of garbage collection.

An algorithm is presented for labehng the connected components of an image represented by a quadtree.The algorithm proceeds by exploring all possible adjacenoes for each node once and only once.As soon as this ~s done, any equivalences generated by the adjacency labeling phase are propagated Analysis of the algorithm reveals that its average executmn tune ~s of the order (W + B.log B) where B and W correspond to the number of blocks comprising the foreground and background, respecuvely, of the image

An algorithm is presented for constructing a quadtree for a binary image given its row-by-row description. The algorithm processes the image one row at a time and merges identically colored sons as soon as possible, so that a minimal size quadtree exists after processing each pixel. This method is spacewise superior to one which reads in an entire array and then attempts to build the quadtree.

An algorithm is presented for computing the total perimeter of a region in a binary image represented by a quadtree. The algorithm explores each segment of the boundary of the region once and only once. Analysis of the algorithm shows that its average execution time is proportional to the number of leaf nodes in the quadtree.

Abstract Experience with a program to convert from LISP 1.6 to INTERLISP is described. The conversion program was designed with two goals in mind. First, it had to be capable of being executed in either of the languages's environments and it had to yield identical results. Second, the speed of the converted program was to be approximately the same as the original program. This meant that the conversion process must be completed prior to execution of the converted program. The various constraints and considerations imposed by these goals are examined. In addition, aside from problems in finding INTERLISP analogs for various LISP 1.6 constructs, careful consideration must also be paid to input/output functions, escape characters, global variables, representation of numbers and different string implementations.

An algorithm is presented for proving equivalence and inequivalence of instances of formulas involving constant terms. It is based on the construction of an equality data base in the form of a grammar. The algorithm differes from other approaches to the problem by being an on-line algorithm. Equality between two formulas can be proved in time proportional to the number of constant and function symbols appearing within them. An algorithm is also given for updating the equality data base. It has a worse case running time which is proportional to the square of the number of different formulas previously encountered.

A method is presented for parsing syntactic constructs that are permitted to appear independently anywhere in a program. Some examples include comments, macros, and constructs for conditional compilation. Each such construct is defined by its own grammar and parsed by a separate coroutine. The coroutine model of parsing allows the program text to be parsed in one pass despite the syntactic inconsistencies among the program text and the additional constructs. The usefulness of the model is demonstrated by showing how a production language parsing method is extended to handle multiple syntax specifications. The implementation of conditional compilation by carrying along two parses in a coroutine manner is also given. The utility of the model is further demonstrated by showing its adaptation to a recursive descent parser.

Eight Artificial Intelligence programming languages (SAIL, LISP, MICROPLANNER, CONNIVER, MLISP, POP-2, AL, and QLISP) are presented and surveyed, with examples of their use in an automated shop environment. Control structures are compared, and distinctive features of each language are highlighted. A simple programming task is used to illustrate programs in SAIL, LISP, MICROPLANNER, and CONNIVER. The report assumes reader knowledge of programming concepts, but not necessarily of the languages surveyed.

The classical common subexpression problem in program optimization is the detection of identical subexpressions. Suppose we have some extra information and are given pairs of expressions ei1=ei2 which must have the same value, and expressions fj1≠fj2 which must have different values. We ask if as a result, h1=h2, or h1≠h2. This has been called the uniform word problem for finitely presented algebras, and has application in theorem-proving and code optimization. We show that such questions can be answered in O(nlogn) time, where n is the number of nodes in a graph representation of all relevant expressions. A linear time algorithm for detecting common subexpressions is derived. Algorithms which process equalities, inequalities and deductions on-line are discussed.

Requirements for a machine description facility for compiler testing are discussed. The compiler testing procedure consists of proving that programs are correctly translated by the compiler at hand. This is achieved by use of a common intermediate representation for both the source and object programs. The intermediate representation for the object program is built by use of a process termed symbolic interpretation. This process interprets a set of procedures which describe the effects of machine language instructions corresponding to the target machine on a suitable computation model in a manner consistent with an execution level definition of the high level language. Some of the important factors which enter into such a definition are discussed. These include architectural constraints posed by the target machine, and a description facility for memory and data types. Once such a definition is formulated, the actual instruction set of the target machine can be described. The highlights and limitations of such a definition facility are discussed in the context of a specific LISP implementation on a PDP-10 computer.