Note: Descriptions are shown in the official language in which they were submitted.
CA 02479606 2004-08-31
2
Method far ~ocument Page Delivery to a Mobile rCommunication Device
t=laid of the Inyention
~t~p49 ] The following is directed in general to displaying content nn mobile
communication devices, and more particularly to a method for viewirx,~ a
selected portion of a
document on a mobile communication device without having to reguest multiple
pages of the
document contents containing document global properties applied to the
selected part of the
document
I~ackaround of the invention
[0002] Mobile communication devices are becoming increasingly popular for
business
and persarral use due to a relatively recetrt increase in number of services
and features that
the devices and mobile infrastructures support Handheld mobile corrrmunioatinn
devices,
sometimes referred to as mobile stations, are essentially portable computers
having wireless
capability, and come in various fon~r~s. These include Personal Digital
Assistants (PPA).
eellular phones and smart phones. While their reduced size is an advantage to
portability,
bandwidth and pmcessir~ constraints of such devices present challenges to the
downloading and viewing of documents, such as word processing documents,
tables and
images.
[0a03] Electronic dvcume~nts are produced using various computer programs,
such as
word processors, spreadsheet programs, fiinancial software, and presentation
software. in
addition to text, such documents captain structural and property information
such as
paragraph indentation, text color and table size, etc.
[8004] When a user of a mo>~ile communication device wishes to view only
selected
portions of a document stared on a remote sErver, other portions of the
document that
contain the structural information alai properties used by the selected
portion must also
typically be transmitted to the mobile communication device. The required
downloading of
these other portions occurs over a potentially bandwidth-Constrained wireless
nefinroric. FQr
example, if a user wishes to view only a single paragraph in a Section at the
middle of a 400-
page document, the entire section (and sometimes even entire doGUment~ that
contains
default properties for the paragraph must be transmitted to the mobile
communication
devlCS.
(0Q05] Once downloaded to the device, the electronic document is viewed using
a e~ser
interface on the mobile communication device, which typically differs from tha
user interface
2
CA 02479606 2004-08-31
3
used to create and view a d~ument on a pt;rsanal computer: For example,
whereas the
user interface on a personas computer may include a large, color display and a
pointing
device such as a mouse, the mobile communication device typically has only a
small,
possibly nan~color, screen, and may not have a mouse. 1n addition, the mobile
communication device typically has gniater processing power and memory
limitations than a
personal computer
Summary of the Inyention
[OO~B] According to an aspect of the Pnvention, a method is provided for
viewing a
selected portion (page) of a document on a mobile communicatson device without
having to
retrieve the full document onto the device. In one embodiment, a server
pagination function
is used for marking pages of a document based on size required by a mobile
communication
device. According to another aspect of the invention, document pages are
generated and
transmitted by the server to the mobile device in such a way as to associate
all of the
required properties and attributes for the selected portion (page).
EO~OTI BY using this approach for page delivery from the server, the client on
the mobile
device is able to retrieve any portion (page) of a document and display it
independently,
since alt of its properties and attributes are already associated. This
eliminates the order
dependence for displaying a document such as required by a desktbp
application, More
importantly overall network bandwidth usage is limited.
j0~08] Additional aspects and advantages will be apparent to a person of
ordinary skill in
the art, residing in the detar7s of constn,~ction and operation as more fully
hereinaf6er
described ar>d claimed, reference being had to the accompanying drawings.
Brief Description of the Drawings
Eooag] A detailed description of the prefierred embodiment is set forth in
detail below, with
referer~e to the following drawings, in which:
Figure 1 is a block diagram of a network environment in which the preferned
embodiment may be practiced;
Figure 2 is a tree diagram showing the 6aslc structure of a Document Object
Model
(DOM) used in the preferred embodiment of the invention;
Figure 8 shows the top-level of the DpM structure in Figure 2;
Figure 4 shows an exemplary DOM struckure for a word processing document;
Figure 5 shows an exemplary DC1AA structure for a table document;
CA 02479606 2004-08-31
Figure 6 shows an exemplary DDM structure for a word processing document
containing an image subdocurnent;
Figure 7 is a flowchart showing document DOM stnacture construction and
pagination according to the preferred embodimernt; and
Figure 8 is a flowchart showing document 170M page generation and delivery
according to the preferred embodiment.
Detailed De$criation of the Pr$ferred Embodiment
[DalO] VUrth reference to Figure 1, network envirt~r~ment 10 is shown in which
the
preferred embodiment of the invention may be pracf'iced. Network environment
10 includes
mobile devices 12 communica~ng via a wireless network 14 to a server 2$ for
downloading
document athactxnents to the mobile devices 12. While only one server 28 is
shown for
illustration purposes, a person of skill in the art will understand that
network environment 90
could have many such servers for hosting web sites or graphic download sites,
providing
access to picture files such as ,1PE;G, TIFF,13MP, PNG, SGI, MP4,MOV, GIF, SV~
etc. As
would be understood by one of ordinary ski61 in the art, wireless networks 14
include
GSMIGPRS, CDPD, TDMA, ioEN Mobitex, DataTAC netvuarks, or future networks such
as
EDGE or UMTS, and broadband networks like Bluetooth and variants of $02.11.
[001 t] A connection to a faced service nrquires special considerations, and
may require
special permission as authorized through a Network Access Point (NAP) 16. For
generic
$ervioes, such as web access, a foxy-gateway or Network Address'franslator
(NAT) 1$
may be pro~rided so that a network operator can control and bill for the
access. NATs 18
enable management cat a limited supply 4f public lntemet addresses for largo
populations of
wireless mobile devices. Solutions ofifered by a prox~gateway yr NAT 1$ can
require a
complex infrastructure and thus may be managed by a value-added service
providers
(VASPsy, which provide, fior instance, WAP gatewaysi WAP proxy gateway
solutions, multi-
media messaging servers (MMS) and Internet Multi-Media Services (IMSy.
j0012] private Irttranet services 26 afro connected ~6nn Internet 20 may
require their own
Private Intranet Proxy Gateway 24. for accessing content on server 2$. Such
private services
include WML access to corporate mall systems, HTML access to GRM databases, or
any
other services that deliver tnformatlon as formatted data w~h links and UI~Ls
embedded, As
shown, it is possible that a private service 26 may be connected directly to
wireless network
14, as opposed to connected via Internet 20.
(OU13, Referred to throughout this document for the purpose of describing the
preferred
CA 02479606 2004-08-31
r~
embodiment is the structure of a l7~acurnent Object Model {DOM) far a document
attachment
to be viewed on a mobile dev'~ 92.
[1701 A~j The attachment server 28 uses a designated file-parsing distiller
for a specific
document type to build an in-memory Document Object Model {DOM) structure
representing
an attachment of that document type. The document C~OM structure is stored in
a memory
cache of server 28, and can be iterated bi-directionally
[0015] As shown in Figure 2, the graph-.based documentDOM structure consists
of
nodes arxt leaves. The nodes serve as the parents of leaves and nodes, while
leaves are
end points of a branch in the graph. Each node and leaf can have a set of
attributes to
specify its own characteristics. For example, a paragraph node can contain
attributes to
specify its 2~lignment, style, entry of document TOG, etc. In additson, each
of the nodes and
the leaves has a unique idenfifier; called a ~0M ID, to identify itself in the
document DONI
structure.
[0016] The document DOM structure is divided into three parts: top-level,
component
and references. The tap level refers to the document root structure, while the
main document
is constructed in the component and the references represent document;
references to either
internal or external sub-document parts. The following paragraphs examine each
part in
detail.
[0017] The rnot node of a document DOM structure, referred to as
°Document', contains
several children nodes, referred to as "Conien'~", which represent different
aspects of the
document cardents. Each "Contents° node contains one or multiple
°Corrt~ainer° nodes used
to store various document global attributes. The children of the "Gorrtainer"
nodes are
components, which store the document structural and navig2~tional information.
When tt~
attachment server 28 builds the DOM structure for an attachment file for the
first time, the
top-level structure is a single parent child chain as shosnm in Figure 3:
[1018, Three types of components are defined by the attachment server 2$: text
components, table components and image componerds, which represent text,
tables arid
images in a document, respectively, The text and fiable components are
described in detail
below, and the image component structure is identical.
[0019] A component consists trf a hierarchy of command nodes, Each command
represerns a physical entity, a property, or a reference defined in a
document. For the text
component. the physical entity commands are page, section, paragraph, text
segments,
comments, footnote and er~dnote commands, which by name define the
corresponding entity
contained in a dvcurnent. The property commands for the text component are
font, tact Color,
CA 02479606 2004-08-31
text background color, hyperlink startlend and bookmark commands. The text
component
has only one reference command, referred to as the text reference command,
which is used
to reference a subdoeument defined in the main body of a document. Usually,
the children of
a text component are page or section command nodes that, in tum, comprise a
set of
paragraph command nodes_ The paragraph command can contain one or multiple
nodes for
the remaining command types.
[420] Using the following sample text document, the corresponding document DOM
strut:kure is shown in Figure 4:
First paragraph.
second paragraph with bold and red text.
[0021] As Figure 4 demonstrates, the section command, which is the child of
the text
component, consists of two paragraph commands. The first paragraph command
contains
one text segment command and the text content for that paragraph is added as
an attribuke
to the text segment command. The second paragraph ctsnmand h~ a relatively
more
complex structure, as the text properties in the paragraph are much richer.
Each time a text
properky (font, text color, etc) changes, a corresponding text property
command is created
and the change value is added to that command as an attribute. The following
text segment
command recnrds the text with the same Text properky as an attribute. As
document structure
gets richer and more complex, more ta~mmands of corresponding types are
created and the
document properties are added as attributes to those commands.
[r?022] The table component has the same three types of commands as the text
component, but different command names. The document LOOM structure for the
sample
table dacumerrt below is shown in Figure 5:
[p023I As shown in ttte Frgure 5, the table component has physics) entity type
commands of table, tabterow and tabl~ell, where the tablecell command can
contain all
available commands for the text component, fn the example above, the first
child TabIeRow
command of the table command has an attribute "Index" defined by value of 0.
'fhls indicates
that the indicated table row is the first one defined in the table. The
attribute of the leftrnost
table cell command ire Figure 5 has the same meaning.
6
CA 02479606 2004-08-31
7
[I102~] A document sometimes contains subdacurnents, for example images,
tables, text
boxes ets The QOM structure set forth herein uses a reference command to point
to the
graph of such subdocuments. Thus, far the following sample document, the
attachment
server 28 generates the DOM structure shown in Figure 6:
This document has subdocument of images lifts this an
Second paragraph contains the same image.
[0025) The structure shown in Figure G is identical to that discussed above in
connection
with Figures 4 and 5, except for the attributes of the two reference commands.
The
attachment server 28 constructs the image in "Sample Three° as a
separate image
component, which contains all of the image data In its own DOM hierarchy !n
the DOM
structure for the main document, the values of the "Ref' attributes of those
two reference
commands paint to the image component, as indicated by the dashed lines, such
that the
DOM structure connects together all parts of the document.
[Oo26~ Having described the document DOM structure used to implement an
embodiment of the invention, a detailed discussion will now be provided of a
pagination
function or method according to the preferred embodiment.
[0027] The pagination function is a client and server side operation. Fgure 7
shows the
processing steps, from which it wilt be noted that the server 28 uses a map in
memory for
document DOM cache storage and the key ~ the map is the document ID.
initially, when the
user of a mobile rommurdcation device 12 sends a request to the server 28 to
view a
document. the device '12 sends two attributes and fhe nut~nber of bytes it
requires
(RequireS~e) as a response from the server (e.g. 3K bytes). The two attributes
are whether
the device is a color or monochrome device, and the screen size (width x
height x color
depth) of the device in pixels. Other information about the device '12 can
also be transmifted
to the server 28 (e_g. memory size). After the server 2g receives a dncument-
viewing
request, it starts the pagination process (step 30), and initializes the
rrariables Pagelndex
and PageSize.
f~p2$I ~e ~Itowirs9 teams and variables are used in the process of Figure 7:
[0029] The Pagelndex variable is defined in the server 28 and used by the
server to
record the current page index being paginated by the serves The page index is
initially set to
D indicating "Page 1".
~o030] PageSize is a variable defined in the server ~8 and used fey the server
to record
7
CA 02479606 2004-08-31
the current size far the page being paginated and is reset to D when
paginating a new page.
jOD31] Hyperlink map is a u2frfabla defined in the server 28, which is a
container
consisting of the elemerrk type of hyperlink node in the document DOM
structure. The key
(ID) for each element in the container is the hypertink target string.
[0032 Bookmartc map is a variable defined in the Server ~8 which is a
container
consisting of the element type of current page index (Pagelndex value) far the
bookmark in
the dAcument DOM structure. The key (1D) for each element in the container is
the
bookmark ring.
[0033) The server process constricts a document 1l7 (step ~2) based an the
document
contents and uses tha ILa to check the document DOM cache (step 33) to
determine whether
the document DOM structure for that document has been constructed. If the
document DOM
strcrature does not exist in the cache, the server. builds the DOM structure
(step 34) for the
document and adds it to the cache (step 35).
[0034' To constnrct the document ID, the original document hle is opened and
read in
binary mode_ The server 28 creates a MD5 Context structure, hashes the MD5
context
structure with raw binary data, byte-by byte, from the file, finalizes the MD5
confiext structure
and re#rieves the l6byte key fortrie fife. The MDa content s#ruchare has the
following
structure in syntax of C+* language
iypedef strucf
f
unsigned long ad~rStatej4J; !* state (~4BCD) 'l
unsigrtedlong adwCounfj2),~ l"numberofbits, mOduto 2"64 (lab first) *l
unsigned Char abyBuflerj64J; P input buffer'/
} tMD5_C7X,~
[~~35J Caching the document DC7M structure requires considerable memory, and
therefore increases the overall hardware deptoyrnent co$t. On the oth~r hand,
building the
DOM structure for a document is even more time and CPU Intensive 'err contrast
to the
document key construction operation, especially for big documents. Since
processing Time is
more critical than hardware deployment cost for wireless operation, caching
the doeurnent
DOM is the approach adopted for the preferred emtyodiment, rather than
building the DOM
structure for the document each time the server receives a viewing request and
then
discarding the structure after sending the response back to the client device
12.
(0o3~) Once the document GOM structure has been built and stored in the cache,
the
8
CA 02479606 2004-08-31
server 2$ determines whether a page mark has already been set in the root
(step 3f3)_ if not,
the server traverses through the DbM structure (steps 38, 39, ~0 and ~1 ) and
calculates the
output size (PageSize) for each node in the DOM structure based on the number
of bytes
(RequireSize) provided by the device 12. The sErver increments the Pagelndex
(step ~4Z),
adds it as an attribute to each node in order to mark the start of each page,
and adds each
node as an attribute to the root node with the string representation of
Pagelndex as the
attribute name (step 43). Following this pagination function, the attachment
server 2$ is able
to transmit the document page-by-page tc~ the requesting mobile device 12
based on client
generated requests, and process flow continues to Figure 8 for CtOM page
generation and
defrvery (step 44j.
[003?, The page mark attribute name is associated with the device inforrnatian
and
required response size (RequireSize) provided by the device 12, to enable the
server to
paginate through the document DOM structure and generate the response based ~
device
capabilitx For example if the device is a monochrome type, the color
infannation contained
inside the Dt7M structure will be ignored during the server pagination and
response
generation operations and therefore optimize the wireless bandwidth
utilization.
[0038] Since the key to the memory map is the document ID, the algorithm used
to
calculate the document ID (step 32j must guarantee the uniqueness of the key.
According to
the best made, as set forth above, the algorithm used inside the center 2$ is
the MD5
messaging encryption algorithm invented by Professor Ronald L. Rivest of MIT
L.abor~tory
for Computer Science and RSA Data Security, Inc. There are several other
hashing options
that can be used. However MD5 is the most efficient and retiabls one based on
the broad
range of different document content required to be processed by the server 28.
[oa3s~3 In the proeESS of FigureB, PageSlertNode is DOM structure node type
which, in
the preferred embodiment is a COM (Common obiect modutey object base
intertace. VecParent
is typically a one-tiimerrsionat cont~aine~ fnr example vector, coryiaiMng
elements of DOM
structure node type. It 1s used to scare the parents (recursively until the
node of component
type) for the page-starting node. as discussed in greater detail below bStart
is a Boolean
variable de~rned in the server 28 and used to signal that the required page
has already been
been trmversed.
jOQ40a In operation, the server 2$ uses Pagelndex to build the page mark
attribute (step
48j and search for tile node representing the page start (step ~47j for the
page of interest
identified by the client device 92. It is used by the server 28 to cache the
node which marks
the start for the page required by the client device 72. ante the node is
found, the server 2$
CA 02479606 2004-08-31
recursively retrieves the parent of the node (step A.8) until it reaches the
component level
(step 49) and puts all the parents into storage (llecParent}, namely the
parent container
(step 5s7). The server 28 then traverses the DOM structure again (steps 51 et
seq) to persist
the irrmemory structure to a form that can be transmitted across the network
to the mobile
device 12. if a node is one of those stored in the parent container (step 54),
it generates the
output for the node (step 57}. The output includes the contents and attributes
far all of the
nodeslleaves belonging to that page as veil as the attributes of the parents
far the page start
node.
[0041 Upon locating the corresponding page start node (step 55), the server 28
sets a
Boolean (bStart) to true, indicating that the page has been traversed (step
56), and
generates the output (step 57) for each following node to be iterated until
the next page mark
is found (step 58). Once the server 28 determines that it has completed
traversing the DOM
structure (step 52), or has found the next page start mark (step 58), the
process finishes
(step 59).
[Q04x] Frorn Figure $, it wilt be noted that all of the parents for #~e
page~.start node are
output into the response, which means the default attributes and properties
defined for the
node but rontained in ii=s parents, will persist. However, the siblings of the
node are ignored if
they do not belong to the resporsse page. Fc~r exarrtple, if the client
(mobile device 12)
requires the second part for a spreadsheet, the server 28 not only generates
the response
containing the corresponding text cont~rrt;~ but also includes the global
information for the
table such as number of rows and columns and current table row and cell index,
etc., into
the response. Once the client receives the response, it can display the text
at the Correct
position without having to request the first partof the spreadsheet from the
server:
jai943, A person skitied in the ark, having read this description of the
preferred
embodiment, may conceive of variations and altema#ve embodiments. For example.
generating multiple sets of page marks for successive pages requires
considerable time arid
CPU usage since the server 28 has to re-traverse the 1~QM struoiwe.
Acco~ir~ly, one
alterrtatave is for the server 28 td create only one set of page marks in a
document DOM
structure and generatE the response based an the device information. However,
this
approach is likely to create more page marks than necessary and will introduce
extra
transactions between the wireless device 12 and the server 28 if the user
wants to view a
Large porkion at a document. Based on the understanding that minimizing the
wireless
bandwidth usage is more critical than the processing time on the server,
creating multiple
sets of the page marks and caching them is the approach adopted in the
preferred
rmbadiment.
CA 02479606 2004-08-31
[~0~14.] Ail such variations and alternative embodiments ere believed to be
within the
ambit Ql=the ciairrts appended hereto.
91
