Facilitating memory constrained client devices by employing deck reduction techniques

• US 6,523,062 B1
• Filed: 06/29/1999
• Issued: 02/18/2003
• Est. Priority Date: 06/29/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bridgman, Thomas E., Lection, David B., Wesley, Ajamu A.
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): NGUYEN, THU HA T
• Application Number:
  US09/342,884
• Time in Patent Office: 1,330 Days
• Field of Search: 709/230, 709/232, 709/238, 709/201, 709/203
• US Class Current: 709/203
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/04 specially adapted for terminals or networks with limited capabilities; specially adapted for terminal portability
• CPC Class Codes: H04L 67/565 Conversion or adaptation of application format or content adding application control or application functional data H04L67/561
• CPC Class Codes: H04L 67/5651 Reducing the amount or size of exchanged application data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method, system, and computer program product for facilitating network delivery of Wireless Markup Language (WML) decks (or decks in similar notations) to memory-constrained client devices such as Wireless Application Protocol (WAP) devices, by applying a novel deck-reduction process to the decks, such that the decks are reduced by fragmentation into new decks of a manageable size. No loss of deck content occurs in this fragmentation process. The cards of the original deck are grouped into new sub-decks, where each sub-deck is no larger than a particular maximum deck size. When defining the new sub-decks, card adjacency is used along with commonality of event bindings and text strings, in order to regroup the cards in such a way as to reduce the size of the resulting sub-decks while minimizing the number of remote references generated.

Claims

1. In a computing environment capable of having a connection to a network, a computer program product for facilitating network delivery of documents encoded as decks to client devices, said computer program product residing on a storage medium readable by a computer system in said environment and comprising:

computer-readable program code means for fragmenting a deck into a plurality of sub-decks if said deck has a deck size larger than a target size, wherein each of said sub-decks then has a sub-deck size smaller than said target size and wherein said fragmenting does not discard deck content, further comprising;

computer-readable program code means for decoupling a plurality of cards from said deck;

computer-readable program code means for building a card adjacency graph, said graph comprising a plurality of nodes and links between selected ones of said nodes, wherein each of said nodes represents a card existing in or referenced from said deck and wherein each of said links represents an adjacency relationship between a pair of cards corresponding to a pair of said selected nodes;

computer-readable program code means for applying a card localization process to said card adjacency graph, further comprising computer-readable program code means for creating a set of distance tuples from said card adjacency graph; and

computer-readable program code means for aggregating said decoupled cards into said sub-decks using said set of distance tuples; and

computer-readable program code means for rebinding said sub-decks to one another.

2. The computer program product for facilitating network delivery of documents encoded as decks according to claim 1, wherein each of said tuples pertains to a selected one of said links and is comprised of a numeric indicator of event binding commonality and a variable substitution factor.

3. The computer program product for facilitating network delivery of documents encoded as decks according to claim 1, further comprising:

computer-readable program code means for receiving a request for said deck from a client device prior to said fragmenting; and

computer-readable program code means for forwarding a primary one of said sub-decks to said client device after said rebinding.

4. The computer program product for facilitating network delivery of documents encoded as decks according to claim 1, further comprising computer-readable program code means for fragmenting zero or more oversized cards from a plurality of cards in said deck, wherein said oversized cards are characterized by having a card size larger than a target card size.

5. The computer program product for facilitating network delivery of documents encoded as decks according to claim 1, further comprising computer-readable program code means for storing said rebound sub-decks on a persistent storage medium.

6. The computer program product for facilitating network delivery of documents encoded as decks according to claim 3, wherein said target size is based upon said client device.

7. The computer program product for facilitating network delivery of documents encoded as decks according to claim 1, wherein said decks are encoded using Wireless Markup Language (WML).

8. The computer program product for facilitating network delivery of documents encoded as decks according to claim 1, wherein said decks are encoded using Wireless Application Protocol Binary XML notation (WBXML).

9. A system for facilitating network delivery of documents encoded as decks to client devices in a computing environment capable of having a connection to a network, comprising:

means for fragmenting a deck into a plurality of sub-decks if said deck has a deck size larger than a target size, wherein each of said sub-decks then has a sub-deck size smaller than said target size and wherein said fragmenting does not discard deck content, further comprising;

means for decoupling a plurality of cards from said deck;

means for building a card adjacency graph, said graph comprising a plurality of nodes and links between selected ones of said nodes, wherein each of said nodes represents a card existing in or referenced from said deck and wherein each of said links represents an adjacency relationship between a pair of cards corresponding to a pair of said selected nodes;

means for applying a card localization process to said card adjacency graph, further comprising computer-readable program code means for creating a set of distance tuples from said card adjacency graph; and

means for aggregating said decoupled cards into said sub-decks using said set of distance tuples; and

means for rebinding said sub-decks to one another.

10. The system for facilitating network delivery of documents encoded as decks according to claim 9, wherein each of said tuples pertains to a selected one of said links and is comprised of a numeric indicator of event binding commonality and a variable substitution factor.

11. The system for facilitating network delivery of documents encoded as decks according to claim 9, further comprising:

means for receiving a request for said deck from a client device prior to said fragmenting; and

means for forwarding a primary one of said sub-decks to said client device after said rebinding.

12. The system for facilitating network delivery of documents encoded as decks according to claim 9, further comprising means for fragmenting zero or more oversized cards from a plurality of cards in said deck, wherein said oversized cards are characterized by having a card size larger than a target card size.

13. The system for facilitating network delivery of documents encoded as decks according to claim 9, further comprising means for storing said rebound sub-decks on a persistent storage medium.

14. The system for facilitating network delivery of documents encoded as decks according to claim 11, wherein said target size is based upon said client device.

15. The system for facilitating network delivery of documents encoded as decks according to claim 9, wherein said decks are encoded using Wireless Markup Language (WML).

16. The system for facilitating network delivery of documents encoded as decks according to claim 9, wherein said decks are encoded using Wireless Application Protocol Binary XML notation (WBXML).

17. A method for facilitating network delivery of documents encoded as decks to client devices in a computing environment capable of having a connection to a network, comprising the steps of:

fragmenting a deck into a plurality of sub-decks if said deck has a deck size larger than a target size, wherein each of said sub-decks then has a sub-deck size smaller than said target size and wherein said fragmenting does not discard deck content, further comprising the steps of;

decoupling a plurality of cards from said deck;

building a card adjacency graph, said graph comprising a plurality of nodes and links between selected ones of said nodes, wherein each of said nodes represents a card existing in or referenced from said deck and wherein each of said links represents an adjacency relationship between a pair of cards corresponding to a pair of said selected nodes;

applying a card localization process to said card adjacency graph, further comprising computer-readable program code means for creating a set of distance tuples from said card adjacency graph; and

aggregating said decoupled cards into said sub-decks using said set of distance tuples; and

rebinding said sub-decks to one another.

18. The method for facilitating network delivery of documents encoded as decks according to claim 17, wherein each of said tuples pertains to a selected one of said links and is comprised of a numeric indicator of event binding commonality and a variable substitution factor.

19. The method for facilitating network delivery of documents encoded as decks according to claim 17, further comprising the steps of:

receiving a request for said deck from a client device prior to said fragmenting step; and

forwarding a primary one of said sub-decks to said client device after said rebinding step.

20. The method for facilitating network delivery of documents encoded as decks according to claim 17, further comprising the step of fragmenting zero or more oversized cards from a plurality of cards in said deck, wherein said oversized cards are characterized by having a card size larger than a target card size.

21. The method for facilitating network delivery of documents encoded as decks according to claim 17, further comprising the step of storing said rebound sub-decks on a persistent storage medium.

22. The method for facilitating network delivery of documents encoded as decks according to claim 19, wherein said target size is based upon said client device.

23. The method for facilitating network delivery of documents encoded as decks according to claim 17, wherein said decks are encoded using Wireless Markup Language (WML).

24. The method for facilitating network delivery of documents encoded as decks according to claim 17, wherein said decks are encoded using Wireless Application Protocol Binary XML notation (WBXML).

25. A method of facilitating network delivery of documents encoded as decks to client devices in a computing environment capable of having a connection to a network, said decks comprising a plurality of cards, said method comprising steps of:

duplicating, from an input deck which exceeds a target deck size, deck-level information into each card of said input deck, unless said card overrides said deck-level information;

determining one or more sets of shared information, said shared information occurring in two or more of said cards;

aggregating said cards to create new sub-decks, such that a size of each of said sub-decks is less than said target deck size, by selecting one or more of said cards in which one or more of said sets of shared information occurs and factoring out duplicated occurrences among said selected one or more cards, thereby creating one of said new sub-decks; and

inserting links into said new sub-decks such that said new sub-decks can be traversed in an analogous manner as said input deck.

26. The method according to claim 25, wherein said sets of shared information comprise shared text and shared event bindings.

27. The method according to claim 25, further comprising the steps of:

determining, prior to operation of said duplicating step, which of said cards exceed a target card size; and

for each determined card,

fragmenting said determined card into a plurality of sub-cards, each of said sub-cards having a card size less than said target card size; and

inserting a card-to-card link into each of said sub-cards except a final one of said sub-cards, thereby allowing said sub-cards to be traversed in an analogous manner as said determined card.