Browsing by Author "Yoo, Jin Soung"

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    A Join-less Approach for Co-location Pattern Mining: A Summary of Results
    (2005-12-29) Yoo, Jin Soung; Shekhar, Shashi; Celik, Mete
    Spatial co-location patterns represent the subsets of features whose instances are frequently located together in geographic space. For example, MacDonald's and Burger Kings are likely co-located in a local business map. Co-location pattern discovery presents challenges since the instances of spatial features are embedded in a continuous space and share a variety of spatial relationships. A large fraction of the computation time is devoted to identifying the instances of co-location patterns. We propose a novel join-less approach for co-location pattern mining, which materializes spatial neighbor relationships with no loss of co-location instances and reduces the computational cost of identifying the instances. The join-less co-location mining algorithm is efficient since it uses an instance-lookup scheme instead of an expensive spatial or instance join operation for identifying co-location instances. We prove the join-less algorithm is correct and complete in finding co-location rules. The experimental evaluations using synthetic datasets and real world datasets show the join-less algorithm performs more efficiently than a current join-based algorithm and is scalable in dense spatial datasets.
  • Thumbnail Image
    Item
    A Partial Join Approach for Mining Co-location Patterns: A Summary of Results
    (2005-12-29) Yoo, Jin Soung; Shekhar, Shashi
    Spatial co-location patterns represent the subsets of events whose instances are frequently located together in geographic space. We identified the computational bottleneck in the execution time of a current co-location mining algorithm. A large fraction of the join-based co-location miner algorithm is devoted to computing joins to identify instances of candidate co-location patterns. We propose a novel partial-join approach for mining co-location patterns efficiently. It transactionizes continuous spatial data while keeping track of the spatial information not modeled by transactions. It uses a transaction-based Apriori algorithm as a building block and adopts the instance join method for residual instances not identified in transactions. We show that the algorithm is correct and complete in finding all co-location rules which have prevalence and conditional probability above the given thresholds. An experimental evaluation using synthetic datasets and a real dataset shows that our algorithm is computationally more efficient than the join-based algorithm.
  • Thumbnail Image
    Item
    In-Route Nearest Neighbor Queries: A Summary of Result
    (2004-12-30) Yoo, Jin Soung; Shekhar, Shashi
    Nearest neighbor query is one of the most important operations in spatial databases and their application domains, such as location-based services and advancedtraveler information systems. This paper addresses the problem of finding the in-route nearest neighbor(IRNN) for a query object tuple which consists of a given route with a destination and a current location on it. The IRNN is a facility instance via which the detour from the original route on the way to the destination is smallest. This paper addresses four alternative solution methods. Comparisons among them are presented using an analytical modeling and an experimental framework. Several experiments using real road map datasets are conducted to examine the behaviors of the solutions in terms of five parameters affecting the performance. The overall experiments show that our strategy to reduce the expensive path computations to minimize the response time is reasonable. The spatial distance join-based method always shows better performance with fewer path computations compared to the recursive methods. The computation costs for all methods except the precomputed zone-based method increase with increases in the road map size and the query route length but decrease with increases in the facility density. The precomputed zone-based method shows the most efficiency when there are no updates on the road map.
  • Thumbnail Image
    Item
    Mining Time-Profiled Associations: A Preliminary Study
    (2005-04-04) Yoo, Jin Soung; Zhang, Pusheng; Shekhar, Shashi
    A time-profiled association is an association pattern consistent with a query sequence along time, e.g., identifying interacting relationship of droughts and wild fires in Australia with the El Nino phenomenon in the past 50 years. Association patterns by traditional association rule mining approaches reveal the generic dependency among variables, however, the evolution of these patterns along time is not captured. Hence the time-profiled association mining is used to incorporate the temporal evolution of association patterns and identify the co-occurred patterns consistent along time. Mining time-profiled associations is computational challenging due to large size of itemset space and long time points in practice. A naive approach of mining time-profiled associations can be characterized using a two-phase paradigm. The first phase generates the statistical parameter (e.g., support) sequences along time, and the second phase retrieves similar sequences with the query sequence. However, exponentially increasing computational costs of generating all combinatorial candidate itemsets become prohibitively expensive for the previous work. In this paper, we propose a novel one-step algorithm to unify the generation of the sequence of statistical parameters and sequence retrieval. The proposed algorithm substantially reduces the itemset search space by pruning candidate itemsets based on the monotone property of lower bounding measure of sequence of statistical parameters. Experimental results show that our algorithm outperforms the naive approach.
  • Thumbnail Image
    Item
    Similarity-based Time-Profiled Association Mining: A Summary of Results
    (2005-12-30) Yoo, Jin Soung; Shekhar, Shashi
    Given a time-stamped transaction database, time-profiled associations represent those subsets of items whose support time sequence satisfies a given specification. Considering the specification to be the similarity with the El Nino index sequence, the decreased fish-catch in Peru is an example of time-profiled associations. Classical association mining uses simple numeric interest measures (e.g., support) and a simple subset specification such that support is greater than a certain threshold. In contrast, time-profiled association mining uses a composite interest measure, i.e., a sequence of supports over a sequence of time slots and can use a richer subset specification, such as time series correlation and Euclidean distance. Mining time-profiled associations is computationally challenging due to the large size of datasets, composite interest measures, and richer subset specification. In this paper, we propose a monotonic lower bounding of Lp norm based similarity measure, and propose two novel algorithms to mine time-profiled associations. We show that the proposed algorithms are correct and complete in finding time-profiled associations. Experimental results show that the proposed algorithms outperform the naive approach.