Ex Parte Ramesh et al

Board of Patent Appeals and Interferences

Feb 21, 2012

10622666 (B.P.A.I. Feb. 21, 2012)

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/622,666 07/18/2003 Bhashyam Ramesh 11168 3863
26890 7590 02/21/2012
JAMES M. STOVER
TERADATA CORPORATION
10000 INNOVATION DRIVE
DAYTON, OH 45342
EXAMINER
HICKS, MICHAEL J
ART UNIT PAPER NUMBER
2165
MAIL DATE DELIVERY MODE
02/21/2012 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 BHASHYAM RAMESH and MICHAEL W. WATZKE
____________________

Appeal 2010-001763
Application 10/622,666
Technology Center 2100
____________________

Before JOHN A. JEFFERY, ST. JOHN COURTENAY, III,
and THU A. DANG, Administrative Patent Judges.

DANG, Administrative Patent Judge.

DECISION ON APPEAL

Appeal 2010-001763
Application 10/622,666

2
I. STATEMENT OF THE CASE
Appellants appeal under 35 U.S.C. § 134(a) from a Final Rejection of
claims 1-18 (App. Br. 2). Claims 19 and 20 are withdrawn (id.). We have
jurisdiction under 35 U.S.C. § 6(b).
We affirm-in-part.

A. INVENTION
Appellants’ invention is directed to a database system and data
structure for indexing spatial objects; wherein, an n-dimensional space is
divided into quad-tree cells (QTCs) to form a quad-tree structure and each
spatial object is assigned to one or more QTCs based on the location of the
spatial object in the n-dimensional space (accomplished using a Z-ordering
algorithm) (Abstract). The corresponding spatial object index entry includes
a designator (a binary code) for the QTC to which the spatial object is
assigned and a pointer to the spatial object (id.).

B. ILLUSTRATIVE CLAIM
Claim 1 is exemplary:
1. A method for creating a global spatial index for use in a
partitioned parallel environment including P partitions, each
partition residing on one or more parallel processing systems,
the global spatial index including:

creating a linear quad-tree structure dividing an
n-dimensional space into linear quad-tree cells
(QTCs), each QTC having a designator, the
designators having an order;

Appeal 2010-001763
Application 10/622,666

3
creating a set of spatial objects, each spatial object being
assigned to one or more of the QTCs depending on
the location of the spatial object in the n-
dimensional space;

creating one or more index entries for each spatial object,
each index entry including the designator for the
QTC to which the spatial object was assigned and
a pointer to the spatial object; and

storing the index entries in substantially equal numbers
among the P partitions, at least one of the P
partitions being stored on a different data storage
facility than the other P-1 partitions, the partition
where an index entry is stored being determined
by:

sorting the index entries by QTC designator into
QTC bins, each QTC bin corresponding to
one of the QTCs, each QTC bin containing
the index entries for the spatial objects that
were assigned to that QTC;

working through the QTC bins in order of the
QTCs’ designators, dividing the index
entries in the QTC bins into P substantially
equal parts, even when the index entries are
not uniformly distributed among the QTC
bins;

storing the index entries associated with each part
of the list in a different partition; and

duplicating an index entry in two or more
partitions only if the location of the spatial
object falls into two or more QTCs for
which index entries are stored in more than
one partition.

Appeal 2010-001763
Application 10/622,666

4
C. REJECTION
The prior art relied upon by the Examiner in rejecting the claims on
appeal is:
Hjaltason and Samet, Speeding up construction of PMR
Quadtree-based spatial indexes, 11 VLDB Journal 109, 109-
137 (2002) (hereinafter “Hjaltason”).

Aggarwal and Vitter, The Input/Output Complex of Sorting and
Related Problems, 31 Communications of the ACM 1116,
1116-1127 (1988) (hereinafter “Aggarwal”).

Claims 1-18 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over Hjaltason in view of Aggarwal.

II. ISSUES
The dispositive issue before us is whether the Examiner has erred in
determining that the combination of Hjaltason and Aggarwal teaches or
would have suggested:
1. “sorting the index entries by QTC designator into QTC bins,
each QTC bin corresponding to one of the QTCs, each QTC bin containing
the index entries for the spatial objects that were assigned to that QTC”
(claim 1, emphasis added); and
2. “creating a separate spatial object index record for each region
which includes the location of the spatial object, where each index record
includes a pointer to its associated spatial object and a designator for a
region that includes the location of its associated spatial object” (claim 14,
emphasis added).

Appeal 2010-001763
Application 10/622,666

5
III. FINDINGS OF FACT
The following Findings of Fact (FF) are shown by a preponderance of
the evidence.
Hjaltason
1. Hjaltason discloses construction of quadtree-based spatial
indexes which can index arbitrary spatial data, such as a geometric
representation, within a database; wherein, a quadtree is a linear tree or a
Binary tree (B-tree) that stores objects contained in the leaf nodes of the
quadtree in a linear index (Abstract; Sect. 3.3.3, ll. 19-30).
2. A Morton Block Index (MBI) represents quadtree blocks (or
QTCs) using Morton codes comprising an encoding of the path within the
tree representation of the quadtree; wherein, the MBI uses a B-tree to
organize the quadtree contents and Morton codes to serve as keys (Sect.
3.3.1, ll.1-4 and Sect. 3.3.2, ll.1-2).
3. In situations where the database is dynamic, one method for
constructing and updating spatial indexes includes building an index afresh
from the entire relation (known as bulk loading) (Sect. 1, ll. 19-30); wherein,
the input data (or the set of all of the objects) is sorted prior to bulk loading
(Sect. 5.4, ll. 1-5 and 13).
4. There are two schemes for storing objects in a quadtree index;
wherein, the first scheme stores the entire spatial description of the object
and the second scheme stores a reference ID for the object and uses a table
lookup to determine the geometry of the object (Sect. 3.3.3, ll.1-14 and 19-
30).
Appeal 2010-001763
Application 10/622,666

6
Aggarwal
5. Aggarwal discloses an algorithm for a distribution sort that uses
approximate partitioning elements that break up a file into roughly equal-
sized “buckets;” wherein, the records are divided based upon a key value
(Sect. 5, “Distribution Sort,” ll. 1-6).

IV. ANALYSIS
Claims 1-18
Appellants contend that the “combination of Hjaltason and Aggarwal
does not teach sorting the index entries by QTC designator or QTC number”
because “Hjaltason describes sorting the input data” and not “sorting index
entries” (App. Br. 13).
Though the Examiner admits that Hjaltason “fails to disclose … that
the index entries are sorted by QTC designator into QTC bins, each QTC bin
corresponding to one of the QTCs, each QTC bin containing the index
entries for the spatial objects that were assigned to that QTC” (Final Rej. 4;
Ans. 5), the Examiner finds that Aggrawal discloses this feature since it
discloses that “objects are sorted by keys” (id.). The “Examiner notes
[further] that the index key [of Hjaltason] is the column of the index upon
which the index is sorted” and “[a]s such, the Morton Codes (e.g. QTC
designators) acting as the index keys, by definition, includes the index being
sorted by [the] Morton Code” (Ans. 13).
In the Reply Brief, Appellants contend that the “Examiner … ‘noted,’
without providing citation to Hjaltason, that ‘the index key is the column of
the index upon which the index is sorted’” (Reply Br. 2). Appellants assert
that there is “no support in Hjaltason for the Examiner’s contention” and
Appeal 2010-001763
Application 10/622,666

7
“[c]ontrary to the Examiner’s position, an index may be sorted on fields
other than the index key” (id.).
Hjaltason discloses construction of quadtree-based spatial indexes for
indexing arbitrary spatial data; wherein, the quadtree stores objects from the
leaf nodes of the quadtree in a linear index, such as the MBI (FF 1 and 2).
In particular, the MBI uses a B-tree to organize the quadtree contents and
Morton codes to serve as keys (FF 2). One method for constructing and
updating spatial indexes includes building an index afresh; wherein, the
input data (or the set of all of the objects) is sorted prior to bulk loading (FF
3).
Although we agree with the Examiner’s finding that MBI comprise
index entries and Morton (binary) codes comprise QTC designators, the
sections of Hjaltason cited by the Examiner are silent as to QTC bins or
sorting on the MBI’s into a QTC bin.
We find further a contradiction in the Examiner’s finding that
Hjaltason fails to teach the feature of “sorting the index entries by QTC
designator into QTC bins” (Ans. 5) and his later finding that Hjaltason
teaches this feature since “the Morton Codes (e.g. QTC designators) acting
as the index keys, by definition, includes the index being sorted by [the]
Morton Code” (Ans. 13). We agree with Appellants’ argument that
“Hjaltason [merely] describes sorting the input data [the set of spatial
objects]” and not “sorting index entries” (App. Br. 13, FF 3). Accordingly,
contrary to the Examiner’s findings, we find that the sorting of the spatial
objects prior to construction of the quadtree-based spatial indexes does not
necessarily result in a sorted index (FF 1 and 3) and there appears to be no
support in the cited sections of Hjaltason for this finding.
Appeal 2010-001763
Application 10/622,666

8
In addition, Aggarwal discloses an algorithm for a distribution sort
that uses approximate partitioning elements that break up the file into
roughly equal-sized “buckets;” wherein, the records are divided based upon
a key value (FF 5). Although Aggarwal discloses partitioning a file into
equal-sized “buckets” (FF 5), we do not find any teaching in the cited
portions of Aggarwal that discloses sorting an index entry as required by the
claim.
Accordingly, we find that Appellants have shown that the Examiner
erred in rejecting claim 1 over Hjaltason in view of Aggarwal. Independent
claims 8, 11, and 18 recite similar limitations and thus stand with claim 1.
Accordingly, we also reverse the rejection of claims 8, 11, and 18 and claims
2-7, 9-10, and 12-13 depending respectively from claims 1, 8, 11, and 18
over Hjaltason in view of Aggarwal.
As to independent claim 14, Appellants argue that “combination of
Hjaltason and Aggarwal does not teach an index record that includes a
pointer to its associated spatial object and a designator for a region that
includes the location of its associated spatial object” (App. Br. 13).
As noted supra, Hjaltason discloses quadtree-based spatial indexes
such as the MBI that uses Morton codes to as keys (FF 2). We agree with
the Examiner that the Morton codes comprise a QTC designator (Ans. 12).
Hjaltason also discloses that the spatial object may either be stored or
referenced using a reference ID and a table lookup to determine the actual
geometry of the object (FF 4). We find that the reference ID and table
lookup serve as pointers to the spatial object. That is, we find that “creating
a separate spatial object index record for each region which includes the
location of the spatial object, where each index record includes a pointer to
Appeal 2010-001763
Application 10/622,666

9
its associated spatial object and a designator for a region that includes the
location of its associated spatial object” reads upon Hjaltason’s MBI
including a Morton code and a reference ID with table lookup for
referencing the spatial object.
Accordingly, we find that Appellants have not shown that the
Examiner erred in rejecting independent claim 14 under 35 U.S.C. § 103(a)
over Hjaltason in view of Aggarwal and claims 15-17 depending
respectively from claim 14.

V. CONCLUSION AND DECISION
The Examiner’s rejection of claims 1-13 and 18 under 35 U.S.C. §
103(a) is reversed, while the Examiner’s rejection of claims 14-17 under 35
U.S.C. § 103(a) is affirmed.

AFFIRMED-IN-PART

peb