(12) United States Patent
`Rutledge et al.
`
`(10) Patent N0.:
`
`(45) Date of Patent:
`
`US 6,650,998 B1
`*Nov. 18, 2003
`
`US006650998B1
`
`5,315,636 A
`
`5/1994 Patel
`
`........................ .. 455/461
`
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`.......... .. H04N/7/15
`12/1993
`0574138 A1
`OTHER PUBLICATIONS
`
`N.S., “My Yahoo? News Ticker”, PC Magazine, Feb., 18,
`1997, V16, n4, p. 143.
`D.L., “NETdelivery”, PC Magazine, Feb., 18, 1997, v16, n4,
`p. 143.
`Mace, T., “The PointCast Network”, PC Magazine, Feb. 18,
`1997, V16, n4, p. 143.
`
`(List continued on next page.)
`Primary Examiner—Ella Colbert
`(74) Attorney, Agent, or Firm—Morgan & Finnegan, L.L.P.
`
`(57)
`
`ABSTRACT
`
`A network-based search system in which queries and infor-
`mation records are qualified by temporal and geographical
`references, such as those provided by a map-based directory
`system. Briefly, queries are submitted using text strings
`together with time tags and location tags. Time tags and
`location tags refer to the date/time the query was last
`submitted for a search and the geographical area of interest
`(defined by ranges of latitude and longitude coordinates),
`respectively. The information records being searched pref-
`erably contain similar time and location tags. However, time
`and location tags associated with information records refer
`to the date/time the record was last modified and the origin
`of the record, respectively. Amechanism is also provided for
`determining location tags for records that do not include
`location tags. In all, a comparison between the time and
`location tags associated with a query and the time and
`location tags associated with the information records permits
`geographically irrelevant records to be suppressed and
`allows the user to automatically receive only information
`that has been modified since the user last requested it. Thus,
`search results are automatically pre-filtered prior to being
`transmitted to the user who originated the query, which
`conserves network resources and reduces the amount of
`
`context-based filtering required of the user.
`
`2 Claims, 9 Drawing Sheets
`
`(10
`
`(54)
`
`(75)
`
`INFORMATION SEARCH SYSTEM FOR
`ENABLING A USER OF A USER TERMINAL
`TO SEARCH A DATA SOURCE
`
`Inventors: Charles Wayne Rutledge, Whitehouse
`Station, NJ (US); Norman Ashton
`Whitaker, Jr., Atlantic Highlands, NJ
`(US)
`
`(73)
`
`Assignee: AT&T Corp., New York, NY (US)
`
`(*)
`
`Notice:
`
`This patent issued on a continued pros-
`ecution application filed under 37 CFR
`1.53(d), and is subject to the twenty year
`patent
`term provisions of 35 U.S.C.
`154(a)(2).
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`Appl. No.: 08/901,249
`
`Filed:
`
`Jul. 28, 1997
`
`Related U.S. Application Data
`
`Continuation—in—part of application No. 08/824,106, filed on
`Mar. 25, 1997, which is a continuation—in—part of application
`No. 08/613,307, filed on Mar. 11, 1996, now abandoned.
`
`Int. Cl.7 .............................................. .. G06F 17/30
`. 701/211; 701/213; 707/3
`
`Field of Search ................ .. 707/1, 5, 10, 100-104,
`707/200-206; 434/112, 116; 455/12.1, 406,
`412, 434, 456, 457, 466; 701/211; 370/352;
`358/442
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`.......... .. 345/443
`3/1989 Shimada et al.
`.. 379/88.2
`7/1989 Marino et al.
`379/45
`4/1992 Thompson
`702/5
`6/1992 Krenzel
`3/1993 Lanter ...................... .. 707/101
`
`
`
`4,811,244 A
`4,850,007 A
`5,109,399 A
`5,124,915 A
`5,193,185 A
`
`(21)
`
`(22)
`
`(63)
`
`(51)
`(52)
`(58)
`
`(56)
`
`(DD
`1 DAIABASE SERVER
` nmmonv |)AlABAS[
`1
`§
`I3n<—_
`_
`3
`‘~
`YELLOW PAGES
`I35 2’
`,WHITE PAGES
`
`
`
`'
`
`555555555555555555555555555555
`‘K5
`comm SERVER
`190
`IIME/LOCATION
`rim
`
`1
`1
`
`DATABASE HANDLER
`H5
`NWT
`1
`
`
`Microsoft Corp. Exhibit 1005
`
`
`
` DATABASE HANDLER
`
`Microsoft Corp. Exhibit 1005
`
`

`
`US 6,650,998 B1
`Page 2
`
`6/1998 Johnson ................. .. 379/93.23
`5,771,280 A
`8/1998 Sklar et al.
`............... .. 345/356
`5,790,121 A
`12/1998 Kettleretal.
`.......... .. 348/14.08
`5,844,597 A
`5,852,810 A =x< 12/1998 Sotimff et al.
`.
`.... N 705/27
`5,855,015 A * 12/1998 Shoham ....... ..
`707/5
`5,867,494 A =x<
`2/1999 Krishnaswamy et al.
`370/352
`5,893,093 A *
`4/1999 Wills ........................... .. 707/5
`5,914,951 A
`6/1999 Bentley et al.
`370/352
`5,919,247 A
`7/1999 Van Hoff etal.
`709/217
`5,930,474 A
`7/1999 Dunworth et a1.
`709/217
`5,835,236 A *
`8/1999 Barbari ........... ..
`358/442
`5,938,721 A *
`8/1999 Dussell etal.
`.
`701/211
`5,944,768 A *
`8/1999 Ito etal. ...... ..
`340/990
`5,944,769 A
`8/1999 Musk et 6.1.
`701/201
`5,990,886 A
`11/1999 Serdy etal.
`.............. .. 345/329
`5,999,525 A * 12/1999 Krishnaswamy et al.
`370/352
`6,044,205 A *
`3/2000 Reed et al.
`............... .. 709/201
`6,067,500 A *
`5/2000 Morimoto etal.
`340/988
`6,138,162 A
`10/2000 Pistriotto et al.
`......... .. 709/229
`
`
`
`OTHER PUBLICATIONS
`Loshin P. “Tune In Turn on the Web” BYTE Feb. 1997
`’
`’
`’
`’
`’
`‘'22’ “2’ P‘ 145-6‘
`* cited by examiner
`
`’
`
`Microsoft Corp. Exhibit 1005
`
`U.S. PATENT DOCUMENTS
`
`379/9308
`~~~~~~~~~~~~~~~~~ ~~
`6/1994 Lewis
`5,325,423 A
`. . . .. 709/218
`2/1995 Caci . . . . . . . . . . . . . . . .
`5,392,223 A
`~~ 235/381
`2/1995 Hamilton eta1~
`5,393,964 A
`.. 348/135
`5/1995 Veatch .......... ..
`5,414,462 A
`707/3
`6/1995 Gemll eta1~ ~
`5,426,780 A
`~~ 370/261
`6/1995 Freeman et 91
`5,428,608 A
`~ 379/355
`9/1995 Menezes ,,,,, ~
`5,452,353 A
`. 379/56.1
`10/1995 Marsh et al.
`..... ..
`5,463,671 A
`~~ 434/112
`5,470,233 A * 11/1995 Fmehteiman eta1~
`~~ 345/429
`5,475,802 A
`12/1995 WeSe0tteta1~ ~~
`340/721
`5,481,590 A
`1/1996 Grimes ~~~~~~~ ~~
`~ 379/9322
`5,515,424 A
`5/1996 Kemiey ~
`5,530,851 A *
`6/1996 Feitiei ~~~~~~~~~~~~~~~ ~~ 707/2
`5,537,324 A
`7/1996 Nimma eta1~
`~~ 701/208
`5,559,707 A
`9/1996 DeL0ime eta1~
`~~ 701/200
`5,602,903 A *
`2/1997 LeB1ane eta1~ ~
`~ 455/456
`5,682,525 A
`10/1997 Beiive eta1~ ~
`~ 707/104
`5,701,469 A * 12/1997 Brandlietal.
`.. 707/102
`.
`5,727,057 A *
`3/1998 Emery et 6.1.
`.. 379/211
`5737533 A
`4/1998 D6 H0114 ~~~~ ~~
`~~ 799/219
`5,740,549 A
`4/1998 Reill etal.
`..
`705/14
`5,764,736 A
`6/1998 shaeiar et al.
`.. 379/93.09
`5,764,906 A *
`6/1998 Edelstein et al.
`......... .. 709/219
`
`
`
`..
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 1 of 9
`
`US 6,650,998 B1
`
`FIG.
`
`1
`
`000000000000000000000000000000000000000000000000000000000000000000000000000‘H
`‘
`185
`CONTROL SERVER
`190
`TIME/LOCATION
`FILTER
`
`
`
`110
`
`195
`
`
`
`,
`"
`_
`DATABASE HANDLER
`115
`
`
`
`E
`
`5
`;
`;
`
`E
`g
`
`
`
`«D-— N
`
`LOCATION/COORDINATES
`DATABASE
`
`§
`g
`
`SITES DATABASE
`______________________
`
`I
`
` WEB CRAWLER
`180
`
`
`TIME STAMP
`
`110
`
`I
`
`_
`
`
`
`12o
`
`
`
`_____________
`INTERNEI
`‘95
`5% } DATABASE HANDLER
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 2 of 9
`
`US 6,650,998 B1
`
`Inpa
`N
`
`FIG.2B
`
`235
`
`FIG.2A
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 3 of 9
`
`US 6,650,998 B1
`
`FIG. 3
`
`VIRTNU0C503
`
`345 NEIGHBORHOOD
`
`FIG. 4A
`
`File Edit
`
`Search Connect Hotlist Settings
`
`Jump to Place...
`Move
`
`Zoom...
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`
`
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 4 of 9
`
`US 6,650,998 B1
`
`FIG. 4B
`
`Places in "New Jerse " W
`
`Atlantic Highlands
`Avenel
`
`Avon
`
`Belmor
`
`Brielle
`
`FIG. 4C
`
`move
`
`Move current viewpoint:
`
`|:|
`
`J
`
`‘i‘
`BE‘W,
`
`El
`
`0 W.»
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 5 of 9
`
`US 6,650,998 B1
`
`FIG. 4D
`
`zoom
`
`(‘D U)
`
`9
`
`Os:(‘F2CDc...9’W
`
`O O O O O O O O O O O
`
`l\)[\)l\Jl\>l\)CJ103\l1£DCD_.l\.)CN-5
`
`O
`
`OBOOOOOOOO
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 6 of 9
`
`US 6,650,998 B1
`
`FIG. 5
`
`
`
`
`MAINTAIN CURRENT TILE ID’s BEING
`DISPLAYED AND CORRESPONDING
`
`HIGH, LOW ZOOM LAYER AND
`
`LAT/LONG OF CENTER OF
`
`CURRENT VIEWPOINT
`
`
`
`RECEIVE A ZOOM COMMAND ?
`
`YES
`
`51
`
`IS ZOOM COMMAND WITHIN
`SAME HIGH/LOW LAYER ?
`NO
`
`
`
`
`
`DEGREE OF RESOLUTION
`
`516
`
`
`DETERMINE REQUIRED
`
`BASED ON ZOOM
`
`
`ZOOM LAYER
`
`COMMAND
`
`CHECK THE CLOSEST HIGHER
`
`
`
`
`
`
`
`
`518
`
`
`
`
`
`
`
`
`ADD OR SUBTRACT
`
`THEMATIC OVERLAYS
`
`FROM CURRENTLY
`
`DISPLAYED MAP TILES
`
`Microsoft Corp. Exhibit 1005
`
`
`
`RETRIEVE TILES
`CORRESPONDING TO CLOSET
`
`HIGHER ZOOM LAYER AND
`LAT/LONG. GO TO STEPS
`516 AND 518 AND RETURN
`
`DISPLAY RETRIEVED TILES
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 7 of 9
`
`US 6,650,998 B1
`
`FIG. 6
`
`File
`
`Edit
`
`Connect
`
`Hotlist
`
`Settings
`
`Directory Search...
`
`Current Searches...
`
`Search Terms=::|
`
`ElAuto - fetch
`
`Geographical Area ?
`
`.
`O Unrestricted
`© mile radius around HOME
`0 Current View
`
`How long should the
`request stay in place ?
`
`El Just this once
`B one Day
`3 one week
`'3 0"° M°”th
`
`Update every
`
`0 Minutes
`0 Hours
`(9 Days
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 8 of 9
`
`US 6,650,998 B1
`
`File
`
`Edit
`
`Connect
`
`Hotlist
`
`Settings
`
`Directory Search...
`
`Web Search...
`
`IRS income tax legislation
`"jesse james’, outlaw
`maple sugar industry
`squash <and> racquet
`used car prices,
`toyota
`
`View Resuus
`
`it
`
`FIG. 8
`
`%"
`’<“
`$8
`
`a.
`<‘
`‘v
`<s,
`%"
`'3’ <§‘
`'®‘
`®
`xii“
`$5’ x\
`01“
`\>"<‘
`<i9<$¥"
`‘#3
`§3“*
`ts‘
`e>‘\§‘°«x\"
`Iilfl MIN W W W
`
`\\§"
`®
`\9‘‘
`xx\“
`
`s,
`®
`:$‘
`®‘‘
`0*
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 9 of 9
`
`US 6,650,998 B1
`
`FIG. 9
`
` RECEIVE:
`QUERY (NEW REQUEST BIT, TIME REFERENCE,
`MINLAT, MAXLAT, MINLONG, MAXLONG) AND
`
`910
`
`
`
`RECORD (LAST MODIFIED, minlat, maxlat,
`minlong, maxlong)
`
`
`
`
`
`
`
`
`MINLAT < maxlat AND
`
`MAXLAT > minlat AND
`
`MINLONG < maxlong AND
`MAXLONG > minlong
`
`YES
`
`
`
`KEEP RECORD
`
`980
`
`
`
`
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`US 6,650,998 B1
`
`1
`INFORMATION SEARCH SYSTEM FOR
`ENABLING A USER OF A USER TERMINAL
`TO SEARCH A DATA SOURCE
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation-in-part of application
`Ser. No. 08/824,106,
`filed, Mar. 25, 1997, which is a
`continuation-in-part of application Ser. No. 08/613,307,
`filed, Mar. 11, 1996, now abandoned, both of which are
`incorporated herein by reference.
`
`FIELD OF THE INVENTION
`
`This invention relates generally to an information search
`system and, more specifically, to a network based informa-
`tion search system in which information queries and records
`are qualified by time and/or geographical references
`
`BACKGROUND OF THE INVENTION
`
`It has become routine for a user of a personal computer to
`search a large distributed data source, such as the internet,
`for information relevant to a topic of interest. With the aid
`of a browser such as Netscape and a search engine such as
`Alta Vista, Lycos or Yahoo, the user can perform text string
`searches for the desired information. Although text string
`searches provide users with the ability to customize each
`search, text string searches of large distributed databases
`often produce thousands of hits, many of which are irrel-
`evant to the user’s topic of interest. As one can imagine,
`subsequent filtering of the search results by the user is a
`tedious and time consuming process. Furthermore, a user
`who repeats a search to obtain the most up-to-date informa-
`tion must compare the search results against information
`from earlier searches to filter the updates, thereby adding to
`the user’s burden.
`
`Alternatively, a user may subscribe to an on-line maga-
`zine or newsgroup, which are known in the art as informa-
`tion “push” systems, to receive globally broadcast informa-
`tion of interest without having to transmit a search request.
`The user can “tune” to one of a limited number of channels
`to obtain the information of interest. However, the user is
`limited to the broad classification of the channel to which he
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`is tuned (e.g., “Sports News/NFL”) and thus, unlike with
`text string searching, cannot truly customize his subscrip-
`tion.
`
`45
`
`As such, there is currently no way for a user to perform
`text string searches of a data source in a manner that
`significantly increases the percentage of relevant “hits” and
`thus decreases the amount of time spent by a user filtering
`search results.
`
`SUMMARY OF THE INVENTION
`
`A technical advance is achieved in the art by providing a
`method and system for a geographical information search
`system.
`A system and method are disclosed for searching a data
`source using text string searches in which queries and
`information records are qualified by temporal and/or geo-
`graphical references. In an exemplary embodiment, tempo-
`ral and geographical references associated with a query are
`the date/time the query was last submitted by a user and the
`user’s geographical area of interest (defined by ranges of
`latitude and longitude coordinates), respectively. The tem-
`poral and geographical references associated with an infor-
`mation record are the date/time the record was last modified
`
`50
`
`55
`
`60
`
`65
`
`2
`and the “origin” of the record, respectively. A comparison
`between the temporal and geographic references associated
`with a query and those associated with the information
`records in the data source permits geographically irrelevant
`records to be suppressed and allows an individual user to
`receive only information that has been modified since the
`user last requested it. Thus, search results are automatically
`pre-filtered prior to transmission to the user thereby con-
`serving network resources and reducing the amount of
`context-based filtering required of the user.
`Other and further aspects of the present invention will
`become apparent during the course of the following detailed
`description and by reference to the attached drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The subject matter regarded as the invention is particu-
`larly pointed out and distinctly claimed in the concluding
`portion of the specification. The invention, however, both as
`to organization and method of operation,
`together with
`advantages thereof may be best understood by reference to
`the following detailed description when read with the
`accompanying drawings in which:
`FIG. 1 illustrates a block diagram of a communications
`network that employs an embodiment of a geographical
`information search system in accordance with the present
`invention.
`FIGS. 2A and 2B illustrate two embodiments of a data
`
`structure wherein spatial data in a map database are stored
`in accordance with the present invention.
`FIG. 3 illustrates an exemplary manner wherein geo-
`graphical regions for display are categorized in accordance
`with one embodiment of the present invention.
`FIGS. 4A—4D illustrate the menu screens relating to a
`“view” function which are available to the user of a geo-
`graphical information search system in accordance with one
`embodiment of the present invention.
`FIG. 5 is a flow chart illustrating the process for varying
`the zoom level of a map displayed on a terminal in accor-
`dance with one embodiment of the present invention.
`FIGS. 6 and 7 illustrate the menu screens relating to a
`“search” function which are available to the user of a
`
`geographical information search system in accordance with
`one embodiment of the present invention.
`FIG. 8 illustrates the format of a search query in accor-
`dance with one embodiment of the present invention.
`FIG. 9 is a flow chart illustrating the process for filtering
`records retrieved in response to a search query in accordance
`with one embodiment of the present invention.
`FIG. 10 illustrates the format of a database storing infor-
`mation that relates place names to geographical extents in
`accordance with one embodiment of the present invention.
`
`DETAILED DESCRIPTION
`
`FIG. 1 illustrates a block diagram of a communications
`network that advantageously employs an embodiment of a
`geographical information search system in accordance with
`the present invention. As shown in FIG. 1, a plurality of user
`terminals 110 such as personal computers are configured to
`access a database server 100. Auser can access the database
`
`server 100 via either a modem 115 or a computer commu-
`nications network such as the internet 120.
`
`Database server 100 includes a directory database 125,
`which preferably stores yellow pages (i.e., business) and
`white pages (i.e., residential) listings (130, 135). Each listing
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`US 6,650,998 B1
`
`3
`may include name, telephone number and other relevant
`information. The database server 100 also includes a geog-
`raphy database 140, which comprises two components: a
`map database 145 and a location/coordinates database 150.
`The map database 145 stores geographic regions categorized
`into map tiles and zoom layers as will be discussed in detail
`hereinafter. The location/coordinates database 150 stores
`information correlating “place names” (e.g., Monmouth,
`N.J to a range of location coordinates defined in terms of
`latitude and longitude, as will be discussed in detail here-
`inafter.
`
`In addition, database server 100 includes a content data-
`base 160, which,
`like the geography database 140, also
`comprises two components: an advertising database 165 and
`a sites database 170. The advertising database 165 stores
`advertising information preferably relating to entities having
`listings in the directory database 125. The sites database 170
`stores web sites (e.g., URLs), each referenced by a text
`string that describes the contents of the site. The sites
`database 170 is populated autonomously by a network agent
`such as a web crawler 175. The web crawler 175 searches for
`
`links over the a computer
`sites by following hypertext
`communications network such as the internet. Upon finding
`a site, the web crawler 175 adds the site to the sites database
`170 together with a time stamp 180. The time stamp
`indicates the date and time that the site was added to the
`
`database. Upon revisiting a site, the web crawler 175 will
`determine if the site has been modified since it was first
`
`found and, if it has been, the web crawler 175 will update the
`corresponding time stamp accordingly.
`Acontrol server 185 manages and supervises the activities
`of the database server 100. Control server 185 is coupled to
`the directory database 125,
`the map database 145,
`the
`location/coordinates database 150, the advertising database
`165, and the sites database 170. The database server 100
`receives requests for information from computer terminals
`110 and in response to such requests takes appropriate
`actions as will be discussed in detail hereinafter. These
`
`requests include performing string-based searches of the
`various databases (125, 165, 170) and viewing geographical
`regions stored in map database 145. As shown in FIG. 1, the
`control server 185 includes a time/location filter 190 for
`filtering search results, as will also be discussed in detail
`hereinafter.
`
`In accordance with one aspect of the present invention,
`each computer terminal 110 includes a database handler 195,
`which is configured to transmit search queries to database
`server 100, as will be described in detail hereinafter. The
`database handler 195 is also configured to operate in accor-
`dance with the principles of a geographic interface system
`(GIS). To this end, database handler 195 receives informa-
`tion relating to geographic regions, which are retrieved from
`map database 145 and combines this information with
`predetermined information retrieved from directory data-
`base 125 and advertising database 165 to display an image
`of a geographic region together with directory or advertising
`information relating to an entity depicted on the image, as
`discussed in detail in application Ser. No. 08/824,106.
`The operation of geographic interface systems (GIS) is
`well-known and described, for example, in: (1) SAGE Intro-
`ductory Guidebook, Robert M. Itami and Robert J. Raulings,
`DISR (Melbourne, Australia, 1993); (2) Principles of Geo-
`graphical Information Systems for Land Resources
`Assessment, Clarendon Press, Oxford University Press,
`(New York 1986); (3) Geographic Information Systems: A
`management perspective, Aronoff, Stanley WDL
`Publications, (Ottawa, Canada 1989); and (4) Geographic
`
`4
`Information Systems: An Introduction, Star, Jeffrey, and
`Estes, John E. Prentice-Hall, Inc. (Englewood Cliffs, N.J.
`1990). Commercially available geographic information sys-
`tems may be obtained from Eliris, Inc., and Arc/Info, Inc.
`Generally, database handler 195 is a computer program
`installed in each computer terminal 110. In accordance with
`one embodiment of the present invention, database handler
`195 operates as a geographic information system (GIS).
`Database handler 195 is used for retrieving, analyzing, and
`displaying map data, corresponding to geographical maps,
`stored in map database 145 in conjunction with customer
`record data stored in customer directory database 125. To
`this end, the Earth’s features are not only represented in
`pictorial form, as in conventional paper maps, but as infor-
`mation or data.
`
`The data stored in map database 145 contains all the
`spatial information relating to conventional geographical
`maps. With the aid of a geographic information system
`(GIS),
`this spatial data is advantageously displayed, on
`computer terminal 110, just like a paper map with roads,
`rivers, vegetation and other features represented as lines on
`a map complete with legend, border and titles. At least one
`important
`feature of geographic information systems
`(GIS’s) is that the information stored in map database 145 is
`stored in a structured format referred to as a spatial database.
`The way spatial data are structured allows the user to store,
`retrieve and analyze the information.
`FIGS. 2A and 2B illustrate two examples of methods
`wherein spatial data in map database 145 is stored. FIG. 2A
`illustrates an example, where map features are stored in
`vector format. To this end, data is stored as a series of points,
`lines and polygons, such as points 200,
`lines 205, and
`polygons 210, with a substantially high degree of accuracy.
`In accordance with one embodiment of the invention, build-
`ings are preferably represented as polygons or points having
`a given size corresponding to the actual size of the building.
`Roads and rivers are preferably represented by lines having
`given lengths and widths corresponding to their actual
`dimensions.
`
`FIG. 2B illustrates another example, where map features
`are stored in raster or grid format. A matrix of cells 240
`generalize the location of features on a map. Many geo-
`graphic information systems may be configured to handle
`both vector and raster data from a wide variety of sources
`including satellite imagery, hand digitized maps and scanned
`images.
`As illustrated in FIGS. 2A and 2B map information in
`map database 145 is represented thematically. A standard
`topographic map will show roads, rivers, parks, and building
`patterns and other features on a single map sheet. In a
`geographic information system (GIS) these features are
`categorized separately and stored in different map themes or
`overlays. For example, roads are preferably stored in a
`separate overlay 215. Likewise, rivers and streams are
`preferably stored in a separate overlay 220. Parks are stored
`in a separate overlay 225, and buildings are stored in a
`separate overlay 230. This way of organizing data makes
`maps much more flexible to use since these overlays or
`themes can be combined in any manner that
`is useful.
`Furthermore, updating map information may be accom-
`plished more easily. As illustrated in FIG. 2b, information
`stored in raster format appears less realistic than that stored
`in vector format.
`
`In accordance with one embodiment, each thematic over-
`lay is advantageously separated in additional corresponding
`overlays, although the invention is not limited in scope in
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`US 6,650,998 B1
`
`5
`that respect. For example, overlay 215 corresponding to
`roads, may comprise many road overlays, with roads in each
`overlay categorized on a hierarchial basis. Preferably, inter-
`state highways are stored in one overlay, and state highways
`in another overlay and local roads in still another overlay.
`Likewise, overlay 220, corresponding to parks, may com-
`prise many park overlays, with parks in each overlay cat-
`egorized on the basis of size. For example, large state parks
`may be stored in one overlay, and smaller city and neigh-
`borhood parks may be stored in another overlay. This
`overlay categorization allows the user to view each retrieved
`map with a predetermined degree of resolution. As more and
`more layers are combined, more detail appears on the map
`being displayed.
`In one embodiment, geographical regions available for
`display are also categorized into tiles and zoom layers as
`illustrated in FIG. 3, with each tile and zoom layer defined
`by a range of latitude and longitude coordinates. For
`example, various maps with different scales may be stored
`in map database 145. FIG. 3 represents an exemplary zoom
`layer system for a map database system having five zoom
`layers, with each zoom layer a factor of eight greater in scale
`than the more detailed zoom layer below it.
`For example, zoom layer 305 includes a tile 300 that
`represents a portion of a general map of a country. Such a
`map, when displayed on computer terminal 110, illustrates
`gross details, such as state boundaries. Zoom layer 315
`includes a plurality of tiles 310, each of which represent a
`map relating to one or more states corresponding to the area
`represented by tile 300. Each tile 310 when displayed on
`computer terminal 110,
`illustrates more details of areas
`contained in a state. Zoom layer 325 includes a plurality of
`tiles 320, each representing a map of a county corresponding
`to the area represented by tiles 310. Each tile 320, when
`displayed on computer terminal 110, illustrates more details
`of areas contained in a county. Zoom layer 335 includes a
`plurality of tiles 330, each representing a map of a town
`corresponding to the area represented by tiles 320. Each tile
`330, when displayed on computer terminal 110, illustrates
`more details of areas contained in a town. Finally, zoom
`layer 345 includes a plurality of tiles 340, each representing
`a map of a neighborhood corresponding to the area repre-
`sented by tiles 330. Each tile 340, when displayed on
`computer terminal 110, illustrates details of areas contained
`in a neighborhood, including buildings. FIGS. 2a illustrates
`an exemplary map tile 235 that is formed by combining
`thematic layers 215 through 230. It will be appreciated that
`any combination of thematic layers 215 through 230 may be
`employed to form a map tile 235.
`Each zoom layer corresponds to a predetermined scale.
`Furthermore, each tile in each layer represents an actual
`length of a geographic region being represented in accor-
`dance with each zoom layer. Using this exemplary scaling
`system, each tile 340 of zoom layer 345 represents a square
`area with each side having an approximate length of 2000
`feet. Likewise each tiles 330 of zoom layer 335 represents
`a square area with each side having an approximate length
`of 3 miles. Tiles 320 of zoom layer 335, each represent a
`square area with each side having an approximate length of
`24 miles. Tiles 310 of zoom layer 315, each represent a
`square area with each side having an approximate length of
`194 miles. Finally tile 300 of zoom layer 305 represents a
`square area with each side having an approximate length of
`1550 square miles.
`It is to be noted that a plurality of overlay maps such as
`220 through 230 may correspond to each tile. Thus,
`the
`system allows each map region to be visualized at a prede-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`termined scale, depending on the zoom layer from which a
`tile, or portion of a tile, is being displayed. It also allows the
`user to control the degree of detail that is included in each
`tile being displayed, depending on the number of thematic
`layers used in a combination of overlays to display the tile.
`In addition to various themes or overlays 215 through 230
`and zoom layers 305 through 345, map database 145 also
`stores the label information relating to each location. A label
`information may comprise a text string; location of the label
`on the map; its orientation and size.
`In order to ensure that all images of maps stored in map
`database 145 overlay accurately,
`the data set
`is “geo-
`referenced” to a common coordinate system. For example,
`Universal Transverse Mercator (UTM) projection is com-
`monly used to define coordinates in the system. This tech-
`nique is well-known and thus,
`is not discussed in detail
`herein.
`
`Map database 145 represents an object-oriented database,
`in which each map record or map tile consists of a list of
`objects. Table -1- illustrates the data structure of an exem-
`plary map tile, although the invention is not limited in scope
`in that respect.
`
`Location
`
`Object List
`
`TABLE 1
`
`This is the reference location of the map tile identified with
`a unique map tile identifier.
`This is a list of map objects, which in general represent
`entities which can logically carry a single label (whether or
`not they are labeled). Examples of objects are: overlays
`that include streets, building outlines, parks, bodies of
`water, etc.; Labels (text strings, location of labels,
`orientation, etc.); Polygons (a set of filled polygons, drawn
`in order); Ranges of latitude and longitude coordinates;
`Directory Reference (objects that include pointers to the
`directory database. These pointers may comprise a unique
`identifier number (“ID#”) as discussed in detail in co-
`pending application Ser. No. 08/824,106.)
`
`Thus, personal computer terminal 110 may allow a user to
`retrieve and display images corresponding to map tiles or
`portions of map tiles from map database 145. Preferably, the
`user is able to zoom these images, starting at, for example,
`a very high altitude, where only gross details are visible,
`e.g., state boundaries, and gradually zoom into a given
`location until great detail is visible, such as building names,
`numbers and outlines. In response to a user’s commands as
`discussed in more detail hereinafter, database handler 195
`retrieves a selected map tile, and displays all the objects
`indicated in the corresponding object list of the map record.
`The user-interface of database handler 195 is described in
`more detail hereinafter with reference to FIGS. 4A—4D.
`
`FIG. 4A illustrates an example of a menu screen that is
`displayed in accordance with one embodiment of the inven-
`tion. The menu advantageously includes several function
`categories comprising: File, Edit, View, Search, Connect,
`Hotlist, and Settings, although the present invention is not
`limited in scope in that respect. The user may select any one
`of these functions, in response to which the database handler
`195 provides additional options available to the user.
`The file, edit, connect, hotlist and settings features,
`although advantageous, refer to additional capabilities of the
`user interface through which searches are initiated in accor-
`dance with one embodiment of the present invention. The
`operation of the file, edit, connect, hotlist and settings
`features is discussed in detail in application Ser. No. 08/824,
`106, which is incorporated herein by reference. Because the
`operation of these features is not essential to an understand-
`ing of the present invention, they are not discussed in detail
`
`Microsoft Corp. Exhibit 1005
`
`Microsoft Corp. Exhibit 1005
`
`

`
`US 6,650,998 B1
`
`7
`herein. In contrast, the operation of the View and search
`functions is discussed in detail hereinafter.
`
`FIGS. 4A—4D illustrate the menu options relating to the
`“view” function of data base handler 195. FIG. 4A illustrates
`
`an exemplary menu of features available when the “view”
`function is selected. In response to the selection of a viewing
`feature, database handler 195 sends a request to database
`server 100 to access and retrieve corresponding map tiles
`stored in map database 145.
`One of the features available under the “view” function is
`
`the “jump” to a location feature. In response to this request,
`database server 100 retrieves a list of all available map tiles
`in a hierarchial order. For example, the user may first browse
`the list of countries that map database 145 maintains a
`corresponding map tile therefor. In response, the user may
`select a desired country. Database server 100 then provides
`a list of map tiles that are associated with the desired
`country. These map tiles preferably relate to a list of states
`that map database 145 maintains. In response, the user may
`select a desired state. Database server 100 then provides a
`list of map tiles that are associated with the desired state.
`These map tiles preferably relate to a list