David Karger's issue on inferencing search

Hi David

RE: Your issue on inferencing search

[ 029. ]
Summary: Inferencing Search
Raised By: David Karger
Status: open
Description: 

3.2.6 

I am made nervous by the discussion of inferencing search.  This
formulation takes a tractable database problem and turns it into an
NP-hard or even undecidable computational nightmare.  I feel much more
secure factoring the problem into "search what's currently explicit in
the databse" and "use tools to infer (best effort) new information
that can be added to the database.

Equivalence does feel like a "safe" specialized form of inference
worth giving attention to.

================

When I wrote inferencing search I was thinking about subclass, subproperty
and equivalence relationships i.e. arguably the core semantic network
relationships. So can your issue be resolved by:

1. Replacing the term "inferencing search" with something else? Do you have
any suggestions?

2. Noting that when you perform inferencing, often it is advantageous to
cache results so that these results do not have to be recomputed later on? 

3. Just by noting that inferencing search may be problematic as you
highlight?

Alternatively do you have a suggestion of how to change section 3.2.6 so you
are happier with the wording? 

Dr Mark H. Butler
Research Scientist                HP Labs Bristol
mark-h_butler@hp.com
Internet: http://www-uk.hpl.hp.com/people/marbut/

Received on Friday, 16 May 2003 12:38:16 UTC