Re: completeness

If you or Uli will tell you how I answer this question for, say,  
Google, then I will answer it about Sem Web apps the same way.
   In the world of people I work with outside the university (and many  
within), people sometimes talk about recall and precision, but I've  
never heard anyone argue about completeness of a Web Application.  The  
users I am representing are not logicians and don't care about getting  
"all and only the right answers" because they say things like "there  
are no such things as right answers" - they say things like "If I can  
make a better recommendation than <system X> my profits go up" or "we  
are trying to help people find 'useful' information" -- these things  
are not quantified well in the world of logics, but they sure as heck  
mattter a lot out on the Web.
   Or if you prefer a more academic answer, those of us who don't play  
in the logic space also do real work, we do sometimes need ground  
truth (so to show scaling, we usually have a dataset for which the  
results are known, and we show we get all those answers - not prove we  
will always get all answers - just that we get the right ones for  
known queries) - but then we scale to problems where we no there is no  
known algorithm that can find all the results before the heat death of  
the universe, and we compare what sort of answers our heuristics get  
over the ones other people get.
  So let me ask a question that was asked to one of PhD students at  
his proposal --  The questioner asked roughly "You claim your system  
is sound and complete, but having proved the algorithms have this  
property, how do you make the claim about your system?  Your  
implementation uses Java, which goes through a compiler, and it is  
provable that that compiler is neither sound nor complete."  When the  
student stopped sputtering, the suggestion was made that he learn the  
difference between algorithms and systems.
  -JH


On Feb 21, 2008, at 10:58 AM, Alan Ruttenberg wrote:

>
> Since this question goes to the motivation for this fragment, I  
> would like it if Jim, Zhe, and Jeremy, who are the torchbearers,  
> could please respond with some guidelines about this, ideally drawn  
> from experiences working with customers.
>
> Thanks,
> Alan
>
> On Feb 20, 2008, at 2:54 PM, Ulrike Sattler wrote:
>
>>
>> Hi,
>>
>> I thought I'd share some of my thoughts regarding completeness,  
>> scalability, & interoperability that might explain why I keep  
>> shouting "what do you mean by *scalable*"?
>>
>> 1) Even I can write a very scalable OWL DL query answering engine  
>> if it doesn't have to be complete: when asked to retrieve instances  
>> of a class C, it simply always only returns nothing...wait, I can  
>> even do better by returning "told" instances of C!
>>
>> 2) If we agree that (1) is sort of cheating, then we need to be  
>> more precise what "completeness" means: now, if we say "my engine  
>> will retrieve as many instances of C as it can manage in the given  
>> time", then we might get more than the told instances, but we could  
>> be  in trouble regarding interoperability: your engine could return  
>> a very different answer set from mine, since they have different  
>> strengths or optimisation techniques or,e.g., rule orderings.
>>
>> So, what I would like to see as a clarification of "we can trade a  
>> bit of completeness for some scalability" is a description what  
>> *kind* of completeness we give up for (ideally) how much gain in  
>> performance.
>>
>> Cheers, Uli
>>
>>
>>
>
>

"If we knew what we were doing, it wouldn't be called research, would  
it?." - Albert Einstein

Prof James Hendler				http://www.cs.rpi.edu/~hendler
Tetherless World Constellation Chair
Computer Science Dept
Rensselaer Polytechnic Institute, Troy NY 12180

Received on Thursday, 21 February 2008 16:42:20 UTC