Challenges of Navigational Queries: Finding Best Paths in Graphs

Simple item page
dc.contributor.authorRaschid, Louiqa
dc.contributor.authorVidal, Maria-Esther
dc.contributor.authorWu, Yao
dc.contributor.authorCardenas, Marelis
dc.contributor.authorMarquez, Natalia
dc.date.accessioned2005-10-06T16:30:25Z
dc.date.available2005-10-06T16:30:25Z
dc.date.issued2005-10-06T16:30:25Z
dc.description.abstractLife science sources are characterized by a complex graph of overlapping sources, and multiple alternate links between sources. A (navigational) query may be answered by traversing multiple alternate paths between an origin and target source. Paths may be characterized by several metrics, including the cardinality of objects of the target source(TOC), the cost of query evaluation of a plan for the path, and the user's preference for specific paths. Our challenge is finding the best paths among the set of all solutions, AllPaths, that meet some user specified ranking criteria. If the user ranking criteria is strict, then the problem is to find the Top K paths. If the user wants a trade-off of several metrics, then the problem is to find the Skyline paths that are not dominated by other paths. {\em NSearch} is a naive solution. {\em BFSrchOpt} is a heuristic best-first search strategy. It uses a metric to rank partial solutions (subpaths) and (local) metrics to guide graph traversal, and produces BFPaths. We compare the precision and recall of BFPaths compared to the Top K\% or Skyline of AllPaths. We study the impact of graph properties on the behavior of {\em BFSrchOpt}. {\em BFSrchOpt} can be orders of magnitude faster than {\em NSearch}.en
dc.format.extent444495 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/2815
dc.language.isoen_USen
dc.relation.isAvailableAtCollege of Computer, Methematical & Physical Sciencesen_us
dc.relation.isAvailableAtComputer Scienceen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_us
dc.subjectsearchen
dc.subjectpathen
dc.titleChallenges of Navigational Queries: Finding Best Paths in Graphsen
dc.typeArticleen

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
search.ps
Size:
434.08 KB
Format:
Postscript Files
Download
Thumbnail Image
Name:
search.pdf
Size:
205.17 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of search.ps
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.81 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Computer Science Research Works