De-fragmentation of transmission sequences

• US 7,752,252 B2
• Filed: 05/17/2002
• Issued: 07/06/2010
• Est. Priority Date: 05/17/2002
• Status: Expired due to Fees

• Current Assignee: DoCoMo Communications Laboratories Europe GmbH (Government of Japan), NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Hirschfeld, Robert, Wagner, Matthias
• Primary Examiner(s): Boutah; Alina N.
• Application Number:
  US10/514,977
• Publication Number:
  US 20060101042A1
• Time in Patent Office: 2,972 Days
• Field of Search: 709/200, 709/232, 709/241, 709/246, 709/247, 707/5, 707/101
• US Class Current: 709/200
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents
• 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/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04W 80/12 Application layer protocols, e.g. WAP [Wireless Application Protocol]

Abstract

The present invention aims at avoiding fragmentation during transmission of a structured document (10). This is achieved by a method of progressive transmission for a structured document (10), the structured document (10) comprising sub-documents (12, 14, 16, . . . ) with related relevance weightings. In particular, a fragmentation measure is determined according to the transmission sequence in an automatic manner using a formal expression of fragmentation. After comparison the fragmentation measure with a predetermined threshold value the transmission sequence is modified to reduce fragmentation when the fragmentation measure exceeds the threshold value.

Claims

1. A method of de-fragmenting a transmission sequence to transmit a structured document prior to transmission of the structured document, the structured document comprising sub-documents with related relevance weightings being modelled as nodes of a graph, the context linkages between different sub-documents being modelled as arcs of the graph, and the transmission sequence being modelled as an ordered set of nodes, comprising the steps:

selecting the node with highest relevance weighting as next node of a de-fragmented transmission sequence;

determining a distance measure from the selected node to nodes of the transmission sequence which are not assigned to the de-fragmented transmission sequence using the graph modelling of the structured document and shortest path metrics;

adjusting relevance weightings for nodes which are not assigned to the de-fragmented transmission sequence as a function of the related distance measure;

recursively repeating the previous steps until all nodes of the transmission sequence are processed.

2. A method according to claim 1, characterized in that relevance weightings for nodes which are not assigned to the de-fragmented transmission sequence are adjusted in indirect proportion to the related distance measure.

3. A method according to claim 2, characterized in that the relevance weighting for each is adjusted by dividing the relevance weighting of the node through the distance measure to the selected node.

4. A method according to one of the claims 1 to 3, characterized in that the graph is a tree.

5. De-fragmentation apparatus for de-fragmentation of a transmission sequence for a structured document prior to transmission thereof, comprising:

a memory unit adapted to store a structured document and a model thereof, where sub-documents of the document are stored in relation to nodes of a tree, context linkages between different sub-documents are stored as edges of the tree, and the transmission sequence is stored as an ordered set of nodes on a level of detail of the tree selected for document transmission;

a processing unit adapted to determine the total number of nodes in the tree, the processing unit having

a selection unit adapted to select a node with highest relevance weighting as next node of a de-fragmented transmission sequence, and

a distance measurement unit adapted to determine a distance measure from the selected node to nodes of the transmission sequence which are not assigned to the de-fragmented transmission sequence using a graph modeling of the structured document and shortest path metrics; and

a de-fragmentation unit adapted to adjust the relevance weighting for each node on the level of detail as a function of a node number.

6. De-fragmentation apparatus according to claim 5, characterized in that the processing unit is adapted to traverse the tree in prefix order and to store a node number for each node in the tree in the memory unit.

7. De-fragmentation apparatus method according to claim 6, characterized in that processing unit is adapted to adjust the relevance weighting for each node in the memory unit when traversing the tree in prefix order.

8. De-fragmentation apparatus method according to one of the claims 5 to 7, characterized in that the processing unit is adapted to adjust relevance weightings for nodes in the memory unit in indirect proportion to the number of the node.

9. De-fragmentation apparatus method according to 7, characterized in that the processing unit is adapted to adjust the relevance weighting for each node in the memory unit with a factor defined to total number of nodes in the tree divided by number of the node.

10. A de-fragmentation apparatus for de-fragmentation of a transmission sequence of a structured document prior to transmission thereof, comprising:

a memory unit adapted to store a model of the structured document, where sub-documents of the document and related relevance weightings are stored as nodes of a graph, context linkages between different sub-documents are stored as arcs of the graph, and the transmission sequence is stored as an ordered set of nodes;

a processing unit having

a selection unit adapted to select a node with highest relevance weighting as next node of a de-fragmented transmission sequence;

a distance measurement unit adapted to determine a distance measure from the selected node to nodes of the transmission sequence which are not assigned to the de-fragmented transmission sequence using the graph modelling of the structured document and shortest path metrics;

an de-fragmentation unit adapted to adjusting relevance weightings for nodes which are not assigned to the de-fragmented transmission sequence as a function of the related distance measure;

wherein

the processing unit is adapted recursively activate the selection unit, the distance measurement unit, and the de-fragmentation unit until all nodes of the transmission sequence are processed.

11. A de-fragmentation apparatus according to claim 10, characterized in that the de-fragmentation unit is adapted to adjust relevance weightings for nodes which are not assigned to the de-fragmented transmission sequence in indirect proportion to the related distance measure.

12. A de-fragmentation apparatus according to claim 10, characterized in that the de-fragmentation unit is adapted to adjust relevance weightings for nodes which are not assigned to the de-fragmented transmission sequence by dividing the relevance weighting of the node with the distance measure to the selected node.