US Patent 7952499 Random access in run-length encoded structures

Patent 7952499 was granted and assigned to Microsoft on May, 2011 by the United States Patent and Trademark Office.

Overview Structured Data Issues Contributors Activity

Is a

Patent

Patent attributes

Current Assignee

Microsoft

Patent Jurisdiction

United States Patent and Trademark Office

Patent Number

7952499

Date of Patent

May 31, 2011

Patent Application Number

12696226

Date Filed

January 29, 2010

Patent Primary Examiner

‌

Peguy JeanPierre

Patent abstract

Random access to run-length encoded data values is provided. A target value is identified by a logical index into a structure of run-length-encoded values. To access the value, a bookmark is selected based on the logical index, on a maximum logical index of the bookmark, and on a specified bookmark distance. An initial run in the structure is located, based on the selected bookmark. A final run is chosen, at most one bookmark distance from the initial run. The target value is the value of the final run. Efficiency heuristics are used when generating bookmarks or creating the structure of run-length-encoded values.