Spatial Database: Accomplishments and Research NeedsOutlineIntroductionIntroduction: Spatial DatabaseSpatial Database (cont’d)Related WorkAuthors’ ContributionScope and OutlineThree Layer ArchitectureAccomplishmentsAccomplishments: Space TaxonomySpace Taxonomy…Rpresentative Function Specified by OGIS …A Sample of Spatial OperationsAccomplishments: Spatial Data ModelSpatial Data Type Hierarchy by OGISAccomplishments:Spatial QueryingSpatial Querying …Query ExampleFigures for Spatial QueryAccomplishments: Spatial File Organization and IndicesR-TreeOther AccomplishmentsResearch NeedsResearch Needs: Space TaxonomyResearch Needs: Spatial Data ModelResearch Needs: Spatial Query ProcessingDifficult Spatial Queries From GISExample of Spatial Query ProcessingResearch Needs: Spatial File Oragnization and Indices: Physical LeverlResearch Needs: OtherSummary and DiscussionSlide 33MoreRecent Research in Spatial Database1Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Spatial Database: Accomplishments and Research Needspresented by Fei Shenfrom S.Shekar,S.Chawla, S.Ravada,A.Fetterer, X.Liu,C.T.LuEEE Transactions on Knowledge and Data Engineering 11(1): 45-55, 19992Shen FEiiCSCI599-Fall2000CSCI599-Fall2000OutlineIntroduction & definition•Spatial Database•Related Work and Authors’ Contribution•Scope and OutlineAccomplishmentsResearch NeedsSummary and Discussion3Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Introduction4Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Introduction: Spatial DatabaseDEF: Efficient and Effective management of data related to a spacePhysical World, e.g. geography, urban planning, astronomyEngineering Design, e.g. VLSI circuits design, design of automobileConceptual Information Space, e.g. multi-dimension support system, fluid flow, electro-magnetic fieldExisting ApplicationGeographic Information SystemComputer Aid Design5Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Spatial Database (cont’d)Existing ApplicationMultimedia Information SystemData WarehousingNASA Earth Observation SystemCommercial ExamplesInformix’s Spatial Data BladeOracle’s Universal Server with Spatial DataESRI’s Spatial Data Engine6Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Related WorkWon Kim SSD 93Research Direction•Validation of relative performance•Query Optimization for spatial queries•Cost Model•Extensible Data Structure and Spatial Operations•Object Oriented ParadigmGuting VLDB 1994Survey and Classification•Spatial Data System•Spatial Data Model•Spatial Query Language•Spatial Indexing•Spatial Join Methods7Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Authors’ ContributionAuthors’ ContributionIdentify Recent AccomplishmentCurrent Research needs8Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Scope and OutlineObject-relational DatabasesSpatial Data TypesSpatial OperationsMulti-Dimensional IndexingThree Layer ArchitectureObject Relational Database Management systemSpatial DatabaseSpatial Application•GIS, MIIS9Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Three Layer Architecture10Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Accomplishments11Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Accomplishments: Space TaxonomySet Base SpaceFormalize the set relationshipRelational and Object-relational DB uses this model of spaceTopological SpaceBasic Concept: NeighborGIS Operation: overlap, adjacentNetwork SpaceBasic Concepts: graphs, nodes, edge, connectivityGIS Operation: connected, path12Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Space Taxonomy…Euclidian Coordinatized SpaceBasic Concepts: coordinate systemGIS Operation: North of, South ofMetric SpaceFormalize the distance relationships13Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Rpresentative Function Specified by OGIS …14Shen FEiiCSCI599-Fall2000CSCI599-Fall2000A Sample of Spatial Operations15Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Accomplishments: Spatial Data ModelData Abstraction: hides the details of data storageField-based ModelTransform a space partition to an attribute domainLocal, focal, zonal operationsObject-based ModelInformation Space populated by discrete, identifiable, spatially referenced entity Distance and Boundary operations16Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Spatial Data Type Hierarchy by OGIS17Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Accomplishments:Spatial QueryingEfficient RepresentationObject ModelSpaghetti ModelNode-arc-area Model(NAA) modelDouble-connected-edge-list (DCEL)Boundary Representation, Field Based ModelTessellationTriangular irregular networks (TIN)18Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Spatial Querying …Efficient AlgorithmFilter and refine algorithm1. Filter: returns a set of candidate object which is a superset of the objects fulfilling a predicate2. Refine: for each candidate, the exact geometry is checkedPlane sweeping algorithmSpatial join- nested loop, tree matching space partitioning, join-index19Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Query ExampleExampleFind all lakes which have an area greater than 5 sq. km. And within 20 km. From campground20Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Figures for Spatial Query21Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Accomplishments: Spatial File Organization and IndicesSpace Filling CurveClusteringMetric Clustering TechniqueTopological Clustering Technique-CCAMSpatial Indices for point objectsGrid Files, Point-Quad-Tree, KD-treeSpatial Indices for extended objectR-tree, Field tree, Cell treeBSP tree, Balanced and Nested Grid Files22Shen FEiiCSCI599-Fall2000CSCI599-Fall2000R-TreeHeight balanced extension of B+ treeObjects are represented by MBR23Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Other AccomplishmentsFile design for storage on tertiary storage deviceJuke boxesDeclustering MethodDynamic-load balancing techniquesMulti-dimensional spatial dataHierarchical algorithmShortest path computationView materialization24Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Research Needs25Shen FEiiCSCI599-Fall2000CSCI599-Fall2000Research Needs: Space TaxonomyA sequence of operations on discretized dataLead to growing errorsFormalize the discetization processFormalize the associated errorsFormalized the interpolationE.g. estimate the characteristics of terrain or ecological conditions from a
View Full Document
Unlocking...