De-fragmentation of transmission sequences

• US 20060101042A1
• Filed: 05/17/2002
• Published: 05/11/2006
• Est. Priority Date: 05/17/2002
• Status: Active Grant

• 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: Wagner, Matthias, Hirschfeld, Robert
• Granted Patent: US 7,752,252 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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-55. -55. (canceled)

56. A method of progressive transmission for a structured document, the structured document comprising sub-documents with related relevance weightings,

characterized by the steps:

generating a transmission sequence for the sub-documents according to relevance weightings;

determining a fragmentation measure according to the transmission sequence in an automatic manner using a formal expression of fragmentation;

comparing the fragmentation measure with a predetermined threshold value;

de-fragmenting the generated transmission sequence when the fragmentation measure exceeds the threshold value prior to transmission of the structured document.

57. A method according to claim 56, characterized in that sub-documents of the structured document are modeled as nodes of a tree, the number of sub-documents being k, and that progressive transmission is achieved on a level of detail of the tree selected for document transmission.

58. A method according to claim 57, characterized in that

a reading sequence according to an intended reading ordering of sub-documents is an ordered set of nodes on the level of detail of the tree

R=[r_l, . . . ,r_k],

the transmission sequence for progressive transmission is an ordered set of nodes on the level of detail of the tree D=[d_l, . . . ,d_k], wherein

the fragmentation measure is determined using a permutation vector π

;

{l, . . . ,k}→

{l, . . . ,k} defined according to

π

(i)=j, with r_i=d_j for i,jε

{l, . . . ,k}.

59. A method according to claim 58, characterized in that the fragmentation measure is an absolute fragmentation measure defining the sum of distances of sub-components from their original position in the reading sequence according to

$F_{\mathrm{abs}}=\sum _{}^{}$

i = 1 k ⁢



π

⁡

( i ) - i 

.

60. A method according to claim 59, characterized in that the absolute fragmentation measure is normalized into a relative fragmentation measure according to

$F_{\mathrm{rel}}=\frac{2}{{\left(k-1\right)}^2}$

F abs .

61. A method according to claim 58, characterized in that the fragmentation measure is a ratio of incoherence measuring how far absolute positions of nodes in the reading sequence are changed after generation of the transmission sequence, the ratio of incoherence being defined according to

$Z_{\mathrm{abs}}=\sum _{}^{}$

i = 1 k - 1 ⁢



π

⁡

( i + 1 ) - π

⁡

( i ) 

.

62. A method according to claim 61, characterized in that the ratio of incoherence is normalized into a relative ratio of incoherence according to

$Z_{\mathrm{rel}}=\frac{2}{k·}$

( k - 1 ) ·

( Z abs - ( k - 1 ) ) .

63. A method according to claim 58, characterized in that the fragmentation measure is a readability measure expressing how many nodes in the transmission sequence are still in the order according to the reading sequence, the readability measure being defined according to

$S_{\mathrm{abs}}=\sum _{}^{}$

i = 1 k - 1 ⁢

{ 1 , if ⁢

 

⁢

π

⁡

( i + 1 ) - π

⁡

( i ) = 1 0 , otherwise } .

64. A method according to claim 63, characterized in that the readability measure is normalized into a relative readability measure according to

$S_{\mathrm{rel}}=\frac{1}{k-1}·$

S abs .

65. A method according to one of the claims 56 to 64, characterized in that the fragmentation measure is determined for nodes on a level of detail of the tree selected for document transmission.

66. A method according to claim 65, characterized in that the level of detail is specified through a distance from a root node of the tree.

67. A method according to claim 56, characterized in that sub-documents comprise data defined according to the document model of an application.

68. A method according to claim 56, characterized in that progressive transmission is achieved to a mobile device having limited capabilities.

69. A method according to one of the claim 68, characterized in that the mobile client is a mobile client, such as a mobile telephone, a personal digital agent, a portable computer or a hybrid.

70. A method according to claim 67, characterized in that the mobile client is described using at least one attribute.

71. A method according to one of the claim 56, characterized in that structured documents are submitted for progressive transmission with a markup language selected from a group comprising WAP, HTML, cHTML, or XML.

72. A method according to claim 56, characterized in that progressive transmission is achieved via a connection provided according to a standard selected from a group comprising GSM, PDC, GPRS, PPP, HSCSD, WLAN, HiperLAN, IrDa, Bluetooth, IS 45, IS 95, IMT 2000.

108. A computer program product directly loadable into the internal memory of a content transmission device, comprising software code portions for performing the steps for progressive transmission according to claim 56, when the product is run on a processor of the content transmission device.

110. A computer program product according to claim 108, characterized in that the device is a server or a mobile device.

73. 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 being modelled as nodes of a tree, the context linkages between different sub-documents being modelled as edges of the tree, and the transmission sequence being modelled as an ordered set of nodes on a level of detail of the tree selected for document transmission, comprising the steps:

a) determining the total number of nodes in the tree;

b) adjusting the relevance weighting for each node on the level of detail as a function of a node number.

74. A method according to claim 73, characterized in that it further comprises the step of traversing the tree in prefix order to assign a node number to each node in the tree.

75. A method according to claim 74, characterized in that adjusting the relevance weighting for each node is achieved when traversing the tree in prefix order to assign a node number to each node in the tree.

76. A method according to one of the claims 73 to 75, characterized in that relevance weightings for nodes are adjusted in indirect proportion to the number of the node.

77. A method according to 76, characterized in that the relevance weighting for each node is adjusted with a factor defined to total number of nodes in the tree divided by number of the node.

78. A method according to claim 73, characterized in that the level of detail is specified as distance from a root node of the tree.

109. A computer program product directly loadable into the internal memory of a content transmission device,

characterized by

comprising software code portions for performing the steps for de-fragmenting a transmission sequence according to claim 73, when the product is run on a processor of the content transmission device.

79. 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.

80. A method according to claim 79, 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.

81. A method according to claim 80, 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.

82. A method according to one of the claims 79 to 81, characterized in that the graph is a tree.

84. Transmission apparatus according to claim 82, characterized in that the memory unit is adapted to store sub-documents of the structured document as nodes of a tree, the number of sub-documents being k, and a level of detail of the tree selected for progressive transmission.

85. Transmission apparatus according to claim 84, characterized in that

the memory unit is adapted to store a reading sequence according to an intended reading ordering of sub-documents as an ordered set of nodes on the level of detail of the tree R=[r_l, . . . ,r_k],

the memory unit is adapted to store the transmission sequence for progressive transmission as an ordered set of nodes on the level of detail of the tree D=[d_l, . . . ,d_k], and

the fragmentation measurement unit is adapted to determine a fragmentation measure of the transmission sequence using a permutation vector π

;

{l , . . . ,k}→

{l, . . . ,k} defined according to

(i)=j, with r_i =d_j for i,jε

{l, . . . ,k}

86. Transmission apparatus according to claim 85, characterized in that the fragmentation measurement unit is adapted to determine as an absolute fragmentation measure defining the sum of distances of sub-components from their original position in the reading vector according to

$F_{\mathrm{abs}}=\sum _{}^{}$

i = 1 k ⁢



π

⁡

( i ) - i 

.

87. Transmission apparatus according to claim 85, characterized in that the fragmentation measurement unit is adapted to normalize the absolute fragmentation measure into a relative fragmentation measure according to

$F_{\mathrm{rel}}=\frac{2}{{\left(k-1\right)}^2}$

F abs .

88. Transmission apparatus according to claim 84, characterized in that the fragmentation measurement unit is adapted to determine the fragmentation measure as a ratio of incoherence measuring how far absolute positions of nodes in the reading sequence are changed after generation of the transmission sequence, the ratio of incoherence being defined according to

$Z_{\mathrm{abs}}=\sum _{}^{}$

i = 1 k - 1 ⁢



π

⁡

( i + 1 ) - π

⁡

( i ) 

.

89. Transmission apparatus according to claim 87, characterized in that the fragmentation measurement unit is adapted to normalize the ratio of incoherence into a relative ratio of incoherence according to

$Z_{\mathrm{rel}}=\frac{2}{k·}$

( k - 1 ) ·

( Z abs - ( k - 1 ) ) .

90. Transmission apparatus according to claim 84, characterized in that the fragmentation measurement unit is adapted to determine the fragmentation measure as a readability measure expressing how many node in the transmission sequence are still in the order according to the reading sequence, the readability measure being defined according to

$S_{\mathrm{abs}}=\sum _{}^{}$

i = 1 k - 1 ⁢

{ 1 , if ⁢

 

⁢

π

⁡

( i + 1 ) - π

⁡

( i ) = 1 0 , otherwise } .

91. Transmission apparatus according to claim 89, characterized in that the fragmentation measurement unit is adapted to normalize the readability measure into a relative readability measure according to

$S_{\mathrm{rel}}=\frac{1}{k-1}·$

S abs .

92. Transmission apparatus according to claim 84, characterized in that the fragmentation measurement unit is adapted to determine the fragmentation measure for nodes on a level of detail of the tree selected for document transmission.

83. Transmission apparatus for progressive transmission of a structured document, comprising:

a memory unit adapted to store the structured document comprising sub-documents with related relevance weightings and a transmission sequence for the sub-documents according to relevance weightings;

characterized by

a fragmentation measurement unit adapted to determine a fragmentation measure of the transmission sequence in an automatic manner using a formal expression of fragmentation and to compare the fragmentation measure with a predetermined threshold value;

de-fragmentation unit adapted to re-arrange the transmission sequence when the fragmentation measure exceeds the threshold value prior to transmission of the structured document;

an interface unit adapted to exchange transmission data according to the transmission sequence.

93. Transmission apparatus according to one of the claims 83 to 91, characterized in that the memory unit is adapted to store sub-documents data defined according to the document model of an application.

94. Transmission apparatus according to one of the claims 83 to 92, characterized in that the interface unit is adapted to transmit data to a mobile device.

95. Transmission apparatus according to one of the claims 83 to 92, characterized in that the transmission apparatus is a server and is adapted to transmit data to a client device.

96. Transmission apparatus according to claim 95, characterized in that the client device is a mobile client.

97. Transmission apparatus according to claim 96, characterized in that the memory unit is adapted to store attribute information for the mobile device.

98. Transmission apparatus according to claim 83, characterized in that the interface unit is adapted to receive data being related to structured documents for subsequent progressive transmission using a markup language selected from a group comprising WAP, HTML, cHTML or XML.

99. Transmission apparatus according to claim 83, characterized in that the interface unit is adapted to progressive transmission with a connection provided according to a standard selected from a group comprising GSM, PDC, GPRS, PPP, HSCSD, WLAN, HiperLAN, IrDa, Bluetooth, IS 45, IS 95, IMT 2000.

100. 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;

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.

101. De-fragmentation apparatus according to claim 100, 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.

102. De-fragmentation apparatus method according to claim 101, 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.

103. De-fragmentation apparatus method according to one of the claims 100 to 102, 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.

104. De-fragmentation apparatus method according to 102, 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.

105. 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.

106. A de-fragmentation apparatus according to claim 105, 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.

107. A de-fragmentation apparatus according to claim 105, 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.