Browsing by Author "Chawla, Sanjay"

Now showing 1 - 8 of 8
  • Thumbnail Image
    Item
    Consistency Checking for Euclidean Spatial Constraints: A Dimension Graph Approach
    (2000-07-11) Liu, Xuan; Shekhar, Shashi; Chawla, Sanjay
    In this paper, we address the problem of consistency checking for Euclidean spatial constraints. A dimension graph representation is proposed to maintain the Euclidean spatial constraints among objects. The basic idea is to project the spatial constraints on both X and Y dimensions, and the dimension graph is constructed on each dimension. By using the dimension graph representation, the problem of consistency checking is then transformed to a graph cycle detection problem. The consistency checking can be achieved with O(N+E) time as well as space complexity, where N is the number of spatial object, and E is the number of spatial predicates in the constraint. The proposed approach to consistency checking for spatial constraints is faster than O(N2) when the number of predicates is much smaller than N2 and there are few disjunctions in the spatial constraint. The dimension graph and consistency checking algorithm can be used for points, intervals and polygons in 2 dimensional space. The algorithm can guarantee the global consistency.
  • Thumbnail Image
    Item
    Data Mining and Visualization of Twin-Cities Traffic Data
    (2001-03-08) Shekhar, Shashi; Lu, Chang-tien; Chawla, Sanjay; Zhang, Pusheng
    Data Mining(DM) is the process of extracting implicit, valuable, and interesting information from large sets of data. As huge amounts of data have been stored in traffic and transportation databases, data warehouses, geographic information systems, and other information repositories, data mining is receiving substantial interest from both academia and industry. The Twin-Cities traffic archival stores sensor network measurements collected from the freeway system in the Twin-Cities metropolitan area. In this paper, we construct a traffic data warehousing model which facilitates on-line analytical processing(OLAP), employ current data mining techniques to analyze the Twin-Cities traffic data set, and visualize the discoveries on the highway map. We also discuss some research issues in mining traffic and transportation data.
  • Thumbnail Image
    Item
    Efficient Join-Index-Based Join Processing: A Clustering Approach
    (1999-08-06) Shekhar, Shashi; Lu, Chang-tien; Chawla, Sanjay
    A Join Index is a data structure used for processing join queries in databases. Join indices usepre-computation techniques to speed up online query processing and are useful for data-sets which are updated infrequently. The cost of join computation using a join-index with limited buffer space depends primarily on the page-access sequence used to fetch the pages of the base relations. Given the join-index, we introduce a suite of methods based on clustering to compute the joins. We derive upper-bounds on the lengths of the page-access sequences. Experimental results with Sequoia 2000 data sets show that the clustering method outperforms the existing methods based on sorting and online-clustering heuristics.
  • Thumbnail Image
    Item
    Equivalence Classes of Direction Objects and Applications
    (1999-07-21) Shekhar, Shashi; Liu, Xuan; Chawla, Sanjay
    Direction is an important spatial relationship that is used in many fields such as geographic information systems (GIS) and image interpretation. It is also frequently used as a selection condition in spatial queries. In our recent work we have described a novel viewpoint to model direction as a `spatial object' based upon the concepts of vectors, points and angles. This was a departure from the conventional approach of treating direction as a spatial relationship between objects. In this paper, based upon `direction objects', we partition the directional space into a set of equivalence classes. By defining an algebra on equivalence classes we provide a framework to model semantics of direction predicates for qualitative spatial reasoning. We then proceed to extrapolate the definition of direction equivalence classes to define `path' equivalence classes with an application to the landmark-based route description problem. Keywords: Directional relationships, Direction objects, Equivalence Classes, Landmark-based routing.
  • Thumbnail Image
    Item
    Extending Data Mining for Spatial Applications: A Case Study in Predicting Nest Locations
    (2000-04-18) Chawla, Sanjay; Shekhar, Shashi; WuLi, Wei; Ozesmi, Uygar
    Spatial data mining is a process to discover interesting and potentially useful spatial patterns embedded in spatial databases. Efficient tools for extracting information from spatial data sets can be of importance to organizations which own, generate and manage large geo-spatial data sets. The current approach towards solving spatial data mining problems is to use classical data mining tools after "materializing" spatial relationships and assuming independence between different data points. However, classical data mining methods often perform poorly on spatial data sets which have high spatial auto-correlation. In this paper we will review spatial statistical techniques which can effectively model the notion of spatial-autocorrelation and apply it to the problem of predicting bird nest locations in a marshland.
  • Thumbnail Image
    Item
    Modeling Spatial Dependencies for Mining Geospatial Data: A Statistical Approach
    (2000-01-10) Chawla, Sanjay; Shekhar, Shashi; Wu Li, Wei
    Geo-spatial data mining is a process to discover interesting and potentially useful spatial patterns embedded in spatial databases. Efficient tools for extracting information from geo-spatial data sets can be of importance to organizations which own, generate and manage large geo-spatial data sets. The current approach towards solving spatial data mining problems is to use classical data mining tools after "materializing" spatial relationships and assuming independence between different data points. However, classical data mining methods often perform poorly on spatial data sets which have high spatial auto-correlation. This approach often leads to poor results because it does not take into account the fundamental notion of spatial autocorrelation. In this paper we will overview statistical techniques which can effectively model the notion of spatial-autocorrelation. We will also present a "roadmap" for extending classical data mining techniques to manage geo-spatial data which will the serve as basis for future research.
  • Thumbnail Image
    Item
    Processing Object-Orientation-based Direction Queries in Spatial Databases
    (2000-05-04) Liu, Xuan; Shekhar, Shashi; Chawla, Sanjay
    Direction based spatial relationships are critical in many domains including geographic information systems(GIS) and image interpretation. They are also frequently used as selection conditions in spatial queries. In this paper, we explore processing of queries based on object-orientation-based directional relationships. A new Open Shape based strategy (OSS) is proposed. OSS converts the processing of the direction predicates to the processing of topological operations between open shapes and closed geometry objects. Since OSS models the direction region as an Open Shape, it does not need to know the boundary of the embedding world, and also eliminating the computation related to the world boundary. We perform algebraic analysis as well as experimental evaluation for OSS. The experimental result demonstrates that the OSS consistently outperforms classical range query strategy both in I/O and CPU cost.
  • Thumbnail Image
    Item
    Spatial Contextual Classification and Prediction Models for Mining Geospatial Data
    (2002-02-14) Shekhar, Shashi; Schrater, Paul; Vatsavai, Ranga R.; WuLi, Wei; Chawla, Sanjay
    Modeling spatial context (e.g., autocorrelation) is a key challenge in classification problems that arise in geospatial domains. Markov Random Fields (MRFs) is a popular model for incorporating spatial context into image segmentation and land-use classification problems. The spatial autoregression model (SAR), which is an extension of the classical regression model for incorporating spatial dependence, is popular for prediction and classification of spatial data in regional economics, natural resources, and ecological studies. There is little literature comparing these alternative approaches to facilitate the exchange of ideas (e.g., solution procedures). We argue that the SAR model makes more restrictive assumptions about the distribution of feature values and class boundaries than MRF. The relationship between SAR and MRF is analogousto the relationship between regression and Bayesian classifiers. This paper provides comparisons between the two models using a probabilistic and an experimental framework. Keywords: Spatial Context, Spatial Data Mining, Markov Random Fields, Spatial Autoregression.