搜索
IntegrityinDatabases—SixthInternationalWorkshoponFoundationsofModelsandLanguagesforDataandObjectsSchlossDagstuhl,Germany,S.Conrad,H.-J.Klein,andK.-D.Schewe(eds.),pp.119-132,September1996.Multi-ResolutionSpatialDatabases:ConsistencyAmongNetworks*NectariaTryfonaNationalCenterforGeographicInformationandAnalysisBoardmanHall,UniversityofMaine,Orono,ME04469-5711,U.S.A.nectaria@spatial.maine.eduandMaxJ.EgenhoferNationalCenterforGeographicInformationandAnalysisDepartmentofSpatialInformationScienceandEngineeringandDepartmentofComputerScienceBoardmanHall,UniversityofMaine,Orono,ME04469-5711,U.S.A.max@spatial.maine.eduAbstractHeterogeneousgeographicdatabasescontainmultipleviewsofthesamegeographicobjectsatdifferentlevelsofspatialresolutionwhichmustbeconsistentwitheachother.ThispaperdevelopsaformalmethodofassessingconsistencyoftopologicalrelationsinR2atahighlevelofabstraction,overcomplexlystructuredspatialobjectsthatformnetworks.Networksareafrequentlyuseddatatypeingeographicapplicationswhere,forinstance,ariverwithitstributariesandlakesisconsideredasinglespatialobject.Therelationshipsbetweensuchanetworkandanotherspatialobjectareoftenusedascriteriafordescribingtheconsistencyinmulti-scalegeographicapplications.Theproposedmodelincludescomputationalmethodstodeterminewhentwonetworksarethesameornot.Themodelisfurtherextendedtocovertherelationshipsbetweenanetworkandanotherspatialobject,suchasaregionoraline.Thesemethodswillplayanimportantroleintheassessmentofspatialsimilarityofsceneswithcomplexconfigurationsincludingroadsandurbanareas,paths,andotherlineargeographicfeatures.1.IntroductionGeneralizationisanindispensablepartofcartographicproduction,spatialdecisionsupportsystems,andotherscientificbranchesconstitutingthecontextofGeographicInformationSystems(GISs).Itresultsinmultiplerepresentations,occasionallythoughtofascopies,ofthesamescenesofobjectsatdifferentlevelsofspatialresolution,alsoreferredtoasscale[MLW95].Thesameobjectsarerepresentedinseveraldifferentways,tailoredtowardstheneedsofdifferentusersandanalyses.GISusersperformsuchoperationsaszoomingintoandoutofamap-likerepresentation,andexpectthatthepredominantspatialrelationsbepreservedthroughoutsuchscalechanges.Likewise,aqueryevaluationalgorithmexecutedatacoarserlevelshouldgivethesame,oratleastaverysimilar,resultasaqueryprocessedagainstamoredetailedlevel[BEF92].Cartographicmapseriesatdifferentscalesareanotherexampleofapplicationsthatneedmultiplerepresentationlevels.Thekeytothesuccessfuladoptionofmulti-resolutiongeographicdatabasesisthemaintenanceofconsistencyacrossthedifferentrepresentations.Consistencydescribestheabsenceofanylogicalcontradictionswithinamodelofreality.Itisanimportantcriterionforgeographicdatabases,especiallywhenmapproductionisinvolved.Forexample,theU.S.NationalOceanService(NOS)maintainsatwo-tiermapproductionsystem,ANCS-II,whichallowscartographerstoderiveandmaintainchartpanelsatdifferentscalesforthesamegeographicareafromasinglegeographicdatabase[N94].Thiscartographicdatabaserequiresmapgeneralizationtoproducethelocationandappearanceoffeaturestobeplacedatchartsofdifferentscale.NOS’sguidelines*ThisworkwaspartiallysupportedbyaMassiveDigitalDataSystemscontractsponsoredbytheAdvancedResearchandDevelopmentCommitteeoftheCommunityManagementStaffandadministeredbytheOfficeofResearchandDevelopment.MaxEgenhofer’sresearchisfurthersupportedbytheNationalCenterforGeographicInformationandAnalysisthroughNSFgrantSBR-8810917,andbygrantsfromtheNationalScienceFoundationundergrantNo.IRI-9309230,RomeLaboratoriesundergrantnumberF30602-95-1-0042,andtheScientificandEnvironmentalDivisionoftheNorthAtlanticTreatyOrganization.IntegrityinDatabases—SixthInternationalWorkshoponFoundationsofModelsandLanguagesforDataandObjectsSchlossDagstuhl,Germany,S.Conrad,H.-J.Klein,andK.-D.Schewe(eds.),pp.119-132,September1996.forthisgeneralizationprocessdemandthatafeaturepresentatasmallscalealsoberepresentedatanylargerscaleofthesamearea.Althoughtherehasbeenconsiderableresearchinrecentyearsoncartographicgeneralization[BM91,MLW95]andvariousaspectsofmultiplerepresentations[BK91,PD95,RS95,TVP+92],wecurrentlylackmethodstoconsistentlymaintainmulti-resolutiongeographicdatabases.Othereffortsinrepresentingconsistentlygeographicdataonlydealwithonelevelofdetail[P96,US96].Currently,multi-resolutiongeographicdatabasesrecordexplicitlymultiplerepresentationscoveringthesamegeographicareaatdifferentscales.Suchdatabasesrequireamechanismtodetectinconsistenciesamongthedifferentrepresentations.Inthefuturemulti-resolutiongeographicdatabasesareenvisionedthatwouldderivemultiplerepresentations“onthefly,”providingmoreflexibilitysuchascontinuouszooming.Undersuchascenario,qualitycontrolmechanismswillbeneededtoconfirmthatageneralizationalgorithmsproducesconsistentresults.Themethodsdiscussedinthispaperapplytobothscenarios.Assessmentandmaintenanceofconsistencyamongmultiplecopiesofgeographicdatarequiresgeographicdomainknowledge.Thispaperfocusesondomainknowledgeaboutnetworks,animportantspatialdatatypesharedbymanygeographicapplicationssuchashydr