Ex Parte Grosset et al

Patent Trial and Appeal Board

Apr 10, 2014

11609531 (P.T.A.B. Apr. 10, 2014)

UNITED STATES PATENT AND TRADEMARK OFFICE 1
___________ 2
3
BEFORE THE PATENT TRIAL AND APPEAL BOARD 4
___________ 5
6
Ex parte ROBIN GROSSET and DAVID HOOD 7
___________ 8
9
Appeal 2011-010790 10
Application 11/609,531 11
Technology Center 2100 12
___________ 13
14
15
Before HUBERT C. LORIN, ANTON W. FETTING, and 16
MICHAEL C. ASTORINO, Administrative Patent Judges. 17
FETTING, Administrative Patent Judge. 18
DECISION ON APPEAL 19
Appeal 2011-010790
Application 11/609,531

2
STATEMENT OF THE CASE1 1

1 Our decision will make reference to the Appellants’ Appeal Brief (“App.
Br.,” filed December 23, 2010) and Reply Brief (“Reply Br.,” filed June 1,
2011), and the Examiner’s Answer (“Ans.,” mailed April 1, 2011).
Robin Grosset and David Hood (Appellants) seek review under 2
35 U.S.C. § 134 of a final rejection of claims 1-16 and 19-22, the only 3
claims pending in the application on appeal. We have jurisdiction over the 4
appeal pursuant to 35 U.S.C. § 6(b). 5
The Appellants invented a way of storing multidimensional data (Spec. 6
para. 0001). 7
An understanding of the invention can be derived from a reading of 8
exemplary claim 1, which is reproduced below [bracketed matter and some 9
paragraphing added]. 10
1. A method comprising: 11
[1] receiving multidimensional data elements, 12
wherein each multidimensional data element is defined 13
by a plurality of objects having different object types, 14
wherein each object type is associated with a different 15
dimension within a multidimensional data space, 16
and 17
wherein an object value is stored to each object; 18
[2] forming a respective tuple 19
for each of the multidimensional data elements 20
by mapping each object value to an associated reference; 21
Appeal 2011-010790
Application 11/609,531

3
[3] applying, 1
with a processor, 2
a Hilbert function 3
to two or more of the references of each of the 4
tuples 5
to determine a respective Hilbert ordering 6
for each of the tuples; 7
and 8
[4] storing each of the Hilbert orderings 9
to a respective record 10
within a tree data structure 11
allocated within a linear data storage structure. 12
The Examiner relies upon the following prior art: 13
Reiter US 5,752,243 May 12, 1998
Pasumansky US 6,460,026 B1 Oct. 1, 2002
Lawder US 2003/0004938 A1 Jan. 2, 2003
Claims 1-8, 10-16, 19, and 22 stand rejected under 35 U.S.C. § 102(b) as 14
anticipated by Lawder. 15
Claim 9 stands rejected under 35 U.S.C. § 103(a) as unpatentable over 16
Lawder and Pasumansky. 17
Claims 20 and 21 stand rejected under 35 U.S.C. § 103(a) as 18
unpatentable over Lawder and Reiter. 19
Appeal 2011-010790
Application 11/609,531

4
ISSUES 1
The issue of anticipation turns primarily on whether Lawder describes 2
actually storing its Hilbert ordering values. A new issue of obviousness 3
turns on whether it was predictable to store Lawder’s Hilbert ordering values 4
in Lawder’s tree records stored as pages. 5
FACTS PERTINENT TO THE ISSUES 6
The following enumerated Findings of Fact (FF) are believed to be 7
supported by a preponderance of the evidence. 8
Facts Related to Claim Construction 9
01. The Appellants’ disclosure contains no lexicographic definition 10
of “Hilbert function.” 11
02. A Hilbert function is defined as follows:2 12
13
Facts Related to Appellants’ Disclosure 14
03. The invention is directed to techniques that enable more 15
consistent and efficient access of multidimensional tuples. For 16
example, multidimensional tuple Hilbert ordering techniques are 17
described that facilitate storage of multidimensional tuples to a 18
tree structure (e.g., a B-tree) that may be stored within pages of a 19

2 http://mathworld.wolfram.com/HilbertFunction.html.
Appeal 2011-010790
Application 11/609,531

5
linear data storage structure. The techniques order the 1
multidimensional tuples within the B-tree such that similar tuples 2
remain local to one another within the same region of B-tree. By 3
applying the Hilbert ordering function to the multidimensional 4
tuples prior to storage, the tuples are ordered in the B-Tree in 5
accordance with the Hilbert function even within individual pages 6
or regions of the linear storage space, allowing the B-tree to grow 7
in a balanced fashion. Spec. para. 0006. 8
Facts Related to the Prior Art 9
Lawder 10
04. Lawder is directed to an efficient method of partitioning and 11
indexing multi-dimensional data together with a conceptually 12
simple and computationally efficient method of selectively 13
retrieving subsets of the data, where subsets are defined as the 14
data lying within rectangular regions within multi-dimensional 15
space. Lawder para. 0001. 16
05. A file or database of multi-dimensional data contains 17
representations of logical entities, each of which is described by 18
an ordered set of attributes, or ‘dimensions’ or coordinates. 19
Moreover, these entities need to be organized and stored in some 20
way so that sub-sets can be selectively and ‘efficiently’ retrieved 21
according to values or ranges of values in one or more of any of 22
their attributes Lawder para. 0002. 23
06. Multi-dimensional data objects are mapped to one-dimensional 24
values using a Hilbert Curve which passes through the points in a 25
Appeal 2011-010790
Application 11/609,531

6
particular sequence. Thus a one-dimensional value corresponding 1
to a point is the sequence of the point along the curve. The 2
mapping induces a linear ordering of points in multi-dimensional 3
space and so also orders the data objects. The data objects are 4
then partitioned into ordered subsets corresponding to pages of 5
storage in a data store. Each page, or partition, corresponds to a 6
length of the Hilbert Curve. All of the points on one length of 7
Hilbert Curve (whether they correspond to actual data objects or 8
not) map to lower one-dimensional values than all of the points on 9
the next length of curve, corresponding to the next partition, thus 10
the partitions are ordered. Lawder para. 0025. 11
07. The partitions are then indexed using a simple one-dimensional 12
index method, such as the B-Tree, by placing a reference to each 13
partition in the index together with the location of the partition 14
within the data store. A reference to a partition may be the lowest 15
sequence number of a point on the length of the Hilbert Curve to 16
which the partition corresponds. Alternatively, it may be the 17
highest sequence number. Alternatively the reference may be the 18
lowest or highest sequence number of an actual data object stored 19
within the partition. The reference may also be a pair of lowest 20
and highest values of points delimiting a length of Hilbert Curve. 21
Lawder para. 0026. 22
08. The execution of a query on the data store, that is to say, the 23
retrieval of data objects that lie within a specified multi-24
dimensional rectangle, proceeds as follows: firstly, the lowest 25
Hilbert Curve sequence number of any point within the query 26
Appeal 2011-010790
Application 11/609,531

7
region is calculated and the page that may contain its 1
corresponding data object, if it exists, is then retrieved and 2
searched for data objects lying within the query region. Secondly, 3
the lowest sequence number of any point within the query region 4
which is higher than the sequence number of any point on the 5
section of Hilbert Curve corresponding to the page just searched is 6
calculated, if it exists. The page that may contain this sequence 7
number’s corresponding data object, if it exists, is then retrieved 8
and searched for data objects lying within the query region. The 9
previous step is then repeated until no further pages are found to 10
exist that intersect with the query region. Lawder paras. 0027-11
0029. 12
09. The mapping method, in utilizing the Hilbert Curve, partitions 13
data so that, in general, each partition contains data objects that 14
are close to each other in multi-dimensional space. Thus data 15
objects that are in proximity to each other are clustered in the data 16
store. This aids minimizing the number of pages to be searched in 17
the execution of a query. Lawder para. 0035. 18
10. Lawder relates to data spaces, or database domains, containing 19
finite numbers of points, or finite numbers of possible actual data 20
values, in which the Hilbert Curve, which is an ‘approximation’ of 21
the Hilbert Space-filling Curve, passes through all points once and 22
once only. Lawder approaches the organization of multi-23
dimensional data by regarding the data as points lying on the 24
Hilbert Curve. Lawder para. 0073. 25
Appeal 2011-010790
Application 11/609,531

8
11. The Hilbert Curve is named after the German mathematician 1
David Hilbert. Hilbert represented the coordinates of points in 2
space with a binary radix and this method is also used by Lawder. 3
Each point in any space of finite granularity of points lies a unique 4
distance along the curve from its beginning and thus is placed in 5
order along a one-dimensional line of distance, or sequence, 6
values. Thus points in multi-dimensional space, or n-dimensional 7
space, where n is the number of dimensions in a space, are 8
mapped to or transformed into values in one dimension that may 9
be stored in or indexed by any simple one-dimensional data 10
structure. Lawder paras. 0074 and 0075. 11
12. In order to map multi-dimensional data to one-dimensional 12
values, it is first necessary to map individual attribute values of 13
the data to integers. The Hilbert Curve passes through points in 14
spaces that are squares in 2 dimensions, cubes in 3 dimensions or 15
hyper-cubes in spaces with more than 3 dimensions and so the 16
domain, or range of possible values, of the integers is the same in 17
all dimensions even if the domains of individual attributes are of 18
different size. A maximum integer value is the number that in the 19
binary representation comprises bits or digits of value 1. Thus the 20
maximum value of an integer is defined as 2k-1, where k is chosen 21
as appropriate for the size of the largest attribute domain of any 22
possible item of multi-dimensional data to be stored in the 23
database. The number of binary digits in an integer attribute value 24
therefore equals k. This value of k corresponds to what is called 25
the order of curve used in the mapping between multi-dimensional 26
Appeal 2011-010790
Application 11/609,531

9
data and one-dimensional values. It is convenient and preferred, 1
although not necessary, in a practical software if the maximum 2
integer value accommodated for an attribute value is the same as 3
the maximum value accommodated by an unsigned integer data 4
type supported by the computer programming language and its 5
compiler used for the implementation. For example, an unsigned 6
integer data type which comprises 32 binary digits accommodates 7
multi-dimensional data whose largest attribute domain is within 8
the range [0 . . . 232-1]. It is also preferred, although not 9
necessary, that the smallest possible data type that can 10
accommodate the maximum attribute value is used in the software 11
implementation, in order to optimize the performance of the 12
implementation. Lawder para. 0076. 13
13. The Hilbert Curve has certain interesting properties whereby 14
points that are close to each other in n-dimensional space are, in 15
general, mapped to one-dimensional values that are also in 16
proximity to each other. Points that are consecutive in their 17
ordering, according to the mapping using the Hilbert Curve, are 18
adjacent in space. Thus the mapping achieves a degree of 19
clustering of data with similar values in all attributes or 20
dimensions which is desirable in the absence of prior knowledge 21
of the pattern of queries that will be executed over a collection of 22
data. The multi-dimensional data that make up a database are 23
partitioned into sub-sets. Each sub-set corresponds to a logical 24
unit of storage held on a computer. Each sub-set is defined as a 25
collection of points lying on a single contiguous section or length 26
Appeal 2011-010790
Application 11/609,531

10
of the Hilbert Curve. Actual multi-dimensional data values stored 1
in the database are called datum-points. Each logical unit of 2
storage is commonly called a page of data. Thus the Hilbert 3
Curve is conceptually cut into sections, each section 4
corresponding to a page. Each section of curve is delimited by a 5
pair of points, one lying at each end of the section. The length of 6
each curve section depends on the local density of datum-points 7
and the physical capacity for datum-points of the page to which it 8
corresponds. Lawder para. 0078 and 0079. 9
14. A database held in computer memory comprises a set of pages 10
and the size of this set depends on the volume of data, or number 11
of datum-points, contained in the database and the average 12
number of datum-points stored on the pages divided by the 13
capacity of the pages. Each page also corresponds to a volume of 14
space within an n-dimensional hyper-cubic space that defines the 15
domain of the database. The form of the data space that 16
corresponds to any particular page may also be a hyper-cube but 17
will usually be more complex. Ideally, datum-points are 18
partitioned into sets such that as much of the capacity of the page 19
of storage as possible is actually utilized for the storage of datum-20
points, thus minimizing the number of pages in the database. 21
Mapping to the Hilbert Curve induces a logical ordering of pages, 22
similar to the ordering of points on the Hilbert Curve. All of the 23
datum-points on any page map to lower one-dimensional values, 24
that are called derived-keys, than do all of the datum-points 25
contained on all succeeding pages. The lowest derived-key 26
Appeal 2011-010790
Application 11/609,531

11
corresponding to any datum-point placed on a page, when the 1
page is created, becomes the index key for the page. Such index 2
keys are called page-keys. Page-keys are placed in a one-3
dimensional index together with their corresponding logical page 4
addresses in computer memory. Insertion of a datum-point into 5
the database entails mapping the datum-point’s coordinates to its 6
sequence number, or derived-key, and placing or storing the 7
datum-point on the page that corresponds to the section of curve 8
on which it lies. The format in which the datum-point is stored 9
on the page is independent of the present invention and any 10
suitable format can be used. This approach partitions data rather 11
than the space in which it lies. It adapts easily on update, that is, 12
insertion and deletion of datum-points. For example, if a page 13
becomes full, half of the datum-points whose derived-keys are 14
greater or less than those of the other half can be moved to a new 15
page or some other similarly defined portion may be moved to a 16
logically adjacent page. In other words, the same approach used 17
for partitioning a collection of one-dimensional values in the one-18
dimensional B-Tree or one of its variants, such as the B+-Tree, 19
can be used for partitioning multi-dimensional data. Lawder 20
paras. 0080-0085. 21
15. In a practical application, the capacity of a page to store datum-22
points may amount to hundreds or thousands of datum-points. 23
Lawder para. 0098. 24
16. An understanding of the way in which the Hilbert Curve is 25
drawn is gained from the 2-dimensional embodiment illustrated in 26
Appeal 2011-010790
Application 11/609,531

12
FIGS. 4 to 5 showing the first 3 steps of a potentially infinite 1
process. In FIG. 4 a square is initially divided into 4 quadrants, 2
or, more generally, into 2n ‘quadrants’ in n dimensions, and a line, 3
or ‘first order curve’, is drawn through their centre points which 4
are ascribed sequence numbers in the order in which the curve 5
passes through them. The first order 2-dimensional Hilbert Curve 6
is regarded as passing through the 4 points in a space that lie at the 7
centres of the quadrants illustrated. The sequence in which the 8
curve passes through the quadrants defines an ordering of the 9
quadrants. The sequence number of a point lying on the Hilbert 10
Curve is called a derived-key. This term is also used to refer to 11
the sequence number of a quadrant within a space containing 4 12
quadrants in 2 dimensions or 2n ‘quadrants’ in n dimensions. 13
Whether usage of the term relates to the sequence number of a 14
point on the Hilbert Curve or to a quadrant in a space is clear from 15
the context. Lawder paras. 0101 and 0102. 16
17. It is not practicable to store the tree representation of the Hilbert 17
Curve in memory for calculating mappings for any useful value of 18
order of curve. However, a tree contains a finite number of types 19
of node. Different types of node (equivalent to different 20
orientations of first order curve) can be regarded as being different 21
states enabling the tree structure to be expressed more compactly 22
as a state diagram. Lawder para. 0132. 23
18. Referring to states in a state diagram is a convenient and 24
concise way of describing the mapping process. Nevertheless, 25
Appeal 2011-010790
Application 11/609,531

13
mappings may be calculated instead without the aid of state 1
diagrams. Lawder para. 0137. 2
19. Lawder identifies for retrieval datum-points lying within hyper-3
rectangular query regions, or query ranges. A hyper-rectangle is 4
the equivalent in n-dimensional space of a rectangle in 2-5
dimensional space, where n>2. Lawder para. 0145. 6
ANALYSIS 7
Claim 1 is drawn to creating an ordering of a set of multidimensional 8
data elements. Efficient ordering is important for database functions such as 9
insertion and searching. The database function of sorting is inextricably tied 10
to ordering, as sorting is a form of ordering. Once data elements have plural 11
attributes, ordering becomes ambiguous as to the ordering criteria. One tool 12
for assisting this ordering is mapping the elements to a singular element 13
ordering that preserves as much of the original data relationships as possible. 14
Both the instant application and Lawder describe Hilbert function mapping 15
as a tool for such ordering. FF 03 and 06-09. Although computing Hilbert 16
functions may be complex (FF 02), such computation is not at issue. Rather 17
the use of existing Hilbert function software for mapping multidimensional 18
data to achieve known efficiencies is at issue. 19
Because both the instant claim 1 and Lawder perform Hilbert function 20
mapping on multidimensional data, Lawder necessarily performs the first 21
three steps of claim 1. Lawder stores its equivalent to the recited 22
multidimensional data elements in memory pages, where the pages are 23
indexed by the Hilbert order of the first such element in the page. Lawder 24
does not describe how the data elements are stored within a given page, but 25
Appeal 2011-010790
Application 11/609,531

14
instead states that any suitable format can be used. FF 14. The pages in turn 1
are stored as records in trees and the index values are stored in a one-2
dimensional index. Id. 3
All of the arguments pertain to the final step in claim 1 of storing each of 4
the Hilbert orderings, reciting a specific implementation for retaining the 5
orderings. 6
We are not persuaded by the Appellants’ argument that: 7
the Examiner interpreted the sequence number of a point lying 8
on the Hilbert curve in Lawder (i.e., a “derived-key” as used in 9
the first sense in Lawder) as corresponding to the “Hilbert 10
orderings” recited in Appellant[s’] claim 1. However, in other 11
portions of the Examiner’s same application of Lawder to 12
Appellant[s’] claim 1, the Examiner appears to have interpreted 13
the sequence numbers of quadrants within a space in Lawder, 14
(i.e., a “derived-key” as used in the second sense in Lawder) as 15
corresponding to the “Hilbert orderings” recited in claim 1. 16
App. Br. 9. Lawder does refer to its Hilbert order values as derived-keys. 17
Lawder’s referral of derived-keys as quadrant sequence numbers is the same 18
reference, as Lawder describes computing Hilbert functions as though the 19
space the function is to order is partitioned into such quadrants. Thus, the 20
quadrants are visual or perceptual metaphors for the computations that result 21
in the Hilbert ordering of Lawder. FF 14. 22
We are not persuaded by the Appellants’ argument that: 23
Instead of storing the tree representation in memory, Lawder 24
indicates that the tree structure in FIG. 7 of Lawder is expressed 25
as a state diagram, as shown in FIG. 8 of Lawder, where each 26
distinct type of node corresponds to a distinct state in the state 27
diagram. Thus, the tree structures shown in FIGS. 7 and 14 of 28
Lawder do not depict derived-keys being stored to tree data 29
structures. Rather, FIGS. 7 and 14 are provided for purposes of 30
Appeal 2011-010790
Application 11/609,531

15
illustrating a mapping algorithm that is implemented by state 1
diagrams, e.g., the state diagram shown in FIG. 8. Accordingly, 2
the Examiner’s indication that “derived keys . . . are stored 3
within a tree data structure as shown in Figs. 7, 14 [in Lawder]” 4
is not supported by the evidence on record. 5
App. Br. 11 (internal footnote omitted). See also App. Br. 17. Lawder again 6
relies on a metaphor to more easily understand the processing. Lawder uses 7
state diagrams, not as diagrams of process state, but as an easier tool to 8
portray orderings of the multidimensional data. FF 17-18. 9
We are not persuaded by the Appellants’ argument that: 10
the evidence on record does not indicate that the sequence 11
numbers of points lying on the Hilbert Curve in Lawder (i.e., 12
what the Examiner has proposed as corresponding to the 13
“Hilbert orderings” recited in claim 1) are stored to records 14
within the tree structures shown in FIGS. 7 and 14 of Lawder. 15
Rather, the derived-keys shown in FIGS. 7 and 14 of Lawder 16
are sequence numbers of quadrants within a space - not the 17
sequence numbers of points lying on the Hilbert Curve. The 18
Examiner did not cite any teaching in Lawder that would 19
suggest that the sequence numbers of points lying on the 20
Hilbert Curve in Lawder (i.e., what the Examiner has proposed 21
as corresponding to the “Hilbert orderings” recited in claim 1) 22
are stored to records within the tree structures shown in FIGS. 7 23
and 14 of Lawder. 24
App. Br. 13 (internal footnote omitted). While we agree that the derived-25
keys in Lawder for all but the first element in each page do not have a 26
storage implementation described, Lawder does explicitly store the page-27
indexes which are Hilbert orderings for the first elements of the pages. 28
We are not persuaded by the Appellants’ argument that: 29
The sequence numbers of quadrants (i.e., the “derived-keys”) 30
shown in FIGS. 7 and 14 of Lawder, however, are not 31
determined by the application of a Hilbert function to two or 32
Appeal 2011-010790
Application 11/609,531

16
more references of a tuple. Rather, the tree structures in FIGS. 1
7 and 14 of Lawder are used to illustrate a technique of 2
mapping a point having coordinates in n-dimensional space to a 3
derived-key for the point using a Hilbert Curve. Therefore, the 4
derived-keys included within the tree structures of FIGS. 7 and 5
14 are independent of any actual multidimensional data 6
elements that may be mapped by using the tree representations. 7
App. Br. 15-16 (internal footnote omitted). Again, Lawder uses a geometric 8
metaphor for its mappings, which is why Lawder sometimes refers to its 9
Hilbert ordering values as quandrant designations. 10
We are persuaded, however, by the Appellants’ argument that: 11
Lawder fails to disclose "storing each of the Hilbert orderings 12
to a respective record within a tree data structure allocated 13
within a linear data storage structure,” as recited in 14
Appellant[s’] claim 1. 15
App. Br. 7. 16
We are similarly persuaded by the Appellants’ argument that: 17
Instead of storing the tree representation in memory, Lawder 18
indicates that the tree structure in FIG. 7 of Lawder is expressed 19
as a state diagram, as shown in FIG. 8 of Lawder, where each 20
distinct type of node corresponds to a distinct state in the state 21
diagram. Thus, the tree structures shown in FIGS. 7 and 14 of 22
Lawder do not depict derived-keys being stored to tree data 23
structures. Rather, FIGS. 7 and 14 are provided for purposes of 24
illustrating a mapping algorithm that is implemented by state 25
diagrams, e.g., the state diagram shown in FIG. 8. Accordingly, 26
the Examiner’s indication that “derived[-]keys . . . are stored 27
within a tree data structure as shown in Figs. 7, 14 [in Lawder]” 28
is not supported by the evidence on record. 29
App. Br. 11 (internal footnote omitted). Although Lawder stores some of its 30
Hilbert orderings in its page indexes in a one dimensional index, the indexes 31
are just that, and not records in Lawder’s trees. We further find that 32
Appeal 2011-010790
Application 11/609,531

17
Lawder’s pages themselves form a linear data structure, as they are 1
sequentially stored, as are the data elements stored within each page stored 2
by Hilbert function order. As the claim itself makes clear, a tree metaphor 3
for a data structure is compatible with linear data storage structures. This is 4
within the knowledge of any student who has taken a data structure class, 5
and so is within the knowledge of one of ordinary skill. 6
The Examiner answers this issue by finding that: 7
Lawder teaches mapping multi -dimensional data to one-8
dimensional sequence numbers, i.e. derived keys, the “Hilbert 9
ordering”. Each derived key can be represented as a tree 10
structure as shown in Figs. 6 [and] 7, such as point P. 11
Furthermore, data points are stored on a page based on the 12
derived key of the data points. 13
Ans. 14. This statement is correct, but not dispositive of the issue of 14
whether those ordering values are actually stored in Lawder’s pages. 15
Mapping and representation do not require storage. Storing data points does 16
not necessitate storing the (Hilbert order) positional values of those points. 17
NEW GROUND OF REJECTION 18
The following new ground of rejection is entered pursuant to 19
37 C.F.R. § 41.50(b). Claims 1, 10, and 19 are rejected under 20
35 U.S.C. § 103(a) as unpatentable over Lawder. 21
We found supra that Lawder fully describes the mapping of 22
multidimensional data to a one dimensional ordering as in each of the 23
claims. The only limitation recited in each of these claims that Lawder does 24
not explicitly describe is storing the orderings so mapped in Lawder’s pages 25
themselves. 26
Appeal 2011-010790
Application 11/609,531

18
Lawder explicitly describes an implementation in which its pages are 1
organized in a B+ tree. Because Lawder fails to explicitly describe how it 2
recovers its Hilbert orders (Lawder’s derived-keys), but instead allows that 3
“[t]he format in which the datum-point is stored on the page is independent 4
of the present invention and any suitable format can be used,” Lawder could 5
not be said to anticipate the claims. 6
The issue arises, however, as to whether explicitly storing Lawder’s 7
derived key for each of its data-points in Lawder’s pages would have 8
predictably been among the data storage formats Lawder referred to. If so, 9
then these claims would have been obvious over Lawder, as Lawder 10
describes the remaining limitations. 11
This issue is easily answered, as storing function results in look-up 12
tables to avoid having to incur the expense of plural function invocations is a 13
notoriously old and well known programming technique. More to the point, 14
Lawder explicitly describes searching by Hilbert order within a page 15
containing Hilbert ordered objects. FF 08. Theoretically this may be 16
performed by a linear search and counting. In a practical application, 17
however, the capacity of a page to store datum-points may amount to 18
hundreds or thousands of datum-points (FF 15). It is almost essential, not to 19
say predictable, to store the Hilbert ordering values to perform such 20
searches. Thus, it was at least predictable to one of ordinary skill to store the 21
Hilbert function orderings with their respective objects in Lawder’s tables. 22
CONCLUSIONS OF LAW 23
The rejection of claims 1-8, 10-16, 19, and 22 under 35 U.S.C. § 102(b) 24
as anticipated by Lawder is improper. 25
Appeal 2011-010790
Application 11/609,531

19
The rejection of claim 9 under 35 U.S.C. § 103(a) as unpatentable over 1
Lawder and Pasumansky is improper. 2
The rejection of claims 20 and 21 under 35 U.S.C. § 103(a) as 3
unpatentable over Lawder and Reiter is improper. 4
A new ground of rejection is entered pursuant to 37 C.F.R. § 41.50(b). 5
Claims 1, 10, and 19 are rejected under 35 U.S.C. § 103(a) as unpatentable 6
over Lawder. 7
DECISION 8
The rejection of claims 1-16 and 19-22 is reversed. 9
Claims 1, 10, and 19 are rejected under 35 U.S.C. § 103(a) under a new 10
ground of rejection entered pursuant to 37 C.F.R. § 41.50(b). 11
This Decision contains a new rejection within the meaning of 37 C.F.R. 12
§ 41.50(b) (2011). 13
Our decision is not a final agency action. 14
37 C.F.R. § 41.50(b) provides that Appellants, WITHIN TWO 15
MONTHS FROM THE DATE OF THE DECISION, must exercise one of 16
the following two options with respect to the new rejection: 17
(1) Reopen prosecution. Submit an appropriate amendment 18
of the claims so rejected or new evidence relating to the 19
claims so rejected, or both, and have the matter 20
reconsidered by the Examiner, in which event the 21
proceeding will be remanded to the Examiner. . . . 22
(2) Request rehearing. Request that the proceeding be 23
reheard under § 41.52 by the Board upon the same record 24
. . . . 25
No time period for taking any subsequent action in connection with this 26
appeal may be extended under 37 C.F.R. § 1.136(a). See 37 C.F.R. 27
Appeal 2011-010790
Application 11/609,531

20
§ 1.136(a)(1)(iv) (2011). 1
REVERSED; 41.50(b) 2
llw 3