Browsing by Author "Celik, Mete"

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
    Discovering and Quantifying Mean Streets: A Summary of Results
    (2007-10-25) Celik, Mete; Shekhar, Shashi; George, Betsy; Rogers, James P.; Shine, James A.
    Mean streets represent those connected subsets of a spatial network whose attribute values are significantly higher than expected. Discovering and quantifying mean streets is an important problem with many applications such as detecting high-crime-density streets and high crash roads (or areas) for public safety, detecting urban cancer disease clusters for public health, detecting human activity patterns in asymmetric warfare scenarios, and detecting urban activity centers for consumer applications. However, discovering and quantifying mean streets in large spatial networks is computationally very expensive due to the difficulty of characterizing and enumerating the population of streets to define a norm or expected activity level. Previous work either focuses on statistical rigor at the cost of computational exorbitance, or concentrates on computational efficiency without addressing any statistical interpretation of algorithms. In contrast, this paper explores computationally efficient algorithms for use on statistically interpretable results. We describe alternative ways of defining and efficiently enumerating instances of subgraph families such as paths. We also use statistical models such as the Poisson distribution and the sum of independent Poisson distributions to provide interpretations for results. We define the problem of discovering and quantifying mean streets and propose a novel mean streets mining algorithm. Experimental evaluations using synthetic and real-world datasets show that the proposed method is computationally more efficient than nave alternatives.
  • Thumbnail Image
    Item
    Mixed-Drove Spatio-Temporal Co-occurrence Pattern Mining
    (2008-05-06) Celik, Mete; Shekhar, Shashi; Rogers, James P.; Shine, James A.
    Mixed-drove spatio-temporal co-occurrence patterns (MDCOPs) represent subsets of two or more different object-types whose instances are often located in spatial and temporal proximity. Discovering MDCOPs is an important problem with many applications such as identifying tactics in battlefields, games, and predator-prey interactions. However, mining MDCOPs is computationally very expensive because the interest measures are computationally complex, datasets are larger due to the archival history, and the set of candidate patterns is exponential in the number of object-types. We propose a monotonic composite interest measure for discovering MDCOPs and novel MDCOP mining algorithms. Analytical results show that the proposed algorithms are correct and complete. Experimental results also show that the proposed methods are computationally more efficient than naive alternatives.
  • Thumbnail Image
    Item
    Modeling Spatial and Spatio-temporal Co-occurrence Patterns
    (2008-07) Celik, Mete
    As the volume of spatial and spatio-temporal data continues to increase significantly due to both the growth of database archives and the increasing number and resolution of spatio-temporal sensors, automated and semi-automated pattern analysis becomes more essential. Spatial and spatio-temporal (ST) data analyses have emerged in recent decades to develop understanding of the spatial and spatio-temporal characteristics and patterns. However, in the last decade, the growth in variety and volume of observational data, notably spatial and spatio-temporal data, has out-paced the capabilities of analytical tools and techniques. Major limitations of existing classical data mining models and techniques include the following. First, these do not adequately model richer temporal semantics of data observations (e.g. co-occurrence patterns of moving objects, emerging and vanishing patterns, multi-scale cascade patterns, periodic patterns). Second, these do not take into account time dimension of the data observations. Third, these do not provide sufficient interest measures and computationally efficient algorithms to discover spatial and spatio-temporal co-occurrence patterns. These limitations represent critical barriers in several application domains that require to analyze huge datasets. In this dissertation, I proposed addressed these limitations by i) providing a framework to model the rich semantics of the ST patterns of data observations by developing a taxonomy of spatial and ST co-occurrence patterns, ii) designing new techniques that are taking into account the time dimension of the data, and iii) developing new monotonic composite interest measures and scalable algorithms. The proposed approaches reduced the manual effort by reducing the plausible set of hypotheses. Major focus would be on developing scalable algorithms to mine spatial and ST co-occurrence patterns.
  • Thumbnail Image
    Item
    NORTHSTAR: A Parameter Estimation Method for the Spatial Autoregression Model
    (2007-02-09) Celik, Mete; Kazar, Baris M.; Shekhar, Shashi; Boley, Daniel; Lilja, David J.
    Parameter estimation method for the spatial autoregression model (SAR) is important because of the many application domains, such as regional economics, ecology, environmental management, public safety, transportation, public health, business, travel and tourism. However, it is computationally very expensive because of the need to compute the determinant of a large matrix due to Maximum Likelihood Theory. The limitation of previous studies is the need for numerous computations of the computationally expensive determinant term of the likelihood function. In this paper, we present a faster, scalable and NOvel pRediction and estimation TecHnique for the exact SpaTial Auto Regression model solution (NORTHSTAR). We provide a proof of the correctness of this algorithm by showing the objective function to be unimodular. Analytical and experimental results show that the NORTHSTAR algorithm is computationally faster than the related approaches, because it reduces the number of evaluations of the determinant term in the likelihood function.