Napa holds Google's critical data warehouses in log-structured merge trees for real-time data ingestion and sub-second response for billions of queries per day. These queries are often multi-key look-ups in highly skewed tables and indexes. In our production experience, only progressive query-specific partitioning can achieve Napa's strict query latency SLOs. Here we advocate good-enough partitioning that keeps the per-query partitioning time low without risking uneven work distribution. Our design combines pragmatic system choices and algorithmic innovations. For instance, B-trees are augmented with statistics of key distributions, thus serving the dual purpose of aiding lookups and partitioning. Furthermore, progressive partitioning is designed to be "good enough" thereby balancing partitioning time with performance. The resulting system is robust and successfully serves day-in-day-out billions of queries with very high quality of service forming a core infrastructure at Google.

Google services continuously generate vast amounts of application data. This data provides valuable insights to business users. We need to store and serve these planet-scale data sets under the extremely demanding requirements of scalability, sub-second query response times, availability, and strong consistency; all this while ingesting a massive stream of updates from applications used around the globe. We have developed and deployed in production an analytical data management system, Napa, to meet these requirements. Napa is the backend for numerous clients in Google. These clients have a strong expectation of variance-free, robust query performance. At its core, Napa's principal technologies for robust query performance include the aggressive use of materialized views, which are maintained consistently as new data is ingested across multiple data centers. Our clients also demand flexibility in being able to adjust their query performance, data freshness, and costs to suit their unique needs. Robust query processing and flexible configuration of client databases are the hallmark of Napa design. Most of the related work in this area takes advantage of full flexibility to design the whole system without the need to support a diverse set of preexisting use cases. In comparison, a particular challenge we faced is that Napa needs to deal with hard constraints from existing applications and infrastructure, so we could not do a "green field" system, but rather had to satisfy existing constraints. These constraints led us to make particular design decisions and also devise new techniques to meet the challenges. In this paper, we share our experiences in designing, implementing, deploying, and running Napa in production with some of Google's most demanding applications.

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.

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.

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.

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.

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.

We identify an opportunity to share data among mobile apps hosted in the cloud, thus helping users improve their mobile experience, while resulting in cost savings for the cloud provider. In this work, we propose a platform for sharing data among mobile apps hosted in the cloud. A “sharing ” is specified by a triple consisting of: (a) a set of data sources to be shared, (b) a set of specified transforma-tions on the shared data, and (c) a staleness (freshness) requirement on the shared data. The platform addresses the following two main challenges: What sharings to admit into the system under a set of specified constraints, how to implement a sharing at a low cost while maintaining the desired level of staleness. We show that reductions in costs are achievable by exploiting the commonalities between the different sharings in the platform. Experimental evaluation is per-formed with a cloud platform containing 25 sharings among mo-bile apps with realistic datasets containing user, social, location and checkin data. Our platform is able to maintain the sharings with very few violations, even under a very high update rate. Our results show that our method results in a cost savings of over 35 % for the cloud provider, while enabling an improved mobile experience for users. 1.

Big data analytical systems, such as MapReduce, perform aggressive materialization of intermediate job results in order to support fault tolerance. When jobs correspond to exploratory queries submitted by data analysts, these materializations yield a large set of materialized views that we propose to treat as an opportunistic physical design. We present a semantic model for UDFs that enables effective reuse of views containing UDFs along with a rewrite algorithm that provably finds the minimum-cost rewrite under certain assumptions. An experimental study on real-world datasets using our prototype based on Hive shows that our approach can result in dramatic performance improvements.

Multistore systems utilize multiple distinct data stores such as Hadoop's HDFS and an RDBMS for query processing by allowing a query to access data and computation in both stores. Current approaches to multistore query processing fail to achieve the full potential benefits of utilizing both systems due to the high cost of data movement and loading between the stores. Tuning the physical design of a multistore, i.e., deciding what data resides in which store, can reduce the amount of data movement during query processing, which is crucial for good multistore performance. In this work, we provide what we believe to be the first method to tune the physical design of a multistore system, by focusing on which store to place data. Our method, called MISO for MultISstore Online tuning, is adaptive, lightweight, and works in an online fashion utilizing only the by-products of query processing, which we term as opportunistic views. We show that MISO significantly improves the performance of ad-hoc big data query processing by leveraging the specific characteristics of the individual stores while incurring little additional overhead on the stores.

Enabling data sharing among mobile apps hosted in the same cloud infrastructure can provide a competitive advantage to the mobile apps by giving them access to rich information as well as increasing the revenue for the cloud provider. We introduce a costing tool that allows application owners (i.e., consumers) and the cloud service provider to assess the cost of a desired data sharing. The costing tool enables the consumers to effectively explore the cost space by choosing between alternative configurations of varying data qualities, specified by the staleness and the accuracy of the data sharing. In other words, staleness and accuracy requirements on the data sharing are used as levers for controlling costs. These capabilities are implemented in a What-if analysis tool, which has been integrated with a large data-sharing platform. We conducted extensive experiments on the integrated platform with a sharing ecosystem created around Twitter data and show the effectiveness of the results produced by the What-if tool.

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.

No abstract available.

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.

Given a unlabelled set of points X ϵ ℝNbelonging to k groups, we propose a method to identify cluster assignments that provides maximum separating margin among the clusters. We address this problem by exploiting sparsity in data points inherent to margin regions, which a max-margin classifier would produce under a supervised setting to separate points belonging to different groups. By analyzing the projections of X on the set of all possible lines L in ℝN, we first establish some basic results that are satisfied only by those line intervals lying outside a cluster, under assumptions of linear separability of clusters and absence of outliers. We then encode these results into a pair-wise similarity measure to determine cluster assignments, where we accommodate non-linearly separable clusters using the kernel trick. We validate our method on several UCI datasets and on some computer vision problems, and empirically show its robustness to outliers, and in cases where the exact number of clusters is not available. The proposed approach offers an improvement in clustering accuracy of about 6% on the average, and up to 15% when compared with several existing methods.

The mobility of today is defined by the multitude of apps, which while working in isolation, can achieve a variety of tasks for the mobile user. The mobility of tomorrow is envisioned as one where mobile apps work together by sharing information to create a seamless mobile experience, where the focus is the mobility of the user but not the device. A Platform as a Service (PaaS) system called COSMOS (stands for Clouddb for Seamless Mobile Services) is proposed to provide the necessary support for seamless mobility. COSMOS is a multitenant, SLA-aware, cloud based PaaS system, which is currently under active development. The core component of COSMOS is the Sharing Middleware (SMILE), which provides the infrastructure for mobile apps residing on COSMOS to share data actively with one another. SMILE allows for management of SLAs on the shared data, which means that some serious technical challenges will have to be overcome in order to guarantee the desired level of access on the shared data to all those who access it. The key challenge is in ensuring that SLA guarantees are provided in the face of multiple users with diverse workloads and SLA requirements, while providing performance guarantees for the data owners in sharing data with others using performance isolation policies. Additional services for mobile apps, such as mobile context, recommendation and analytics are proposed by leveraging on SMILE. The challenges in designing COSMOS and SMILE as well as solution strategies are discussed.

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 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.

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.

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.

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.