(12) United States Patent
`Rutledge et al.
`
`USOO6650998B1
`US 6,650,998 B1
`*Nov. 18, 2003
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54)
`
`(75)
`
`(73)
`(*)
`
`(21)
`(22)
`
`(63)
`
`(51)
`(52)
`(58)
`
`(56)
`
`INFORMATION SEARCH SYSTEM FOR
`ENABLING A USER OF AUSER TERMINAL
`TO SEARCHA DATA SOURCE
`
`Inventors: Charles Wayne Rutledge, Whitehouse
`Station, NJ (US); Norman Ashton
`Whitaker, Jr., Atlantic Highlands, NJ
`(US)
`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................................................. G06F 17/30
`U.S. Cl. .................
`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
`
`4,811,244 A 3/1989 Shimada et al. ............ 345/443
`4,850,007 A 7/1989 Marino et al. ....
`... 379/88.2
`5,109,399 A 4/1992 Thompson ....
`... 379/45
`5,124.915 A 6/1992 Krenzel .....
`... 702/5
`5,193,185 A 3/1993 Lanter ........................ 707/101
`
`5,315,636 A 5/1994 Patel .......................... 455/461
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`O574138 A1 12/1993 ............ HO4N/7/15
`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 Point Cast 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. A mechanism 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
`
`00
`
`: DATABASE SERVER
`25
`
`| s=
`WHE PAGES
`
`:
`
`GEOGRAPHYDATABASE
`145 is
`
`LOCATION/COORDINATES
`DATABASE
`
`CONTEN CATABASE
`
`:
`| 165
`
`
`
`O
`
`85
`CONTROL SERVER
`190
`Tyt/Lotation H
`TER
`
`DAABASEHANDLER
`is
`
`ODE
`
`
`
`AABASE HANDLER
`
`IPR2020-00686
`Apple EX1010 Page 1
`
`

`

`US 6,650,998 B1
`Page 2
`
`
`
`U.S. PATENT DOCUMENTS
`
`5,771,280 A 6/1998 Johnson ................... 379/93.23
`5,790,121 A 8/1998 Sklar et al. ................. 345/356
`5,844,597 A 12/1998 Kettler et al. ............ 348/14.08
`5,325,423 A 6/1994 Lewis ................... 379/93.08
`5,852,810 A * 12/1998 Sotiroff et al. .
`... 705/27
`5,392.223 A 2/1995 Caci ........................... 709/218
`5,855,015 A * 12/1998 Shoham .........
`707/5
`5,393,964 A 2/1995 Hamilton et al.
`... 235/381
`5,867,494. A * 2/1999 Krishnaswamy et al. ... 370/352
`5,414.462 A 5/1995 Veatch ............
`... 348/135
`5,893,093 A * 4/1999 Wills ............................. 707/5
`5,426,780 A 6/1995 Gerull et al. .................. 707/3
`5,914,951 A 6/1999 Bentley et al. ...
`370/352
`5,428,608 A 6/1995 Freeman et al.
`... 370/261
`5,919.247 A 7/1999 Van Hoff et al. ........... 709/217
`5,452,353 A 9/1995 Menezes .......
`... 379/355
`5,930.474. A 7/1999 Dunworth et al. .......... 709/217
`5,463,671 A 10/1995 Marsh et al. .......
`379/56.1
`5.835,236 A * 8/1999 Barbari.............
`. 358/442
`5,470.233 A * 11/1995 Fruchterman et al. ...... 434/112
`5,938,721. A * 8/1999 Dussell et al. .
`... 701/211
`5,475.802 A 12/1995 Wescott et al. ..
`... 345/429
`5,944,768 A * 8/1999 Ito et al.........
`... 340/990
`5,481,590 A
`1/1996 Grimes .........
`... 34.0/7.21
`5,944,769 A 8/1999 Musket al. ...
`... 701/201
`5,515,424 A 5/1996 Kenney ..
`... 379/93.22
`5.990,886 A 11/1999 Serdy et al. ................ 345/329
`5,530,851 A
`6/1996 Fortier .......................... 707/2
`5.999.525 A * 12/1999 Krishnaswamy et al. ... 370/352
`5,537,324 A 7/1996 Nimura et al.
`... 701/208
`6,044,205. A
`3/2000 Reed et al. ................. 709/201
`5,559,707 A
`9/1996 DeLorime et al.
`... 701/200
`6,067,500 A * 5/2000 Morimoto et al. .......... 340/988
`5,602.903 A * 2/1997 LeBlanc et al. .
`... 455/456
`6,138,162. A 10/2000 Pistriotto et al. ........... 709/229
`5,682,525 A 10/1997 Bouve et al. .
`... 707/104
`5,701,469 A * 12/1997 Brandli et al.
`... 707/102
`OTHER PUBLICATIONS
`5,727,057 A * 3/1998 Emery et al. .
`... 379/211
`3. A
`E.- - - - -
`": Loshin, P., “Tune In, Turn On the Web”, BYTE, Feb. 1997,
`5,764,736 A
`6/1998 Sai O. o,
`v22, n2, p. 145-6.
`5,764.906 A * 6/1998 Edelstein et al. ........... 709/219
`* cited by examiner
`
`IPR2020-00686
`Apple EX1010 Page 2
`
`

`

`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 1 of 9
`
`US 6,650,998 B1
`
`FIC. 1
`
`100
`
`10
`
`RLO
`f
`
`r- - - - - - - -
`
`- a m n unu -
`
`- - - -- 19
`
`DATABASE SERVER
`125
`
`185
`CONTROL SERVER
`190
`TIME/LOCATIONH
`FILTER
`
`DATABASE HANDLER
`115
`
`MODEM
`
`:
`
`
`
`:
`
`1705 C
`lsIEs DataBaseDATABASE
`
`Ll - - - - - - - - - - - - - - - - w - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - a
`
`w--a a
`
`hur a
`
`sur - - - - - - - -
`
`- r
`
`110
`
`120
`
`Our
`
`
`
`WEB CRAWLER
`180
`TIME STAMP
`
`
`
`INTERNET
`
`195
`
`is.” ) DATABASE HANDLER
`
`IPR2020-00686
`Apple EX1010 Page 3
`
`

`

`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 2 of 9
`
`US 6,650,998 B1
`
`{{2 * 5)I, H.
`
`
`
`IPR2020-00686
`Apple EX1010 Page 4
`
`

`

`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 3 of 9
`
`US 6,650,998 B1
`
`305 COUNTRY
`
`315 STATE
`
`325 COUNTY
`
`-335 TOWN
`
`345 NEIGHBORHOOD
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 4A
`
`
`
`File Edity
`
`IPR2020-00686
`Apple EX1010 Page 5
`
`

`

`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 4 of 9
`
`US 6,650,998 B1
`
`FIG. 4B
`
`iump to location
`
`C ) HardDisk
`
`Drive
`Conce
`
`Places in "New Jersey W.
`3Abescon
`Atlantic Highlands
`Avenel
`AVOn
`Belmor
`Brielle
`
`OWe
`
`FIC. 4C
`
`
`
`Move current viewpoint:
`
`4.
`O<GF=E>O
`ty
`
`(O miles
`O kilometers
`
`IPR2020-00686
`Apple EX1010 Page 6
`
`

`

`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet S of 9
`
`US 6,650,998 B1
`
`FIG.
`
`4D
`
`
`
`ZOO
`
`24 O Countries
`23 O
`22 O
`21 O
`20 O States
`19 O
`18 O
`17 O
`16 O
`15 O Counties
`
`11 O Cities
`
`Buildings
`
`IPR2020-00686
`Apple EX1010 Page 7
`
`

`

`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 6 of 9
`
`US 6,650,998 B1
`
`FIG. 6
`
`MAINTAIN CURRENT TILE ID's BEING
`DISPLAYED AND CORRESPONDING
`HIGH, LOW ZOOM LAYER AND
`LAT/LONG OF CENTER OF
`CURRENT WIEWPOINT
`
`514
`
`RECEIVE A ZOOM COMMAND 2
`YES
`IS 700M COMMAND WITHIN
`SAME HIGH/LOW LAYER 2
`NO
`CHECK THE CLOSEST HIGHER
`ZOOM LAYER
`
`516
`DETERMINE REQUIRED
`DEGREE OF RESOLUTION
`BASED ON 700M
`COMMAND
`
`RETRIEVE TILES
`CORRESPONDING TO CLOSET
`HIGHER 700M LAYER AND
`LAT/LONG. GO TO STEPS
`516 AND 518 AND RETURN
`
`
`
`
`
`
`
`
`
`518
`
`ADD OR SUBTRACT
`THEMATIC OVERLAYS
`FROM CURRENTLY
`DISPLAYED MAPTILES
`
`
`
`
`
`DISPLAY RETRIEVED TILES
`
`524
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IPR2020-00686
`Apple EX1010 Page 8
`
`

`

`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 7 of 9
`
`US 6,650,998 B1
`
`
`
`File
`
`Edit
`
`View
`
`Search
`
`Connect
`
`Hotlist
`
`Settings
`
`Ad Search.
`Current SeOrches...
`
`Web SeOrch
`
`O Auto - fetch
`
`Geographical Area ?
`
`OUnrestricted
`(O20 mile radius around HOME
`O Current View
`
`How long should the
`request stay in place 2
`O Just this Once
`O One Day
`O One Week
`DOne Month
`
`Update every
`
`O Minutes
`O Hours
`
`IPR2020-00686
`Apple EX1010 Page 9
`
`

`

`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 8 of 9
`
`US 6,650,998 B1
`
`FIC. 7
`
`
`
`File
`
`Edit
`
`View
`
`Connect
`Search
`Directory Search.
`
`Hotlist
`
`Settings
`
`Web Search.
`Ad Search...
`
`IRS income tax legislation
`2 "jesse james', Outlaw
`maple sugar industry
`squash {and> rocquet
`used COr prices, toyoto
`
`FIG. 8
`
`S. Sk s-
`& SY S S
`& S S is
`$ss
`\ys
`\y
`NS
`NS
`& SKS &
`SS & SS & S.
`N
`SY S.
`N
`MAX LAT
`TEXT IN AT TIME
`N
`
`Sw
`
`&
`SS
`
`Sw
`S
`
`IPR2020-00686
`Apple EX1010 Page 10
`
`

`

`U.S. Patent
`
`Nov. 18, 2003
`
`Sheet 9 of 9
`
`US 6,650,998 B1
`
`FIG. 9
`
`910
`
`RECEIVE:
`QUERY (NEW REQUEST BIT, TIME REFERENCE,
`MINLAT, MAXLAT, MINLONG, MAXLONG) AND
`RECORD (LAST MODIFIED, miniat, maxlot,
`minlong, moxlong
`)
`
`920
`TIME EARLIER THAN LAST MODIFIED 2
`
`MINLAT K maxlot AND
`MAXLAT X miniot AND
`MTNLONG < maxlong AND
`MAXLONG > minlong
`YES
`KEEP RECORD
`
`
`
`980
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`930
`
`
`
`
`
`
`
`
`
`940
`DISCARD RECORD
`(TOOOLD)
`
`970
`DISCARD RECORD
`WRONG AREA
`
`IPR2020-00686
`Apple EX1010 Page 11
`
`

`

`1
`INFORMATION SEARCH SYSTEM FOR
`ENABLING A USER OF AUSER TERMINAL
`TO SEARCHA 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
`
`15
`
`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
`is tuned (e.g., “Sports News/NFL) and thus, unlike with
`text String Searching, cannot truly customize his Subscrip
`tion.
`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
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,650,998 B1
`
`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. A user 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
`
`IPR2020-00686
`Apple EX1010 Page 12
`
`

`

`15
`
`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
`Sites by following hypertext links over the a computer
`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.
`A control 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
`65
`management perspective, Aronoff, Stanley WDL
`Publications, (Ottawa, Canada 1989); and (4) Geographic
`
`45
`
`50
`
`55
`
`60
`
`US 6,650,998 B1
`
`25
`
`35
`
`40
`
`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
`
`IPR2020-00686
`Apple EX1010 Page 13
`
`

`

`S
`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
`
`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
`
`US 6,650,998 B1
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`IPR2020-00686
`Apple EX1010 Page 14
`
`

`

`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 database 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 hiera