PCT
`
`
`
`WORLD INTELLECTUAL PROPERTY ORGANIZATION
`International Bureau
`INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`
`
`(51) International Patent Classification © :
`WO 97/41520
`
`
`(11) International Publication Number:
`GO6F 17/30, 13/42, 9/46, 15/16
`
`
` (43) International Publication Date:
`6 November 1997 (06.11.97)
`
`
` (21) International Application Number: PCT/US97/04719|(81) Designated States: AL, AM, AT, AT (Utility model), AU
`
`
`(Petty patent), AZ, BA, BB, BG, BR, BY, CA, CH, CN,
`(22) International Filing Date:
`20 March 1997 (20.03.97)
`
`
`
`CU, CZ, CZ (Utility model), DE, DE (Utility model), DK,
`DK (Utility model), EE, EE (Utility model), ES, Fl, Fi
`
`
`
`(Utility model), GB, GE, GH, HU,IL, IS, JP, KE, KG,
`
`
`
`(30) Priority Data:
`KP, KR, KZ, LK, LR, LS, LT, LU, LV, MD, MG, MK,
`08/640,334
`30 April 1996 (30.04.96)
`us
`
`
`
`MN, MW, MX, NO, NZ, PL, PT, RO, RU, SD, SE, SG,
`
`
`SI, SK, SK (Utility model), TJ, T™,TR, TT, UA, UG, US,
`
`
`UZ, VN, YU, ARIPO patent (GH, KE, LS, MW, SD, SZ,
`
`(71) Applicant(for all designated States except US): INTEL COR-
`
`
`UG), Eurasian patent (AM, AZ, BY, KG, KZ, MD, RU,TI,
`PORATION [US/US]; 2200 Mission College Boulevard,
`TM), European patent (AT, BE, CH, DE, DK, ES,FI, FR,
`
`Santa Clara, CA 95052 (US).
`
`
`GB, GR,JE, IT, LU, MC, NL, PT, SE), OAPI patent (BF,
`
`
`
`BJ, CF, CG, CI, CM, GA, GN, ML, MR, NE, SN,TD, TG),
`(72) Inventors; and
`
`(75) Inventors/Applicants (for US only): HUANG,Chu-Yi[-/US]:
`
`
`
`Apartment 12, 10620 S.W. Davies Road, Beaverton, OR
`Published
`
`97008 (US). ROMRELL, David, A. {US/US}; 2323 N.W.
`With international search report.
`
`
`188th Avenue #1911, Hillsboro, OR 97124 (US). TSO,
`Before the expiration of the time limit for amending the
`
`
`
`Michael, Man-Hak [AU/US]; 5744 S.E. Preston Court,
`claims and to be republished in the event of the receipt of
`Hillsboro, OR 97123 (US).
`
`
`amendments.
`
`94086 (US).
`
`
` (54) Title: A METHOD FOR SCALING LARGE E-MAIL DATABASES FOR DEVICES WITH LIMITED STORAGE
`
`(74) Agents: TAYLOR, Edwin, H.et al.; Blakely, Sokoloff, Taylor
`& Zafman LLP, 1279 Oakmead Parkway, Sunnyvale, CA
`
`
`EMAIL AGENT (57) Abstract
`
`
`
`(INTEL
`
` A method and apparatus for scaling E-mail (electronic mail) address book (132) databases for devices with limited storage capacity
`and synchronization of a first set of mail subsetter (128) for automatically generating a default personal address book (PAB) (128) and a
`mail synchronizer for application independent E-mail synchronization. A pseudo unique identification (200) is generated for each message
`
`
`
`
`Page 1 of 94
`
`GOOGLEEXHIBIT 1027
`
`Page 1 of 94
`
`GOOGLE EXHIBIT 1027
`
`

`

`Singapore
`
`Albania
`Armenia
`Austria
`Australia
`Azerbaijan
`Bosnia and Herzegovina
`Barbados
`Belgium
`Burkina Faso
`Bulgaria
`Benin
`Brazil
`Belarus
`Canada
`Central African Republic
`Congo
`Switzerland
`Cote d'Ivoire
`Cameroon
`China
`Cuba
`Czech Republic
`Germany
`Denmark
`Estonia
`
`Slovenia
`SI
`Slovakia
`SK
`Senegal
`SN
`Swaziland
`SZ
`Chad
`TD
`Togo
`TG
`Tajikietan
`TJ
`™ Turkmenistan
`Turkey
`Trinidad and Tobago
`Ukraine
`Uganda
`United States of America
`Uzbekistan
`Viet Nam
`Yugoslavia
`Zimbabwe
`
`Lesotho
`Lithuania
`Luxembourg
`Latvia
`Monaco
`Republic of Moldova
`Madagascar
`The former Yugoslav
`Republic of Macedonia
`Mali
`Mongolia
`Mauritania
`Malawi
`Mexico
`Niger
`Netherlands
`Norway
`New Zealand
`Poland
`Portugal
`Romania
`Russian Federation
`Sudan
`Sweden
`
`FOR THE PURPOSES OF INFORMATION ONLY
`
`Codes used to identify States party to the PCT on the front pages of pamphlets publishing international applications under the PCT.
`
`ES
`FI
`
`Spain
`Finland
`France
`Gabon
`United Kingdom
`Georgia
`Ghana
`Guinea
`Greece
`Hungary
`Treland
`Israel
`{celand
`Italy
`Japan
`Kenya
`Kyrgyzstan
`Democratic People’s
`Republic of Korea
`Republic of Korea
`Kazakstan
`Saint Lucia
`Liechtenstein
`Sri Lanka
`Liberia
`
`Page 2 of 94
`
`Page 2 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-1-
`
`A METHOD FOR SCALING LARGE
`E-MAIL DATABASES FOR DEVICES
`WITH LIMITED STORAGE
`
`This application is a Continuation-In-Part of pending application serial
`number 08/431,500 entitled APPLICATION INDEPENDENT RECORD LEVEL
`SYNCHRONIZATIONfiled April 28, 1995.
`
`(1)
`
`Field of the Invention
`
`The inventionrelates to E-mail (electronic mail) systems. More
`particularly, the present invention is related to the method and apparatusfor scaling
`E-mail address book databases for devices with limited storage capacity.
`
`(2)
`
`Background
`
`E-mail (electronic mail) is one of the most popular data use application for
`data and voice telephones,in particular, for cellular telephones. However,
`telephonesaretypically limited in storage capacity. An average advancedcellular
`phone (such as a SmartPhone) being designed has less than one mega byte (MB)
`of storage available for use by a user. In contrast, a typical electronic address
`database using corporate environments are very large.
`
`Giventhe storage constraints of devices such as a SmartPhone and the
`desirability for access to a large electronic address database,it is desirable to have
`some type of a default personal address book. Currently, there are a couple of E-
`mail systems which maybe used to offer some type of method for generating a
`default personal address book. However, neither of the systems are easy to use.
`For example, cc: Mail Mobile System from Lotus Development Corporation and
`cc: Mail Remote System from Lotus Development Corporation duplicate the
`address database (generally several mega-bytes in size) on a notebook PC
`(Personal Computer), or require the user to generate their own address book there
`
`Page 3 of 94
`
`Page 3 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-2-
`
`is no subsetting offered by the systems. Additionally the E-mail systems do not
`work with devices with limited storage such as is found in SmartPhones.
`
`MSMail system from Microsoft allows subsetting using personal address
`books, however, with this method and apparatus, the user must manually select
`and moveentries in the network databaseto his or her personal address book.
`Additionally, the method and apparatus clearly does not scale to large databases
`such as for corporations, where there may be a large number of employees. More
`specifically, manually finding, selecting and moving, for example one hundred
`people regularly from a large list of employeesis not only inefficient and slow but
`ultimately unusable in a corporate orlarge organizational environment, e.g. with
`tens of thousands of employees.
`
`Additionally, MS Mail does not provide synchronization for the personal
`address book and the network database. For example, if John Doe is in both a
`user's personal address book and in a network database and if John Doe's nameis
`deleted from the network database, his namewill remain in the user's personal
`address book. Hence,the user will not know that John Doe is no longer available
`until a mail is transmitted to him and the mail is returnedas“undeliverable”or
`
`“user unknown”.
`
`CC: Mail from Lotus Development Corporation provides synchronization
`butit is very inefficient. Synchronization is performed on-line with CC: Mail, 1.e.
`whenauser is connected and requires that the entire database be reconciled.
`Exemplary circumstances requiring reconciliation include when new records are
`added such as for new employees, when records have been deleted suchas to
`account for employeeattrition, and when updates are made such as for changed
`telephone numbers. Scanning a large database for changetakestens of minutes
`and since synchronization mustbe performed periodically, use of CC: Mail
`Remote or Mobile in a large organizational environment becomesimpractical.
`
`Thereforeit is desirable to have a method and an apparatus for scaling E-
`mail address book databases for devices with limited storage capacity by providing
`an easy to use method for generating default personal address books automatically
`
`Page 4 of 94
`
`Page 4 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-3-
`
`and to provide an efficient method for keeping the personal address books
`synchronized with a main database.
`
`
`
`BRIEFSUMMARYOFTHEINVENTION
`
`A method and an apparatus for scaling E-mail (electronic mail) address
`book databasesfor devices with limited storage capacity and synchronization of a
`first set of mail with a second setof mail at the message/folder level. A memory
`contains a mail subsetter for automatically generating a default personal address
`book and a mail synchronizer for application independent E-mail synchronization.
`A pseudouniqueidentification is generated for each message or folder in the mail
`boxes to be synchronized. An event log is then generated for each mail box. The
`memoryalso has a Synchronization mechanism for makingthefirst set of data and
`the second set of data equivalentby using the information in the ChangeList
`generated by the Change Detection Mechanism. A processor runs the mail
`synchronizer.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Figure la illustrates the architecture of the present invention.
`Figure 1b illustrates an exemplary system block diagram with an
`implementationofthe present invention,
`Figure Icillustrates an exemplary system block diagram ofthe present
`invention.
`Figure 1d illustrates an exemplary personal address book.
`Figure le illustrates the general steps followed in an exemplary installation
`procedureinstalling the presentinvention’s client device address book (DAB).
`Figure2aillustrates an exemplary block diagram of the mail synchronizer
`of the present invention.
`Figure 2billustrates a block diagram ofthe identification (ID) generator
`illustrated in Figure 2a.
`
`Page 5 of 94
`
`Page 5 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-4-
`
`Figure 2c is a block diagram of event log generator 334 illustrated in
`Figure 2a.
`Figure 2d is an exemplary block diagram of the synch mechanism ofthe
`present invention.
`Figure 3a illustrates the general steps followed by the creation mechanism
`(creator) 122 illustrated in Figure Ic.
`Figure 3billustrates general steps followed in obtaining user settings (step
`301 of flow diagram in Figure 3a).
`Figure 3c illustrates the general steps followed including a personal
`address book (PAB) (step 302 illustrated in flow diagram Figure 3a).
`Figure 3d describes the general steps followed in processing the message
`(step 338 in Figure 3c).
`Figure 3e describes the general steps by which an addressis processed
`(step 346 offlow diagram illustrated in Figure 3d).
`Figure 3fillustrates the general steps followed including a device address
`book image (DABD(step 303 of flow diagram illustrated in Figure 3a).
`Figure 3g illustrates general steps in creating a DAB(step 304 of flow
`diagram of Figure 3a).
`Figure 3h describesthe general steps followed by the update mechanism
`(updator 123 illustrated in Figure 1c) of the present invention.
`Figure3i illustrates the general steps followed in processing changes in the
`mailbox (step 372 of Figure 3h).
`Figure 3j illustrates the general steps followed in synchronizing PAB with
`the data source (step 373 of Figure 3h).
`Figure 3k illustrates the general steps followed by the address
`synchronizer.
`Figure 4aillustrates an exemplary source ID table 410.
`Figure 4billustrates an exemplary changelist 420 for DAB 132.
`Figure 4cillustrates an exemplary changelist for DABI 130.
`Figure 4d illustrates an exemplary mergedlist created by merging and
`sorting by time the changelist for DABillustrated in Figure 4b andthe change list
`for DABIillustrated in Figure 4c.
`
`Page 6 of 94
`
`Page 6 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-5-
`
`Figure 5ais a block diagram illustrating an exemplary synchronization
`apparatus of the present invention.
`Figure 5bis a flow diagram illustrating the generalsteps followed by the
`apparatusillustrated in Figure 5a.
`Figure Sc illustrates exemplary data structures for exemplary ChangeLists
`CLO and CLI.
`Figures 5d - 5f are alternate embodiments of a system block diagram
`illustrating the mail synchronization method and apparatusofthe present
`invention.
`Figures 5g and 5h arestate transition diagramsillustrating how a change
`log is truncated to result in exactly one changeflag marked for each record.
`Figure 6aillustrates the general steps followed by the mail synchronizerof
`the present invention.
`Figure 6b describes the general steps followed by the present invention in
`generating a pseudo uniqueID for each mail in a mail box to be synchronized with
`another mail box.
`Figure 6c describes the general steps followed by the present invention in
`generating an eventlog for a mail.
`Figures 6d and 6¢illustrate the general steps followed bythe present
`invention in generating an event log for folders.
`Figure 7a is a flow chart describing the general steps followed by a SUID
`mechanism.
`Figures 7b and 7c are flow charts describing the general steps followed by
`a Change Detection mechanism.
`Figure 7dillustrates an exemplary data structure modified by the steps
`described in Figure 7b.
`Figures 8a - 8d are flow charts describing the general steps followed by an
`Error Correction mechanism.
`Figures 9a - 9e, and 10a and 10bare flow charts describing the general
`Steps followed by a Synchronization mechanism.
`Figures 11a - 11¢ are flow charts describing the general steps followed by
`a Change Existing Data mechanism.
`Figure 12is a tableillustrating the mail synchronization method ofthe
`present invention.
`
`Page 7 of 94
`
`Page 7 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`6-
`
`Figure 13 is a table illustrating exemplary mail synchronization scenarios
`where there are messages/folders with the same Key Field values.
`
`
`
`DETAILEDDESCRIPTIONOFTHEINVENTION
`
`Thepresent invention provides a method and an apparatus for a storage
`efficient mechanism suchthat users can address E-mail off-line on their
`SmartPhonesor Personal Digital Assistant’s (PDA’s), without devotingalarge
`amountof storage space for a database or having to frequently consult a remote
`database for extra E-mail related information such as by looking up E-mail
`addresses on a network server. The method and the apparatusof the present
`invention involves automatically generating, storing and maintaining a subset of a
`large address book containing E-mail addresseslocally on a client device with
`limited storage space such as a SmartPhone. The advantage of storing the E-mail
`addresseslocally on the client deviceis that users can address and compose E-mail
`off-line. This reduces connection time and cost required to send messages.
`Periodically, the data in the personal address book is synchronized with data in a
`master address book. The present invention therefore provides an easy-to-use
`methodfor generating a default personal address book automatically and an
`efficient method for keeping a personal address book synchronized with a master
`database.
`Figure 1a is an exemplary system block diagramillustrating the method
`and apparatusof the present invention. The present invention stores a subset of a
`given large address book(also referred herein as a master address book) locally on
`a SmartPhoneor any otherclient device such as a PDA (Personal Digital Assistant)
`to decrease connection time and enhance responsiveness to E-mail address
`
`requests.
`E-mail agent 100 runs continuously on a user's PC (personal computer) or
`network server 102, periodically checking for new messages. Additionally, E-
`mail agent 100 takes appropriate actions suchasto notify the user if a message is
`urgent. E-mail agent 100 is coupled to MAPI (Messaging Application
`Programming Interface) 105 which is a standard API (Application Programming
`Interface) for transferring and manipulating mail messages, MS Mail 101 which is
`an application used to access mail through MAPI (Mail Application Program
`
`Page 8 of 94
`
`Page 8 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-7-
`
`Interface), VIM (Vendor Independent Messaging) 109 whichis also a standard
`APIfor transferring and manipulating mail messages and cc: Mail 103 which is an
`application based on VIM foraccessing mail. The system is designed so that other
`mail API’s and applications can be supported.
`E-mail client application 104 runsonclient device 106 such as a
`SmartPhoneandallowsa user to compose messages, access his or her network E-
`mails and to manage messagefolders. Periodically, E-mail client application 104
`and E-mail agent 100 connectthrough a telephonecall (or through serial cable,
`LAN,etc.) to synchronizetheir states.
`Figure 1b illustrates an exemplary system block diagram ofthe present
`invention. Computer 102 has memory 114 coupled to CPU 116. Memory 114
`has mail synchronization 112 and various other elements 110 (also referred herein
`as subsetter 110) for subsetting a large E-mail address book to generate a smaller
`E-mail address book for client device 106. Further, computer 102 may have
`various peripheral devices 118 such as a keyboard and/or a display device.
`Computer 102 is also coupledto client device 118 as wasillustrated in Figure La.
`Figure Ic illustrates various componentsof the present invention residing
`on host device 102 and client device 106 respectively. Host device (desktop or
`server) 102 has PIM (Personal Information Manager) 120 whichstores contact
`names and numbers(i.e. addressing information). Host PC 102 also has creator
`122 forinitial creation of personal address book (PAB) 128, updator 123 for
`maintaining changes to PAB 128 based on new messages and changesin the
`network databases, mailbox 124 for storing all received and sent mail messages
`and MAB(master address book) 126 for storing E-mail directory information.
`MAB126 maybe a corporate address book if a user is on a LAN(localarea
`network) or may be a personal“master address book”ofa userif the useris ata
`stand alone PC. PAB (Personal Address Book) 128 in host device 102 is for
`Storing addresses, names, numbers, etc., (i.e. addressing information). PAB 128
`maybe periodically updated for changestoits addressentries. Source ID
`(identification) table 127 is a list of sources from which data for PAB 128 may be
`obtained. Sources of data for PAB 128 maybe by user manual entry, from MAB
`126, from PIM 120, etc. Each sourceis given a unique identifying number.
`Additionally, host device 102 also has DABI (Device Address Book Image) 130
`
`Page 9 of 94
`
`Page 9 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-8-
`
`which maybe stored in PAB 128 andis equivalentto the size of the limited storage
`area of DAB (Device Address Book) 132 of client device 106.
`More specifically, DABI 130 of host device 102 is a mirror image of DAB
`132 of client device 106. In one embodimentof the present invention, DABI 130
`is part of PAB 128(i.e. a subset of PAB 128).
`In this embodiment, whenever
`PAB 128 is updated, DABI 130 is automatically updated as well.
`In another
`embodimentof the present invention, DABI 130 maybe separate from PAB 128.
`In this alternate embodiment, DABI 130 may be updated according to the changes
`made to PAB 128. In both embodiments, whenever DABI 130 of host device 102
`is updated, DABI 130 ofhost device 102 and DAB 132 ofclient device 106 are
`synchronized with each other using address synchronizer 121. During
`synchronization, if an address in DAB 132 of host device 102 is no longerin
`DABI 130ofclient device 106, then the corresponding entry in DAB 132is
`deleted. Otherwise, if an address in DAB 132 of host device 102 is in DABI 130
`of client device 106, then the entire corresponding entry in DAB 132is replaced
`with the corresponding updated entry in DABI 130.
`Client device 106 may be various remoteclient devices such as a
`SmartPhone, a PDA or a notebook PC. Both host PC 102 andclient device 106
`have an application (e.g. E-mail systems), appO 134 and app! 136 respectively,
`for which the subsetting and the synchronization of the address books are being
`performed.
`PIM 120, Mailbox 124 and MAB126 mayreside on network server 127
`instead of on host PC 102. Morespecifically, modulesillustrated in host PC 102
`may exist locally (on host PC 102) or remotely (on network server 127) and it is
`assumedthat a network will take care of remote access if needed(i.e. for
`Mounting Network Volumes, Remote Procedure Calls, etc.). Such network
`implementation may be understood by a personskilled in the art given the detailed
`description of the present invention illustrated herein.
`Figure 1d illustrates an exemplary PAB 128 ofthe presentinvention. Each
`address entry 133 has variousfields 135, source IDs 137 and address entry
`ranking score 139. Theillustrated exemplary fields 135 are E-mail addressfield,
`name field and home phonefield. Eachfield 135 has a corresponding source ID
`137 which identifies what the source of the contents of field 135 is.
`
`Page 10 of 94
`
`Page 10 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-9-
`
`DABI 130 of host device 102 and DAB 132ofclient device 132 are
`subsets of PAB 128 and are formatted similar to PAB 128 with variousfields 135
`associated with selected address entries 133.
`With the present invention,it is assumedthata userof client and host
`device 106 and 102is likely to want to communicate with those users with whom
`he or she has communicated with in the past. Aspart of installation module 131
`for installing a client device E-mail host device connection (described in Figure le
`and the accompanying description),all the E-mail messagesin a given user's E-
`mail folders and archives are scannedanda list of E-mail addresses including
`mailing list names which are all the cohorts the user has corresponded with are
`compiled. Thelist also includesall the recipients copied on the messages.
`The namesand mailing lists of cohorts communicated with are then used to
`match against the names in MAB 126of a E-mail system such as CC: Mail 103 or
`MS Mail 101. The matching address entries are then automatically pulled out to
`form PAB 128. Each matching address entry 133 in PAB 128 contains the same
`informationas the corresponding MAB 126 entry, such as phone numbers, mail
`stops, etc. Additional information mayalso be retrieved from other applications
`(i.e. sources) which include address books, such as external contact databases or
`personal information managers (PIMs) 120. For non-matching entries’ (cohorts
`that are not in MAB 126) additional information such as phone number, mail stop,
`etc. for fields 135, may be retrieved from other sources (e.g. a contact database or
`PIM 120). The user mayalso be prompted to manually add additional information
`that was not included in MAB 126, the contact database, or PIM 120.
`Further, a user mayoptionally edit, add or delete address entries 133 from
`PAB 128 The user can also optionally specify PIM 120to be used to import
`additional contact information for the records in MAB 126. PIM 120 is also used
`if there is no data in the corporate address book.
`Since client device 106 such as SmartPhoneshavelimited storage that may
`notbe able to store the entire PAB 128, two capabilities are used to resolve this
`problem. First, only selected fields 135 of the additional information for address
`entries 135 are copied to DAB 132ofclient device 106 from PAB 128 (i.e. DABI
`130), minimizing the memory used by each address entry 133. Second, PAB 128
`is maintained as a ranked list according to address ranking score 139, and only the
`
`Page 11 of 94
`
`Page 11 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-10-
`
`highest ranked entries (most likely used) are copied into DAB 132 ofclient device
`106.
`
`To keep PAB 128 synchronized automatically, the present invention stores
`a duplicate of the user's PAB 128 on his or her PC 102 or network server 127.
`When a new E-mailis received, the present invention automatically checksif the
`sender and other users copied on the messageare in the compiled PAB 128. If so,
`the present invention updatesthe priority listing by updating address ranking score
`139. If not, the addresses are added to PAB 128 in the same manneras described
`above. Periodically, such as once a day, the present invention checks the PC copy
`of the user's PAB 128 against MAB 126.
`Anyentries including mailing lists which have been deleted from the
`network database (e.g. when a given useris no longer with the company) are
`deleted from the user's PAB 128. Any entries which have been changed such as
`whena user has a new phone numberare updated. Likewise, changesin fields
`from contact databases or PIM’s are also deleted and updated. The changesto the
`PABare queued on PC 102 and periodically transmitted to client device 106 for
`updates. Since it is very time consuming to periodically check the PC copyof the
`user's PAB 128 against MAB 126 andto perform the deletion and updates,
`updates to PAB 128 maybe performed whentheuseris not using his or her PC
`102.
`
`Additionally, a user may manually add additionalinformation(i.e. contents
`of fields 135 of PAB 128) when newentries are added to PAB 128. Since the
`update is being performed as a backgroundtask (possibly onthe server), the
`manually added fields 135 are left blank and a queue of addressentries 133
`needing informationis kept so the user canlater be notified and add the fields 135.
`Occasionally, a user may need to address a person notin his or her PAB
`128. In this case the user is given two options. The first option is to have E-mail
`client application 104 dial-up to connect to E-mail agent 100 and browsethe entries
`stored in PAB 128, MAB 126, or PIM 120. The second option is to allow the
`user to manually type and use an address without searching any address books.
`Thelatter option is useful for new contacts that would not be in an address book.
`Figure leillustrates the general steps followed in an exemplary installation
`procedureinstalling the present invention's client device E mail host device
`connection.
`In step 151, a user’s E-mail folders are scanned to find all the cohorts
`
`Page 12 of 94
`
`Page 12 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-11-
`
`that have been communicated with. Each cohort is added to PAB 128 witha
`numeric score reflecting how the address wasused(i.e. author of received
`message, destination of sent message, copied on sent message,etc.). If the cohort
`wasalreadyin thelist, then the score is increased. The result is a rankedlist ofall
`cohorts communicated with in the form of address ranking score 139.
`In step 152, MAB 126is scanned. Forillustration purposes,it is assumed
`that MAB 126 is a corporate E-mail directory. As entries are found that match the
`cohorts’ addresses, additional information in the corporate E-mail directory is
`copied to PAB 128. For example,the full name of the address is copied, along
`with the employee ID, mail stop, department, and phone number. For those
`address entries not found in the corporate E-mail directory (for example,off-site
`E-mail cohorts and recent new hires), no additional information is added durin£
`this stage of the installation procedure.
`In step 153, the user is given the option to include additional information
`that was not included in the corporate E-mail directory. If this optionis selected,
`then the user is prompted for PIM 120, contact database, or manual entry as the
`source (or sources) of this additional information. Installation module 131 scans
`the known sources for the cohorts communicated with. For example, a user may
`select to find additional information from a PIM such as ECCO from NetManage
`or from manualentry if empty fields are found.
`The additionalfields selected in ECCO contain home phone numbers,
`cellular phone numbersand mail addresses. As entries are found in the ECCO
`database, they are also copied into PAB 128. Along with eachfile stored in PAB
`128, there is a corresponding identifier 137 that indicates the source ofthe
`information containedin that field (MAB 126, PIM, Database, Manual Entry,
`etc.). The identifier is used later for synchronization of changes back to the source
`as will be described later. After scanning all known sources ofadditional
`information, there may still be emptyfields. The user can optionally enterthis
`information manually.
`In step 154,installation module 131 copies a portion of PAB 128(i.e.
`DABIT 130) to client device 106. The result is DAB 132. First the user selects
`whichfields of the PAB 128 should be included in DAB 132. For example, only
`the full name, work number, cellular number and home phone numberfields of
`PAB 128 may beselected. Installation module 131 then computes how many
`
`Page 13 of 94
`
`Page 13 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-12-
`
`entries can be copied onto DAB 132ofclient device 106 and copies only these
`entries starting with the highest ranking entry.
`Figures 2a through 2d, and 5 through 13 illustrate an exemplary method
`and apparatus for data synchronization which may be adaptedfor use in the
`present invention’s address synchronization process. Given the detailed
`description disclosed herein, such implementation of the address synchronization
`processof the present invention may be readily understood by a person skilled in
`the art.
`
`Figure 2ais a block diagram illustrating a mail synchronizer. Mail
`synchronizer 112 synchronizes changes made independently on an e-mail system
`on two separate computers or two different e-mail systems on the same computer.
`Pseudo unique ID (identification) generator 200 generates a pseudo unique ID for
`each mail orfolder in a mail box for an e-mail system. Event log generator 202
`generates an event log by generating events for each ID (i.e. for each mail or
`folder). Synch mechanism 204 synchronizes the mail boxes using the generated
`event logs.
`Figure 2b illustrates a block diagram of the ID generatorillustrated in
`Figure 2a. ID generator 200 has unique attribute selector 206 and ID creator 208.
`Uniqueattribute selector 206 selects an attribute that is most likely to be unique
`given a mail or a folder. ID creator 208 generates an ID for each mail or folder in a
`mail box.
`
`Figure 2c is a block diagram of the event log generatorillustrated in Figure
`2a. Event log generator 202 has mail event log generator 210 and folder event log
`generator 212. Mail event log generator 210 generates an eventfor the event log
`for each mail in mail boxes to be synchronized. Folder event log generator 212
`generates an event for the event log for each folder in the mail boxes to be
`synchronized.
`Figure 2d is a block diagram of the synch mechanism ofthe present
`inventionillustrated in Figure 2a. Synch mechanism 204 has sub-parts, Change
`Detection mechanism 230, Error Detection mechanism 234, Change Existing Data
`mechanism 238 and Synchronization mechanism 236. Change Detection
`mechanism 230 detects the changes which have occurred to a given mail box since
`the last synchronization. Error Detection 234 identifies incorrect updates and
`creates performed by Change Detection mechanism 230. Error conditions
`
`Page 14 of 94
`
`Page 14 of 94
`
`

`

`WO 97/41520
`
`PCT/US97/04719
`
`-13-
`
`triggering Error Detection 234 include when a record's Key Attribute has changed
`in MBO' and/or when more than one message/folderis sharing the same Key
`Attribute values (an example of a non-unique identifier case is described in more
`detail below). Synchronization mechanism 236, performsthe synchronization of
`data sets, given information regarding the mail boxes produced by Change
`Detection mechanism 230. Change Existing Data 238 modifies existing data to
`make the mail boxes equivalent.
`Figure3aillustrates the general steps followed by the creation mechanism
`(creator) 122illustrated in Figure 1c.
`In step 301, user setting according to the
`general steps followed in Figure 3b is obtained. (For a detailed description of the
`steps followed, turn to Figure 3b and the accompanying description).
`In step 302,
`PAB(Personal Address Book) 128is created following the general steps
`illustrated and described in Figure 3c.
`In step 303, DABI (Device Address Book
`Image) 130 is created following the generalstepsillustrated in Figure 3f. In step
`304, DAB (Device Address Book) 132 is created following the general steps
`illustrated and described in Figure 3g.
`Figure 3billustrates the general steps followed in obtaining user settings
`(step 301 of flow diagram in Figure 3a).
`In step 321, additional information
`sources are selected. The sources mayinclude, but are notlimited to, personal
`information managers, contact databases, or manual entry.
`In step 322, the user
`specifies what data fields are to be included in the device address book. The data
`fields are hereinafter referred to as “Additional Information”as they are in addition
`to the required E-mail address field. A sample of whatadditionalfields the user
`mayselect includes, butare not limited to, full name, work address, home
`address, work phone numbers, home phone number, cellular number, pager
`number, employee identification, birthday mail stop fields.
`In step 323, the ranking profile is selected. The rankingprofile consists of
`the score to be given to each entry depending on howanentry wasused. For
`example, a cohort that is cop