Modern telecommunication networks are complex and costly to build—they must cover large areas, maintain high reliability and robustness, and provide high quality of service. Thus, network planning is a challenging task that requires considering many factors, including expected volumes of network traffic, geospatial constraints, environmental impacts, available technologies, construction costs, and regulatory compliance. This often involves coping with computationally hard problems like Steiner tree, vertex cover, and graph partitioning, over a geospatial model of the network. Thus, network planning is not always optimal and it can often be enhanced to improve network quality while reducing costs.

When planning cellular networks, the goal is to position antennas and adjust their parameters to maximize the coverage and minimize the interference between antennas. In new generations of cellular networks like 5G, network planning is becoming critical due to the use of high frequencies and the densification of the network. Antenna locations are typically decided based on the availability of cellular towers, however, tunable parameters, like tilt and transmission power, determine the network capacity and the quality of service. To optimize the network and compute coverage and interference for different tilt and power values, radio propagation is simulated using ray tracing over a geospatial model of the environment. In this paper, we present a ray-tracing module that computes long-distance effects of cellular transmissions, to accurately model interference between remote antennas. The two main novelties are (1) the computation of diffraction to include non-line-of-sight propagation, and (2) parallel computation for efficiency and scalability. The demonstration presents the geospatial effect of diffraction on the computation and the use of GPUs for scalability while avoiding race condition in the transformation from a polar coordinate system to a Cartesian representation.

Ethical use of data in generative AI is a growing concern. Large generative AI models are trained on pervasive data sets from a variety of sources, where the data records are fused into the models and become inseparable from them. This raises questions regarding data ownership and the use of personal data, artwork, and copyrighted content in generative AI models. Should people and businesses be allowed to request the removal of their data from a model, even if the data were collected in public places? Should the use of data in generative AI vary across different places based on local copyright laws? How should local laws and regulations regarding data misuse and harmful content be enforced? Can people and organizations verify that their data records have been removed from models or are being used properly? In this paper we discuss the geospatial aspects of data ownership in large generative AI models. We present a vision of generative AI applications that are aware of data ownership and location provenance, based on spatio-temporal features of the data and the usage. These aspects of location-aware AI governance could mitigate some of the risks associated with generative AI and support ethical use of it, in both local and global applications.

The task of finding Hierarchical Heavy Hitters (HHH) was introduced by Cormode et al. [12] as a generalisation of the heavy hitter problem. While finding HHH in data streams has been studied extensively, the question of releasing HHH when the underlying data is private remains unexplored. In this paper, we formalise and study the notion of differentially private HHH, in both the streaming and non-streaming setting. In the non-streaming setting, we show the surprising result that the relative error in estimating the count for any prefix is independent of the height of the hierarchy and the number of heavy hitters in the stream. Additionally, our algorithms also improve the error guarantees of Ghazi et al. [24] for the problem of counting over trees. Meanwhile, in the streaming setting, the main issue is that although the exact version of HHH has low global sensitivity (as counting queries are 1-sensitive), the approximation functions due to streaming have high global sensitivity, linear in the available space. Despite this obstacle, we show that the absolute error for estimating frequencies in the streaming setting is independent of the available space.

Planning of cellular networks is a process in which network engineers select locations for the cellular antennas and adjust parameters like transmission frequency, transmission power and tilt. The goal of network planning is to provide cellular coverage in places that are populated while decreasing interference between nearby antennas. To compute the coverage and interference, a geospatial model of the environment is created and radio propagation models are used for simulating the propagation of the electromagnetic waves. In this paper, we demonstrate a ray tracing tool that we have developed for computation of radio propagation. The tool computes the radio propagation over a 3D model of the world and presents the result as a heat map, in real time. The two main novelties of the system are (1) the ability to play the radio propagation as a video, for analyzing the effect of obstacles on the signal strength in different locations, and (2) inverse ray tracing which finds for a given location the antennas whose transmission affects the cellular signal or the interference at that location.

Accessibility and inclusion in information systems provide guidelines and methods for building applications and devices that work for everyone, including for people with disabilities and other diverse characteristics. Systems that apply accessible and inclusive design (AID) provide an easy way to adapt features for people with different capabilities. In geospatial applications and wearable technology, aspects of location and time should be taken into account as well. In this paper we present a visionary approach of applying contextual filters to the input, output and the underlying dataset of geospatial applications, to examine adaptation of systems, devices and applications to different populations and for verification of accessibility and inclusion. The goal of AID is to help developers add accessibility features to their systems and provide transparency regarding lack of accessibility when needed, e.g., make it clear if there are features that prevent usage by people who lack certain abilities. We explain how to apply AID in physical and virtual worlds, like the metaverse, and we describe how ambient intelligence, accessibility maps and virtual worlds can assist in building accessible and inclusive geospatial applications. We present our vision and elaborate on related challenges and research directions.

We present LedgerView -- a system that adds access control views to permissioned blockchains. The approach is motivated by an AT&T application of tracking refurbished devices. A blockchain is a decentralized tamper-resistant ledger managed by a group of peers. It is used in many applications for storing and sharing sensitive information, e.g., monetary transactions, health records, personal documents, etc. But in blockchain, all the peers see all the stored transactions, while in some applications, access to sensitive information should be limited, that is, concealed from peers and users who do not have proper access permissions. In database management systems, sets of records that are visible to some users and concealed from others are defined by views, but existing blockchain systems lack such access-control capabilities. Thus, in this paper, we introduce access-control views for Hyperledger Fabric. We present two types of views -- irrevocable and revocable, according to whether access to sensitive information can or cannot be revoked. We explain how to implement the two types of view by using cryptographic hash functions and encryption keys, and we show how to support Role-Based Access Control (RBAC). Experiments with supply chain transactions illustrate the incurred costs of the views in LedgerView, including latency, transaction rate and storage overhead.

The growing demand for high-speed networks is increasing the use of high-frequency electromagnetic waves in wireless networks, including in microwave backhaul links and 5G. The relative higher frequency provides a high bandwidth, but it is very sensitive to obstructions and interference. Hence, when positioning a transmitter-receiver pair, the line-of-sight between them should be free of obstacles. Furthermore, the Fresnel zone around the line-of-sight should be clear of obstructions, to guarantee effective transmission. When deploying microwave backhaul links or a cellular network there is a need to select the locations of the antennas accordingly. To help network planners, we developed an interactive tool that allows users to position antennas in different locations over a 3D model of the world. Users can interactively change antenna locations and other parameters, to examine clearance of Fresnel zones. In this paper we illustrate the interactive tool and the ability to test clearance in real-time, to support interactive network planning.

In telecommunication networks, microwave backhaul links are often used as wireless connections between towers. They are used in places where deploying optical fibers is impossible or too expensive. The relatively high frequency of microwaves increases their ability to transfer information at a high rate, but it also makes them susceptible to obstructions and interference. When deploying microwave links, there should be a clear line of sight between every pair of receiver and transmitter, and a buffer around the line of sight defined by the first Fresnel zone should be clear of obstacles. In this paper we discuss the geospatial aspects of microwave backhaul planning and the challenges in developing a system for large scale planning, with the following requirements: (1) the need to cover all of the USA, (2) distance of up to 80 kilometers between towers, and (3) computing batches of thousands of pairs within a few minutes.

Streaming media is gaining popularity, with numerous new services for video on demand and live broadcast. These services stream requested media content to user devices like smart TVs, personal computers and smartphones. Many of these devices are mobile devices, yet streaming media services do not adapt the delivered content to the context of the request, e.g., the location of the user, the time of the request or who are the people near the viewer. In this paper we illustrate how geofencing and geoblocking can be combined with adaptive streaming media to create a new technology of contextually-adapted streaming media. The new technology has the potential to create a new type of experience for streaming media by applying real-time modification of streamed content according to the viewer and the context, e.g., modify inappropriate content when the media is played in public places, change the length of a video played by a train passenger according to a train schedule, etc. The suggested technology can also be used for preventing password sharing in a non-intrusive way and for hyperlocal geoblocking, to facilitate copyright protection. We discuss the vision of modifying streaming media in real time based on the context, elaborate on some of the challenges in implementing this vision, and present novel applications of this new technology.

Associating type to locations can be used to enrich maps and can serve a plethora of geospatial applications. An automatic method to do so could make the process less expensive in terms of human labor, and faster to react to changes. In this paper we study the problem of Geosocial Location Classification, where the type of a site, e.g., a building, is discovered based on social-media posts. Our goal is to correctly associate a set of messages posted in a small radius around a given location with the corresponding location type, e.g., school, church, restaurant or museum. We explore two approaches to the problem: (a) a pipeline approach, where each message is first classified, and then the location associated with the message set is inferred from the separate message labels; and (b) a joint approach where the messages are simultaneously processed to yield the desired location type. We tested the two approaches over a dataset of geotagged tweets. Our results demonstrate the superiority of the joint approach.

Real world anomaly management systems oversee thousands of dynamic data streams and generate an overwhelming number of alerts. As a consequence, important alerts often go unnoticed until there is a crisis. The absence of ground truth, and the fact that the streams are constantly changing (new content, new applications, software and hardware changes) makes assessing the value of alerts difficult. In order to identify groups of important and actionable alerts, we propose: (1) superalerts that reflect characteristics of persistence, pervasiveness and priority, (2) three types of super-alerting based on three types of aggregations and, (3) corresponding metrics for evaluating them. We demonstrate using real-world entertainment data streams.

Three-dimensional models of buildings have a variety of applications, e.g., in urban planning, for making decision where to locate power lines, solar panels, cellular antennas, etc. Often, 3D models are created from a LiDAR point cloud, however, this presents three challenges. First, to generate maps at a nationwide scale or even for a large city, it is essential to effectively store and process the data. Second, there is a need to produce a compact representation of the result, to avoid representing each building as thousands of points. Third, it is often required to seamlessly integrate computed models with non-geospatial features of the geospatial entities.

Unmanned aerial vehicles (UAVs), typically also referred to as drones, are gaining popularity and becoming ubiquitous. As the number of drones in the sky rapidly grows, managing the expected high-volume air traffic is becoming a critical challenge. It is essential to prevent collisions, and to protect the public from nuisances like noise or invasion of privacy, and shield from hazards like falling debris. UAV traffic management should comply with regulation, spatiotemporal constraints and limitations of drones. Spatiotemporal constraints could be no-flight zones or areas where drone flight times are restricted. Drone limitations could refer to their speed, flight range, telecommunication capabilities, etc. Furthermore, managing air traffic for UAVs is very different from managing the traffic of self-driving ground vehicles. First, there are no clearly-marked roads in the sky. Second, some UAVs cannot hover and must have a cleared flight path. Third, air traffic should be managed in a 3-dimensional space. In this paper we present a vision of air-traffic control based on geofencing. We discuss three operation modes: centralized, decentralized and a hybrid of the two other modes. We present some of the challenges involved in drone traffic control and illustrate how geofencing could be a useful tool for that, while leveraging the emerging 5G networking technology.

A ride-hailing service, where passengers choose the origin and destination of their ride, preserves location privacy if the origin and destination of the ride are not revealed to anyone other than the driver. Pseudonymity means that the driver and the passenger use a pseudonym and do not reveal their true identity to each other. The service is trusted if a dishonest passenger cannot use the service without paying, and a driver must provide the service to get paid. In this paper, we introduce cryptotrasnport---a ride-hailing service powered by cryptocurrency and blockchain---and we show that it can preserve privacy, pseudonymity, and trust, simultaneously. Furthermore, by using blockchain technology, cryptotransport matches riders with vehicles in a decentralized fashion, without relying on any company or organization to manage the system.

Modern communication networks are large, dynamic, complex, and increasingly use virtualized network infrastructure. To deploy, maintain, and troubleshoot such networks, it is essential to understand how network elements - such as servers, switches, virtual machines, and virtual network functions - are connected to one another, and to be able to discover communication paths between them. For network maintenance applications such as troubleshooting and service quality management, it is also essential to understand how connections change over time, and be able to pose time-travel queries to retrieve information about past network states. With the industry-wide move to Software Defined Networks and Virtualized Network Functions (VNFs) [26][24], maintaining these inventory and topology databases becomes a critical issue.

A substantial portion of global telecommunication is based on the Internet Protocol (IP), where IP packets are routed from a source host to a destination host via a communication network. While there is some loose connection between IP addresses and geospatial locations, associating packets to geographic coordinates merely according to IP addresses is hard, and often infeasible in real-time, given the rapidity and prodigious volume of packet traffic via routers and switches. This obstructs using geospatial information about the origin, destination, or route of IP packets or flows.

The myriad geotagged posts in the social media constitute a vibrant information source that can be used to support geosocial search, that is, a search for geographic locations based on user activities in online social networks and microblogging platforms. Unlike a traditional geographic search, the results of a geosocial search are not restricted to predefined entities, and may reflect events, sentiments, and other matters that are expressed in the social media. A search for "jogging", for instance, will indicate popular jogging places. A search for "4-th of July Fireworks" would point out places where people watch the spectacle and tweet about it. Yet, geosocial search is different from ordinary Web search because there is no natural partition of the space into documents. There is a need to find new ways to effectively rank, filter, and present results.

Modern communication networks are large, dynamic, and complex. To deploy, maintain, and troubleshoot such networks, it is essential to understand how network elements such as servers, switches, virtual machines, and virtual network functions are connected to one another, and to be able to discover communication paths between them. For network maintenance applications such as troubleshooting and service quality management it is also essential to understand how connections change over time, and be able to pose time-travel queries to retrieve information about past network states. With the industry-wide move to SDNs and virtualized network functions [13], maintaining these inventory databases becomes a critical issue.

This article investigates the problem of geosocial similarity among users of online social networks, based on the locations of their activities (e.g., posting messages or photographs). Finding pairs of geosocially similar users or detecting that two sets of locations (of activities) belong to the same user has important applications in privacy protection, recommendation systems, urban planning, and public health, among others. It is explained and shown empirically that common distance measures between sets of locations are inadequate for determining geosocial similarity. Two novel distance measures between sets of locations are introduced. One is the mutually nearest distance that is based on computing a matching between two sets. The second measure uses a quad-tree index. It is highly scalable but incurs the overhead of creating and maintaining the index. Algorithms with optimization techniques are developed for computing the two distance measures and also for finding the k -most-similar users of a given one. Extensive experiments, using geotagged messages from Twitter, show that the new distance measures are both more accurate and more efficient than existing ones.

A location corroboration of a person is a proof, in the form of a digital record, indicating that this person was at a particular place at a given time. That is, given a user u, a location l and a time t, a location corroboration is a certified evidence that u was at location l at time t. Such corroborations can be used in legal procedures, help solving personal disputes or enable services that rely on knowing with certainty the location of a user at a given time. A corroboration without traces means that the user location is not stored in any public server or in any other public entity, to protect the user privacy. In this paper we present the problem of producing a location corroboration without traces, using a mobile device, and we discuss possible solutions to it.

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.

With mobile devices, web search is no longer limited to specific locations. People conduct search from practically anywhere, including at home, at work, when traveling and when on vacation. How should this influence search tools and web services? In this paper, we argue that information needs are affected by the familiarity of the environment. To formalize this idea, we propose a new contextualization model for activities on the web. The model distinguishes between a search from a familiar place (F-search) and a search from an unfamiliar place (U-search). We formalize the notion of familiarity, and propose a method to identify familiar places. An analysis of a query log of millions of users, demonstrates the differences between search activities in familiar and in unfamiliar locations. Our novel take on search contextualization has the potential to improve web applications, such as query autocompletion and search personalization.

Social media users share billions of items per year, only a small fraction of which is geotagged. We present a data-driven approach for identifying non-geotagged content items that can be associated with a hyper-local geographic area by modeling the location distributions of n-grams that appear in the text. We explore the trade-off between accuracy and coverage of this method. Further, we explore differences across content received from multiple platforms and devices, and show, for example, that content shared via different sources and applications produces significantly different geographic distributions, and that it is preferred to model and predict location for items according to their source. Our findings show the potential and the bounds of a data-driven approach to assigning location data to short social media texts, and offer implications for all applications that use data-driven approaches to locate content.

Recently, there is a rapid growth in the use of microblogs, such as Twitter, and of social networks, such as Instagram, to publish geo-tagged posts that indicate the location of the user at the time when the message is sent. This provides abundant geospatial data that can be analyzed to understand the behavior of masses of people, in particular in urban. Such analysis can improve and facilitate the work of urban planners and of policy makers, e.g., when deciding where to add transportation routes or public institutes. In this demonstration, we present a system that utilizes geo-tagged posts to discover places that were jointly visited by many people. We present the management and the analysis of the data, to illustrate the feasibility of the approach and to indicate new research questions in this domain.

Sampling is being used in statistical surveys to select a subset of individuals from some population, to estimate properties of the population. In stratified sampling, the surveyed population is partitioned into homogeneous subgroups and individuals are selected within the subgroups, to reduce the sample size. In this paper we consider sampling of large-scale, distributed online social networks, and we show how to deal with cases where several surveys are conducted in parallel---in some surveys it may be desired to share individuals to reduce costs, while in other surveys, sharing should be minimized, e.g., to prevent survey fatigue. A multi-survey stratified sampling is the task of choosing the individuals for several surveys, in parallel, according to sharing constraints, without a bias. In this paper, we present a scalable distributed algorithm, designed for the MapReduce framework, for answering stratified-sampling queries over a population of a social network. We also present an algorithm to effectively answer multi-survey stratified sampling, and we show how to implement it using MapReduce. An experimental evaluation illustrates the efficiency of our algorithms and their effectiveness for multi-survey stratified sampling.

In integration of road maps modeled as road vector data, the main task is matching pairs of objects that represent, in different maps, the same segment of a real-world road. In an ad hoc integration, the matching is done for a specific need and, thus, is performed in real time, where only a limited preprocessing is possible. Usually, ad hoc integration is performed as part of some interaction with a user and, hence, the matching algorithm is required to complete its task in time that is short enough for human users to provide feedback to the application, that is, in no more than a few seconds. Such interaction is typical of services on the World Wide Web and to applications in car-navigation systems or in handheld devices. Several algorithms were proposed in the past for matching road vector data; however, these algorithms are not efficient enough for ad hoc integration. This article presents algorithms for ad hoc integration of maps in which roads are represented as polylines. The main novelty of these algorithms is in using only the locations of the endpoints of the polylines rather than trying to match whole lines. The efficiency of the algorithms is shown both analytically and experimentally. In particular, these algorithms do not require the existence of a spatial index, and they are more efficient than an alternative approach based on using a grid index. Extensive experiments using various maps of three different cities show that our approach to matching road networks is efficient and accurate (i.e., it provides high recall and precision). General Terms:Algorithms, Experimentation

Offline map matching is a process of associating a sequence of GPS location readings measured with a device held by a traveling user, to the real-world roads that were presumably traveled by the user. The main goals in map matching are (1) to provide an association which is as accurate as possible with respect to actual traveled roads, and (2) to compute the matching as efficiently as possible. We describe our implementation of a map matching algorithm that enables parallel computation of the matching, being developed as part of the ACM SIGSPATIAL CUP 2012 contest, and we present the results of an experimental evaluation over the data of the contest. We show that our algorithm is efficient and robust in the sense that it maintains a high level of accuracy even when the sampling rate is low.

This demo presents TARSIUS---a system for traffic-aware route search. In a traffic-aware route search (TARS), the user provides start location, target location and search terms, which specify types of geographical entities that should be visited along the route. A TARS query may include additional temporal constraints and limitations on the order by which entities are visited. The goal is to find the fastest route from the start location to the target, via entities of the specified types, while taking into account variations in the travel speed, due to changes in traffic conditions. Planning a route under conditions of uncertainty requires the system to also take into account the possibility that some visited entities will not satisfy the user requirements so that the route may need to go via several entities of the same type. In the demonstration we present the system. We demonstrate a web-based user interface that facilitates the formulation of TARS queries. We show how queries are posed and evaluated over a database that contains real traffic data. Since answering a TARS query is NP-hard, we present three heuristics to the problem. Using the system, we illustrate the routes that are computed by these heuristics.

The impedance mismatch problem that occurs when relational data is being processed by object-oriented (OO) programs, also occurs when OO programs process RDF data, on the Semantic Web. The impedance mismatch problem stems from the inherent differences between RDF and the data model of OO languages. In this paper, we illustrate a solution to this problem. Essentially, we modify an OO language so that RDF individuals become first-class citizens in the language, and objects of the language become first-class citizens in RDF. Three important benefits that follow from this modification are: (1) it becomes natural to use the language as a persistent programming language, (2) the language supports implicit integration of data from multiple data sources, and (3) SPARQL queries and inference can be applied to objects during the run of a program. This demo presents such a modified programming language, namely Ruby on Semantic Web, which is an extension of the Ruby programming language. The demo includes a system, where users can run applications, written in Ruby on Semantic Web, over multiple data sources. In the demo we run code examples. The effects of the execution on the data sources and on the state of the objects in memory are presented visually, in real time.

Many relational operations are best performed when the relations are stored sorted over the relevant attributes (e.g. the common attributes in a natural join operation). However, generally relations are not stored sorted because it is expensive to maintain them this way (and impossible whenever there is more than one relevant sort key). Still, many times relations turn out to be nearly-sorted, where most tuples are close to their place in the order. This state can result from "leftover sortedness", where originally sorted relations were updated, or were combined into interim results when evaluating a complex query. It can also result from weak correlations between attribute values. Currently, nearly-sorted relations are treated the same as unsorted relations, and when relational operations are evaluated for them, a generic algorithm is used. Yet, many operations can be computed more efficiently by an algorithm that exploits this near-ordering.

Complex search tasks that utilize information from several data sources, are answered by integrating the results of distinct basic search queries. In such integration, each basic query returns a ranked list of items, and the main task is to compute the join of these lists, returning the top-k combinations. Computing the top-k join of ranked lists has been studied extensively for the case where the answer comprises merely complete combinations. However, a join is a lossy operation, and over heterogeneous data sources some highly-ranked items, from the results of the basic queries, may not appear in any combination. Yet, such items and the partial combinations in which they appear may still be relevant answers and should not be discarded categorically.

When integrating geo‐spatial data sets, a join algorithm is used for finding sets of corresponding objects (i.e., objects that represent the same real‐world entity). This article investigates location‐based join algorithms for integration of several data sets. First, algorithms for integration of two data sets are presented and their performances, in terms of recall and precision, are compared. Then, two approaches for integration of more than two data sets are described. In one approach, all the integrated data sets are processed simultaneously. In the second approach, a join algorithm for two data sets is applied sequentially, either in a serial manner, where in each join at least one of the joined data sets is a single source, or in a hierarchical manner, where two join results can be joined. For the two approaches, join algorithms are given. The algorithms are designed to perform well even when location of objects are imprecise and each data set represents only some of the real‐world entities. Results of extensive experiments with the different approaches are provided and analyzed. The experiments show the differences, in accuracy and efficiency, between the approaches, under different circumstances. The results also show that all our algorithms have much better accuracy than applying the commonly used one‐sided nearest‐neighbor join.

A route search is an enhancement of an ordinary geographic search. Instead of merely returning a set of entities, the result is a route that goes via entities that are relevant to the search. The input to the problem consists of several search queries, and each query defines a type of geographical entities. When visited, some of the entities succeed in satisfying the user while others fail to do so; however, only the probability of success is known prior to arrival. The main task is to find a route that visits at least one satisfying entity of each type. In an interactive search , the route is computed in steps. In each step, only the next entity of the route is given to the user, and after visiting that entity, the user provides a feedback specifying whether the entity satisfies her. This paper investigates interactive route search in the presence of order constraints that specify that some types of entities should be visited before others. We present heuristic algorithms for interactive route search for two cases, depending on whether the constraints define a complete order or a partial one. The main challenge is to utilize the feedback in order to compute a route that is shorter and has a higher degree of success, compared to routes that are computed non-interactively. We also discuss how to compare the results of the algorithms and introduce suitable measures for doing so. Experiments on real-world data illustrate the efficiency and effectiveness of our algorithms.

In a probabilistic route search, there is a start location, a target location, and search queries Q1, ..., Qn. Each Qi has an answer set Ai consisting of geo-spatial objects and their probabilities. The probability of an object o ∈ Ai specifies the likelihood that o satisfies Qi. The goal is to compute a route that is short and yet has a high probability of satisfying all the Qi. This paper investigates interactive route search. Upon arrival at each object, the user provides feedback specifying whether the object satisfies its corresponding query. The goal is to compute the next object to be visited, based on the feedback. Several heuristic algorithms are given and compared experimentally.

In a geographical route search, given search terms, the goal is to find an effective route that (1) starts at a given location, (2) ends at a given location, and (3) travels via geographical entities that are relevant to the given terms. A route is effective if it does not exceed a given distance limit whereas the ranking scores of the visited entities, with respect to the search terms, are maximal. This paper introduces route-search queries, suggests three semantics for such queries and deals with the problem of efficiently answering queries under the different semantics. Since the problem of answering route-search queries is a generalization of the traveling salesman problem, it is unlikely to have an efficient solution, i.e., there is no polynomial-time algorithm that solves the problem (unless P=NP). Hence, in this work we consider heuristics for the problem. Methods for effectively computing routes are presented. The methods are compared analytically and experimentally. For these methods, experiments on both synthetic and real-world data illustrate their efficiency and their effectiveness in computing a route that satisfies the constraints of a route-search query. Categories and Subject Descriptors

Integration of two road maps is finding a matching between pairs of objects that represent, in the maps, the same real-world road. Several algorithms were proposed in the past for road-map integration; however, these algorithms are not efficient and some of them even require human feedback. Thus, they are not suitable for many important applications (e.g., Web services) where efficiency, in terms of both time and space, is crucial. This paper presents two efficient algorithms for integrating maps in which roads are represented as polylines. The main novelty of these algorithms is in using only the locations of the endpoints of the polylines rather than trying to match whole lines. Experiments on real-world data are given, showing that our approach of integration based on matching merely endpoints is efficient and accurate (that is, it provides high recall and precision).

A framework for describing semantic relationships among nodes in XML documents is presented. In contrast to earlier work, the XML documents may have ID references (i.e., they correspond to graphs and not just trees). A specific interconnection semantics in this framework can be defined explicitly or derived automatically. The main advantage of interconnection semantics is the ability to pose queries on XML data in the style of keyword search. Several methods for automatically deriving interconnection semantics are presented. The complexity of the evaluation and the satisfiability problems under the derived semantics is analyzed. For many important cases, the complexity is tractable and hence, the proposed interconnection semantics can be efficiently applied to real-world XML documents.

Under either the OR-semantics or the weak semantics, the answer to a query over semistructured data consists of maximal rather than complete matchings, i.e., some query variables may be assigned null values. In the relational model, a similar effect is achieved by computing the full disjunction (rather than the natural join or equijoin) of the given relations. It is shown that under either the OR-semantics or the weak semantics, query evaluation has a polynomial-time complexity in the size of the query, the database and the result. It is also shown that the evaluation of full disjunctions is reducible to query evaluation under the weak semantics and hence can be done in polynomial time in the size of the input and the output. Complexity results are also given for two related problems. One is evaluating a projection of the full disjunction and the other is evaluating the set of all tuples in the full disjunction that are non-null on some given attributes. In the special case of γ-acyclic relation schemes, both problems have polynomial-time algorithms in the size of the input and the output. In the general case, such algorithms do not exist, assuming that P ≠ NP. Finally, it is shown that the weak semantics can generalize full disjunctions by allowing tuples to be joined according to general types of conditions, rather than just equalities among attributes.

Abstract EquiX is a search language for XML that combines the power of querying with the simplicity of searching. Requirements for such languages are discussed, and it is shown that EquiX meets the necessary criteria. Both a graph‐based abstract syntax and a formal concrete syntax are presented for EquiX queries. In addition, the semantics is defined and an evaluation algorithm is presented. The evaluation algorithm is polynomial under combined complexity. EquiX combines pattern matching, quantification, and logical expressions to query both the data and meta‐data of XML documents. The result of a query in EquiX is a set of XML documents. A DTD describing the result documents is derived automatically from the query.

Flexible queries facilitate, in a novel way, easy and concise querying of databases that have varying structures. Two different semantics, flexible and semiflexible, are introduced and investigated. The complexity of evaluating queries under the two semantics is analyzed. Query evaluation is polynomial in the size of the query, the database and the result in the following two cases. First, a semiflexible DAG query and a tree database. Second, a flexible tree query and a database that is any graph. Query containment and equivalence are also investigated. For the flexible semantics, query equivalence is always polynomial. For the semiflexible semantics, query equivalence is polynomial for DAG queries and exponential when the queries have cycles. Under the semiflexible and flexible semantics, two databases could be equivalent even when they are not isomorphic. Database equivalence is formally defined and characterized. The complexity of deciding equivalences among databases is analyzed. The implications of database equivalence on query evaluation are explained.

Semistructured data occur in situations where informationThe growing need to integrate data from heterogeneous lacks a homogeneous structure and is incomplete.Yet, up to sources and to access data sources with irregular or incomnow the incompleteness of information has not been reflected plete contents is the main motivation for research into semiby special features of query languages for semistructured structured data models and query languages for them.Semidata.Our goal is to investigate the principles of queries that structured data do not comply with a strict schema and allow for incomplete answers.We do not present, however, are inherently incomplete.Query languages for such data a concrete query language.should ,reflect these characteristics.Queries over classical structured data models contain a number of variables and conditions on these variables.An answer is a binding of the variables by elements of the database such that the conditions are satisfied.In the present paper, we loosen this concept in so far as we allow also answers that are partial, that is, not all variables in the query are bound by such an answer.Partial answers make it necessary to refine the model of query evaluation.The first modification relates to the satisfaction of conditions: under some circumstances we consider conditions involving unbound variables as satisfied.Second, in order to prevent a proliferation of answers, we only accept answers that are maximal in the sense that there are no assignments that bind more variables and satisfy the conditions of the query.