Ex Parte Larson et al

Patent Trial and Appeal Board

Apr 17, 2017

13738503 (P.T.A.B. Apr. 17, 2017)

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.
13/738,503 01/10/2013 Per-Ake Larson 337692.01 8267
69316 7590 04/19/2017
MICROSOFT CORPORATION
ONE MICROSOFT WAY
REDMOND, WA 98052
EXAMINER
HOANG, HAU HAI
ART UNIT PAPER NUMBER
2167
NOTIFICATION DATE DELIVERY MODE
04/19/2017 ELECTRONIC
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.
Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the
following e-mail address(es):
u sdocket @ micro soft .com
chriochs @microsoft.com
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
BEFORE THE PATENT TRIAL AND APPEAL BOARD
Ex parte PER-AKE LARSON and DONALD KOSSMANN
Appeal 2016-008524
Application 13/738,5031
Technology Center 2100
Before ALLEN R. MacDONALD, JOHN P. PINKERTON, and
GARTH D. BAER, Administrative Patent Judges.
PINKERTON, Administrative Patent Judge.
DECISION ON APPEAL
Appellants appeal under 35 U.S.C. § 134(a) from the Examiner’s
Final Rejection of claims 1—20, which constitute all the claims pending in
this application. We have jurisdiction under 35 U.S.C. § 6(b).
We reverse.
1 The real party in interest identified by Appellants is Microsoft Technology
Licensing, LLC. App. Br. 3.
Appeal 2016-008524
Application 13/738,503
STATEMENT OF THE CASE
Introduction
Appellants’ described and claimed invention relates generally to
creating and storing “an adaptive range filter that contains a compact
summary of the contents of an index for a data store in the form of a trie data
structure.” Abstract.2
Claim 1 is representative and reads as follows (with the disputed
limitation emphasized)'.
1. A computer-implemented process to summarize data,
comprising:
creating a trie-structure to index the data wherein:
each node of the trie-structure represents a
particular region of a domain of the data,
a root node represents the whole domain of data to
be indexed,
each parent node fully contains the regions of its
children in the trie-structure, and
leaves of the trie-structure contain occupied bits
indicating whether tuples in the set of data exist in the
particular region of data.
App. Br. 25 (Claims App’x).
2 Our Decision refers to the Final Office Action mailed July 21, 2015 (“Final
Act.”), Appellants’ Appeal Brief filed Dec. 28, 2015 (“App. Br.”) and Reply
Brief filed July 29, 2016 (“Reply Br.”), the Examiner’s Answer mailed May
16, 2016 (“Ans.”), and the original Specification filed Jan. 10, 2013
(“Spec.”).
2
Appeal 2016-008524
Application 13/738,503
Rejections on Appeal
Claim 1 stands rejected under 35 U.S.C. § 103(a) as being
unpatentable over Graefe et al. (US 2013/0318126 Al; published Nov. 28,
2013) (“Graefe”), in view of Fu et al. (US 2006/0294311 Al; published Dec.
28, 2006) (“Fu”).
Claims 2-4 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over Graefe, in view of Fu, and further in view of Yu
(US 2013/0297613 Al; published Nov. 7, 2013).
Claims 7—9 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over Graefe, in view of Fu, in view of Yu, and further in view
of Graefe (US 2011/0208704 Al; published Aug. 25, 2011) (hereinafter
“Graefe ’704”).
Claims 5 and 6 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over Becker (US 6,598,119 B2; issued July 22, 2003), in view
of Graefe, and further in view of Fu.
Claims 10, 11, 14, and 15 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over Graefe, in view of Yu.
Claims 12, 13, and 20 stand rejected under 35 U.S.C. § 103(a) as
being unpatentable over Graefe, in view of Yu, and further in view of Fu.
Claim 16 stands rejected under 35 U.S.C. § 103(a) as being
unpatentable over Graefe, in view of Yu, and further in view of Graefe ’704.
Claim 19 stands rejected under 35 U.S.C. § 103(a) as being
unpatentable over Graefe, in view of Yu, and further in view of Aha et al.
(US 8,502,819 Bl; issued Aug. 6, 2013) (“Aha”).
3
Appeal 2016-008524
Application 13/738,503
Claims 17 and 18 stand rejected under 35 U.S.C. § 103(a) as being
unpatentable over Graefe, in view of Yu, and further in view of Wang
(US 2009/0182726 Al; published July 16, 2009).
ANALYSIS
Appellants argue the cited references fail to teach or suggest a “trie-
structure” as recited in independent claim l.3 See App Br. 9. More
specifically, Appellants argue the Foster B-tree data structure, taught by
Graefe, is different than the claimed trie data structure. See id. According to
Appellants, as defined in Appellants’ Specification, and as understood by
one of ordinary skill in the art, a trie data structure is a specialized type of
tree data structure where no node in the tree data structure stores a key
associated with the node, and, instead, a node’s position in the tree data
structure defines a key with which it is associated. See id (citing Spec. 128).
In contrast, Appellants argue, a B-tree data structure stores keys in its
internal nodes. See App. Br. 10. Appellants further argue none of the other
cited references teach or suggest a trie data structure either. See App. Br. 9.
Further, Appellants essentially reference or repeat their argument regarding
independent claim 1 for independent claims 5 and 10 and dependent claims
2-A, 6-9, and 11-20.4 See App. Br. 13-24.
3 Appellants’ arguments raise additional issues, but we do not reach them
because the identified issues are dispositive of the appeal.
4 Claim 7 depends upon claim 4, and claims 8 and 9 depend upon claim 7.
See App. Br. 26—27 (Claims App’x). However, this appears to be in error, as
claim 4 is a method claim, whereas claim 7 is a system claim. Both
Appellants and the Examiner appear to treat claim 7 as depending upon
claim 5, rather than claim 4. Thus, we interpret claim 7 as depending upon
claim 5, rather than claim 4, and we conclude claims 7—9 are not indefinite
4
Appeal 2016-008524
Application 13/738,503
In response to the Examiner’s position that the broadest reasonable
interpretation of “trie structure” is an ordered tree data structure because
Appellants fail to explicitly claim the distinguishing characteristics of a trie
data structure within the claim (see Ans. 6—8), Appellants further argue a trie
data structure is a known data structure, and thus, the characteristics of a trie
data structure do not need to be recited explicitly in the claims. See Reply
Br. 3. In further response to the Examiner’s position that the claimed trie
data structure is not a proper trie data structure because the claimed trie data
structure does not satisfy the characteristics described in Appellants’
specification (see Ans. 5—6, 8—9), Appellants argue the claimed trie data
structure does indeed satisfy the characteristics described in Appellants’
specification. See Reply Br. 6.
We are persuaded by Appellants’ arguments. Appellants’
Specification defines a “trie structure” as “an ordered tree data structure that
is used to store a dynamic data set. . . rwherel Mo node in the tree stores
the key associated with the node, instead, its position in the tree defines the
key with which it is associated.” See Spec. 128 (emphasis added). We
agree with Appellants that Graefe’s B-tree data structure does not teach the
claimed “trie structure,” because, in Graefe’s B-tree data
under 35 U.S.C. § 112, second paragraph, for mixing statutory classes. See
In re Katz Interactive Call Processing Patent Litigation, 639 F.3d 1303,
1318 (Fed. Cir. 2011) (holding that a single claim that claimed both an
apparatus and method steps of using the apparatus was indefinite under
35 U.S.C. § 112, second paragraph). However, should there be any further
prosecution, Appellants may wish to appropriately amend claim 7 to address
the claim dependency issue.
5
Appeal 2016-008524
Application 13/738,503
structure, the nodes stores keys (see, e.g., Graefe 57 (“comparing key
values stored at each node visited”)), whereas, in the claimed trie data
structure, no single node stores a key. The Examiner’s interpretation of the
claimed “trie structure” as an ordered tree data structure is not reasonable, in
light of the claim language “trie structure,” and in light of the definition of
“trie structure” disclosed in Appellants’ specification. Further, the Examiner
has not persuasively established the claimed “trie structure” is somehow
inconsistent with the definition of “trie structure” disclosed in Appellants’
specification. We further disagree with the Examiner’s position that
Appellants’ argument fails because the claim does not explicitly recite the
feature “no node in the tree stores the key associated with that node” (see
Ans. 7), as one of ordinary skill in the art would understand the claimed “trie
structure,” when properly interpreted in light of the specification, to include
this feature.5
Accordingly, we do not sustain the Examiner’s rejection of
independent claims 1,5, and 10 for obviousness under 35 U.S.C. § 103(a).
We also do not sustain the Examiner’s rejection of dependent claims 2—4, 6—
9, and 11—20, which variously depend from one of the aforementioned
independent claims.
5 For example, if an applicant’s claim recited a “square surface,” the
applicant would not be further required to recite in the claim that the surface
includes four equal sides and four equal angles (i.e., right angles).
6
Appeal 2016-008524
Application 13/738,503
DECISION
We reverse the Examiner’s decision rejecting claims 1—20 under
35 U.S.C. § 103(a).
REVERSED
7