In reference to the patent: US6735595

This patent appears to describe various implementations of what is usually known in the computer science community as an order statistic tree. In particular, the two pseudocode algorithms in the patent document - "ORDINAL" and "FINDKEY" - are fairly straightforward adaptations of "OS-RANK" and "OS-SELECT" from [3] (section 14.1). Many papers from before the issue of this patent (for instance, [5], [6] and [7]) reference the first edition of that text [4], published in 1990, when describing their use of order-statistic trees.

From reading the patent, I can find nothing within the claims that goes significantly beyond a normal understanding of order-statistic trees, such as may be obtained by reading [4]. The patent's descriptions are couched mainly in the language of B-trees and digital (i.e. prefix) trees, rather than the binary trees described in [4], but it is clear that the core idea (and supposed innovation) - that of storing an item count at the head of every subtree and using it to rank/unrank keys - is invariant to the type of tree. Am I right in thinking that this constitutes prior art for this patent?

[3]: Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

[4]: Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. MIT Electrical Engineering and Computer Science Series. MIT Press and McGraw-Hill, Cambridge, Massachusetts and New York, New York, 1990.

[5]: http://www.cs.tut.fi/~ava/NORSIG96.pdf - Valmari, Antti. "Optimality results for median computation." Proceedings of Nordic Signal Processing Symposium. 1996.

[6]: http://www.cs.umn.edu/tech_reports_upload/1993/HidingJitter.pdf - Frankowski, Daniel, and John Riedl. Hiding jitter in an audio stream. Technical Report No. TR-93-50, Department of Computer Science, University of Minnesota, 1993.

[7]: http://www.textfiles.com/bitsavers/pdf/mit/lcs/tr/MIT-LCS-TR-638.pdf - Ernst, Michael D. Serializing parallel programs by removing redundant computation. MS thesis. Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1992.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.