Subject: Atom Rank Extensions: Feedback on r:value and r:range elements wanted (long)

From: Andreas Sewe <[email-masked]>
Date: Fri, 05 May 2006 16:48:51 +0200

Having ended up as co-author of the Atom Rank Extensions draft
<http://www.ietf.org/internet-drafts/draft-snell-atompub-feed-index-09.txt>
I would like to encourage some more discussion on the extension's
features.  I would especially like to know whether they are flexible
enough to cope with all the major use cases while being at the same time
reasonably simple to implement.

The extension should, e.g., be able to cope with most grading schemes in
use; it needs to be able to describe the set of permissible rank values
(grades).  So we are talking (totally) ordered sets here.

Now the order part is easy; that is what @significance
(="ascending"/"descending") is for.  The hard part is to describe the
underlying set of numbers.

Now the current draft defines two elements, r:value and r:range, for
this purpose.  Those two elements can be, however, be collapsed into a
single one, and, with cleverly chosen defaults, defining sets using this
new r:values element is IMHO as simple, if not simpler, as with the old
approach.  Others might have different opinions, though, which I would
really like to hear about.

At any rate, the proposed change looks basically as follows (Note,
however, that the issue of rounding rank values has intentionally been
left out, since this would only distract from the design issue at hand.)

The r:scheme Element

Ranking Schemes are defined using the r:scheme element.  Each scheme
defines the set of rank values permissible for all r:rank elements with
the associated scheme.

[...]

The set of rank values defined by an r:scheme element is the union of
the sets of rank values defined by each of its r:values elements.  Note
that those sets may overlap.

The r:values Element

The r:values elements defines a set of rank values, each of which has to
conform to the XML Schema decimal data type [W3C.REC-xmlschema-2-20041028].

   values = element r:values {
     atomCommonAttributes,
     attribute minimum { xsd:decimal | "unbounded" }?,
     attribute maximum { xsd:decimal | "unbounded" }?,
     attribute steps   { xsd:decimal | "continuous" }?,
     attribute origin  { xsd:decimal }?,
     undefinedContent
   }

The "minimum" attribute specifies an inclusive lower bound on the set of
rank values defined by the r:values element.  Here, the special value of
"unbounded" denotes negative infinity.  If not specified, the value of
the "minimum" attribute is considered to be "unbounded".

The "maximum" attribute specifies an inclusive upper bound on the set of
rank values defined by the r:values element.  Here, the special value of
"unbounded" denotes positive infinity.  If not specified, the value of
the "minimum" attribute is considered to be "unbounded".

The "steps" attribute specifies either an increment or has the special
value "continuous".  If not specified, the value of the "steps"
attribute is considered to be 0.

The "origin" element specifies the base from which steps are to be
calculated. If not specified, the value of the "origin" attribute is
considered to be 0.

If the value of the "steps" attribute is "continuous" the set of rank
values defined by the r:values element is

   { x | minimum <= x <= maximum }.

Otherwise the set of rank values defined by the r:values element is

   { x | minimum <= x <= maximum,
         x = (origin + i * steps) for some integer i }.

The following examples illustrate how different sets of rank values can
be defined by means of a single r:value element:

<!-- The rank value 1 -->
<r:values origin="1" />

<!-- The rank values 1, 2, 3, 4, 5 -->
<r:values minimum="1" maximum="5" steps="1" />

<!-- The rank values 0.0, 0.5, 1.0, 1.5, ...., 10.0 -->
<r:values minimum="0.0" maximum="10.0" steps="0.5" />

<!-- The rational interval [0, 100] -->
<r:values minimum="0" maximum="100" steps="continuous" />

<!-- The integers ..., -2, -1, 0, +1, +2, ... -->
<r:values steps="1" />

<!-- The natural numbers 0, 1, 2, ... -->
<r:values minimum="0" steps="1" />

That's all.  Also note that this approach allows overlapping r:values
sets.  For example, one is now able to define, in a reasonable concise
way, the following grading scheme common in Germany:

<!-- 1.0, 1.3, 1.7, 2.0, 2.3, 2.7, ..., 4.0, and 5.0 -->
<r:scheme significance="descending" ...>
   <r:values minimum="1.0" maximum="4.0 origin="1.0" steps="1.0" />
   <r:values minimum="1.0" maximum="4.0 origin="1.3" steps="1.0" />
   <r:values minimum="1.0" maximum="4.0 origin="1.7" steps="1.0" />
   <r:values origin="5.0" />
</r:scheme>

Of course one could alternatively list all 11 values explicitly, but the
above is rather more concise.  (In fact, the definition of 5.0 could
even be moved into the first r:values element.)

But as I said above, others might see this differently...

Also, I would like to know whether a definition in terms of set notation
is fine with you, or whether we should expand on the natural language
explanations.  Describing precisely what "origin" and "steps" do, in
plain English, is unfortunately surprisingly difficult. :-(

Looking forwards to your feedback,

Andreas Sewe

---

From: "Thomas Broyer" <[email-masked]>
Date: Fri, 5 May 2006 18:05:56 +0200

>    { x | minimum <= x <= maximum }.

And @origin is ignored?

>          x = (origin + i * steps) for some integer i }.

If "i" and "steps" are positive values, then "x" will always be
superior to "origin".

If "origin" is superior to "minimum", then "minimum" is not needed, as
"origin" *is* the minimum value.
If "origin" is less than "minimum", then "x" will always be superior
to "origin + i*steps" for which "i" is the minimum integer value
verifying "origin + i*steps >= minimum"; this is quite easy to
compute, so there's no real need for "minimum" either in this case:
the following r:values are all equivalent:
    <r:values minimum="1.0" maximum="4.0" origin="0.3" steps="1.0" />
    <r:values minimum="1.0" maximum="4.0" origin="1.3" steps="1.0" />
    <r:values minimum="1.3" maximum="4.0" steps="1.0" />
    <r:values minimum="1.3" maximum="3.3" steps="1.0" />

If "steps" is a negative value, its easy to compute the same set of
values using the minimum allowable value as the "origin" (or
"minimum") and a positive "steps". The following r:values are all
equivalent:
    <r:values minimum="1.0" maximum="4.0" origin="3.3" steps="-1.0" />
    <r:values minimum="1.0" maximum="4.0" origin="0.3" steps="1.0" />

So: there is no need for "origin" and negative "steps" values.

There is however one case where that (converting a negative "steps"
value into a positive one) could not be possible: when "minimum"
equals "unbounded".
Couldn't it be spec'd that:
 - if "minimum" is provided and not "unbounded", then "steps" counts
upwards from "minimum" to the greatest value inferior to "maximum"
 - if "minimum" is not provided or "unbounded", then "steps" counts
downwards from "maximum" to negative infinity.

In other words, people transitioning from origin and/or negative-steps
have to do the following:
 - if "steps" is negative and "minimum" is not "unbounded", replace
"minimum" with the smallest allowable value and use a positive "steps"
value
 - if "steps" is negative and "minimum" is "unbounded", replace
"maximum" with the value of "origin" and use a positive "steps" value
(which will count downwards to negative infinity)
 - if "steps" is positive, replace "minimum" with the value of "origin"

> <!-- The rank value 1 -->

Could be expressed as:
    <r:value value="1" /> <!-- a ew r:value element -->
or
    <r:values value="1" /><!-- a new "value" attribute -->
or with the following r:values:
    <r:values minimum="1" maximum="1" />

--
Thomas Broyer

---

From: James M Snell <[email-masked]>
Date: Fri, 05 May 2006 09:03:59 -0700

Andreas Sewe wrote:
>[snip]

Just to note, this seems to be the key disagreement between Andreas and
I on the spec.  IMHO, for schemes consisting of a constrained set of
fixed absolute values (like the German grading system which uses 1.0,
1.3, 1.7, 2.0 etc), specifying a collection of overlapping ranges just
doesn't feel right.

>[snip]
>[snip]
>[snip]

The alternative:

<r:scheme significance="descending" scale="1">
  <r:value label="1" >1.0</r:value>
  <r:value label="1-">1.3</r:value>
  <r:value label="2+">1.7</r:value>
  <r:value label="2" >2.0</r:value>
  <r:value label="2-">2.3</r:value>
  <r:value label="3+">2.7</r:value>
  <r:value label="3" >3.0</r:value>
  <r:value label="3-">3.3</r:value>
  <r:value label="4+">3.7</r:value>
  <r:value label="4" >4.0</r:value>
  <r:value label="4-">4.3</r:value>
  <r:value label="5+">4.7</r:value>
  <r:value label="5" >5.0</r:value>
</r:scheme>

To me, this is a whole lot less complicated because I don't have to deal
with step sizes, origins, minimum and maximum values, overlapping
ranges, etc.  There's just a set of explicitly defined values.  Also
note that in the German grading scheme, each of the values are generally
associated with labels (e.g. 1, 1-, 2+, etc) much in the same way that
the U.S. grading scheme associates percentages with labels (A, B, C,
etc).  Using the overlapping ranges approach, it would not be possible
to specify the labels for the values.

That said, there are cases in which a set of ranges are appropriate. For
example, the typical US grading system.

<r:scheme significance="ascending" scale="2">
  <r:range label="F" minimum="0.00" maximum="0.59" step="0.01" />
  <r:range label="D" minimum="0.60" maximum="0.69" step="0.01" />
  <r:range label="C" minimum="0.70" maximum="0.79" step="0.01" />
  <r:range label="B" minimum="0.80" maximum="0.89" step="0.01" />
  <r:range label="A" minimum="0.90" maximum="0.99" step="0.01" />
  <r:value label="A+">1.00</r:value>
</r:scheme>

In this case, it is obvious that the set of acceptable values is too
large to list individually.

> plain English, is unfortunately surprisingly difficult. :-(

We're working on the language in the spec.  I've never really been happy
with it and had been planning on a scrub for some time, but I wanted our
initial focus to be on the elements and the basic mechanism for defining
the schemes.

- James

---

From: James M Snell <[email-masked]>
Date: Fri, 05 May 2006 10:04:13 -0700

Thomas,

Everything you write below speaks precisely to the point as to why I
would prefer *not* always defining r:scheme in terms of ranges --
especially potentially overlapping ranges.  Ranges can be complicated.

In the current spec, the use of origin is dependent both on the
significance of the scheme (ascending or descending) and on whether or
not minimum/maximum values are specified.

If significance=descending and maximum is specified, then origin ==
maximum and step counts backwards. Larger numbers have lower significance.

If significance=ascending and minimum is specified, then origin ==
minimum and step counts forwards. Larger numbers have greater significance.

Stepped range values should always be calculated relative to the least
significant value.  If the least significant value is not specified,
origin may be used to provide an alternative starting point.  If the
least significant value is specified, specifying an origin is unnecessary.

One point that needs to be clarified in the spec. Step MUST be a
positive decimal value.

Also note that in the current spec, the step is used only to identify
the increment at which values in the range are considered significant
for purposes of comparing ranks.  When producing ordered sets of ranked
entries, intermediate values that fall in-between steps are considered
equivalent to the nearest least-significant, in-step value.

For instance, given the following range in a scheme with ascending
significance,

  <:range minimum="0.00" maximum="1.00" step="0.10" />

The set of values 0.01...0.09 is considered equivalent to the value 0.10.

This is a point that Andreas and I have disagreed on.  His argument has
been that feed publishers should only output r:rank values that
precisely match the step and origin. e.g. a rank of 0.15 would be
invalid given the above scheme.  With this approach, overlapping ranges
are less of a problem so long as all of those ranges use the same size
step and specify different origins.

I, on the other hand, feel that intermediate rank values are acceptable,
in which case, ranges MUST NOT overlap because you'd never be able to
precisely determine the range to which the value belongs.

For schemes consisting of a constrained set of fixed, absolute values,
dealing with all this range stuff is just overkill.  If there are only a
handle of acceptable values, we should just list those specific values
and be done with it.

- James

---

From: Andreas Sewe <[email-masked]>
Date: Mon, 08 May 2006 16:01:05 +0200

>>    { x | minimum <= x <= maximum }.

Well, it is not really ignored but irrelevant, since a value for @steps
of "continuous" can be read as making infinitesimal steps. And then
@origin doesn't really matter. You are covering the entire real line, no
matter where you start -- but of course @minimum and @maximum have a say
in this, too. (Note that defaulting @origin to 0 does no harm, though.
No need to make that another special case.)

> If "i" and "steps" are positive values, then "x" will always be

Note that i is assumed to be an integer, not a natural number; it can be
negative.

You are right, however, with your observation that a negative value for
"steps" should be disallowed. As James already replied, the next
revision of the spec will rectify this.

[...]

> So: there is no need for "origin" and negative "steps" values.

I agree about the negative @steps. @origin is useful, however, even when
its use can be optimized away in some cases.

This is because the above conversion will not work if @minimum is
"unbounded". As you recognized yourself below you, to describe the set
{..., -2.7, -1,7, -0.7, +0.3, +1.7, +2,7, ...}, you need

<r:values minimum="unbounded" origin="0.3" steps="1.0" />

Note that @minimum defaults to "unbounded" -- and is thus not even
needed in the above definition. This is precisely to allow this case to
be written concisely.

(For similar reasons @steps defaults to 0, making it easy to define
singleton sets. That @minimum and @maximum are -- per default -- still
"unbounded" doesn't matter when @steps is 0.
Similar reasoning lead to a default of 0 for @origin. In practice you
should rarely need to specify all four attributes explicitly.)

> downwards from "maximum" to negative infinity.

But what about both @minimum and @maximum being "unbounded"? In this
case you need an origin. In most other cases, however, you can simply
rely on the default of 0. (I expect non-zero origins, except for
singleton sets and a few odd cases like {0.3, 1.3, 2.3, ...}, to be
quite rare in practice.)

> - if "steps" is positive, replace "minimum" with the value of "origin"

The first two cases will be eliminated from the next revision of the
spec; negative steps are not only counter-intuitive but redundant.

The last falsely assumes that i, in (origin + i * steps), is only
non-negative.

>    <r:values minimum="1" maximum="1" />

All true. This proposal, however, deliberately replaces the two elements
r:value and r:range (as present in the current spec) by a single
r:values element, with carefully chosen defaults to make all the common
use cases just as easy to define.

So its purpose is simply to find out which approach -- two elements
(r:value really being redundant) or a single one -- is easier to
understand and implement.

(I guess the workings of the attributes might be a little bit easier to
comprehend if I could find a better name, suitable for the singleton set
case as well, for @origin. Maybe you have a suggestion.)

At any rate, thanks for your comments.

Andreas Sewe

---

From: Andreas Sewe <[email-masked]>
Date: Mon, 08 May 2006 17:00:47 +0200

> 1.3, 1.7, 2.0 etc), specifying a collection of overlapping ranges just

Yes, the key disagreement is not whether we should use a single element 
  or two (I wrote the original proposal to find out atom-syntax's 
preference on this), but whether ranges should be allowed to overlap.

Actually, we disagree on three overlapping (pun intended) questions:

1.) Does r:scheme define anything beyond a set of valid rank values (and 
an order on them)?

Personally I consider r:scheme's child elements as a specialized 
datatype definition language; since we know what use cases we want to 
support, so we can come up with a nice, little language to specify how 
valid and invalid rank values have to look like.

Now James, AFAIK, additionally wants to be able to attach labels to 
r:values and r:ranges. But r:rank's @label attribute does the same job! 
The current spec, however, does not state how conflicts are to be 
resolved. Furthermore, since you can only reasonably stick labels like 
"Good" on non-overlapping ranges, James wants to disallow overlaps. This 
somewhat limits the expressiveness of our datatyping mini-language.

IMHO, it is entirely reasonable to attach different r:rank @labels to 
different entries, even if they have been rated the same:

<r:rank label="Not a movie I want to watch more than once">1.5</r:rank>
<r:rank label="The popcorn was a lot better than the movie">1.5</r:rank>

In other words, I do not see the need for being able to mechanically 
look up a label for every value or range.

2.) How do we handle rank values which do not conform to r:schemes 
definitions.

I would simply consider them, r:scheme defining a datatype, as invalid. 
(Currently this is already done if a rank value is outside the bounds 
defined by its scheme's minimum and maximum.)

James, however, wants to introduce rounding rules: an invalid (as per 
r:scheme) rank value is rounded to the nearest valid rank value. Here, 
overlapping ranges make it again difficult for the implementer to 
determine what the nearest valid value actually is. So James want to 
disallow them.

Admitted, there are real-world examples where being able to use invalid 
rank values would be nice:

The local university, for example, internally uses grades like 1.19. On 
your diploma they only ever show up as 1.0, 1.3, 1.7, and so on. So why 
do we require the publisher to throw away some information, namely the 
exact grade? Because one rounding rule cannot deal with all the bizarre 
rounding schemes in use at schools and universities worldwide. (The 
above would be rounded to 1.0, for instance, although 1.3 would be the 
nearest valid value.) So, allowing rounding does not gain us that much. 
The receiver has to deal with it nevertheless.

3.) And, when it comes to rounding, the issue of @scale comes up. Do we 
really need it? I think not; it just complicates things.

So, those are the three main design issues we are currently facing (at 
least those I am aware of) -- and feedback from atom-syntax is really 
appreciated.

Best wishes,

Andreas Sewe

---

From: Lisa Dusseault <[email-masked]>
Date: Wed, 17 May 2006 18:18:57 -0700

For related work, you could look at the email spam filtering stuff  
from SIEVE: <http://www.ietf.org/internet-drafts/draft-ietf-sieve- 
spamtestbis-02.txt>

The similar problem is that many spam libraries already produce some  
kind of linear or similar scale of severity/likelihood rating for  
emails, much like existing services already provide their own scale  
of post rankings.  The approach SIEVE took, very roughly, was simply  
to tell implementors to find some way to map their implementation's  
ranking scheme to a canonical range of numerical values.  A SIEVE  
implementation might have one algorithm for converting SpamAssassin  
rankings to the canonical scale, and a different algorithm for some  
different library.

Since spam rankings are intended more for automated filters than for  
user display (though clearly the user is sometimes involved in  
evaluating the rankings, as when the user creates/edits a mail filter  
rule like  "file all email with a spam rating > 5 to spam folder"),  
the considerations of course could be different from the case of Atom  
post rankings.

Lisa

---

From: Andreas Sewe <[email-masked]>
Date: Fri, 19 May 2006 11:43:47 +0200

Lisa Dusseault wrote:
> For related work, you could look at the email spam filtering stuff  from 
> SIEVE: <http://www.ietf.org/internet-drafts/draft-ietf-sieve- 
> spamtestbis-02.txt>

Thanks for the pointer. I was aware of SIEVE's Filtering Extension but 
didn't file it mentally as related to the Atom Rank Extension.

> emails, much like existing services already provide their own scale  of 
> post rankings.  The approach SIEVE took, very roughly, was simply  to 
> tell implementors to find some way to map their implementation's  

Unfortunately this approach does not suit ranking entries very well; the 
only "canonical range" I can think of being a superset of every 
conceivable Ranking Scheme is xsd:decimal. Smaller sets simply won't do. 
(While loss of information might be acceptable when classifying spam, 
other ranking use cases, e.g., grades, are less tolerant to it.)

Now this would essentially mean dropping the r:scheme element 
altogether, leaving only r:rank, which was, IIRC, a simplification 
suggested by Robert Sayre some time ago.

But even when dropping r:scheme's capability to define a set of allowed 
values having an r:scheme-like element around would still be useful:

- It provides a single place to specify a scheme's @significance 
(ascending or descending). Otherwise each and every r:rank element needs 
to carry its own @significance -- which is especially pointless since 
@significance has not significance (no pun intended) for a single 
ranking value; it only ever makes sense for a set of values.

- Furthermore, a scheme can also have a @label attached (e.g. "Five 
Stars"), which might then be used in a UI, complementing r:rank's @label 
(e.g. "Good"). But this issue is really independent of the question 
whether r:scheme itself actually has the ability to restrict the 
rankings to {1, 2, 3, 4, 5} or not.

To summarize, droppping r:scheme's datatyping capabilities might be 
acceptable, but dropping the concepts of Ranking Scheme and Domain is 
not. I would, however, like to see datatyping being included as well -- 
iff we can come up with a solution which can describe all the common 
uses cases out there!

Andreas Sewe

---

From: James M Snell <[email-masked]>
Date: Fri, 19 May 2006 08:45:12 -0700

> didn't file it mentally as related to the Atom Rank Extension.

Yes, I had reviewed SIEVE's mechanism a while back.  In fact, one of the
use cases I had originally considered for feed rank is that the r:rank
element could be used by syndication intermediaries to express spam
rankings for feed entries...

e.g.

  <scheme name="tag:example.org,2006:spamtest"
          significance="ascending">
    <range minimum="0" maximum="100" step="1" />
  </scheme>

  <rank scheme="tag:example.org,2006:spamtest"
        label="Not Spam">0</rank>
  <rank scheme="tag:example.org,2006:spamtest"
        label="Might be spam">25</rank>
  <rank scheme="tag:example.org,2006:spamtest"
        label="Likely spam">50</rank>
  <rank scheme="tag:example.org,2006:spamtest"
        label="Spam">100</rank>

> other ranking use cases, e.g., grades, are less tolerant to it.)

Right.  One of the goals for this work is to allow for as broad of a
range of ranking scenarios as possible. No single c18n scheme is capable
of covering such a range.

> ranking value; it only ever makes sense for a set of values.

One point that I really do need to make clear in the draft is that ranks
can be processed relative to ranking schemes other than what is
identified in the rank element's scheme attribute.

For instance, going back to the spam example, it is entirely possible
that I, as a client, could define a variant of the spamtest ranking
scheme that is much more restrictive in range than the generic scheme
shown above.

  <scheme name="tag:example.com,2006:myspamtest"
          significance="ascending">
    <range minimum="0" maximum="50 step="1" />
  </scheme>

The set of entries produced by the processing the spamtest rankings
against this scheme would automatically exclude all entries with a
spamtest rank greater than 50.

> iff we can come up with a solution which can describe all the common

+1

- James