Patent US 7539685 B2 concerns the normalization of btree index keys in a database management system.

There is no citation of the 1977 paper "An Encoding Method for Multifield Sorting and Indexing" by Blasgen, Casey and Eswaran in the subject issued patent from Microsoft.

However, the citation seems relevant and could be very convincingly argued to be prior art. As far as I can tell, the only difference is that the 1977 paper doesn't describe how the same technique can be used with a variety of binary types such that they can also be concatenated, but this is so obvious as to be redundant.

Further, the omission of a citation of that paper is glaring, because it was produced by a group of researchers working on the seminal IBM System R RDBMS, which is widely influential. The influence of that system on Microsoft SQL server (which the patent references - it's from Microsoft research) is widely acknowledged and undeniable.

The first claim of '685 is:

  1. A system for index key normalization in a database comprising a processor adapted for:

    • (a) Selecting an index key for normalization, wherein the index key contains more than one column, and wherein each column of the index key has a type, and wherein the index key contains more than one type of column type;

    • (b) Tracking column normalization, wherein tracking column normalization comprises: creating a tracking variable, wherein the tracking variable has a maximum value determined by a number of columns in the index key; incrementing the tracking variable value each time one of the columns of the index key is normalized; and

    • Determining that normalization of the index key is complete when the maximum value of the tracking variable value is reached;

    • generating a normalized value for the index key, wherein generating the normalized value for the index key comprises:

      • determining a column type for a column; and determining an associated transformative function relating to the type of the column; and applying the associated transformative function to a value of the column resulting in the normalized column value;
      • generating a marker corresponding to the column, wherein the marker acts as a header for the normalized column value;
      • storing a normalized index key value, wherein the normalized index key value is updated for each column value that is normalized; and
      • appending the marker and the normalized column value to a previously generated marker and normalized column value.

Does anyone have any advice on having the patent invalidated? What is involved, what does it cost?


  • I found a paper by a Microsoft researcher in 2001 called "The evolution of effective B-tree: page organization and techniques: a personal account" one of the papers it cites is the Blasgen, Casey and Eswaran paper. The author is not the inventor of the patent in question. The paper is posted at Microsoft research.microsoft.com/pubs/77583/p64-lomet.pdf
    – George White
    Jan 31, 2014 at 8:31
  • Thank you. It seems the late Gennady Antoshenkov, referenced in that paper (who died years prior to the patent application, and never worked for Microsoft or MS research) addressed different approaches to encoding to preserve existing sort order, as outlined here: citeseerx.ist.psu.edu/viewdoc/… .
    – John Moran
    Feb 1, 2014 at 9:37

1 Answer 1


Getting this or any issued U.S. patent's claims narrowed or all of its claims made null can be done in one of two proceedings at the USPTO called an ex parte reexamination or an Inter Parte Review. The least expensive is the ex parte reexam. The filing fee is a minimum of $6000 for an ex parte petition. That is just the filing fee, you will also want professional help in putting it together. With this you get to throw your rock and then have no further involvement.

Inter Parte Review is a much bigger deal. It is a quasi-judical proceeding before the appeals board within the USPTO that you participate in. The min. fee is a non-refundable $9K + another $14K that you do get back if the boards decides not to take on the case at all. And those amounts are small in comparison to your legal bill.

To literally be invalidated takes a court action and you would only be in court if the patentee was suing you.

  • So, I'll ask what may seem like a naive question: since I don't really have much of an economic interest in invalidating this patent, is there some limited way in which I can attempt to "morally" invalidate it? For example, can I suggest it for inclusion in a publicly maintained list of dubious patents? It does strike me that the patent is of very low quality.
    – John Moran
    Feb 1, 2014 at 9:40
  • I guess this site provides that function in that any google search in the future of that patent number is likely to bring this up. The reference you site might otherwise be hard to find. Separately, in a quick look at the prosecution history, this went through zmany office actions and the claims were narrowed significantly in the process. Claim 1 went from 6 lines to more then a page. And there are multiple independent claims. One might be invalidated but leave the rest standing.
    – George White
    Feb 1, 2014 at 22:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .