Subject: Hashing, and Ted's concerns about wastefulness

From: Graham Klyne <[email-masked]>
Date: Mon, 01 Feb 1999 12:57:55 +0000

At 22:52 29/01/99 PST, Larry Masinter wrote:
>> The lookup problem bothers me, because I believe there will be
>> relatively few cases where the hash as given would be instantly
>> recognizable (since it includes both features and feature values).
>
>   (SONY_VGA_MODELXXX) :-
>      (| (& (pix-x=640)
>            (pix-y=280)
>            (color=256))
>         (& (pix-x=1028)
>            (pix-y=1028)
>            (color=256)))
>is equivalent in this regard to
>   (fh=1aXb124AsDfg) :-
>       (| (& (pix-x=640) ...)
>
>i.e., there's a value that expands to other values, that you
>either know or have to look up. The advantage of "fh" is that
>if Sony's VGA display's features are the same as NEC's, you
>don't need to keep both in the table.

If I understand your approach correctly, you want to have a way of
expressing arbitrary aggregations that does not rely on some registration
mechanism to define its meaning, and also does not say anything about how
unknown aggregates are resolved.

I'd like to make a small counter-proposal to the that incorporates an idea
from Ted, overcomes some issues of compatibility with current syntax, and
still (I believe) achieves your goal:

#   (h.1aXb124AsDfg) :-
#       (| (& (pix-x=640) ...)

(What I have done is replaced the 'fh' tag with 'h.<hash>' as an auxiliary
predicate tag.)

Another approach that also permits some indication of retrieval mechanism:

#   (h.<URI>="<hash>")

within a capability expression (this conforms to current syntax rules),
where <hash> is calculated over the body of a notional auxiliary predicate:

#   (h.<URI>) :- 
#       (| (& (pix-x=640) ...)

[...]
>> So the question for the "fh" possibility is: how and when do we allow
>> for the hash to be disaggregated?
>
>Yes, but it's not so different for any of the other proposals
>for aggregated feature.

I agree.

A key advantage I see to the hash approach is that one has a way to
validate whatever disaggregated value one may have to hand without resort
to externally held reference information.

>> I suppose we can create a feature that is, in fact, a request for fh
>> to be disaggregated.  
>
>I think that's mixing descriptive information and protocol in
>an unfortunate way. I think disaggregation is likely to be
>protocol dependent, even though the semantics of "fh" is
>protocol independent.

Again, I agree.

If two expressions contain the same sub-expression:

#    (h.<hash>
or
#    (h.<URI>="<hash>")

then they are known to match at that point without disaggregation.  OTOH,
if they have different hash values then disaggregation is needed to
determine whether or not they truly match.  No additional "feature" is
required to trigger the disaggregation mechanism;  simply some kind of
"lazy evaluation" component in the feature set matching process.

Further, using my second proposal, two different tags:

#    (h.<URI1>="<hash>")
#    (h.<URI2>="<hash>")

can be assumed to match if the hash values are the same (e.g. for rebadged
versions of the same mobile phone).

An attractive property of this approach is that it can be used with the
current specification (with registration of the 'h.' facet), in many cases
will yield the correct result, and will never yield a false feature set
match.  Agents with additional knowledge can reconcile the apparently
different feature tags (this is also behaviour consistent with the current
specification.)

#g

------------
Graham Klyne
([email-masked])

---

From: Ted Hardie <[email-masked]>
Date: Mon, 1 Feb 1999 12:35:12 -0800 (PST)

> where <hash> is calculated over the body of a notional auxiliary predicate:

I think this is workable, but we will need to be very careful in presenting
this to ensure that there is no confusion between g.<URI> h.<URI>; we also
need to specify exactly what you get if you retrieve h.<URI>.

I agree.

> "lazy evaluation" component in the feature set matching process.

I think that we have a problem here related to the "directionality" issue
Larry brought up with my previous message.

Think about it this way: This system works based on set intersection.
If either party presents information about their set using a hash, the
other party must be able to either recognize the predicates implied or
disaggregate the hash in order to determine whether the sets
intersect.  There are a couple of ways to do this, and they loosely
fit different scenarios.  Send along the hash with the predicates, and
you can use the hash in place of repeating elements without worrying
that the other party won't understand it.  Refer to the hash with a
URI that contains the disaggregated form, and the parties will
sometimes be able to retrieve the disaggregated forms.  Indicate a
failure to recognize and rely on in-bound communication to carry the
disaggregated forms from the other party to the party expressing the
failure.

I strongly believe that we need to do 1 if we do anything at all.  I
believe that 2 has value, but that the value is limited unless we
specify pretty strictly how the disaggregated predicates are
represented at the URI; I am also worried that there are problems both
with specifying a particular URL scheme for this and with not
specifying one.  For 3, Larry and I seem to disagree on the utility of
specifying a method for naming the failure as an "understanding the
hash" issue, and I think we need to hear other voices on that part of
the problem.

None of this is to say that lazy evaluation isn't a good thing; I mean simply
that we have to have some idea of what the disaggregation mechanisms are
to get a solution that will work across protocols.

> different feature tags (this is also behaviour consistent with the current

Can someone (Bill, Graham, Larry) write up one of these proposals as
an ID, so we can have something to discuss concretely?

			thanks,
				Ted Hardie