of High-Dimensional Environmental Sustainability D

QuestVisandMDSteer:TheVisualizationofHigh-DimensionalEnvironmentalSustainabilityDatabyMattWilliamsB.Ed.,UniversityofBritishColumbia,1998;Hon.B.Math.,UniversityofWaterloo,1994ATHESISSUBMITTEDINPARTIALFULFILLMENTOFTHEREQUIREMENTSFORTHEDEGREEOFMasterofScienceinTHEFACULTYOFGRADUATESTUDIES(DepartmentofComputerScience)WeacceptthisthesisasconformingtotherequiredstandardTheUniversityofBritishColumbiaJuly2004cMattWilliams,2004AbstractThevisualizationoflargehigh-dimensionaldatasetsisanactivetopicwithintheresearchareaofinformationvisualization(infovis),aresearchareathatstudiesthevisualrepresentationsofcomplexabstractdatasets.Mythesispresentstwoinfovissystemsthatweremotivatedbythedesiretoexplorea294-dimensionalenvironmen-talsustainabilitydataset.Ourcollaboratorsdevelopedtheenvironmentaldatasetfromexpertknowledgeonecological,economical,andsocialsystemswhichwereusedtomodelfuturescenariosconsistingof294measuresofenvironmentalsustain-abilitysuchasurbanpopulation,watersupplylevels,ortonnesofwaste.Sincethesecomplexsystemsandlargedatasetsaredifficultforanon-expertusertocom-prehend,wedevelopedQuestVis,atoolthatappliesinfovistheoriesandtechniquestoimprovethecomprehensibilityduringexplorationoftheenvironmentaldataset.Thetoolconsistsofthreecomponents:theinputpanel,theMultiscaleDimensionVisualizer(MDV),andtheScenarioSpaceExplorer(SSE).TheMDVpresentsuptoten294-dimensionalfuturescenariossimultaneouslyonthescreentoenableuserstogetaquickoverviewofthedata.Thesimultaneouspresentationalsoenablesuserstocomparemultiplefuturescenariosside-by-side.TheSSEpresentsthespaceofall120000futurescenariosinaninteractivetwo-dimensionallayoutwhichpro-videstheuseranoverviewofthepossibilities.TheSSEistightlycoupledwiththeMDVtoprovidecontexttothespecificfuturescenariosthatarepresentedintheMDV.Thesetightlylinkedcomponentstogetherprovideanoverview+detailsframeworkwithinwhichuserscaneffectivelyexplorethedatasetandimmediatelyseetheconsequencesoftheirchoices.ThecreationofthedimensionalityreducedoverviewinQuestVisledtoasecondresearchdirection.WerealizedthatcurrentimplementationsofMultidi-mensionalScaling(MDS),atechniquethatattemptstobestrepresentdatapointsimilarityinalow-dimensionalembedding,arenotsuitedformanyoftoday’slarge-scaledatasets.ThisrealizationmotivatedustodevelopMDSteer,asteerableMDScomputationengineandvisualizationtoolthatprogressivelycomputesanMDSlayoutandhandlesdatasetsofoveronemillionpoints.Ourtechniqueemployshi-erarchicaldatastructuresandprogressivelayoutsthatallowtheusertosteerthecomputationofthealgorithmtotheinterestingareasofthedataset.Thealgorithmiiiterativelyalternatesbetweenalayoutstageinwhichasub-selectionofpointsareaddedtothesetofactivepointsaffectedbytheMDSiteration,andabinningstagewhichincreasesthedepthofthebinhierarchyandorganizesthecurrentlyunplacedpointsintoseparatespatialregions.Thisbinningstrategyallowstheusertose-lectonscreenregionsofthelayouttofocustheMDScomputationintotheareasofthedatasetthatareassignedtotheselectedbins.Weshowbothrealandcom-monsyntheticbenchmarkdatasetswithdimensionalitiesrangingfrom3to300andcardinalitiesofoveronemillionpoints.iiiContentsAbstractiiContentsivListofTablesviListofFiguresviiAcknowledgementsviii1Introduction11.1InformationVisualizationBackground.................21.1.1Overview+Details........................31.1.2HighDimensionality.......................31.1.3VisualEncoding.........................41.2OverviewofResearch..........................41.3Contributions...............................51.4ThesisOrganization...........................62RelatedWork72.1HighDimensionality...........................72.1.1DimensionalityReduction....................82.1.2ExplicitlyHigh-DimensionalVisualizations..........112.2Interaction................................132.3Aggregation................................143QuestVis163.1FutureScenarioModelling........................173.2TheQuestUsageModel.........................173.3QuestVisDesign.............................183.3.1QuestLimitations........................183.3.2QuestVisDesignGoals......................223.3.3DatabaseArchitecture......................233.4MultiscaleDimensionVizualizer(MDV)................243.4.1ColourEncoding.........................243.4.2Aggregation............................26iv3.4.3DetailedOutput.........................283.5InputChoices...............................283.5.1CouplingInputChoiceswithOutputIndicators........293.6ScenarioSpaceExplorer(SSE).....................313.6.1Colourization...........................333.6.2Trail................................333.6.3Filtering..............................343.7TheQuestVisUsageModel.......................353.8Implementaion..............................374MDSteer384.1Steerable,ProgressiveMDS.......................394.1.1Algorithm.............................404.1.2Bins................................414.1.3TerminationConditions.....................454.2Results...................................464.2.1Timing..............................474.2.2Stress...............................484.2.3Visua