Investigate the 2006 Election Fraud at Democratic Underground Forum on Election Reform.

Annotations

We are planning on upgrading the NCSA server and clients to support group and public annotations. Personal annotation support might be affected as well. This document discusses some of the design and implementation issues.

There are still many inconsistencies and incomplete thoughts contained herein, mostly at the end.

Terminology

Annotations may be used for multiple purposes not all of which are suggested by the term "annotation". For now, we will call any of these uses an "annotation", which originally means "to note". Uses include responses to an article or another response in the sense of a conversation, additions to a sorted list of items, and evaluations of the worth or appropriateness of a document.

Instead of "annotations", I'd prefer to call them "notes". It's shorter and means about the same thing. There are several "notes" systems out there that this might be confused with, but the term is so generic, it is hard to see that there might be an intellectual property problem. PLATO had the first notes system. Lotus notes still lives on. The verb "note" is the same as the noun "note" whereas "annotate" and "annotation" are clumsy.

An "annotation server" is a server that returns annotations for a document, manages the data about the annotations, and possibly stores the annotations themselves. Personal annotations are readable and writable by a single person; a server is not (usually) needed. Group annotations are readable and writable by members of a group. Public annotations are readable and writable by anyone.

It is possible to distinguish between various combinations of the readable and writable capability for any set of users. "Readable" may or may not be "writable", and vice versa. Readable but not writable is called "read-only". Writable but not readable is called "write-only". Readable and writable is called "read-writeable", "read/write", or the qualifier is left out.

Requirements

The main requirements of an annotation system are that it be scalable and uniform. Other requirements: reliability, security, ... ?

Scalability

The annotation system must be scalable to the whole world. Group annotations are not so much of a problem for scalability because each group annotation server may restrict the size of the group and the documents which may be annotated. There is often a shared responsibility within groups to make the group work for all its members.

However, public annotations have a scalability problem for a number of reasons. The public is essentially a very large group that includes everyone. (We also should consider the public minus some individuals.) With more people, there is more that needs to be said and the shear volume of public annotations is the major threat to scalability. Part of the problem is where to store and serve all the public annotations. Possible solutions to this problem include distributing the processor and storage load and expiring old annotations.

For everyone to see public annotations, the annotations must be available in a public place. But this public place should not be a single public place for annotations of all documents, otherwise that place will be overloaded. The public place should also not be multiple public places without complete redundancy between them. Massive replication can be tricky to maintain as well as a waste of space - this is the Usenet paradigm.

Another scalability issue is access to the public annotations for any particular document. Out of trillions of documents and annotations, how is a client supposed to find an annotation server that can return all active public annotations of a particular document?

Uniformity

We wish to support group and public annotations with the same mechanism, at least regarding the annotation servers. This will similify the implementation and installation of annotation servers. Annotation servers should have similar features regarding how they specify which individuals or groups of individuals are allowed to create, modify, or destroy an annotation for a particular document or set of documents.

Clients will need to handle group and public annotations a little differently because where to get the annotations is specified in different ways. The user specifies which groups to use, but the public annotations must be found another way that is globally consistent for all people. How clients request annotations from servers and how servers return annotations should otherwise be the same for group and public annotations. Personal annotations could also be handled this way. Clients need to identify to users what kind of annotation each one is, but otherwise, they should be treated uniformly.

Design and Implementation

I mix design with implementation partly because I can never decide where to draw the line. Several design and implementation possibilities are also discussed, rather than one fixed one, at least until we decide which way to go. Additional requirements will come out of this process too.

Distributed

The solution we prefer for the scalability problem is to have each server of a document point to a single public annotation server for that document. This distributes the load to as many servers as required and also allows public annotation servers to be moved around as required. Each document server could be its own public annotation server as well, but this is not a requirement.

Annotations of all documents should not be concentrated on a small number of machines, as discussed above. But there is another way to distribute annotations that has the additional benefit of trivially allowing authors to continue to edit their annotations after they have been "submitted". This involves storing the body of an annotation on the author's server and just pointing to it from the annotation server with a URL (or URN). The author also assumes the cost of maintaining the storage and serving the annotation, except for the header information which should be stored by the annotation server.

Group annotations are distributed among all the group annotation servers. They will typically be close to the group that maintains them, such as an NCSA or MIT group. Annotations within a group annotation server need not be distributed, provided the group is not too large. If a group is large, caching can alleviate some of the burden on the server. If a group is very large, perhaps it should be public anyway. Groups could distribute annotations over several annotation servers, one for each set of documents.

The server tells the client where to get public annotations, whereas the group annotation servers are known only by the client.

Personal Annotations

Generally, personal annotations may be created by individuals for any documents since users are responsible for maintaining the space for the annotations and only they see the annotations.

Group Annotations

Group annotations are limited to those specific individuals or groups of individuals (e.g. everyone from a domain) designated to be in the group. A group server may restrict the set of documents that may be annotated, such as only documents at a set of servers or in a subdirectory of a server. Group members may be limited to only write annotations but not edit them, or not write them but only read them. Group annotation servers might remain unadvertized.

Users must tell their clients which annotation groups they are a member of so clients can request the annotations for a particular document. A user may be a member of several annotation groups, and for each one a separate group annotation server is specified. When a user starts up a client or changes the list of annotation groups, the client should query each group annotation server to see if the user is a member of the group. This may involve asking the user for a password. Thereafter, while the client session is still active, the user should not have to manually supply a password (the client should do it for him).

Nested groups might be useful. Several levels of groups within groups, or rather groups that include other groups as members.

Public Annotations

Public annotations are generally readable by all, otherwise they would not be public. A server might allow write-only annotations for a few individuals, or members of a group, or everyone except for some individuals.

Public annotation servers should probably restrict the set of documents they serve annotations for to avoid overload. The public annotation server for a document is known by each document (or known by its URC), and it tells the client when requested. So the existence of the public server is public knowledge.

Read-only/write-only/read-writable X public/group/personal

We can combine the read-only/write-only/read-writable dimension with the public/group/personal dimension in several ways, not all of which make sense. Each combination corresponds to an annotation server that servers annotations with the specific restrictions. Here is a list of most of them:

public read-writable - open to the world
public read-only, personal read-writable - serves annotations to the world from a single person.
public write-only, personal read-writable - serves annotations from the world to a single person.
public read-only, group read-writable - serves annotations to the world from a group.
public write-only, group read-writable - serves annotations from the world to a group.
group read-writable - open to a group, closed to the world.
group read-only, personal read-writable - serves annotations to a group from a person.
group write-only, personal read-writable - serves annotations from a group to a person.
personal read-writable - open to a person, closed to the world or groups.

Some conclusions about these combinations:

If the public is allowed to read and write annotations, there is no need to specify what individuals or groups may do with the annotations because they are already in the public.
Writable is always combined with readable unless it is the public or group writing to a group or person respectively. Everyone should be able to read annotations they wrote, no matter who it was. (Trouble is finding out who someone is to verify that they are allowed to read it.)
For public read-only, it doesnt make sense to have group or personal read-only or write-only, because groups and individuals have at least as much permission as the public.
Restrictions (i.e. read-only or write-only) apply to higher levels (group and public); lower levels (personal and group) are usually read-writable.
Annotation servers that are write-only by the public or a group and read-writable by a group or person, respectively, essentially describe a mailing list or personal mailbox.

There may be several public annotation servers for a document, each one with different combinations of restrictions. If there is any public aspect of an annotation server, either public read-only, write-only, or read-writable, the server of the document must know where the public annotation server is. That is, a public read-only but group read-writable annotation server is still partly public. We need to split the readable and writeable aspects of annotations.

A public annotation server must specify whether it is read-writable, read-only, or write-only. If it is read-only, it should name the group (or groups) or persons who can write annotations (everyone can read them).

Moderation of group or public annotations involves first submitting a proposed annotation to the moderator (or group of moderators) of the document. The submission is to a group or personal write-only annotation server readable by the moderators. The moderator may then post the submitted annotation for public reading to the public read-only server.

The sender and all receivers of a mail message should be able to read it as if it were an annotation of some document. These ad-hoc groups composed of the sender and receivers should be as easily managable as mailing lists.

Moderation of Public Annotations

Giving control of the public annotations for a document to the owner of the document means that the owner could have moderation control of the annotations. Furthermore, the administrator of the public annotation server may want to have some control over what annotations are permitted to exist.

Even if moderators try to be exceedingly fair, there will always be some subtle biases, and sometimes some obvious ones, or someone will claim there are. But to achieve completely unmoderated public annotations, something like the massive replication of usenet news must be used to distribute articles so no one has control. Even so, there are controls such as site administrators deciding which set of news groups to carry. And there are controls over how the news groups are organized and how that organization is changed.

If writers of annotations are not happy with the document owner or the annotation server administrator, they could go elsewhere or start up another annotation server, so I doubt this will be much of a problem. My hope is that because there are plenty of options, and plenty of people of all persuasions, there will be someone to sponser a document and public annotations with any desired range of restrictions. Furthermore, because many readers will prefer some restrictions and many readers will prefer some other restrictions, then people will generally gravitate to documents that meet their preferences. Most people will therefore be happy. A small minority will have trouble finding what they want, or creating it if they cannot find it.

Should there be more than one public annotation server for a document? The user usually does not care which they choose, unless different factions are all trying to make annotations to the same document. In that case, it would make more sense to just start a new document with its own public annotation server.

Annotations of Regions of Documents

Often the suggestion is made that annotations should be applicable to regions or parts of documents. The main problem with this idea is that documents change and position information becomes outdated as a result. This is particularly true if the annotation is suggesting a change to the document.

Identifying where these annotations apply is also a user interface challenge, particularlly with many overlapping regions. Such a display would tend to conflict with other ways of displaying annotations, i.e. in a tree structure or sorted by date. One possible solution to this is that the tree of annotations would be displayed as before, but selecting an annotation (in some way different from following the link to the annotation) would highlight the region it applies too. Each of the regions that have annotations could also (in addition) have some mark next to it so that the reader knows there is an annotation. Clicking on the mark would display the subtree (or forest) of annotations for that region.

Threaded

When a client displays a document with annotations, at the bottom or top of a document, the header information for each annotations should be displayed. For each annotation, any annotations to it should be listed under the heading for the annotation, and so on recursively. The result is a threaded tree display of all annotations under a document. Furthermore, when a particular annotation is selected to be displayed, just those annotations under it should be displayed similarly.

(Problem: When the user selects an annotation to display, should the client ask the annotation server again for annotations of that annotation? The client should already know which annotations those are from the higher level request for the tree of annotations, so it should not have to request that subtree again. But then how does the user request the lastest subtree?) Threaded display of annotations is particularly useful for group and public annotations, but also for personal annotations to support the mailbox application. Threaded display allows the reader to see the overall structure of the annotations, to determine which areas have inspired alot of responses, and to access deep parts of the tree more quickly.

A concern about threaded annotations is who maintains the whole tree, if anyone? If the original document maintains the tree, what happens when the body of an annotation is on another machine. In that case, it would seem like any annotation of that annotation should be maintained on that machine. But this need not be the case. For each document, whether it is an annotation or top-level, it could indicate the annotation server where its public annotations are served. This way, an annotation that is maintained on another machine (with only a URL pointing to it) could still refer back to the same machine as the annotation server of the document it is annotating. The pointer to the annotation server could then be easily changed to another machine to allow the subtree of this annotation to be split off. See divergence below. Users will want to avoid future display of subtrees of discussions they are not interested in. This preference can be stored in the client side database, and any new annotations under "killed" annotations would be hidden. But all intermediate annotations under killed annotations would have to be remembered in the database too. This should not happen that frequently since as soon as it does start to happen, the subtree probably belongs in its own base document. So maybe it is not worth supporting killed annotation subtrees. In fact, user preferences could be transmitted to the annotation servers so the owner may be informed of the need.

Trees vs Stars

An alternative to the tree structure is called the "star" structure. For each document, there is only one level of annotations - annotations of annotations are not possible. Stars are simpler for users in some ways because one can read through all unread annotations in a sequence. Since new annotations are always appended to the end of the list, one knows that readers are seeing the same thing, and thus the conversational style of communication is well modelled. A writer can assume more about what the reader has seen, and so there is less need to copy parts of articles for reference. Someone who wants to write an annotation typically waits before responding until they have reached the end of a list of annotations so they know they haven't missed anything. If you need to refer back to an earlier annotation, you can easily mention it rather than quoting it.

In a tree of annotations, reading through just the new annotations is not so easy. A tree models constant interruptions in the flow of a conversation. But a tree more correctly models the structure of information - since people respond directly to what they want rather than referring back to an earlier annotation. This also permits the tree to be moved around more easily when divergence occurs because the subject of subannotations is generally about the same subject as the parent.

The order in which new annotations in a tree are presented could be by date or by a top-to-bottom, preorder (depth-first) traversal of the tree. Either way, the context of annotations will jump around more than for a star structure. It will help to see the whole tree, with parents, of headers of new annotations so that one knows where one is jumping around, as in threaded news readers.

Multiple Parents

The parent of an annotation is the document that it is an annotation of. But it is often the case that an annotation is relevant to more than one document (or annotation), so each annotation could have possibly multiple parents. With multiple parents, the structure is a directed acyclic graph rather than a tree. This is more difficult to display.

The multiple parents of an annotation could be specified by allowing the user to enter a list of URLs of additional parents. But more generally, even after an annotation is written, the list of parents may need to be changed.

To prevent loops, each annotation must have older parents. This can be enforced when the annotation is created, or when the parent links are modified.

Multiple parents are a source of several problems. Each parent needs to know where all the current annotations under it are. If the parents of an annotation are within two different base articles (the typical case) then at least a reference to the annotation must be stored under each base article. This is essentially a distributed file system, and instead of implementing that, we should be making use of someone elses implementation. So until then, I'm going to nix the multiple parents idea.

Further justification for not supporting multiple parents is that if ever a topic is relevant to two or more topics, it is really a topic on its own, and so it belongs in its own base article. Until such an annotation is moved to a new base article, references to other possible parents may be made explicitly in the text while describing the relationship to the other parents.

Another issue to consider is that even if a topic relates to one or more other topics, that relationship is not always the same kind of parent/child relationship. Some children are subtopics, some are super topics, some are at the same level, etc. So overuse of the parent references could add to the confusion.

Divergence

Discussions often diverge from the original topic, and this should not be discouraged. Rather, when divergence occurs, the subtree that diverges could be hidden from the document it is contained in, and/or the parent list for the top of the diverging subtree should be changed (to a new parent, or orphan it to create a new top-level document).

Display of Annotation Trees

The only annotations you can see are personal ones, group readable ones for groups you are a member of, and public readable ones. Group or personal annotations of public annotations are reasonable, and all should be displayed in the same tree. Which kind of annotation each one is should be indicated in the headers.

Public readable annotations will be the norm, so they should be more abbreviated.

  "My annotation to the public"
	Daniel LaLiberte (liberte@ncsa.uiuc.edu)

If an annotation comes from a group you are a member of, the group should be identified.

  "My annotation to members of NCSA"
	group NCSA, Daniel LaLiberte (liberte@ncsa.uiuc.edu)

If a group annotation is from someone outside the group, this is important to see,

  "Annotation to you guys at NCSA"
	group NCSA, non-member: Joe Blow (joe@blow)

Personal annotations are readable only by you and you wrote them.

  "Annotation to myself"
	personal

A personal annotation to you may be written by someone else, though, and sent to you.

  "Annotation from someone else to dan"
	personal, Joe Blow (joe@blow)

The user must have a way to specify what kind of annotation they want to write. For each annotation server that a user has write access to, there should be some user interface control to support creation of that kind of annotation. The controls may be menus, or buttons displayed after the tree of annotations, or something else (e.g. on the dialog for entering the annotation). This is up to the browser and user to decide.

Personal annotations are usually possible. Group annotations are possible only if the user has specified a list of group annotation servers. A group annotation server might not allow annotations for the current document, so the user should be informed of this before they start to write an annotation. Public annotations are allowed if and only if the document provides the URN of a public writable annotation server.

Filtering and Preferences

Filtering of annotations is a process of modifying a list or tree of annotations to present what the user desires. Some examples: alternate sortings of annotations, remove annotations by specific authors, about specific subjects, old annotations, etc. Sorting may be by date, author, subject, threaded, or by other info that is available.

Annotation filtering might be done by the server of the annotations or by clients. Users of clients know how they want to do the filtering, so if the server does the filtering, these preferences must be passed to the server for each document and the server must resend the filtered annotations each time the preferences are changed. Therefore, it is better for the client to do the filtering if the preferences might be changed frequently. But if server-side filtering results in a much smaller number of annotations to send back to the client, this can be a large benefit. A good application of this is to send only the new annotations relative to a date.

For group annotations, the group annotation server could maintain a database of user preferences so they need not be sent each time the annotations for a document are requested. This is practical only if the number of members in the group is not too large. Public annotation servers could not hope to maintain such a database for the whole world.

What's New

Sending all the annotations for every document will get increasingly expensive as the number of annotations grows. Furthermore, users will not want to see the same old annotations. Very soon, people will only want to see new annotations. How will the new annotations be requested and returned? Finding out what is new or changed in a document or its annotations is a fundamental concern. One cannot hope to keep up with changes to vast numbers of documents without help from tools similar to newsreaders and the associated personal news database.

This can be implemented as a particular kind of filtering. It makes sense for this filtering to be done by the server to avoid sending lots of annotations that the client has already seen.

One needs to learn not only what is new for a single document, but what is new for a whole lot of documents. One should be able to start up a client-side program that automatically queries the servers of many documents to find out which ones have something new, and generate an HTML document (or several) with all of this information. The list of documents that a user would be interested in should not be too large, since otherwise there might be too much to keep up with. But nothing is lost (without automatic expiration) in the web so it should not matter if you cannot get back to a discussion for awhile (unless you wish to participate).

It is important to show headers of parent annotations even when they are not new to remind the reader of the context. The parent annotation headers need not be sent by servers if the client-side database remembers them from previous sessions. But each annotation header should include a reference to the parents annotation headers, as a URL or URN, so the client may piece together the whole tree.

Here is an algorthim for the server-side to build a tree of new annotations relative to some date, including all parent annotations.

Find the next new annotation (starting with the oldest). This is called the current annotation. Start a new tree with it.
Look up the first parent annotation of the current annotation that is under the same document (not an annotation under another document). If there is no such parent, then the current annotation does not belong here.
If the parent annotation has been visited already, then insert the subtree under that visited annotation after any other annotations at this level, else insert the parent annotation before the current annotation.
Repeat 2 and 3 using the parent annotation as the current annotation until the document is reached.
Move on to the next new leaf annotation.

This algorithm must be modified to account for annotations that the user does not want to see. First, the client has to send to the server the list of annotations he does not want to see. (I don't think we want to do this.) When looking for a parent of an annotation, if a hidden parent is found and there are no other parents at this level, then we need to back up to an earlier repetition and chose a different parent at that level, recursively. If we run out of alternatives, then the leaf annotation is hidden. This is expensive since we could avoid the whole traversal for annotations that happen to be under hidden annotations if we could start from only visible annotations to find new annotations under those. There is a top-down algorithm for this, but it is more expensive when there are more visible annotations that have no new annotations under them.

We could leave the hiding of new annotations under hidden annotations to the clients, but there is another problem. Even though an annotation might be hidden under one path, there might be another path to the annotation that is visible. To solve this problem, the new annotations should be listed under each parent, and each parent of each parent etc. This would be a large redundancy in the data sent to the client in the case that a large subtree has multiple parents.

Perhaps it would be better to not return a tree but only return the full URCs of new annotations. This way, the clients may put them together just as newsreaders do. If the clients store the parent URCs, they may put the tree together using the above.

Modifying after Submitting

The tree of annotations for a document needs to be editable both by the owner of the document and by the owners of each annotation. The body of each annotation also needs to be editable by the owners of the annotations.

Editing the tree of annotations consists of deleting items, moving them to other places (changing the parents, or orphaning them as new top-level documents) or hiding subannotations.

To support safe editing, authentication is required. Group annotation servers will already support authentication, so they may be extended to support editing fairly easily.

But for public annotations, it is simpler to avoid this issue for now and let annotations be write-once. It is no worse that usenet or mail, which people are well adapted to.

Authentication

My main concern is avoiding the situation where each document, or each annotation server has a different password for each user.

How are the limits on readability and writability declared and imposed? The server configuration should be able to restrict public annotation capability to documents in certain directories. The already available authentication methods should be used for this.

Annotations of documents not served by HTTP

Annotations of documents other than HTML served by HTTPD servers should be possible. Plain text is also displayed by browsers. Other document types are not guarenteed to be displayed by browsers and may be viewed with some external viewer. Even so, browsers could display annotations of such documents in a separate window. We are not going to be concerned about these now.

However, plain text and html returned by ftp and gopher (or other) servers may have personal annotations even now. And group annotations will not be a problem because they will be associated with URLs (or URNs) of documents. But public annotations, as I have been thinking of them, will only be associated with documents served by HTTPDs. Ah, but with URNs, the URC associated with the URN could say where the public annotation server is.

Annotations of CGI generated documents should also be possible. If the only identity of a document that an annotation server need be concerned about is its URL (or URN) then for equivalent URLs, the same annotations should be returned.

One related problem is that the same document may be retrieved by a couple different URLs, even for the same server. The mapping to annotations should really be based on URNs.

URNs and URCs

Using URNs, it does not matter where the URLs point. This makes it possible to support annotations of any kind of documents, or anything that has a URN. URNs make it more convenient to organize annotations in a hierarchy since the subtrees of the hierarchy may be moved. Annotation servers should have URNs too. An annotation server could be just a cgi script at a server, and this virtual document could therefore have a URN.

But how are URNs named so as to make sense forever? They may be named relative to the base document with an increaing numeric order over all annotations in the tree. This order will reflect the date. So the database of all annotations to a document, recursively, will be in one place, and once a URN is added to a document, it stays there forever. If the document itself moves, the URNs of annotations go with it; this is a relative-URN. The URN of the document itself is maintained higher up. If the document is deleted, the URNs of annotations under it are moved higher up since they should survive the document. But these annotations should eventually be deleted or copied elsewhere.

Until URNs and URN resolvers exist and browsers know how to look them up, URLs can be used. The problem, of course, is when a document moves around every link to it must be changed. So we can avoid more problems by putting the URL at the top level of all annotations for the document. We can still use URCs to store the meta information about annotations.

The URC for an annotation, or any document, could say where its public annotation server is. The owner of the document may change this pointer to branch off from the base document.

The URC for each annotation contains:

  Title: <the title string - with no HTML tags>
  URL: <location of the body - might be on a different server>
  Date: <when it was written/submitted>
  Reference: <URN of a parent of the annotation>
  Reference: <URN of another parent of the annotation>
  Annotations: <URN of public annotation server>
  Author: <who wrote the annotation - might be a group, might be anonymous>
  AuthorURL: <personal URL of the author>
  Email: <email address of the author>

We need a path from the URC to the place in the tree where the annotation is inserted. It might be inserted more than one place. These paths are dependent on the URLs of the parents of the annotation, so it would be best if they can be generated from the parents URLs rather than storing redundant data.

The URNs for each subannotation under an annotation go in the directory for that annotation. These could just be listed in a file.

How does the client know for a list of annotation servers which are read only, which are write only, and which are read-write? This affects how it interacts with the servers. It should not bother to ask servers for annotations if the server is write only, and it should not provide a button for adding annotations if it is read only. Also, the name of the group or users who receive write only annotations should be given since this needs to be diplayed to the user. Readable annotations should be identified by name too.

  Annotations: <URN of public read-writable server>, <name>
  ReadAnnotations: <URN of a publically read-only annotation server>, <name>
  ReadAnnotations: <URN of another publically read-only annotation server>, <name>
  WriteAnnotations: <URN of a publically write-only annotation server>, <name>

It seems very redundant to list the public read-only and write-only servers for each annotation. It should be possible to inherit servers from parent annotations. This would make it easier to change the annotation servers for a whole subtree of annotations. An override of the public read-writable annotation server would apply to that annotation and all subannotations. ReadAnnotations servers or WriteAnnotation Servers could be added to an annotation, and all subannotations. How could they be removed?

One problem with inheriting annotation servers from parent annotations is that clients would have to look up all the URCs for all parents to find out what their annotation servers are. Another problem is if an annotation has more than one parent; each might have different combinations of annotation servers.

A problem with each annotation having its own set of read and write annotations servers is that they would have to be consulted by clients to find all the subannotations under each annotation. This would be alot more communication between clients and annotation servers.

Another minor problem is how annotation writers specify the set of read and write annotation servers for their annotation.

I want each annotation to be a document on its own, to the extent that annotations for that annotation are found in the same way as for the top level document. This means that documents have to be accessed via their URCs too since this is where the public annotation servers are specified.

The URCs for each document could have the same root name as for the document with a suffix of ".urc".

Annotation Protocol

We are defining a higher-level protocol on top of HTTP for the purpose of communicating between servers and clients the availability annotations, the URC-like information about each annotation, and the text of the annotations themselves. The protocol must also support the creation, editing, and destruction of annotations.

Getting Annotations

A client first requests a document from a server, and the server responds with the document and a header indicating where the public annotation servers are. Clients who don't know about public annotations will simply not see this header. This dialog looks like:

whatever...

The client then requests each public annotation server to return the URC-like information about each public annotation of the document. Or the client may request only annotations created (or modified?) after some date, the last date the annotations were requested perhaps. The public annotation servers return this information using some compressed notation, rather than sending whole URCs. (There are some packed encoding standards here that we should adopt.) Here is what this dialog looks like:

whatever...

The client also requests all group annotation servers that the user has specified to return group annotations of the document, perhaps with a date. The same kind of URC-like info is returned:

whatever...

If a group or public annotation server is a machine local to the client, the client may use a more direct connection to the server, or to its files.

The client constructs the tree of annotations from this information and enables controls that allow the user to add or edit annotations for those annotation servers that apply.

Submitting and Editing Annotations

The protocol for submitting annotations is as follows: The user requests to add an annotation for a particular document or an annotation. The server checks that the user is allowed to do so, and then provides a form for entering the annotation (like HyperNews). The user submits the annotation (or not) and the form uses method POST to send the annotation to the server. The server responds with a temporary document that would be the annotation, and another form to accept and finalize the annotation. The user has some short amount of time (10 minutes) to accept, otherwise the annotation is thrown away.

Editing is similar but the form is filled out with the information that had been entered previously. Before editing can start, authentication is required. Group annotation servers can authenticate the same way as for creating new annotations, but there may be need for individual passwords as well as group passwords. Public annotation servers have a problem because anyone can create a new annotation, but only the author of an annotation should be allowed to edit it.

Restructuring the annotation tree is a special case of editing annotations. Only the parent links of annotations is changed. This may be used to remove the last parent link from an annotation, so it becomes a base document. Or it may be used to add a parent link to an annotation so it appears in more than one place in the tree, or as an annotation of more than one document. Restructuring relative to a particular annotation should be allowed by the owner of the annotation or by the owner of any of its parents, recursively up to the base document. Orphaned annotations should be moved up to the top level of the base document; there they may stay until they are reclaimed or deleted.

What does restructuring do to finding out what is new or changed?

Deleting Annotation

Annotations may be deleted by the author or by the owner of the base document. The protocol is that a DELETE message is sent with the URL of the annotation to delete.

Personal Databases

The client side will have a database of when each document was last read by the user of the client. The client may send this date to the annotation server so that headers of any newer annotations to the document (or to its annotations) can be returned. The user may not read all these annotations, but the client side database could record the headers of all annotations seen.

Instead of headers or URCs, just URNs could be stored. But the URC data should be displayed to the user, so the annotation server (or some other URN->URC service) should be able to provide the URC given the URN of an annotation.

To build the tree of annotations, for each annotation, the parent annotations are needed. So the client should either store the parent annotation URCs or be able to ask for them.

This might be a huge database, containing not only URNs of documents read, and perhaps URCs of them too, but also URNs seen but not read. Parts of this database may be pruned out automatically based on age or when the user decides that everything under a certain node should be forgotten because they dont plan to return. But plans change.

As the web grows ever huger, people will be able to view less and less of the whole thing. A person's database of known pointers will reflect their view of the web. People working on similar things will have similar databases, or portions of databases will intersect. These personal databases may be used as personal caches of portions of the web that the owners are interested in following. But they are more than that, and they should not be flushed out as normal caches are. URCs may be flushed out though, as long as the URN is left to be able to retrieve the URC.

This personal database is also called a "cool list".

Naive Clients

It might be nice to allow servers to automatically send the annotations to clients that do not know how to ask for them. To work right, this needs to happen given the same URL as for a client that does know how to ask for the annotations. This means that the client has to ask for the document in a different, but hidden, way than it normally does. The server would have to be changed to lookup and append all public annotations as HTML text unless it is told not to do so. When it is told to not do so, the client can ask again for the annotations if it wants them.

If public annotations cannot be turned off by clients that don't know how to do so, this might have a bad consequence of discouraging use of public annotations. Currently, one cannot turn off personal annotations, but there are rarely any and usually none. Annotations are an important part of the life of the document, so I would be surprised if readers would not want to see them. If an author is concerned that the quality of annotations is discouraging readers, then they should probably get busy and edit the annotation tree to improve the quality. This is true even if all clients could turn off annotations. So the conclusion is that automatically displaying all annotations is better than not doing so.

One way we can implement this is to use the ACCEPTS MIME types variable that is passed in by clients. Clients who know about public annotations would indicate this by including a x-www-annotate MIME type. Servers who see that and support public annotations would not automatically append the public annotations but would send back a header that tells the client where to get the annotations. Clients would then request the annotations and filter them as desired. Servers who do not see the x-www-annotate MIME type could assume that the client is not aware of annotations and could therefore automatically append all public annotations to the document. One additional benefit of this scheme is that if clients really do not want to see public annotations, but are still not annotation-aware, they could do so by sending the x-www-anotate type.

Storage

Problems: moving them, changing viewing constraints, multiple parents.

Where are annotations stored and organized? A special directory could be designated by the server configuration to hold all annotations. Since annotations are retrieved via a CGI script, the association between URLs and the annotations of them should be fairly straightforward so that the script need not look up any configuration information. What can the server pass into the environment of the CGI script?

Preferrably, all annotations for a document should be in one directory so they may be moved around more easily. Furthermore, annotations of annotations could be in subdirectories. (This is how it is done in HyperNews.)

Documents may be distributed widely in a filesystem, and those that are generated have no particular location. The URL (or URN) itself must be used to map to the location of the annotations. There could be a file with URLs and corresponding directory names. This file could be read in by the server when it is started up, but that is not often enough since it needs to change dynamically. When a document is created, a new entry must be made for that file. Actually, it is only need when annotations are added to the document.

Perhaps the directory for annotations should be specified by the file itself. In the header for the file, a META tag could indicate where public annotations are. The author of a document could add this information to the header, or if it is not there, perhaps annotations are not allowed.

The specification of where the annotations are for a document could be a full path to a directory. This directory would have to be in a place where the server is already allowed to read documents. It would have to be writable by the server, if the annotations are writable at all. The author of the document should also have write access, unless the server provides all the editing services.

How does the author choose the name of the directory for annotations? Can the author be free to do this? Probably not for all sites. The author can arrange with the server administrator to pick a name. The names of subdirectories for subannotations could, of course, be computed by the server.

If annotations, or their headers were in one fixed place, per document, then a hierarchical file structure (even with links between nodes to form a DAG) could still be used to represent the whole tree of annotations for a document. The nodes in the tree structure would reference the fixed annotation files. The tree structure could be rearranged arbitrarily and the annotation files would not need to be moved. The annotation file could have the list of all parents, and each parent would be some annotation in some tree structure. If a parent is in another document, then where the annotation really is is arbitrary. One of the parents could be chosen as the home.

If only a list of annotations at the top level for a document were returned to a client then the only way for the client to see the whole tree would be to request the annotation list for each annotation, recursively. This would be alot more traffic on the net than if all the annotations were sent in the first place.

Maybe wrong:

A single annotation server might serve annotations both for the public and several groups. So within each directory for the servers that the annotations server serves, there should be subdirectories for public and each group that is served from that server. The name of a group may not be "public". Alternatively, the top-level directory of annotations could be divided into public and each group, with servers of each category under those directories. Probably the first is better since it keeps servers together.

What is the name space of group servers? They have unique URNs but what about the names of groups describe above? They may be arbitrary names picked by the user.

The structure of annotations on a server starts at the directory containing all annotations. Within that directory are subdirectories, one for each server that it serves annotations for, named for the URNs of the servers. Within each of those server directories are all the URNs of the documents that it serves annotations for, one directory for each. Within those directories for each document are several things. The URC for each annotation in the tree, the body of each annotation, and a directory for each annotation that has subannotations. Within those subannotation directories are subdirectories for each subannotation that also has subannotations, etc. Also in each directory, from the document directory down, is a pregenerated list of annotation headers at that level, with inclusion of lower level lists from each subdirectory. This is used when the whole tree is to be returned to annotations naive browsers.

Permissions for who can add new directories for servers, add new directories for documents for each server, and read-writable annotations for each document are stored in the directories for each of these things. Who is specified as either public, a list of groups, and/or a list of individuals.

Hierarchical Storage?

Should annotations be organized in a hierarchical file system at all? There are some problems with this having to do with moving things around.

Moving an annotation out completely from one document to another is a problem. First, to move it safely, the new parent should be linked in before the old parent is removed. A placeholder should probably be displayed in the old parent, at least for awhile. The annotation body needs to be copied to the new annotation server - this is true anytime the parent whose annotation server holds the annotation body is removed as a parent. An annotation server might not want to wait until the annotation is copied before it removes it, especially if it is a large inappropriate document.

When an annotation is removed from a server, any annotations to it should follow. Copying of subannotations should probably happen when the parent is copied. When an annotation moves, its URN stays the same. So subannotations need not have their parent pointers changed when the parent is moved. The URLs for all the subannotations recursively must be changed though, just as for the parent.

Since references to an annotation are currently hard coded in a URL, when the annotation is moved, references need to be changed. It would be nice to support essentially the same thing as URNs now via an indirection. Headers for all annotations for a document would live in the same place, and URLs would point to those headers (same as in HyperNews). When an annotation is moved, the information in the annotation header would simply point to the new location. The list of which annotations apply to a document would be stored separately. But this same scheme applies whether or not the headers are stored hierarchically since the headers always live where they are first born no matter where they are moved. If an annotation is moved more than once, as will happen with frequent reorganizations, following the indirections can take some time. The original site for an annotation might disappear altogether. We really need URNs for each annotation. Another problem with hierarchical storage occurs when an annotation has more than one parent. The parents need not be for the same document or on the same server. Any particular hierarchy is irrelevant in this case. Why does something have more than one parent anyway? The parent is really just an arbitrary reference to another document that perhaps inspired the annotation, and the reference from the parent to the offspring is the corresponding back link. HyperNews has two representations of responses. One is the hierarchical file structure containing each individual response header, and the bodies as well. The other is a pregenerated list of responses in each directory, each including the response list of any subdirectories. The annotations tree will be a little different. A pregenerated list of annotations will be useful for first time presentation of a document, but not useful for frequent revisits to get what is new. Revisits may occur more frequently than first time visits. There is also the problem of revisits using naive browsers - they can only receive the whole tree. This should happen less often as more browsers are improved.

Related Ideas Independent of Annotations

Client-side Editing of Text

A neat thing to do. Not essential though.

Outline Eliding/Expanding

The tree structure of threaded annotations suggests the need for an outline editor that allows the user to elide or expand portions of the tree. This same capability applies to other tree structures of HTML documents, such as headings and nested lists. So nothing new is required for annotations.

Display of Annotations in a Separate Window

A general feature applicable to all kinds of links is that selecting a link with appropriate modifier should display the document in another window that is not a new window but the same other window as last time. This is similar to newsreaders, for example, that let the user select an article by title and it is displayed in another window. Selecting another article displays it in that same window.

There are some other related window-system ideas. One is to allow a document to be split between separate tiled windows. This would allow you to display the tree of annotations in a separate window. Another idea is to allow several documents to be automatically embedded in a document. This would allow the contents of a subtree of annotations to be displayed in one document.