Search

The standard sequential pattern mining scheme hardly considers the positions of events in a sequence, and therefore it is difficult to focus on more interesting patterns that represent better the causal relationships between events. Without quantifying how close two events are in a sequence, we may fail to evaluate how likely an event is caused by the others from the pattern, which is a severe drawback for some applications like prediction. Motivated by this, we propose the recency-based sequential pattern mining scheme together with a novel measure of pattern interestingness to effectively capture recency as well as frequency. To efficiently extract all the recency-based sequential patterns, we devise a mining algorithm, called Recency-based Frequent pattern Miner (RF-Miner), together with an effective prediction method to evaluate the quality of recency-based patterns in terms of their prediction power. The experimental results show that our RF-Miner algorithm can extract more diverse and important patterns that can be used to make prediction of the next event, and can be more efficiently performed by using the upper bounds of our measure than baseline algorithms. [ABSTRACT FROM AUTHOR]

This article introduces and solves a spatial keyword cover problem (SK-Cover for short), which aims to identify the group of spatio-textual objects covering all the keywords in a query and minimizing a distance cost function that leads to fewer objects in the answer set. In a broad sense, SK-Cover has been actively studied in the literature of spatial keyword search, such as the m-closest keywords query and the collective spatial keyword query. However, these existing works focus on minimizing only the largest pairwise distance even though the actual spatial cost is highly influenced by the number of objects in the answer group. Motivated by this, the present article further generalizes the problem definition in such a way that the total cost takes the cardinality of the group as well as the spatial distance. We prove that SK-Cover is not only NP-hard but also does not allow an approximation better than O (log | T |) in polynomial time, where T is the set of query keywords. We first establish an O (log | T |) -approximation algorithm, which is asymptotically optimal in terms of the approximability of SK-Cover, together with effective accessing strategies and pruning rules to improve the overall efficiency and scalability. Despite the NP-hardness of SK-Cover, this article also develops exact solutions that find the optimal group of objects in a reasonably fast manner in practice, especially when it is required to cover a relatively small number of query keywords. In addition to our algorithmic results, we empirically show that our approximation algorithm always achieves the best accuracy and the efficiency comparable to that of a state-of-the-art algorithm intended for m CK , a problem similar to yet theoretically easier than SK-Cover, and also demonstrate that our exact algorithm using the proposed approximation scheme runs much faster than the baseline algorithm adapted from the existing solution for m CK . [ABSTRACT FROM AUTHOR]

Finding k nearest neighbor objects in spatial databases is a fundamental problem in many geospatial systems and the direction is one of the key features of a spatial object. Moreover, the recent tremendous growth of sensor technologies in mobile devices produces an enormous amount of spatio-directional (i.e., spatially and directionally encoded) objects such as photos. Therefore, an efficient and proper utilization of the direction feature is a new challenge. Inspired by this issue and the traditional k nearest neighbor search problem, we devise a new type of query, called the direction-constrained k nearest neighbor (DC kNN) query. The DC kNN query finds k nearest neighbors from the location of the query such that the direction of each neighbor is in a certain range from the direction of the query. We develop a new index structure called MULTI, to efficiently answer the DC kNN query with two novel index access algorithms based on the cost analysis. Furthermore, our problem and solution can be generalized to deal with spatio-circulant dimensional (such as a direction and circulant periods of time such as an hour, a day, and a week) objects. Experimental results show that our proposed index structure and access algorithms outperform two adapted algorithms from existing kNN algorithms. [ABSTRACT FROM AUTHOR]

This article presents a novel type of queries in spatial databases, called the direction-aware bichromatic reverse k nearest neighbor( DBRkNN) queries, which extend the bichromatic reverse nearest neighbor queries. Given two disjoint sets, P and S, of spatial objects, and a query object q in S, the DBR kNN query returns a subset P′ of P such that k nearest neighbors of each object in P′ include q and each object in P′ has a direction toward q within a pre-defined distance. We formally define the DBR kNN query, and then propose an efficient algorithm, called DART, for processing the DBR kNN query. Our method utilizes a grid-based index to cluster the spatial objects, and the B-tree to index the direction angle. We adopt a filter-refinement framework that is widely used in many algorithms for reverse nearest neighbor queries. In the filtering step, DART eliminates all the objects that are away from the query object more than a pre-defined distance, or have an invalid direction angle. In the refinement step, remaining objects are verified whether the query object is actually one of the k nearest neighbors of them. As a major extension of DART, we also present an improved algorithm, called DART+, for DBR kNN queries. From extensive experiments with several datasets, we show that DART outperforms an R-tree-based naive algorithm in both indexing time and query processing time. In addition, our extension algorithm, DART+, also shows significantly better performance than DART. [ABSTRACT FROM AUTHOR]