Search

Many modern navigation systems and map-based services do not only provide the fastest route from a source location $s$ s to a target location $t$ t but also provide a few alternative routes to the users as more options to choose from. Consequently, computing alternative paths has received significant research attention. However, it is unclear which of the existing approaches generates alternative routes of better quality because the quality of these alternatives is mostly subjective. Motivated by this, in this paper, we present a user study conducted on the road networks of Melbourne, Dhaka and Copenhagen that compares the quality (as perceived by the users) of the alternative routes generated by four of the most popular existing approaches including the routes provided by Google Maps. We also present a web-based demo system that can be accessed using any internet-enabled device and allows users to see the alternative routes generated by the four approaches for any pair of selected source and target. We report the average ratings received by the four approaches and our statistical analysis shows that there is no credible evidence that the four approaches receive different ratings on average. We also discuss the limitations of this user study and recommend the readers to interpret these results with caution because certain factors may have affected the participants’ ratings. [ABSTRACT FROM AUTHOR]

Aggregate nearest neighbor (Ann) query in both the euclidean space and road networks has been extensively studied, and the flexible aggregate nearest neighbor (Fann) problem further generalizes Ann by introducing an extra flexibility parameter $\phi$ ϕ that ranges in $(0, 1]$ (0 , 1 ] . In this article, we focus on Fann on road networks, denoted as Fann $_\mathcal {R}$ R , and its keyword-aware variant, denoted as KFann $_\mathcal {R}$ R . To solve these problems, we propose a series of universal (i.e., suitable for both max and sum) algorithms, including a Dijkstra-based algorithm that enumerates $P$ P instead of $\phi |Q|$ ϕ | Q | -combinations of $Q$ Q , a queue-based approach that processes data points from-near-to-far, and a framework that combines incremental euclidean restriction (IER) and $k$ k NN. We also propose a specific exact solution to max-Fann $_\mathcal {R}$ R and a constant-factor ratio approximate solution to sum-Fann $_\mathcal {R}$ R . These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend this problem to top- $k$ k and multiple Fann $_\mathcal {R}$ R (resp., KFann $_\mathcal {R}$ R ) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality. [ABSTRACT FROM AUTHOR]

Novel road-network applications often recommend a moving object (e.g., a vehicle) about interesting services or tasks on its way to a destination. A taxi-sharing system, for instance, suggests a new passenger to a taxi while it is serving another one. The traveling cost is then shared among these passengers. A fundamental query is: given two nodes $s$ s and $t$ t , and an area $\mathcal {A}$ A on road network graph $\mathcal {G}$ G , is there a “good” route (e.g., short enough path) $P$ P from $s$ s to $t$ t that crosses $\mathcal {A}$ A in $\mathcal {G}$ G ? In a taxi-sharing system, $s$ s and $t$ t can be a taxi's current and destined locations, and $\mathcal {A}$ A contains all the places to which a person waiting for a taxi is willing to walk. Answering this Route and Area Matching (ROAM) Query allows the application involved to recommend appropriate services to users efficiently. In this paper, we examine efficient ROAM query algorithms. Particularly, we develop solutions for finding a $\rho$ ρ -route, which is an $s$ s - $t$ t path that passes $\mathcal {A}$ A , with a length of at most $(1+\rho)$ (1 + ρ) times the shortest distance between $s$ s and $t$ t . The existence of a $\rho$ ρ -route implies that a service or task located at $\mathcal {A}$ A can be found for a given moving object $m$ m , and that $m$ m only deviates slightly from its current route. We present comprehensive studies on index-free and index-based algorithms for answering ROAM queries. Comprehensive experiments show that our algorithm runs up to 30 times faster than baseline algorithms. [ABSTRACT FROM AUTHOR]

A significant proportion of all search volume consists of local searches. As a result, search engines must be capable of finding relevant results combining both spatial proximity and textual relevance with high query throughput. We observe that existing techniques answering these spatial keyword queries use keyword aggregated indexing, which has several disadvantages on road networks. We propose K-SPIN, a versatile framework that instead uses keyword separated indexing to delay and avoid expensive operations. At first glance, this strategy appears to have impractical pre-processing costs. However, by exploiting several useful observations, we make the indexing cost not only viable but also light-weight. For example, we propose a novel $\rho$ ρ -Approximate Network Voronoi Diagram (NVD) with one order of magnitude less space cost than exact NVDs. By carefully exploiting features of the K-SPIN framework, our query algorithms are up to two orders of magnitude more efficient than the state-of-the-art as shown in our experimental investigation on various queries, parameter settings, and real road network and keyword datasets. [ABSTRACT FROM AUTHOR]

Outsourcing spatial databases to the cloud provides an economical and flexible way for data owners to deliver spatial data to users of location-based services. However, in the database outsourcing paradigm, the third-party service provider is not always trustworthy, therefore, ensuring spatial query integrity is critical. In this paper, we propose an efficient road network \(k\) -nearest-neighbor query verification technique which utilizes the network Voronoi diagram and neighbors to prove the integrity of query results. Unlike previous work that verifies \(k\) -nearest-neighbor results in the Euclidean space, our approach needs to verify both the distances and the shortest paths from the query point to its \(k\) NN results on the road network. We evaluate our approach on real-world road networks together with both real and synthetic points of interest datasets. Our experiments run on Google Android mobile devices which communicate with the service provider through wireless connections. The experiment results show that our approach leads to compact verification objects ( \(\mathcal {VO}\) ) and the verification algorithm on mobile devices is efficient, especially for queries with low selectivity. [ABSTRACT FROM PUBLISHER]

This work deals with the approximate string search in large spatial databases. Specifically, we investigate range queries augmented with a string similarity search predicate in both euclidean space and road networks. We dub this query the spatial approximate string (SAS) query. In euclidean space, we propose an approximate solution, the MHR-tree, which embeds min-wise signatures into an R-tree. The min-wise signature for an index node u keeps a concise representation of the union of q-grams from strings under the subtree of u. We analyze the pruning functionality of such signatures based on the set resemblance between the query string and the q-grams from the subtrees of index nodes. We also discuss how to estimate the selectivity of a SAS query in euclidean space, for which we present a novel adaptive algorithm to find balanced partitions using both the spatial and string information stored in the tree. For queries on road networks, we propose a novel exact method, RSASSOL, which significantly outperforms the baseline algorithm in practice. The RSASSOL combines the q-gram-based inverted lists and the reference nodes based pruning. Extensive experiments on large real data sets demonstrate the efficiency and effectiveness of our approaches. [ABSTRACT FROM PUBLISHER]

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 n² distances 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 ε-approximate distance oracle of size O(n/ε²) 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 ε-approximate distance oracle of size O(n log n/ε² 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-percent-approximate 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. [ABSTRACT FROM AUTHOR]

The increasing availability of location-aware mobile devices has given rise to a flurry of location-based services (LBSs). Due to the nature of spatial queries, an LBS needs the user position in order to process her requests. On the other hand, revealing exact user locations to a (potentially untrusted) LBS may pinpoint their identities and breach their privacy. To address this issue, spatial anonymity techniques obfuscate user locations, forwarding to the LBS a sufficiently large region instead. Existing methods explicitly target processing in the euclidean space and do not apply when proximity to the users is defined according to network distance (e.g., driving time through the roads of a city). In this paper, we propose a framework for anonymous query processing in road networks. We design location obfuscation techniques that: 1) provide anonymous LBS access to the users and 2) allow efficient query processing at the LBS side. Our techniques exploit existing network database infrastructure, requiring no specialized storage schemes or functionalities. We experimentally compare alternative designs in real road networks and demonstrate the effectiveness of our techniques. [ABSTRACT FROM AUTHOR]