MotivationInformation OverloadBioNavQuery Result Navigation: Dynamic ApproachFrameworkFrameworkNavigation & Cost ModelsNavigation ModelAlgorithmsAlgorithms for EdgeCutExperimentsExperimental EvaluationFuture WorkMotivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkBioNav: Effective Navigation on Query Results ofBiomedical DatabasesAbhijith Kashyap1Vagelis Hristridis2Michalis Petropoulos1Sotiria Tavoulari31Dept. of Computer Science and EngineeringUniversity at Buffalo, SUNY2School of Computing and Information SciencesFlorida International University3Department of PharmacologyYale UniversitySeptember 8, 2008Motivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkMOTIVATIONExploratory queries are increasingly becoming a commonphenomenon in life sciencese.g., search for citations on a given keyword on PubMedThese queries return too-many results, but only a smallfraction is relevantthe user ends up examining all or most of the result tuplesto find the interesting onesCan happen when the user is unsure about what isrelevante.g., user is looking for articles on a broad topic: ’cancer’...query returns over 2 million citations on PubMedThis phenomenon is commonly referred to as’information-overload’Motivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkMOTIVATIONExploratory queries are increasingly becoming a commonphenomenon in life sciencese.g., search for citations on a given keyword on PubMedThese queries return too-many results, but only a smallfraction is relevantthe user ends up examining all or most of the result tuplesto find the interesting onesCan happen when the user is unsure about what isrelevante.g., user is looking for articles on a broad topic: ’cancer’...query returns over 2 million citations on PubMedThis phenomenon is commonly referred to as’information-overload’Motivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkMOTIVATIONExploratory queries are increasingly becoming a commonphenomenon in life sciencese.g., search for citations on a given keyword on PubMedThese queries return too-many results, but only a smallfraction is relevantthe user ends up examining all or most of the result tuplesto find the interesting onesCan happen when the user is unsure about what isrelevante.g., user is looking for articles on a broad topic: ’cancer’...query returns over 2 million citations on PubMedThis phenomenon is commonly referred to as’information-overload’Motivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkMOTIVATIONExploratory queries are increasingly becoming a commonphenomenon in life sciencese.g., search for citations on a given keyword on PubMedThese queries return too-many results, but only a smallfraction is relevantthe user ends up examining all or most of the result tuplesto find the interesting onesCan happen when the user is unsure about what isrelevante.g., user is looking for articles on a broad topic: ’cancer’...query returns over 2 million citations on PubMedThis phenomenon is commonly referred to as’information-overload’Motivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkCOMMON APPROACHES TO AVOIDINFORMATION-OVERLOADRankingCategorizationMotivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkCOMMON APPROACHES TO AVOIDINFORMATION-OVERLOADRankingCategorizationMotivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkCATEGORIZATION IN INFORMATION SYSTEMSAssumptions:Tuples in the database are annotated with one or morecategories orconceptsThe set of concepts are arranged in a concept hierarchyExample: Each citation in PubMed is associated withseveral concepts from the MeSH (Medical SubjectHeadings) hierarchy, typically 12 to 20Users querying the database are familiar with thecontrolled vocabulary of the concept hierarchyMotivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkCATEGORIZATION IN INFORMATION SYSTEMSAssumptions:Tuples in the database are annotated with one or morecategories orconceptsThe set of concepts are arranged in a concept hierarchyExample: Each citation in PubMed is associated withseveral concepts from the MeSH (Medical SubjectHeadings) hierarchy, typically 12 to 20Users querying the database are familiar with thecontrolled vocabulary of the concept hierarchyMotivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkQUERY RESULT NAVIGATION: NAIVE APPROACHGoPubMedCreate the Navigation Tree as follows:Extract the set S of concepts annotating tuples in thequery result set QConstruct the minimal sub-concept hierarchy tree T, thatcovers all concepts in SMotivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkQUERY RESULT NAVIGATION: NAIVE APPROACHGoPubMed Example:Section of Navigation Treefor query ’Prothymosin’(313 results)Motivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkQUERY RESULT NAVIGATION: NAIVE APPROACHGoPubMedProblems:Massive size of the Navigation TreeMeSH has over 48000 concept nodes313 results span over 3000 of these conceptsLarge number of duplicate tuplesEach tuple is annotated with 12-20 MeSH conceptsTotal tuple count is over 5000Effort required to navigate the query results increases!Motivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkQUERY RESULT NAVIGATION: NAIVE APPROACHGoPubMedProblems:Massive size of the Navigation TreeMeSH has over 48000 concept nodes313 results span over 3000 of these conceptsLarge number of duplicate tuplesEach tuple is annotated with 12-20 MeSH conceptsTotal tuple count is over 5000Effort required to navigate the query results increases!Motivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkQUERY RESULT NAVIGATION: NAIVE APPROACHGoPubMedProblems:Massive size of the Navigation TreeMeSH has over 48000 concept nodes313 results span over 3000 of these conceptsLarge number of duplicate tuplesEach tuple is annotated with 12-20 MeSH conceptsTotal tuple count is over 5000Effort required to navigate the query results increases!Motivation BioNav Framework Navigation & Cost Models Algorithms Experiments Future WorkQUERY RESULT NAVIGATION: DYNAMIC APPROACHBioNavExample: Navigation stepsfor query ’Prothymosin’Only aselective set