Subject: Re: WildCards

From: Brian Rosen <[email-masked]>
Date: Wed, 8 Sep 1999 16:13:21 -0400

I very much disagree with this.

Wildcard match in a table of fixed max length
strings is easy to implement.  This is something
that text processing systems do all the time and
there are lots of very efficient techniques to
do it simply.  You certainly do not have an
algorithm that has n*64 of anything (unless all
names are max length!).  One commonly used
technique when only one wildcard is allowed is
to do prefix match on one side and suffix match
on the other.  That's pretty simple, isn't it?

I maintain that while you can choose to infer
some significance to slash in your implementation,
you are in peril of having your (provisioned) name
not having a slash (unless your MG implementation
does something silly like require it).  I happen
to like hierarchical names, but you can be sure that
our implementations will not insist on using them.
I would be very wary of biasing an implementation
towards imputing significance to slash.

However, without any structure to names, you NEED
the flexibility of general wildcard substitution.

Brian

> -----Original Message-----
> From: Abdallah Rayhan [mailto:[email-masked]]
> Sent: Wednesday, September 08, 1999 12:09 PM
> To: [email-masked]
> Subject: Re: WildCards
>
>
> This does not eliminate the fact searching all terminations
> will be expensive.
> What is the difference between foo*, foo*baz and dictionary search ?
>
> I must stress the fact that we are not into dictionary search
> engines but
> solid and stable protocol. I am not willing to make my search
> tables to
> look like dictionaries. It is expensive, inflexible and waste
> of the protocol.
>
> The length of terminations, 64 char, is not cheap. You have
> 2^64 different
> possibilities. Do you have an idea of how complex this is ??? If you
> organize your terminations to start with "a" and you perform
> "a*" you still
> have to do 63. Even, if you use hashtables, you will have to
> search a large
> subset of terminations that start with "a" to obtain your subset.
>
> Things like "/" does not necessary mean hierarchy. However it allows
> a window to organize the look up table search efficiently.
> Even if we dont
> choose to use "/", I dont see why we need the extra complexity of * in
> the middle of names, e.g., foo*baz.
>
> Our mission should be simplify, simplify and simplify and not cram
> things into the protocol because they look nice to have.
>
> Abdallah Rayhan
>
>
> Brian Rosen wrote:
>
> > Sorry, slash has no significance.  You can organize your
> table in alphabetic
> > order, but the difference in implementing foo* and foo*baz
> is not very
> > significant.
> > If you optimize your tables to improve performance of
> wildcards like foo/*,
> > what will you do when the MG asks for foo*?  We got rid of
> hierarchy (over
> > my objections, I
> > point out).  You can always try to optimize an
> implementation that assumes
> > it might have names with slash in them, but in the general
> case, you can't.
> >
> > Search techniques for wildcards are older than the hills.
> > For larger gateways, you can take advantage of the fact
> that terminationIDs
> > are limited to 64 characters.  It's
> > even easy to match on multiple wildcards with a recursive
> technique.  You
> > might indeed have to look over a lot of
> > terminations in a big gateway.
> >
> > Brian
> >
> > > -----Original Message-----
> > > From: Abdallah Rayhan [mailto:[email-masked]]
> > > Sent: Tuesday, September 07, 1999 3:14 PM
> > > To: [email-masked]
> > > Subject: Re: WildCards
> > >
> > >
> > > Wildcards add flexibility but could be problematic too.
> > > Each time a wildcard is used you have to search all
> > > the terminations trying to find which ones match.
> > > How many terminations are we talking about ???
> > >
> > > If we use restricted last character wildcard, there is
> > > a window for efficiency since you can organize your
> > > termination lookup tables by before and after "/".
> > >
> > > Recommendations:
> > > 1- Guide lines for naming terminations are needed
> > > 2- Allow wildcards in certain places, e.g., after
> > > "/" or between two "/" only.
> > >
> > > Abdallah
> > >
> > >
> > > Brian Rosen wrote:
> > >
> > > > Should the wildcard character ("*") be allowed anywhere
> > > > in a TerminationID?  Or should it be restricted to the
> > > > last character, as in "foo/*"
> > > >
> > > > By insistence of several people, the name no longer has
> > > > any hierarchy connotations.  The slash has no significance.
> > > > I argue that if it's just a string, then wildcards should
> > > > be allowed anywhere in the string.  This*Test matches
> > > >         ThisTest
> > > >         ThisIsATest
> > > >         This1Test
> > > > etc.  It's certainly trivial to implement a general
> > > > wildcard pattern match, and may have several uses.
> > > > One specific use is to control the amount of text output
> > > > you get from an audit.
> > > >
> > > > Brian
> > >
>