Patents on Algorithms & Data Structures (with examples)

We have presented several issued patents on Algorithms & Data Structures such as Merkle Tree, Luhn algorithm, PageRank algorithm and much more. We have explained which algorithms can be patented in general.

Table of content:

  1. Can you patent an Algorithm?
  2. Examples of Patents on Algorithms & Data Structures

We will dive deeper into this so that you will get a strong idea of which invention can you patent.

Can you patent an Algorithm?

Yes, you can patent an particular application of an Algorithm or Data Structure. To be clear, you cannot just patent an algorithm or data structure without specifying the application.

For example, we can a Data Structure called Binary Tree. There are two cases:

  • We cannot patent Binary Tree as an Invention.

  • We can patent a specific application of Binary Tree. For example, Binary Tree is used in an Excel sheet. In this, you need to specific the operations of the Binary Tree that you are using in the Excel sheet that you want to patent. You can patent this specific application but not a general data structure or application.

Examples of Patents on Algorithms & Data Structures

Some examples of Patents on Algorithms and Data Structures are:

  • Merkle Tree (Patented in 1979)
  • Luhn algorithm (Patented in 1960)
  • Deflate file format (Patented in 1991)
  • PageRank algorithm (Patented in 1999)
  • RSA algorithm (Patented in 1983)
  • Karmarkar's algorithm (Patented in 1985)
  • Lempel Ziv Welch (LZW) lossless data compression (Patented in 1985)
  • Bresenham's line algorithm (Patented in 1980s)
  • PredPol (Patented in 2000)

We have explored the detailed of the above patented ideas in more depth.

  • Merkle Tree (Patented in 1979)

Merkle Tree, a Tree based Data Structure. This was patented by its Inventor, Ralph Merkle in 1979 as "A method of providing digital signatures".

The patent covered the idea of hash tree in general which was introduced by Ralph Merkle. Merkle Tree is a specific Hash Tree.

A variant of Merkle Tree is used in Blockchain. As patents are valid for 20 years, the patent on Merkle Tree was over in 1999.

  • Luhn algorithm (Patented in 1960)

Luhn algorithm is an algorithm to verify a number. It was patented in 23rd August 1960 (filed in 1954).

Today, this algorithm is in wide use as a method to verify if number are mistyped or are incorrect numbers. It is used to validate credit card numbers, IMEI numbers, Canadian Social Insurance Numbers and much more.

  • Deflate file format (Patented in 1991)

Deflate is a compressed file format that is a combination of LZSS and Huffman Coding. It was used in PKZIP archiving tool. It was patented by Phillip Katz in 1991 with the title "String Searcher and Compressor Using Same"

The patent did not cover all ways in which in could be implemented and this resulted in a loophole. Using this loophole, Deflate became widely used in GZIP, ZIP and PNG files.

  • PageRank algorithm (Patented in 1999)

PageRank algorithm is a well known algorithm as the algorithm that powered Google Search Engine. Very few know that PageRank is a patented algorithm. It was patented in 1999 and was assigned to Stanford University as Larry Page (Inventor) was pursuing PhD at that time.

Google brough Licensing rights from Stanford University for the use of the Algorithm which it sold for 338 Million dollars in 2005.

The patenting rights on PageRank is over as of 2019.

  • RSA algorithm (Patented in 1983)

RSA algorithm is a well known algorithm in cyptosystem and is used for secure transmission of data.

It was patented in 1983 by MIT with the title "Cryptographic communications system and method" and was publicly described and filed in 1977.

In 1973, another researcher Clifford Cocks found the same algorithm in a private setting. It was disclosed later in 1997. The patent rights were over in 2000.

  • Karmarkar's algorithm (Patented in 1985)

Karmarkar's algorithm was the first polynomial time algorithm for solving linear programming problems. It was formulated by Narendra Karmarkar when he was a researcher at IBM, presented it at Stanford University and later, joined AT&T.

At AT&T, the power of the algorithm in practical problem was realized. Karmarkar's algorithm was patented in 1985 by AT&T (Employer of Karmarkar). It was a major trigger to the revolt of software patents in 1980s.

The computer system designed to run this algorithm was priced at $8.9M and its first customer was Pentagon.

The patent was over in 2006 and can be used by anyone currently.

  • Lempel Ziv Welch (LZW) lossless data compression (Patented in 1985)

Lempel Ziv Welch (LZW) lossless data compression is a compression algorithm that is used in GIF format. It was patented in 1985 by the company Unisys.

The patent rights were not enforced but later, royalties were collected. It reduced the popularity of GIF at that time provided an alternative (PNG) was ready.

  • Bresenham's line algorithm (Patented in 1980s)

Bresenham's line algorithm is a algorithm to draw a straight line between two points in a N-dimensional raster (graphic screen). This was a run length algorithm and it was modified by Bresenham to design a Run Slice algorithm.

Variants of this algorithm have been described in several patents with titles:

  • Method and apparatus to draw line slices during calculation
  • Run slice line draw engine with non-linear scaling capabilities
  • Run slice line draw engine with stretching capabilities
  • Method and apparatus for displaying computer graphics data stored in a compressed format with an efficient color indexing system
  • Method and apparatus for displaying a parametric curve on a video display

and much more.

  • PredPol (Patented in 2000)

PredPol, a company has patented an algorithm to predict earthquake aftershocks in 2000. Applications of the variants of PredPol algorithm include Police Patroling and is widely used by the company.

With this article at OpenGenus, you must have a strong idea of Algorithms and Data Structures that are patented. Enjoy.