# US 7,612,695 B2 · Determination of compression state information for use in interactive compression > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,612,695 B2 - Document ID: US7612695B2 - Status: Granted - Kind: B2 - Application number: 12/131,397 - Filed: 2008-06-02 - Published: 2008-12-04 - Granted: 2009-11-03 - Earliest claimed: 2007-06-01 - Assignees: Research In Motion Limited - Inventors: En-Hui Yang; Ajit Singh; Salmaan Ahmed; David P. Sze - Web page: https://patentgrep.com/patent/US7612695B2 ## CPC - G06F 16/1744: {using compression, e.g. sparse files} - H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction - H04L 69/04: Protocols for data compression, e.g. ROHC - H04W 28/06: Optimizing {the usage of the radio link}, e.g. header compression, information sizing {, discarding information (system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72) ## Abstract The invention is directed at a method and apparatus for determining compression state information which is to be used in the compression of data being transmitted between two communicating parties. The method of determining the compression state information for use in interactively compressing data comprises the steps parsing the data to determine a hierarchical data structure of the data; traversing a shared hierarchical node index to determine common compression state information entries between the hierarchical data structure and the hierarchical node index; and selecting at least one of the common compression state information entries for use in compressing the data. ## Claims ### Claim 1 A method of determining side information, including compression state information, for use in interactive compression of data, comprising steps of: parsing an identification of the data; traversing a side information database, including compression state information for use in interactive compression of data, containing side information identifiers shared by communicating parties in a communication to identify elements of the parsed identification known to both communicating parties; and selecting at least one unit of side information based on the identified elements for use in compressing the data. ### Claim 2 (depends on 1) The method of claim 1, wherein parsing the identification of the data comprises parsing a Universal Resource Locator (URL) identifying the requested data. ### Claim 3 (depends on 1) The method of claim 1, wherein parsing the identification of the data comprises parsing an email identification string. ### Claim 4 (depends on 1) The method of claim 1, wherein traversing the side information database comprises traversing a hierarchical node index. ### Claim 5 (depends on 4) The method of claim 4, wherein the hierarchical node index is stored in a mobile communications device. ### Claim 6 (depends on 4) The method of claim 4, wherein the hierarchical node index is stored in a server. ### Claim 7 (depends on 4) The method of claim 4, wherein the hierarchical node index is stored in a shared resource accessible to a mobile communications device and to a server. ### Claim 8 (depends on 4) The method of claim 4, wherein the side information identifiers are represented as nodes in the hierarchical node index. ### Claim 9 (depends on 8) The method of claim 8, wherein selecting the at least one unit of side information comprises applying a rule based on a minimum distance of a node to a closest common ancestor. ### Claim 10 (depends on 9) The method of claim 9, wherein selecting the at least one unit of side information comprises selecting the most recently used leaf node from a plurality of leaf nodes associated with the identified elements. ### Claim 11 (depends on 10) The method of claim 10, wherein each of the plurality of leaf nodes is provided with a unique identifier. ### Claim 12 (depends on 11) The method of claim 11, wherein the unique identifier is a hash of previously compressed data. ### Claim 13 (depends on 8) The method of claim 8, wherein selecting the at least one unit of side information comprises applying a rule based on a minimum number of common nodes. ### Claim 14 (depends on 4) The method of claim 4, wherein selecting the at least one unit of side information comprises selecting at least one leaf node of the hierarchical node index. ### Claim 15 (depends on 4) The method of claim 4, wherein selecting the at least one unit of side information comprises selecting an intermediate node of the hierarchical node index. ### Claim 16 (depends on 1) The method of claim 1, wherein selecting the at least one unit of side information comprises applying a pre-determined rule. ### Claim 17 (depends on 16) The method of claim 16, wherein the predetermined rule is based on a minimum number of common elements. ### Claim 18 (depends on 16) The method of claim 16, wherein the predetermined rule is based on a maximum number of unmatched elements. ### Claim 19 A mobile communication device, comprising: a processor to traverse a side information database, including compression state information for use in interactive compression of data, containing side information identifiers shared by communicating parties in a communication, to identify elements of the parsed identification known to both communicating parties, and to select at least one unit of side information based on the identified elements; and a decoder to use the side information to assist in the interactive decompression of data transmitted in the communication. ### Claim 20 (depends on 19) The mobile communication device of claim 19, wherein the side information identifiers are stored as a hierarchical node index. ### Claim 21 (depends on 20) The mobile communication device of claim 20, wherein the identified elements are common nodes in the hierarchical node index. ### Claim 22 A server for use in interactive compression of data, comprising: a processor to traverse a side information database, including compression state information for use in interactive compression of data, containing side information identifiers shared by communicating parties in a communication, to identify elements of the parsed identification known to both the communicating parties, and to select at least one unit of side information based on the identified elements; and an encoder to use the side information to assist in the interactive compression of data transmitted in the communication. ### Claim 23 (depends on 22) The server of claim 22, wherein the side information identifiers are stored as a hierarchical node index. ### Claim 24 (depends on 23) The server of claim 23, wherein the identified elements are common nodes in the hierarchical node index.