(12) United States Patent
`Us 6,650,998 B1
`(10) Patent N0.:
`(45) Date of Patent:
`*Nov. 18, 2003
`Rutledge et al.
`
`USOO6650998B1
`
`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
`
`HD
`
`(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.
`
`(21)
`
`(22)
`
`Appl. No.:
`Filed:
`
`08/901,249
`
`Jul. 28, 1997
`
`Related US. 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
`
`(63)
`
`(51)
`(52)
`(58)
`
`(56)
`
`4,811,244 A
`4,850,007 A
`5,109,399 A
`5,124,915 A
`5,193,185 A
`
`3/1989 Shimada et a1.
`............ 345/443
`7/1989 Marino et a1.
`.. 379/88.2
`
`..... 379/45
`4/1992 Thompson
`
`6/1992 Krenzel
`.....
`702/5
`3/1993 Lanter ........................ 707/101
`
`100
`1DAIABASE SEW/IR
`
`1
`
`,
`
`i
`§
`
`3
`j
`
`
`
`185
`comm sown?
`190
`[WE/LOCATION
`FILTER
`
`
`
`1
`115
`DATABASE HANDLER
`1
`7MODIM
`
`i
`1
`
`
`
`
`
`135 r ,wunrmzs
`
`
`
`cmmw mums:
`
`145 ,4
`7
`
`LDCATION/COORDINATES
`
`DAME/«SI
`comm DAIAEASE
`
`165 ’Ti 7
`
`
`
`
`
`
` DATABASE HANDLER
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`US 6,650,998 B1
`
`Page 2
`
`US. PATENT DOCUMENTS
`
`53257423 A
`379/93~08
`6/1994 Lewis
`-------------------
`
`5,392,223 A
`2/1995 Caci ..................... 709/218
`
`5,393,964 A
`2/1995 Hamilton 6191-
`-- 235/381
`
`5,414,462 A
`5/1995 Veatch ............
`.. 348/135
`
`5,426,780 A
`-
`~~~~~ 707/3
`6/1995 Gerull 61 211
`5,428,608 A
`6/1995 Freeman 61 211
`~~ 370/261
`
`5,452,353 A
`9/1995 Menezes ~~~~~~~
`~~ 379/355
`5,463,671 A
`.......
`. 379/56.1
`10/1995 Marsh et a1.
`
`5,470,233 A * 11/1995 Fruchterman 61 211
`~~ 434/112
`
`--
`-- 345/429
`5,475,802 A
`12/1995 Wescott et al-
`1/1996 Grimes ~~~~~~~~~
`340/721
`5,481,590 A
`
`~~ 379/93-22
`5,515,424 A
`5/1996 Kenney ~~
`
`
`6/1996 Fortier ----------------- 707/2
`55307851 A *
`7/1996 Nimura 61 211
`5537324 A
`~~ 701/208
`5,559,707 A
`9/1996 DeLorme et al-
`-- 701/200
`5,602,903 A *
`2/1997 1613121110 61 211
`~~ 455/456
`5,682,525 A
`10/1997 Bouve 61 211
`-
`~~ 707/104
`5,701,469 A * 12/1997 Brandli et a1.
`.. 707/102
`5,727,057 A *
`3/1998 Emery et a1.
`.. 379/211
`.
`3:33:33 2
`2/133:
`321111023211~~~~~
`-- 733/533
`
`5,764,736 A
`6/1998 Shaeiar et a1.
`..
`.. 379/93.09
`6/1998 Edelstein et a1.
`........... 709/219
`5,764,906 A *
`
`-
`
`6/1998 Johnson ................... 379/93.23
`5,771,280 A
`8/1998 Sklar et a1.
`................. 345/356
`5,790,121 A
`12/1998 Kettler et a1.
`............ 348/1408
`5,844,597 A
`...... 705/27
`5,852,810 A * 12/1998 Sotiroff et a1.
`.
`
`5,855,015 A * 12/1998 Shoham .........
`707/5
`2/1999 Krishnaswamy et a1.
`5,867,494 A *
`370/352
`5,893,093 A *
`4/1999 Wills ............................. 707/5
`5,914,951 A
`6/1999 Bentley et a1.
`370/352
`5,919,247 A
`7/1999 Van Hoff et a1.
`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 et a1.
`.
`701/211
`5,944,768 A *
`8/1999 Ito et a1.
`........
`340/990
`5,944,769 A
`8/1999 Musk et a1.
`701/201
`5,990,886 A
`11/1999 Serdy et a1.
`................ 345/329
`5,999,525 A * 12/1999 Krishnaswamy et a1.
`370/352
`6,044,205 A *
`3/2000 Reed et a1.
`................. 709/201
`
`6,067,500 A *
`5/2000 Morimoto et a1.
`340/988
`........... 709/229
`6,138,162 A
`10/2000 Pistriotto et a1.
`
`
`
`
`
`
`OTHER PUBLICATIONS
`Loshin, P., “Tune In, Turn On the Web”, BYTE, Feb. 1997,
`V22’ “2’ p‘ 145—6‘
`* cited by examiner
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 1 0f 9
`
`US 6,650,998 B1
`
`FIG.
`
`1
`
`100
`
`...................S
`EDATABASE SERVER
`i
`1
`i
`25
`s
`i
`i
`i
`
`
`
`185
`CONTROL SERVER
`190
`TIME/LOCATION
`FILTER
`
`§
`g
`
`LOCATION/COORDINATES
`DATABASE
`
`
`
`
`
`
`
`
`110
`
`r _I
`
`195 -
`
`
`i
`_
`A
`_
`3 a
`E
`DATABASE HANDLER
`g
`115
`5
`;
`;
`
`
`
`
`
`g
`g
`
`120
`
`~
`
`
`
`I
`
`
`
` WEB CRAWLER
`180
`
`TIME STAMP
`
`INTERNET
`
`‘95
`
`mg } DATABASE HANDLER
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 2 0f 9
`
`US 6,650,998 B1
`
`.mmN
`
`MN.QNK
`
`
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 3 0f 9
`
`US 6,650,998 B1
`
`305 COUNTRY
`
`315 STATE
`
`
`
`325 COUNTY
`
`
`7
`335 TOWN
`
`345 NEIGHBORHOOD
`
`
`
`FIG. 4A
`
`w Search Connect Hotlist Settings
`
`
` File Edit
`
`
`Jump to Place...
`
`
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 4 0f 9
`
`US 6,650,998 B1
`
`FIG. 4B
`
`Places in "New Jerse " W
`
`Brielle
`
`@Ab
`
`Atlantic Highlands
`
`Avenel
`
`Avon
`
`Belmor
`
`FIG. 40
`
`move
`
`Move current viewpoint:
`
`l:l
`
`0 kilometers
`
`Aft
`DD-
`S”;
`
`a
`
`El
`
`, 9.07
`
`J
`
`C) miles
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 5 0f 9
`
`US 6,650,998 B1
`
`FIG.
`
`4D
`
`24 0 Countries
`
`zoom
`
`23 O
`
`22 O
`
`21 O
`
`20 0 States
`
`19 O
`
`18 O
`
`17 O
`
`16 O
`
`15 O Counties
`
`
`
`11 0 Cities
`
`OOOOOOOOOOO
`
`Buildings
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 6 0f 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
`
`
`
`
`
`DETERMINE REQUIRED
`
`
`
`
`
`
`
`
`CORRESPONDING TO CLOSET
`
`
`HIGHER ZOOM LAYER AND
`
`LAT/LONG. GO TO STEPS
`
`
`DISPLAYED MAP TILES
`
`516 AND 518 AND RETURN
` 524
`
`
`RECEIVE A ZOOM COMMAND ?
`
`514
`
`YES
`IS ZOOM COMMAND WITHIN
`SAME HIGH/LOW LAYER ?
`NO
`
`CHECK THE CLOSEST HIGHER
`
`ZOOM LAYER
`
`RETRIEVE TILES
`
`DISPLAY RETRIEVED TILES
`
`
`
`
`
`
`
`
`516
`
`DEGREE OF RESOLUTION
`
`BASED ON ZOOM
`
`COMMAND
`
`ADD OR SUBTRACT
`
`518
`
`THEMATIC OVERLAYS
`
`FROM CURRENTLY
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 7 0f 9
`
`US 6,650,998 B1
`
`FIG. 6
`
`File
`
`Edit
`
`,1:
`
`Connect
`
`Hotlist
`
`Settings
`
`Directory Search...
`
`Current Searches...
`
`mm
`
`ElAuto - fetch
`
`(9 Days
`
`Geographical Area ?
`
`_
`0 Unrestricted
`6) mile radius around HOME
`0 Current View
`
`How long should the
`request stay in place ?
`
`El Just this once
`a One Day
`El One Week
`El One Month
`
`0 Minutes
`
`Update every
`
`0 Hours
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 8 0f 9
`
`US 6,650,998 B1
`
`File
`
`Edit
`
`Connect
`
`Hotlist
`
`Settings
`
`Directory Search...
`
`Web Search...
`
`Ad Search...
`
`toyota
`
`."jesse james’, outlaw
`maple sugar industry
`squash <and> racquet
`used car prices,
`
`View Resuits
`
`FIG. 8
`
`’\
`&,
`Q}
`a,
`s"
`\é‘
`$5
`s
`gem gs»
`<0
`01$
`0" @840"
`as
`s“
`§§®§V
`"nu w
`
`R,
`0%
`5s
`s*
`at
`
`<9
`\\$
`as
`§
`s“
`
`&,
`®
`as
`§
`0*
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`US. Patent
`
`Nov. 18, 2003
`
`Sheet 9 0f 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)
`
`
`
`
`MAXLAT > minlat AND
` MINLAT < maxlat AND
`
`"'0'
`
`MINLONG < maxlong AND
`MAXLONG > minlong
`
`YES
`
`
`
`KEEP RECORD
`
`980
`
`
`
`
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`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 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`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,
`NJ.) 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, NJ.
`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 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`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 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`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 of counties that
`map database 145 maintains. Databa