Search |  Contact |  SRI Home Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap. Do not follow this link, or your host will be blocked from this site. This is a spider trap.A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A ASRI International.  333 Ravenswood Avenue.  Menlo Park, CA 94025-3493. SRI International is a nonprofit corporation.

AIC Seminar Series

Using Schematic Information to Accelerate Search in Large Relational Data Graphs.

Tina Eliassi-RadCASC at Lawrence Livermore National Laboratory

Date:  2004-10-27 at 16:00

Location:  EJ228  (Directions)

   Abstract

The majority of real-world graphs contain semantics. That is, they encode meaningful entities and relationships. These graphs (a.k.a., relational data graphs or RDGs) have types associated with their vertices and edges. A graphÂ’s schematic information defines its types (i.e., the types of the vertices that may be connected via a given edge type). We use such schematic information to reduce and prioritize the search space between a source vertex and a destination vertex. Specifically, we define three probabilistic heuristics that utilize schematic information. We embed our heuristics into A* and compare their performances to breadth-first search and the simple non-probabilistic A* search. We test our heuristics on large RDGs with "scale-free" and "small-world" properties. RDGs with these properties have been used recently to model many real-world phenomena. Our experimental results identify situations in which a particular algorithm is a clear winner. This is joint work with Edmond Chow.

   Bio for Tina Eliassi-Rad

Tina Eliassi-Rad earned her Ph.D. at the University of Wisconsin-Madison in 2001. Since then, she has been employed as a Computer Scientist in the Center for Applied Scientific Computing (CASC) at Lawrence Livermore National Laboratory (LLNL). Her background is in machine learning, artificial intelligence, and mathematical statistics. In particular, her dissertation was about intelligent agents that learn to categorize and extract textual information. Currently, she works on scalable algorithms for statistical modeling and querying of tera-scale scientific data sets and large relational data graphs.

   Note for Visitors to SRI

Please arrive at least 10 minutes early as you will need to sign in by following instructions by the lobby phone at Building E. SRI is located at 333 Ravenswood Avenue in Menlo Park. Visitors may park in the parking lots off Fourth Street. Detailed directions to SRI, as well as maps, are available from the Visiting AIC web page. There are two entrances to SRI International located on Ravenswood Ave. Please check the Builing E entrance signage.

SRI International
©2014 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
SRI International is an independent, nonprofit corporation. Privacy policy