Search

A multi-attribute trajectory consists of a spatio-temporal trajectory and a set of descriptive attributes. Such data enrich the representation of traditional spatio-temporal trajectories to have comprehensive knowledge of moving objects. Range query is a fundamental operator over multi-attribute trajectories. Such a query contains two predicates, spatio-temporal and attribute, and returns the objects whose locations are within a distance threshold to the query trajectory and attributes contain expected values. There are different execution plans for answering the query. To enhance the capability of a trajectory database, an optimizer is essentially required to (i) accurately estimate the cost for alternative query strategies in terms of disk accesses, (ii) build a decision-making module that automatically sorts the data in an appropriate way and selects the optimal query plan, and (iii) update the analytical models when new trajectories are arrived. The cost model supports both uniform and non-uniform spatio-temporal data distribution and incorporates attribute distribution. The optimizer is fully developed inside a database system kernel and comprehensively evaluated in terms of accuracy and effectiveness by using large real and synthetic datasets. [ABSTRACT FROM AUTHOR]

Triangle count is a critical parameter in mining relationships among people in social networks. However, directly publishing the findings obtained from triangle counts may bring potential privacy concern, which raises great challenges and opportunities for privacy-preserving triangle counting. In this paper, we choose to use differential privacy to protect triangle counting for large scale graphs. To reduce the large sensitivity caused in large graphs, we propose a novel graph projection method that can be used to obtain an upper bound for sensitivity in different distributions. In particular, we publish the triangle counts satisfying the node-differential privacy with two kinds of histograms: the triangle count distribution and the cumulative distribution. Moreover, we extend the research on privacy preserving triangle counting to one of its applications, the local clustering coefficient. Experimental results show that the cumulative distribution can fit the real statistical information better, and our proposed mechanism has achieved better accuracy for triangle counts while maintaining the requirement of differential privacy. [ABSTRACT FROM AUTHOR]

Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system. Many, if not all, previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers’ average waiting time. On the other hand, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an index-based $(1-1/e)$ (1 - 1 / e) -approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method that achieves a $(1-\rho)(1-1/e)$ (1 - ρ) (1 - 1 / e) approximation ratio. Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a $(1-\rho)(1-1/e-\varepsilon)$ (1 - ρ) (1 - 1 / e - ɛ) approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency, effectiveness, and scalability of our methods in addressing FAST and FASTCO respectively. [ABSTRACT FROM AUTHOR]

In this modern era, traffic congestion has become a major source of severe negative economic and environmental impact for urban areas worldwide. One of the most efficient ways to mitigate traffic congestion is through future traffic prediction. The research field of traffic prediction has evolved greatly ever since its inception in the late 70s. Earlier studies mainly use classical statistical models such as ARIMA and its variants. Recently, researchers have started to focus on machine learning models because of their power and flexibility. As theoretical and technological advances emerge, we enter the era of deep neural network, which gained popularity due to its sheer prediction power which can be attributed to the complex and deep structure. Despite the popularity of deep neural network models in the field of traffic prediction, literature surveys of such methods are rare. In this work, we present an up-to-date survey of deep neural network for traffic prediction. We will provide a detailed explanation of popular deep neural network architectures commonly used in the traffic flow prediction literatures, categorize and describe the literatures themselves, present an overview of the commonalities and differences among different works, and finally provide a discussion regarding the challenges and future directions for this field. [ABSTRACT FROM AUTHOR]

Traffic bottlenecks are a set of road segments that have an unacceptable level of traffic caused by a poor balance between road capacity and traffic volume. A huge volume of trajectory data which captures realtime traffic conditions in road networks provides promising new opportunities to identify the traffic bottlenecks. In this paper, we define this problem as trajectory-driven traffic bottleneck identification: Given a road network R, a trajectory database T, find a representative set of seed edges of size K of traffic bottlenecks that influence the highest number of road segments not in the seed set. We show that this problem is NP-hard and propose a framework to find the traffic bottlenecks as follows. First, a traffic spread model is defined which represents changes in traffic volume for each road segment over time. Then, the traffic diffusion probability between two connected segments and the residual ratio of traffic volume for each segment can be computed using historical trajectory data. We then propose two different algorithmic approaches to solve the problem. The first one is a best-first algorithm BF, with an approximation ratio of 1-1/e. To further accelerate the identification process in larger datasets, we also propose a sampling-based greedy algorithm SG. Finally, comprehensive experiments using three different datasets compare and contrast various solutions, and provide insights into important efficiency and effectiveness trade-offs among the respective methods. [ABSTRACT FROM AUTHOR]

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

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

GPS enables mobile devices to continuously provide new opportunities to improve our daily lives. For example, the data collected in applications created by Uber or Public Transport Authorities can be used to plan transportation routes, estimate capacities, and proactively identify low coverage areas. In this paper, we study a new kind of query—Reverse k Nearest Neighbor Search over Trajectories (\mathbf{R}{k}\mathbf{NNT} ), which can be used for route planning and capacity estimation. Given a set of existing routes \mathcal{D}_{\mathcal{R}} , a set of passenger transitions \mathcalD\mathcal{T} , and a query route Q , an \mathbfRk\mathbfNNT  query returns all transitions that take Q as one of its k nearest travel routes. To solve the problem, we first develop an index to handle dynamic trajectory updates, so that the most up-to-date transition data are available for answering an \mathbfRk\mathbfNNT query. Then we introduce a filter refinement framework for processing \mathbfRk\mathbfNNT queries using the proposed indexes. Next, we show how to use \mathbfRk\mathbfNNT to solve the optimal route planning problem \mathbfMaxRk\mathbfNNT ( \mathbfMinRk\mathbfNNT ), which is to search for the optimal route from a start location to an end location that could attract the maximum (or minimum) number of passengers based on a predefined travel distance threshold. Experiments on real datasets demonstrate the efficiency and scalability of our approaches. To the best of our knowledge, this is the first work to study the \mathbfRk\mathbfNNT problem for route planning. [ABSTRACT FROM AUTHOR]

With the development of location-based services (LBS), LBS users are generating more and more spatio-textual data, e.g., checkins and attraction reviews. Since a spatio-textual entity may have different representations, possibly due to GPS deviations or typographical errors, it calls for effective methods to integrate the spatio-textual data from different data sources. In this paper, we study the problem of top-$k$ spatio-textual similarity join (Topk-STJoin), which identifies the $k$ most similar pairs from two spatio-textual data sets. One big challenge in Topk-STJoin is to efficiently identify the top- $k$ similar pairs by considering both textual relevancy and spatial proximity. Traditional join algorithms that consider only one dimension (textual or spatial) are inefficient because they cannot utilize the pruning ability on the other dimension. To address this challenge, we propose a signature-based top-$k$ join framework. We first generate a spatio-textual signature set for each object such that if two objects are in the top- $k$ similar pairs, their signature sets must overlap. With this property, we can prune large numbers of dissimilar pairs without common signatures. We find that the order of accessing the signatures has a significant effect on the performance. So, we compute an upper bound for each signature and propose a best-first accessing method that preferentially accesses signatures with large upper bounds while those pairs with small upper bounds can be pruned. We prove the optimality of our best-first accessing method. Next, we optimize the spatio-textual signatures and propose progressive signatures to further improve the pruning power. Experimental results on real-world datasets show that our algorithm achieves high performance and good scalability, and significantly outperforms baseline approaches. [ABSTRACT FROM PUBLISHER]

Geo-textual data are generated in abundance. Recent studies focused on the processing of spatial keyword queries which retrieve objects that match certain keywords within a spatial region. To ensure effective retrieval, various extensions were done including the allowance of errors in keyword matching and autocompletion using prefix matching. In this paper, we propose INSPIRE, a general framework, which adopts a unifying strategy for processing different variants of spatial keyword queries. We adopt the autocompletion paradigm that generates an initial query as a prefix matching query. If there are few matching results, other variants are performed as a form of relaxation that reuses the processing done in the earlier phase. The types of relaxation allowed include spatial region expansion and exact/approximate prefix/substring matching. Moreover, since the autocompletion paradigm allows appending characters after the initial query, we look at how query processing done for the initial query and relaxation can be reused in such instances. Compared to existing works which process variants of spatial keyword query as new queries over different indexes, our approach offers a more compelling way to efficient and effective spatial keyword search. Extensive experiments substantiate our claims. [ABSTRACT FROM PUBLISHER]

As business and enterprises generate and exchange XML data more often, there is an increasing need for efficient processing of queries on XML data. Searching for the occurrences of a tree pattern query in an XML database is a core operation in XML query processing. Prior works demonstrate that holistic twig pattern matching algorithm is an efficient technique to answer an XML tree pattern with parent-child (P-C) and ancestor-descendant (A-D) relationships, as it can effectively control the size of intermediate results during query processing. However, XML query languages (e.g., XPath and XQuery) define more axes and functions such as negation function, order-based axis, and wildcards. In this paper, we research a large set of XML tree pattern, called extended XML tree pattern, which may include P-C, A-D relationships, negation functions, wildcards, and order restriction. We establish a theoretical framework about “matching cross” which demonstrates the intrinsic reason in the proof of optimality on holistic algorithms. Based on our theorems, we propose a set of novel algorithms to efficiently process three categories of extended XML tree patterns. A set of experimental results on both real-life and synthetic data sets demonstrate the effectiveness and efficiency of our proposed theories and algorithms. [ABSTRACT FROM AUTHOR]