(12) Ulllted States Patent
`Du
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,732,120 B1
`May 4, 2004
`
`US006732120B1
`
`(54) SYSTEM AND METHOD FOR PROCESSING
`
`(75)
`
`Inventor: Mike Du, Ca1gary(CA)
`
`(73) Assignee: Geojet Information Solutions Inc.,
`Calgary (CA)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 829 days.
`
`<21) APP1- N0-= 09/149551
`(22)
`Filed:
`Sep. 3, 1998
`
`7
`
`.............................................. ..
`Int. Ci.
`.................................................. .. 707/104.1
`(52) U.S. Cl.
`Of Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..
`707/504: 517: 1: 2: 1041; 345/112: 352:
`226, 803, 968, 156, 163, 168; 340/990,
`995-1, 995-19
`
`(56)
`
`References Cited
`Us. PATENT DOCUMENTS
`
`5]:
`
`3/1993 Lafltef
`5,193,185 A
`1]:1ear1;fe1<r’«§’ete:i1ii1~
`2
`~
`»»
`6/1995 Gerull et ,1.
`5,426,780 A
`5/1998 Donovan et al.
`5,751,612 A
`.......... .. 707/100
`9/1999 Lampert et al.
`5,953,722 A *
`5,963,956 A * 10/1999 Smartt ...................... .. 707/104
`
`~~~~~~~~~~~~- 395/161
`
`
`.............. .. 701/208
`5,968,109 A * 10/1999 Israni et al.
`. . . . .. 707/100
`5,974,419 A * 10/1999 Ashby . . . . . . . . . . . . . . .
`6,047,280 A *
`4/2000 Ashby et al.
`................ .. 707/2
`6,282,489 B1 *
`8/2001 Bellesfield et al.
`....... .. 701/201
`
`* Cited by examiner
`Primary Examiner—Greta Robinson
`(74) Attorney, Agent, or Firm—Blake, Cassels & Graydon
`LLP; Terry L. Leia
`
`(57)
`
`ABSTRACT
`
`$f‘3f§E1£E§°1r‘3911131 2533310165r§fs‘}T§i§§d°tiff?f§?i§§‘f
`tion in tabular format in a second portion of a display. The
`text information is subdivided into a group table and a
`member list table. The group table lists named groups in
`tabular form and members of the groups are lrsted in the
`member
`table. Tabular infgrmation may include attach-
`ments which are capable of appearing as overlaid graphical
`representations on the geographic display. A method of
`coordinating the display of geographic graphical and tabular
`information provides hide/show capabilities for attachment
`graphics responsive to selection of tabular information. A
`method for modelling and storing ‘geographic data is dis-
`closed providing the steps of dividing the spatial extent
`.
`.
`.
`defined by geographic data into uniquely identified cells,
`grouping geographic data by cells, and storing grouped
`h'dt't1b'
`fildfdtb
`d
`;é;<;g;gt;;gn; gggggsgng my 6
`0 a
`a a
`'
`
`22 Claims, 2 Drawing Sheets
`
`25
`
`ZOOM +
`
`ZOOM -
`
`Map Attachment Groups
`- Shopping Centre
`- School
`— Goli Course
`- Parks
`- Lakes
`
`Name
`
`Address
`
`Capita|.............3025 Albion
`Lester............ ..901 Fair
`
`Louis...............3 Oaklee
`
`Maple............ ..123 Maison
`
`Page 1 of 10
`
`CORELOGIC EXHIBIT 1018
`
`

`
`U.S. Patent
`
`May 4, 2004
`
`Sheet 1 of 2
`
`US 6,732,120 B1
`
`25
`
`ZOOM +
`
`ZOOM -
`
`Map Attachment Groups
`
`— Shopping Centre
`-Schooi
`- G011 Course
`- Parks
`
`‘
`
`‘ \\
`‘
`
`§\: GP“ W
`
`232
`
`5
`ser Interface
`Adapter
`
`5
`.
`DISPIBY
`M3013?
`
`234
`
`228
`
`240
`
`‘
`
`p
`
`236
`
`Page 2 of 10
`
`

`
`U.S. Patent
`
`May 4, 2004
`
`Sheet 2 of 2
`
`US 6,732,120 B1
`
`306
`""
`
`
`
`National
`(country)
`
`graphica data
`spatial data
`
`
`
`302
`304
`
`
`
`Partitioning
`Strategy
`
`314
`
`Regional
`(State)
`
`Decreasing
`area
`
`315
`
`310
`r~“
`
`
`Local
`(Rural Munici at
`boundaries?
`'
`
`
`
`
`
`grap ica ata
`
`
`
`318
`
`
`
`308
`
`’-_/ Parcel
`
`
`
`
`
`graphical data
`spatial data
`
`
`
`FIG. 3
`
`Page 3 of 10
`
`

`
`US 6,732,120 B1
`
`1
`SYSTEM AND METHOD FOR PROCESSING
`AND DISPLAY OF GEOGRAPHICAL DATA
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to data organiza-
`tion and graphical displays and more particularly to a
`method and system for retrieving and displaying spatial
`data.
`
`BACKGROUND OF THE INVENTION
`
`Spatial data relating to positioning on the earth’s surface
`is generally referred to as geographic information. Geo-
`graphic information can include relative positioning infor-
`mation to locate specific locations on the earth’s surface as
`well as to locate features and boundaries. Systems for the
`storage and retrieval of such information are termed Geo-
`graphic Information Systems (GIS). Geographic Informa-
`tion Systems are computer processes, systems and data
`structures that deal with the management and processing of
`geographic based information. GIS systems generally fall
`into two categories, namely, file based systems and rela-
`tional database (RDB) based systems.
`File based GIS systems store geographic data in files in
`accordance with a predefined format which is determined by
`the vendor of the GIS system. GIS data files are used to
`record geographic information. The file contents are man-
`aged by a GIS system. File based GIS systems are self
`complete. Such GIS systems rely on internal formats to
`model and index spatial data for internal use within the
`geographic boundaries defined by the file. As a result, file
`based systems are usually fast when the GIS information is
`accessed from one file. However, management of file based
`GIS systems is difficult as the geographic area covered by a
`file is generally limited to a certain size. Accordingly, tens or
`hundreds of files can be required to store geographic infor-
`mation for areas covering large areas. There are several such
`systems available on the market including, for example,
`ESRI’s Arc/Info product which is a file based GIS system.
`Using such a file based system to manage the property based
`map of a city of approximately eight hundred thousand
`people requires significant resources including the need to
`maintain as many as three hundred files in the Arc/Info
`proprietary format.
`There are RDB based systems available in the market as
`well such as the VISION (trademark) system of System-
`house Ltd. For RDB GIS systems, data is stored in a
`relational database where it
`is managed by a relational
`database management system (RDBMS). With an RDBMS,
`only a single database is required in place of the many files
`relied upon by a file based GIS system. With an RDB
`system, each geographic object is represented as a record in
`a first table. A separate index table is used to store the spatial
`index of each geographic object. When retrieval of geo-
`graphic objects within a predefined spatial region is
`required, the index table is queried or examined to locate all
`objects which are within the query region. The records
`selected for the geographic objects are then retrieved from
`the first table. Access to geographic objects stored in an
`RDB system is generally characterized as slow or low speed
`when requiring large numbers of records to be retrieved and
`processed to satisfy a query.
`What is needed is a GIS system to present geographic
`objects with the speed and ease of file based systems while
`maintaining the data management benefits of an RDB sys-
`tem.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`SUMMARY OF THE INVENTION
`
`In a geographic information system (GIS), geographic
`data are organized by hierarchical levels. The upper level of
`the hierarchy include larger spatial objects such as national
`boundaries and national highways. The lower level includes
`smaller spatial extents such as land parcel boundaries. Each
`level in the hierarchy layers may have its own coordinate
`reference system and an associated coordinate transforma-
`tion system to transform a geographic location on the earth
`to the coordinate reference system used in the hierarchical
`level.
`
`In accordance with one aspect of the invention, the spatial
`extent of each layer or level of the hierarchy is subdivided
`by a predefined partitioning strategy. The partitioning strat-
`egy for
`the geographic extent may include any useful
`strategy to define a partition space within the boundaries of
`the geographic space of the hierarchical layer. For example,
`the geographic space can be partitioned using a partitioning
`strategy based on equal sized cell grids, voronoi diagrams,
`political jurisdiction boundaries or any user defined shape
`such as township boundaries or legal land descriptions. The
`partitioned space is called a partition, a sub-space or a cell.
`Each cell is assigned a unique identifier, such as a number,
`to uniquely identify the cell. The unique cell identifier is
`referred to as a spatial index.
`The extent of a hierarchical
`
`level contains numerous
`
`these
`In accordance with the invention,
`spatial objects.
`spatial objects are assigned a spatial index. The spatial index
`of a spatial object is defined by the cell the spatial object lies
`in. If one spatial object overlaps more than one cell than, its
`spatial index may be defined by the cell that the object
`overlaps with the most. Spatial objects on each level are
`grouped by their spatial indices, i.e. the cells they are located
`in. The grouped objects are stored in a long binary column
`of a table in a relational database along with another column
`storing the identification of cells. In this way, once the
`identification of a cell is known, the spatial objects over-
`lapping with the cell can be directly and quickly loaded from
`the long binary field. This approach to store the spatial
`objects with their spatial indices is called a space-based
`approach, compared to the object-based approach currently
`used in RDB based systems. In RDB based systems, the
`spatial indices are stored with spatial objects. In other words,
`the identification of a spatial object is the primary key in a
`spatial index vs. spatial object identification relational table.
`After the geographic space is partitioned by a partitioning
`strategy, GIS spatial data for a partition can be stored in a
`long binary field of a table in a relational database. The
`format of the long binary spatial data is user definable and
`conforms to the spatial data defined by the GIS system. For
`example, if the space is partitioned into 20 cells, there will
`be 20 records with long binary fields to hold the GIS spatial
`data corresponding to each cell.
`In another of its aspects, the invention provides a display
`system to display visual representations of geographic infor-
`mation in the form of a map displayed in a graphical display
`area overlaid by spatially coordinated attachments. The
`graphical display area of visual information depicting a map
`region of interest is overlaid with visual representations of
`attachments and is coordinated to a display area of textual
`information of a plurality of groups or collections of user
`defined categories of such attachments. The user defined
`categories group attachment objects corresponding to like
`attributes to form a collection of such objects. Each attach-
`ment object or member of the attachment group or attach-
`ment collection is capable of visual depiction at a location in
`
`Page 4 of 10
`
`

`
`US 6,732,120 B1
`
`3
`a graphical display of the map. The user defined categories
`are capable of further coordination with a user controllable
`tab list display area of information identifying particulars of
`each of the members of the collection or group of attach-
`ments. Collections or groups of attachments may be further
`grouped into super groups or categories.
`Selecting an attachment category in the category display
`area will cause a display of the attachment tabular informa-
`tion in a coordinated tabular display area. Selecting a record
`or item in the tabular display area will highlight the graphi-
`cal representation of the selected item in the graphical
`display area of the graphical display. Selecting a graphical
`representation of an item in the graphical display area will
`select the attachment category and the record (item) respec-
`tively in the category display area and the tab list display
`area. Thus, there are three coordinated information display
`areas which present graphical and textual information in an
`interrelated manner.
`
`In another of its aspects, the invention provides a display
`system providing a graphical display area to display visual
`representations of geographic information in the form of a
`map coordinated with textual descriptor displays. The dis-
`play area of visual information depicting a map region of
`interest is coordinated to a display area of textual informa-
`tion of a plurality of groups or collections of user defined
`categories. The user defined categories group objects having
`like attributes to form a collection of such objects. Each
`object or member of the group or collection references a
`location in the geographic display area. The user defined
`categories are capable of further coordination with a user
`controllable tab list display area of information identifying
`particulars of each of the objects or members of the category
`collection or group.
`In another of its aspects, the invention provides a map/
`attachment architecture. The inventive architecture comple-
`ments the invented space-based approach to model and store
`spatial data in a relational database. One drawback of the
`space-based approach is that
`it
`is difficult
`to search a
`particular spatial object although the identification of the
`spatial object can be packed in the long binary data blocks
`and the attributes of the spatial object can be stored in
`another table with the identification of the spatial object as
`the primary key. The map/attachment architecture separates
`spatial objects that are best modeled by an object-based
`approach from spatial objects that are best modeled by a
`space-based approach. The separation is subjective. For
`example, in a crime analysis system used by police services,
`the street map objects (street lines and street names) are map
`objects in the map/attachment architecture; the crime data
`(crime types and locations) are attachment objects.
`In
`another street maintenance system, street line segments are
`attachments. Generally, the map objects are spatial objects in
`a background map. They are often termed base map objects.
`Attachment objects are spatial objects users want to View
`and analyze in a spatial context. They are generally stored as
`records in a relational table, or records in several related
`tables. Each record (retrieved from one or more tables) is
`called an attachment object. An attachment is a collection of
`records retrieved from the same table or tables defined by the
`same search criteria. Attachment objects are further grouped
`by categories for easy management.
`In another of its aspects, the invention provides a structure
`to store attachments and attachment categories in a relational
`database. Two tables are used to store attachments and
`
`attachment categories. The schemas allow nested attachment
`categories.
`In yet another of its aspects, the invention provides a data
`structure and method to generalize the spatial translation of
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`an attachment object. The method enables the translation of
`spatial coordinates from other parameters such as street
`address. The translation produces spatial coordinates for an
`attachment that has storage and identification rules separate
`from that of the GIS system. The spatial coordinates trans-
`lation can be effected dynamically at run time or can be
`recorded in the data structure when an attachment record is
`inserted into the database.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The preferred embodiment of the invention together with
`useful variations will now be described with reference to the
`
`drawings in which:
`FIG. 1 depicts a graphical display in accordance with a
`preferred embodiment of the invention illustrating the dis-
`play of coordinated GIS information;
`FIG. 2 is a functional block diagram of a computer system
`adapted to execute the process of the GIS system of the
`present invention; and
`FIG. 3 is a diagram showing the hierarchical base map
`relationships for storage of GIS information in accordance
`with the present invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`FIG. 1 shows a representation of a graphical display
`produced in accordance with the principles of the invention.
`The display, referenced generally by reference numeral 8, is
`produced on a video display terminal showing output from
`a graphics processor such as,
`for example, a personal
`computer. The video display terminal and the components of
`a computer system to produce images on it are described in
`more detail with reference to FIG. 2. The graphical display
`8 is organized into three independent but interrelated display
`areas 10, 24 and 28, each having an associated set of
`graphical display controls.
`The right portion of the display 8 provides a graphical
`display area 10 to display a graphical representation of a
`region of -a geographic extent. For example, a map is shown
`which has been selected for viewing by the user. Adjacent to
`the display area 10 are graphical icons representing control
`means 12 and 14 which the user can interact with to scroll
`
`the map being displayed in display area 10 upwardly or
`downwardly. Typically, user interaction is achieved by the
`user manipulating a mouse device 210 (as shown in FIG. 2)
`to position a pointer icon 11 over control means 12 (for
`example) to cause the viewing region to move upwardly on
`the map. Similarly, horizontal control means 16 and 18 are
`used to move the viewing region in a leftward or rightward
`direction by interacting with control means 16 or 18.
`An image of the geographic extent in View is graphically
`displayed in graphical display area 10. The image displayed
`can be a bitmap image that has been converted to digital
`form (i.e. scanned in using an optical scanner, not shown) or
`the image can be generated from vector graphics depending
`on the native image system of the GIS system. Any particu-
`lar underlying graphical format that can be used to produce
`the image or map appearing in graphical display area 10 is
`useful. All that is required is that the format of the graphical
`data of the image is capable of producing a visual depiction
`of the map in the graphical display area 10. Coordinated
`with the display of the map image are spatial data which
`provide spatial references for particular points or coordi-
`nates within the area of the map depicted in the graphical
`display region 10. The use of such spatial data is described
`below and also in more detail with reference to FIG. 3.
`
`Page 5 of 10
`
`

`
`US 6,732,120 B1
`
`5
`
`Group display area 24 is used to list names of collections
`or groups of map attachments. The collections are named by
`the user to group attachments that are similar in accordance
`with predefined characteristics specified by the user. In the
`example list shown in group display area 24, there are five
`named collections of map attachments listed,
`they are:
`“shopping centre”, “school”, “golf course”, “parks” and
`“lakes”. The number of named attachment collections, or
`names, could be larger than is permitted to be displayed
`within group display area 24. In such a situation, the list of
`group names can be traversed by operating control buttons
`26 and 28 to move the group name list upwardly or down-
`wardly within the group display area 24. A group selection
`indicator 27 is provided to indicate to the user which group
`of map attachments has been selected. Atabular display area
`28 provides of list of text descriptions of the members
`corresponding to the selected group name indicated by
`group selection indicator 27.
`The group selection indicator 27 is shown by way of
`example as an arrow. The arrow is pointing to the group
`“school” to indicate the group is selected. As will be
`understood by those versed in the art, group selection
`indicator 27 can be any suitable visual indicator to signify
`the group selected or under consideration. For example, a
`coloured bar can be used to provide an alternate coloured
`background to the text of the selected group in place of the
`arrow pointer group selection indicator 27 shown in the
`group display area 24.
`Textual descriptions of the individual attachments corre-
`sponding to the group name selected by the group selection
`indicator 27 are displayed in tab list display area 28. The
`contents of tab list display area 28 is any textual information
`to identify individual members of the group selected. In the
`example shown, the “name” and “address” of individual
`“schools” are listed within tab list display area 28. When
`required, tab list display area 28 can be provided with scroll
`control means 30, 32, 34 and 36 to control the vertical and
`horizontal displacement of the tab list information appearing
`in tab list display area 28.
`Moving group selection indicator 27 can be configured by
`the user to cause a visual representation of the individual
`attachments that are members of the selected group to
`appear within the graphical display area 10. As shown in
`FIG. 1, an individual school
`is depicted by attachment
`graphic 30. This graphic 30 corresponds to a particular
`instance or member of the school group indicated by group
`selection indicator 27. The graphic 30 has been “attached” to
`the map using the spatial coordinates translated from the
`school to the coordinate system of the map. Once such an
`attachment is made, the corresponding attachment graphic
`30 is then Visually oriented to be graphically displayed or
`overlaid on the map at the map location corresponding to the
`particular school as depicted by graphic 30.
`Proximal to school graphic 30 is a text box 32 which
`contains textual information to identify or provide text of
`particulars of the school which is within the graphical
`display area 10. Text box 32 may appear automatically as the
`user manipulates group selection indicator pointer 27 to
`move to various groups along the list. In other words,
`interaction with the information displayed in group display
`area 24 can cause the tabular text appearing within tab list
`window 28 to change and can also cause the graphical
`depiction corresponding to particular attachments appearing
`within display area 10 to change. The graphical depiction of
`corresponding to attachments shown within display area 10
`can change in a number of ways. The graphical depiction of
`the attachment, for example school graphic 30, may change
`in appearance or colour, or it may cause a text box 32 to
`appear automatically. Alternately, selection of particular
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`groups within the group display area 24 may cause no
`change within the display area 10. Alternately, selection of
`the group “school” by positioning the group selection indi-
`cator 27 to that group may enable the pointer icon 11 to
`produce the text box 32 when the pointer icon 11 is proximal
`to a graphical depiction of the attachment that corresponds
`with the selected group. In the example given, when pointer
`icon 11 is translated proximal to school graphic 30,
`the
`display system of the invention responds by making text box
`32 visible with the contents to be shown, as for example,
`“Capital Hill School”.
`Referring to FIG. 2, there is shown a functional block
`diagram of a personal computer adapted to process the
`information to produce a graphical display in accordance
`with the invention. A personal computer has a CPU 214
`operating under an operating system such as OS/2
`(trademark)
`from IBM or WINDOWS (trademark) of
`Microsoft Corporation. The CPU communicates over com-
`munications data paths 216 with one or more peripherals
`including read only memory 218 used for power on self test
`and program loading when the computer is switched on. Run
`time data and programs under execution are loaded from a
`data disk 220 through an appropriate 10 adaptor 222 into
`program random access memory 224 for execution by CPU
`214. The operation of the programs controlling the computer
`are visually output to the computer user on a visual display
`226 which is operated by a display adaptor 228 intercon-
`nected with the data path 216. A communications adaptor
`230 may be provided to allow the computer to interact with
`external computers over a network such as a dial up access
`to the Internet over the public switch telephone network or
`access to a local area network of other computers. User
`interface adaptor 232 is provided to capture output from the
`user through interaction with various devices suited for that
`purpose including: a keyboard 234 which is used for text and
`typing forms of user input and a mouse 210 to provide
`positional forms of user input to locate user position indi-
`cator 11 previously described with reference to FIG. 1. Other
`user input/output devices may include a speaker 236 for
`providing audio output to the user and a microphone 240 for
`capturing audio input from the user.
`Referring to FIG. 3 there is shown a layered hierarchical
`data structure for storing the geographic information in
`accordance with the present
`invention. The hierarchy is
`organized from collections of maps where each map pro-
`vides a graphical data portion 302 and a spatial data portion
`304. Collections of maps relating to a larger geographic area
`are provided at the upper layer of the hierarchy 306. Col-
`lections of maps relating to a smaller geographic area are
`provided at the lower layer of the hierarchy 308. In the
`example data organized in accordance with the invention,
`the smallest geographic area is a parcel boundary map layer
`generally referenced by the reference numeral 308. The map
`information includes a graphical data portion 302 capable of
`producing a visual depiction of the map and a spatial data
`portion 304 to provide a coordinate system for positions
`within the plane or volume defined by the map.
`Additional map layers may be readily provided organized,
`for example, by increasing area including local regions such
`as rural boundaries or municipal boundaries as found for
`example within city limits. Data representing this larger
`geographic area is shown in the adjacent upper layer in the
`hierarchy at level 310. Other higher levels of mapping may
`also be included. For example, a regional map or a state map
`as shown in the hierarchy at 312. Similarly, a larger geo-
`graphic area can be depicted by a map including an entire
`nation or country as shown by hierarchical level 306.
`Where multiple levels in a hierarchy of map of increasing
`area are incorporated into the map database, it is necessary
`to establish relationships 314, 316 and 318 between adjacent
`
`Page 6 of 10
`
`

`
`US 6,732,120 B1
`
`7
`map levels in the hierarchy. The relation allows a user to
`“zoom down” by manipulating the user input devices, such
`as the mouse 210 to interact with display area 10 to update
`the display 10 to show the graphical data corresponding to
`the decreased area map next down in the hierarchy that
`corresponds to the portion of the increased area map graphi-
`cally then displayed within the visual display area 10. The
`interrelationship between adjacent levels of maps within the
`hierarchy are established by forward and backward relation-
`ships 314, 316 and 318. By providing spatial relationships
`between the increasing area maps and decreasing area maps,
`the user may interact with the graphical display 10 to zoom
`in or “drill down” for more detail or to zoom out for more
`coverage.
`
`A framework for hierarchical organization of spatial data
`in accordance with the invention as described above with
`
`reference to FIG. 3 can be implemented in a relational
`database system (RDB) such as, for example, Microsoft
`Access (trademark) database system or similar database
`system such as any Open Database Compliant (ODBC)
`database system. Spatial data corresponding to one cell
`spatial location of one instance of a map at one level of the
`hierarchy is stored as one record in the RDB database. The
`coordinates provided by the spatial data of the particular
`location can be saved as a long binary data type. The
`following is a table setting out the schema of such a database
`table:
`
`Columns
`
`Cell ID
`
`Type
`
`INT
`
`SCHEMA 1
`
`Meaning
`
`Identification (index) of the spatial cell
`
`Columns for non-spatial attributes
`
`Data
`
`Long Binary
`
`Spatial data within this group
`
`To understand the advantages of the invention, the fol-
`lowing example is given. Let us assume that a set of
`two-dimensional (2D) geographic objects are modeled by
`hierarchical levels. At level a given level, assume the space
`is partitioned by a set of coordinate grids resulting in 900
`cells. To further define the example, assume that within a
`selected cell, say cell 450, there are five hundred land parcels
`and one thousand texts at the level under consideration. Let
`us further assume that four tables are used to store these
`
`spatial objects in a conventional (two-dimensional) 2D
`RDB-based GIS system. In a conventional prior art 2D
`RDB-b ased GIS system, the schemas for such spatial objects
`are defined as follows.
`
`Prior Art
`
`Object ID Object Type
`
`Schema of Table: Spatial Object
`First
`Coordinate
`
`Point
`Sequence No.
`
`Second
`Coordinate
`
`Schema of Table: Iand Parcel
`
`Object ID
`
`Land Parcel ID
`
`Boundary Color
`
`Page 7 of 10
`
`Schema of Table: Text
`
`Object ID
`
`Text String
`
`Text Color
`
`Schema of Table: Spatial Index
`
`Object ID
`
`Spatial Index ID
`(Cell ID)
`
`With such a prior art 2D RDB based GIS system, in the
`example under consideration if each land parcel contains six
`points,
`then 4000 records of table: Spatial Object; 500
`records of table: Land Parcel; 1000 records of table: Text;
`and 1500 records of table: Spatial Index are needed to store
`the spatial objects in this selected cell. Thus, four tables and
`seven thousand records are used in total. When users want
`
`to browse spatial objects in this cell, the four tables have to
`be accessed to retrieve the seven thousand (7000) records.
`Then the retrieved data has to be processed to construct the
`500 land parcels and 1000 texts in a memory representation
`form for the spatial objects.
`However, if the same spatial objects of the example are
`stored in the data structure in accordance with the invention,
`only one record is needed as illustrated in the table defined
`by Schema 1 and as more particularly explained with
`reference to an example as follows:
`Method to Model and Store Spatial Data in a Relational
`Database
`
`Schema 1 depicts a schema in accordance with the
`invention to facilitate the modeling and storing of geo-
`graphic data in a long binary column of a table in a relational
`database. The first column is the cell ID (identification) of
`cells generated by a partitioning of the spatial extent defined
`by geographic data. The cell could be any shape in addition
`to a rectangle or a cubic. The data column is a long binary
`column to hold spatial objects that are within or intersect
`with the cell. There is provision for other columns to store
`non-spatial attributes common to the spatial objects packed
`in the long binary fields. For example, one non-spatial
`attribute could be an ID of the level the spatial objects are
`assigned to in a hierarchical modeling of spatial data.
`Another non-spatial attribute column could be a type code
`(line, polygon, text, etc.) of the spatial objects packed in the
`long binary data block. The significance of the data orga-
`nized in Schema 1 is that the spatial objects that are within
`or intersect with a cell are packed in a long binary data block
`and that the long binary data block is stored in the long
`binary field of a record identified by the ID of the cell.
`A schema in accordance with the Schema 1 as described
`
`provides the following advantages:
`1. The spatial data can be grouped by a predefined
`space-partitioning strategy. The grouped spatial data
`can be stored in a long binary format of a table in a
`relational database. The format of the long binary data
`can be identical to the internal representation of spatial
`objects inside a GIS system. Accordingly, the spatial
`objects can be loaded into memory directly group by
`group with one record retrieval. No conversion from
`the representation of spatial data in the Schema 1
`format to the representation in the internal GIS format
`is required.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`
`US 6,732,120 B1
`
`9
`2. Because the geographical objects are grouped and
`stored in a long binary column identified by the iden-
`tification of the partitioned space,
`the number of
`records to retrieve in response to a browse is substan-
`tially reduced. For example, if a user wants to browse
`lot boundaries inside a block, the following steps are
`required to retrieve the data from the database in a
`traditional RDB-based GIS system.
`A. Determine the spatial index of the block.
`B. Find all the spatial objects whose spatial indices
`overlap with that of the block.
`C. Retrieve the contents of the spatial objects reported
`in Step B. Because there are many objects inside the
`block and each object is stored in one record in the
`database, many records need to be retrieved.
`Where the spatial object data is stored in accordance with
`the invention, the required steps are:
`A. Find all the cells (partitioned space) which overlap
`with the block.
`
`B. Retrieve each cell record to obtain the spatial objects
`within these cells.
`
`No processing is