227 research outputs found
Outdoor-indoor Space:Unified Modeling and Shortest Path Search
No full textGraph models are widely used for representing the topology of outdoor space (O-Space) and indoor space (I-Space). However, existing models neglect the intersection between O-Space and I-Space, only allowing for computations such as shortest path and nearest neighbor queries in either O-Space or I-Space, separately. In this paper, we present two different outdoor-indoor space (OI-Space) models allowing queries to operate on a mix of both spaces. The first model keeps the distinct nature of the two spaces intact by having explicit connections between outdoor and indoor spaces. The second model abstracts this distinction away, and provides a unified model of outdoor-indoor space. For each model, we present an algorithm that is able to span the two types of spaces to return the real shortest path between two arbitrary points. The experimental evaluations show that the proposed models and algorithms perform well enough to be usable in practice
A pattern-based framework for addressing data representational inconsistency
No full textData representational inconsistency, where data has diverse formats or structures, is a crucial data quality problem. Existing fixing approaches either target on a specific domain or require massive information from users. In this work, we propose a user-friendly pattern-based framework for addressing data representational inconsistency. Our framework consists of three modules: pattern design, pattern detection, and pattern unification. We identify several challenges in all the three tasks in order to handle an inconsistent dataset both accurately and efficiently. We propose various techniques to tackle these issues, and our experimental results on real-life datasets demonstrate better performance of our proposals compared with existing methods
Scalable and fast top-k most similar trajectories search using MapReduce in-memory
No full textTop-k most similar trajectories search (k-NN) is frequently used as classification algorithm and recommendation systems in spatialtemporal trajectory databases. However, k-NN trajectories is a complex operation, and a multi-user application should be able to process multiple k-NN trajectories search concurrently in large-scale data in an efficient manner. The k-NN trajectories problem has received plenty of attention, however, state-of-the-art works neither consider in-memory parallel processing of k-NN trajectories nor concurrent queries in distributed environments, or consider parallelization of k-NN search for simpler spatial objects (i.e. 2D points) using MapReduce, but ignore the temporal dimension of spatial-temporal trajectories. In this work we propose a distributed parallel approach for k-NN trajectories search in a multi-user environment using MapReduce in-memory. We propose a space/time data partitioning based on Voronoi diagrams and time pages, named Voronoi Pages, in order to provide both spatial-temporal data organization and process decentralization. In addition, we propose a spatialtemporal index for our partitions to efficiently prune the search space, improve system throughput and scalability.We implemented our solution on top of Spark’s RDD data structure, which provides a thread-safe environment for concurrent MapReduce tasks in main-memory. We perform extensive experiments to demonstrate the performance and scalability of our approach
Efficiently processing snapshot and continuous reverse k nearest neighbors queries
No full textGiven a set of objects and a query q, a point p is called the reverse k nearest neighbor (RkNN) of q if q is one of the k closest objects of p. In this paper, we introduce the concept of influence zone that is the area such that every point inside this area is the RkNN of q and every point outside this area is not the RkNN. The influence zone has several applications in location-based services, marketing and decision support systems. It can also be used to efficiently process RkNN queries. First, we present efficient algorithm to compute the influence zone. Then, based on the influence zone, we present efficient algorithms to process RkNN queries that significantly outperform existing best-known techniques for both the snapshot and continuous RkNN queries. We also present a detailed theoretical analysis to analyze the area of the influence zone and IO costs of our RkNN processing algorithms. Our experiments demonstrate the accuracy of our theoretical analysis. This paper is an extended version of our previous work (Cheema et al. in Proceedings of ICDE, pp. 577-588, 2011). We make the following new contributions in this extended version: (1) we conduct a rigorous complexity analysis and show that the complexity of one of our proposed algorithms in Cheema et al. (Proceedings of ICDE, pp. 577-588, 2011) can be reduced from O(m 2) to O(km) where m > k is the number of objects used to compute the influence zone, (2) we show that our techniques can be applied to dimensionality higher than two, and (3) we present efficient techniques to handle data updates. © 2012 Springer-Verlag
An efficient method to find the optimal social trust path in contextual social graphs
No full textOnline Social Networks (OSN) have been used as platforms for many emerging applications, where trust is a critical factor for participants’ decision making. In order to evaluate the trustworthiness between two unknown participants, we need to perform trust inference along the social trust paths formed by the interactions among the intermediate participants. However, there are usually a large number of social trust paths between two participants. Thus, a challenging problem is how to effectively and efficiently find the optimal social trust path that can yield the most trustworthy evaluation result based on the requirements of participants. In this paper, the core problem of finding the optimal social trust path with multiple constraints of social contexts is modelled as the classical NP-Complete Multi-Constrained Optimal Path (MCOP) selection problem. To make this problem practically solvable, we propose an efficient and effective approximation algorithm, called T-MONTE-K, by combining Monte Carlo method and our optimised search strategies. Lastly we conduct extensive experiments based on a real-world OSN dataset and the results demonstrate that the proposed T-MONTE-K algorithm can outperform state-of-the-art MONTE_K algorithm significantly
On efficient passenger assignment for group transportation
No full textWith the increasing popularity of LBS services, spatial assignment has become an important problem nowadays. Nevertheless most existing works use Euclidean distance as the measurement of spatial proximity. In this paper, we investigate a variant of spatial assignment problem with road networks as the underlying space. Given a set of passengers and a set of vehicles, where each vehicle waits for the arrival of all passengers assigned to it, and then carries them to the same destination, our goal is to find an assignment from passengers to vehicles such that all passengers can arrive at earliest together. Such a passenger assignment problem has various applications in real life. However, finding the optimal assignment efficiently is challenging due to high computational cost in the fastest path search and combinatorial nature of capacity constrained assignment. In this paper, we first propose two exact solutions to find the optimal results, and then an approximate solution to achieve higher efficiency by trading off a little accuracy. Finally, performances of all proposed algorithms are evaluated on a real dataset
Predicting passengers in public transportation using smart card data
No full textTransit prediction has long been a hot research problem, which is central to the public transport agencies and operators, as evidence to support scheduling and urban planning. There are several previous work aiming at transit prediction, but they are all from the macro perspective. In this paper, we study the prediction of individuals in the context of public transport. Existing research on the prediction of individual behaviour are mostly found in information retrieval and recommender systems, leaving it untouched in the area of public transport. We propose a NLP based back-propagation neural network for the prediction job in this paper. Specifically, we adopt the concept of “bag of words” to build user profile, and use the result of clustering as input of back-propagation neural network to generate predictions. To illustrate the effectiveness of our method, we conduct an extensive set of experiments on a dataset from public transport fare collecting system. Our detailed experimental evaluation demonstrates that our method gets good performance on predicting public transport individuals
A restaurant recommendation system by analyzing ratings and aspects in reviews
No full textRecommender systems are widely deployed to predict the preferences of users to items. They are popular in helping users find movies, books and products in general. In this work, we design a restaurant recommender system based on a novel model that captures correlations between hidden aspects in reviews and numeric ratings. It is motivated by the observation that a user’s preference against an item is affected by different aspects discussed in reviews. Our method first explores topic modeling to discover hidden aspects from review text. Profiles are then created for users and restaurants separately based on aspects discovered in their reviews. Finally, we utilize regression models to detect the user-restaurant relationship. Experiments demonstrate the advantages
- …
