Ex Parte Crabtree

Board of Patent Appeals and Interferences

Aug 18, 2010

10433260 (B.P.A.I. Aug. 18, 2010)

UNITED STATES PATENT AND TRADEMARK OFFICE
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www.uspto.gov
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
10/433,260 06/02/2003 Ian B. Crabtree 36-1750 2595
23117 7590 08/19/2010
NIXON & VANDERHYE, PC
901 NORTH GLEBE ROAD, 11TH FLOOR
ARLINGTON, VA 22203
EXAMINER
STACE, BRENT S
ART UNIT PAPER NUMBER
2161
MAIL DATE DELIVERY MODE
08/19/2010 PAPER
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
____________________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________________

Ex parte IAN B. CRABTREE
____________________

Appeal 2009-0081791
Application 10/433,2602
Technology Center 2100
____________________

Before JOSEPH L. DIXON, STEPHEN C. SIU, and JAMES R. HUGHES,
Administrative Patent Judges.

HUGHES, Administrative Patent Judge.

DECISION ON APPEAL3

1 An oral hearing was held in this appeal on August 11, 2010.
2 Application filed June 2, 2003. The real party in interest is British
Telecommunications PLC. (App. Br. 3.)
3 The two-month time period for filing an appeal or commencing a civil
action, as recited in 37 C.F.R. § 1.304, or for filing a request for rehearing,
as recited in 37 C.F.R. § 41.52, begins to run from the “MAIL DATE”
(paper delivery mode) or the “NOTIFICATION DATE” (electronic delivery
mode) shown on the PTOL-90A cover letter attached to this decision.
Appeal 2009-008179
Application 10/433,260

2
STATEMENT OF THE CASE
Appellant appeals from the Examiner’s rejection of claims 1, 2, and 4-
17 under authority of 35 U.S.C. § 134(a). Claims 3 and 18-27 have been
cancelled. (See Resp. to Non-Compliant Appeal Brief filed September 18,
2008 at p. 3.) The Board of Patent Appeals and Interferences (BPAI) has
jurisdiction under 35 U.S.C. § 6(b).
We reverse.
Appellant’s Invention
Appellant invented a method of building an index for a plurality of
entities represented by points defined in a space, comprising steps for: (1)
creating a first area or region around the extremities of the points; (2)
creating a data structure representing the region, storing in the data structure
data specifying the extremities of the points (extent of the region), and
storing in the data structure links to the points representing the entities in the
region; (3) dividing the region into sub-regions; and (4) reducing the size of
the sub-regions to “shrink” the sub-regions to match the extremities of the
points within the sub-regions. The method stores links to sub-regions in the
data structure, and repeats the process until a predetermined number of
points are contained in each sub-region. (Spec. 2, ll. 4-30; 8, l. 9 to 9, l.
33.)4

4 We refer to Appellant’s Specification (“Spec.”); Appeal Brief (“App. Br.”)
filed August 29, 2008; and Reply Brief (“Reply Br.”) filed January 6, 2009.
We also refer to the Examiner’s Answer (“Ans.”) mailed November 6, 2008.
Appeal 2009-008179
Application 10/433,260

3
Representative Claim
Independent claim 1 further illustrates the invention. It reads as
follows:
1. A method of building an index to a plurality of
entities, wherein each entity is represented by data identifying a
point defined in a space, by creating a hierarchy of sub-area
data structures, the method comprising:
(i) creating a region around the points representing the
entities;
(ii) performing a process in respect of the created region
or sub-region, the process comprising:
creating an area or sub-area data structure;
storing, within the area or sub-area data structure,
data specifying the extent of the respective region or sub-
region;
storing, within the area or sub-area data structure,
links to points falling within the respective region or sub-
region;
dividing the region or sub-region to create a
plurality of sub-regions; and
for each of the plurality of sub-regions that
contains points, reducing the sub-region until further reduction
thereof would result in one of the points falling outside of the
sub-region; and
(iii) repeatedly performing the process in respect of each
created sub-region that contains points until a predetermined
criterion has been satisfied;
wherein the method further comprises storing, within
each area or sub-area data structure, links to sub-area data
structures corresponding to its respective plurality of sub-
regions; and
wherein the hierarchy of sub-area data structures
provides the index to the entities.
Appeal 2009-008179
Application 10/433,260

4
References
The Examiner relies on the following references as evidence of
unpatentability:
Winkelman US 4,435,752 Mar. 6, 1984

Barbara US 5,499,360 Mar. 12, 1996

Keighan US 6,161,105 Dec. 12, 2000

Christy US 6,366,911 B1 Apr. 2, 2002

Bastawala US 6,973,457 B1 Dec. 6, 2005
(filed May 10, 2002)

Rejections on Appeal5
The Examiner rejects claims 1, 2, 5, 6, 10, 11, and 13-17 under
35 U.S.C. § 102(b) as being anticipated by Keighan.
The Examiner rejects claim 7 under 35 U.S.C. § 103(a) as being
unpatentable over Keighan.
The Examiner rejects claim 4 under 35 U.S.C. § 103(a) as being
unpatentable over the combination of Keighan and Barbara.
The Examiner rejects claim 8 under 35 U.S.C. § 103(a) as being
unpatentable over the combination of Keighan and Winkelman.
The Examiner rejects claim 9 under 35 U.S.C. § 103(a) as being
unpatentable over the combination of Keighan and Christy.

5 The Examiner has withdrawn the 35 U.S.C. § 112, second paragraph,
rejection of claims 1, 2, and 4-17 made in the Final Rejection (Fin. Rej. 6).
(Ans. 3.)
Appeal 2009-008179
Application 10/433,260

5
The Examiner rejects claim 12 under 35 U.S.C. § 103(a) as being
unpatentable over the combination of Keighan and Bastawala.

ISSUE
Based on our review of the administrative record, Appellant’s
contentions, and the Examiner’s findings and conclusions, the pivotal issue
before us is as follows:
Does the Examiner err in finding the Keighan reference discloses each
feature of Appellant’s claims, including storing links to points within a
region or sub-region within a data structure for that region or sub-region, and
reducing the size of the sub-region until further reduction thereof would
result in one of the points falling outside of the sub-region?

FINDINGS OF FACT (FF)
Appellant’s Specification
1. Appellant’s Specification describes an indexing method for
building an index of data (a plurality of entities). The method creates a two-
dimensional coordinate space and populates the space with points
representing the data. For Example, the “X” and “Y” coordinates may
represent time and speed or latitude and longitude values. (Spec. 7, l. 12 to
9, l. 16.) The method creates a region around the extremities of the points
(outermost points) and a data structure representing the region and the points
in the region. Appellant’s method stores, in this data structure, data
specifying the outermost points (extent of the region) and links to the points
in the region, which represent the actual data (entities). The method then
divides the region into sub-regions, and for each sub-region, reduces
Appeal 2009-008179
Application 10/433,260

6
(shrinks) the size of the sub-regions to match the outermost points within the
sub-region. The method further stores links to sub-regions in the data
structure, and repeats the process until a predetermined number of points are
contained in each sub-region. (Spec. 2, ll. 4-30; 8, l. 9 to 15, l. 16.)
2. As Appellant’s index comprises sub-region (sub-quad)
information stored to the database, including the extent of sub-regions (in x,
y coordinates), the coordinates of the points falling within the sub-region
(i.e., links to the points), and links to the sub-regions (four sub-regions or
sub-quads) within a particular sub-region. Consequently, the described
index comprises a hierarchy of sub-region data structures defined by the
relationship between each successive sub-region and its respective four sub-
regions. Additionally, the database contains the points stored in the database
in an order inverse of the sub-region hierarchy. (Spec. 14, ll. 22-33.)
Keighan Reference
3. Keighan describes a system for storing, retrieving, and
manipulating data utilizing a database structure. More specifically, Keighan
describes a binary hyperspatial code (BH code), a BH code data structure,
and an apparatus and method for partitioning data utilizing BH code. (Col.
6, ll. 22-33.) Keighan utilizes a “linearization technique which maintains the
dimensional organization of multidimensional data within the data itself”
(col. 2, ll. 37-39) in order to avoid “maintaining two discrete database
engines as well as a proprietary data structure utilizing unique spatial
indexes” (col. 2, ll. 2-4; see col. 10, ll. 20-24). Consequently, “[s]patial data
maintained using the binary BH code data structure maintains the spatial
organization of the data independent of a formal index” (col. 3, ll. 9-11); and
a “single unique BH code value retains all original data values to full
Appeal 2009-008179
Application 10/433,260

7
precision, and maintains the spatial organization of the data without the
necessity of creating and maintaining a separate index structure” (col. 7, ll.
31-34).
4. Keighan’s data points (spatial data) reside in an N-dimensional
space represented by the BH code data structure. (Col. 2, ll. 62-65.)
Keighan’s data points can be represented by a conventional multi-
dimensional table with separate columns for their respective dimensional
values and related attributes (see col. 7, l. 66 to col. 8, l. 4; Fig. 4). The BH
code represents the binary coded multi-dimensional intersection of the
dimensional values, and replaces the dimensional values with a single binary
data value. For example, the BH code “011” could represent a three-
dimensional cubic space having a latitude of 0-90, a longitude of 0-180, and
an elevation of (-5) km to (-2) km. (Col. 7, l. 20 to col. 9, l. 49; Figs. 3-9.)
5. Keighan’s BH code data structure includes the BH code values
and multiple attributes related to the BH code values, which correspond to
characteristics associated with the underlying spatial data. (Col. 3, ll. 3-9;
col. 10, ll. 1-3; Figs. 4, 9, 10.) The data structure takes the form of a
multidimensional table or a partitioned table comprised of one or more
partitions representing “a unique bounded N dimensional space, wherein all
data in one partition exists within the same bounded region of space” (col. 3,
ll. 14-16; col. 9, ll. 62-65). The BH code data structure “linearizes multiple
dimensions into a single BH code value” (col. 2, ll. 65-67), and “maintains
the spatial organization of the data as well as each dimension, thereby
composing the BH code into a single linearized data structure” (col. 3, ll. 1-
3).
Appeal 2009-008179
Application 10/433,260

8
6. Keighan describes an automatic partitioning scheme in which
Keighan’s system stores BH code data (values) and corresponding attributes
in the spatially organized partition. The system creates a child partition
whenever the number of data points for a region/partition exceeds a
threshold or “high water mark.” (Col. 9, ll. 52 to col. 11, l. 26; Figs 10-12.)
Importantly, the “multidimension data partitions are created at loading time
based on the number of dimensions defined for an BH code datatype, and a
user defined data volume per partition [or] ‘high water mark.’” (Col. 10, ll.
25-31.)

ANALYSIS
Appellant contends that Keighan does not disclose “‘storing, within
the area or sub-area data structure, links to points falling within the
respective region or sub-region,’ as required by claim 1” (App. Br. 13-14).
(See App. Br. 13-15; Reply Br. 2-8.) Appellant further contends that
Keighan does not disclose “reducing a sub-region until further reduction
thereof would result in one of the points falling outside of the sub-region”
(App. Br. 16) as recited in claim 1. (See App. Br. 16-18.) The Examiner
finds that Keighan discloses the disputed features of Appellant’s claim 1.
(Ans. 4-5, 15-23.) Specifically, the Examiner finds that Keighan discloses
storing links to points (Ans. 4-5, 19-21 (citing Keighan, col. 6, ll. 27-30; col.
12, ll. 14-18; col. 16, ll. 9-13; col. 17, ll. 30-37; Fig 12)), and reducing the
sub-region to the outermost points in the sub-region (Ans. 5, 21-23 (citing
Keighan, col. 10, ll. 1-6, 25-30, 61-62; col. 11, ll. 8-25; Figs. 11, 12)).
Based on these contentions, we decide the question of whether the
Examiner erred in finding the Keighan reference discloses storing links to
Appeal 2009-008179
Application 10/433,260

9
points within a region or sub-region within a data structure for that region or
sub-region, and reducing the size of the sub-region until further reduction
thereof would result in one of the points falling outside of the sub-region.
After reviewing the record on appeal, we agree with Appellant and find that
Keighan reference does not disclose the disputed features for essentially the
reasons argued by Appellant. We provide our analysis, as follows, to
supplement and clarify Appellant’s arguments.
We initially note that the dispute before us hinges on what constitutes
a “link” and a “point,” and the interpretation of these terms is critical to
resolving this dispute. Appellant does not explicitly define the terms in the
feature of “storing, within the area or sub-area data structure, links to points
falling within the respective region or sub-region.” (App. Br. 22, Claim
App’x., claim 1.) Appellant, however, does describe that the points in the
sub-region represent the actual data for the sub-region – which is stored
separately from the data structure – and that the data structure (database
“table”) for the sub-region contains links to the points, e.g., coordinates of
the points. (FF 1-2.) Further, Appellant’s explain in their Brief that the
limitation “require[s] a field for storing . . . linking data.” (App. Br. 15.)
Consequently, we construe a point to represent data, and a “link” to have its
commonly understood meaning of an identifier or a connecting structure.
Thus, we understand the claimed feature to require storing in a data structure
some data identifying (connected and/or associated with) points within the
sub-region, and that such data must have a “field” in the data structure so
that it can be stored. The points represent the actual data that is stored
separately in the database.
Appeal 2009-008179
Application 10/433,260

10
Conversely, Keighan explicitly describes that its data structure
includes the actual data of interest, not links to points representing data.
Keighan’s BH code represents the location of spatial data, and Keighan’s
data structure includes the BH code and attributes of the spatial data. (FF 3-
5.) Further, Keighan specifically explains utilizing the BH code and
linearization techniques to maintain the dimensional organization of
multidimensional data “within the data itself” to avoid the need for separate
spatial data structures and/or indexes. (FF 3, 5.)
We also agree with Appellant that claim 1 includes a feature of
reducing the sub-region until further reduction thereof would result in one of
the points falling outside of the sub-region – i.e., reducing the size of
(shrinking) the sub-region until it just includes the outermost points in the
sub-region. (FF 1-2.) Even if we were to agree with, arguendo, the
Examiner’s findings regarding links, we cannot agree with the Examiner’s
findings concerning Keighan’s disclosure of reducing sub-regions. Keighan
explicitly describes subdividing sub-regions into further sub-regions, instead
of reducing the size of the sub-regions (prior to sub-dividing them).
Keighan’s subdividing takes place without regard for the dimensions or
outermost points of a particular sub-region. Further, Keighan explicitly
describes creating its data partitions when data is loaded (into the database)
based on BH code dimensions and the data volume per partition (“high
water mark”). (FF 6.) Thus, we also agree with Appellant that Keighan
does not disclose reducing the sub-region until further reduction thereof
would result in one of the points falling outside of the sub-region.
There is simply no explicit or inherent disclosure in Keighan of
storing links to points within a region or sub-region within a data structure
Appeal 2009-008179
Application 10/433,260

11
for that region or sub-region, nor reducing the size of the sub-region until
further reduction thereof would result in one of the points falling outside of
the sub-region as required by Appellant’s claim 1. Thus, we are constrained
by the record before us to find that Keighan does not disclose the disputed
features, and therefore does not anticipate Appellant’s claim 1. Appellant’s
dependent claims 2, 5, 6, 10, 11, and 13-17 depend on independent claim 1
and contain the same limitations as independent claim 1. Therefore, based
on the record before us, we find that the Examiner erred in finding that the
Keighan reference discloses each of the disputed features of Appellant’s
claims 1, 2, 5, 6, 10, 11, and 13-17. Accordingly, we reverse the Examiner’s
anticipation rejection of claims 1, 2, 5, 6, 10, 11, and 13-17.
Rejection of Claims 4, 7-9, and 12 under § 103
The Examiner rejects claims 4, 7-9, and 12 under § 103 over Keighan
in combination with several prior art references: claim 7 over Keighan,
claim 4 over Keighan and Barbara, claim 8 over Keighan and Winkelman,
claim 9 over Keighan and Christy, and claim 12 over Keighan and
Bastawala. Appellant’s claims 4, 7-9, and 12 depend on claim 1. As set
forth supra, we find that Keighan falls short of disclosing, teaching, or
suggesting either storing links to points within a sub-region, or reducing the
size of the sub-region. None of the Barbara, Winkelman, Christy, and
Bastawala references cure these deficiencies. Consequently, we are
constrained by the record before us to find that the Examiner’s cited prior art
combinations of Keighan with Barbara, Winkelman, Christy, and Bastawala
do not collectively teach or suggest the disputed limitations of Appellant’s
claims 4, 7-9, and 12. It follows that Appellant has shown that the Examiner
erred in finding that the cited prior art combinations of Keighan with
Appeal 2009-008179
Application 10/433,260

12
Barbara, Winkelman, Christy, and Bastawala render Appellant’s claims 4, 7-
9, and 12 obvious. Accordingly, we reverse the Examiner’s obviousness
rejection of claims 4, 7-9, and 12.

CONCLUSIONS OF LAW
Appellant have shown that the Examiner erred in rejecting claims 1, 2,
5, 6, 10, 11, and 13-17 under 35 U.S.C. § 102(b).
Appellant have shown that the Examiner erred in rejecting claims 4,
7-9, and 12 under 35 U.S.C. § 103(a).

DECISION
We reverse the Examiner’s rejection of claims 1, 2, 5, 6, 10, 11, and
13-17 under 35 U.S.C. § 102(b).
We reverse the Examiner’s rejections of claims 4, 7-9, and 12 under
35 U.S.C. § 103(a).

REVERSED

rwk

Nixon & Vanderhye, PC
901 North Glebe Road, 11th Floor
Arlington, VA 22203