Kent State University

Patent Trials and Appeals BoardMar 29, 2021

2019004445 (P.T.A.B. Mar. 29, 2021)

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. 14/382,784 09/04/2014 Ruoming Jin KSU.402.US 4253 26360 7590 03/29/2021 Renner Kenner Greive Bobak Taylor & Weber Co., LPA Huntington Tower, Suite 400 106 South Main Street Akron, OH 44308-1412 EXAMINER EYERS, DUSTIN D ART UNIT PAPER NUMBER 2164 NOTIFICATION DATE DELIVERY MODE 03/29/2021 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): pto@rennerkenner.com PTOL-90A (Rev. 04/07) UNITED STATES PATENT AND TRADEMARK OFFICE ____________________ BEFORE THE PATENT TRIAL AND APPEAL BOARD ____________________ Ex parte RUOMING JIN and NING RUAN ____________________ Appeal 2019-004445 Application 14/382,7841 Technology Center 2100 ____________________ Before JOSEPH L. DIXON, MARC S. HOFF, and ELENI MANTIS MERCADER, Administrative Patent Judges. HOFF, Administrative Patent Judge. DECISION ON APPEAL STATEMENT OF THE CASE Appellant appeals under 35 U.S.C. § 134 from a Final Rejection of claims 1–4, 6–12, 14–18, and 21–24.2 We have jurisdiction under 35 U.S.C. § 6(b). We reverse. Appellant’s invention is a method for scaling reachability computations on relatively large graphs to respond to reachability queries. An initial graph is identified. A computing system may then identify a backbone, which can be used to create a scaled-down, subsequent graph. 1 Appellant states that the real party in interest is GraphSQL. Appeal Br. 2. 2 Claims 5, 13, 19, and 20 have been cancelled. Appeal 2019-004445 Application 14/382,784 2 Spec. ¶¶ 16, 24. A reachability environment may then compute a reachability of vertices within the initial graph. Id. ¶ 17. If the distance between two vertices of the plurality of vertices does not exceed a locality threshold, reachability is computed using the initial graph. If the distance between two vertices of the plurality of vertices exceeds the locality threshold, reachability is computed using the subsequent graph. Id. ¶ 41. Claim 1 is reproduced below: 1. A method for scaling reachability computations on relatively large graphs to respond to reachability queries, the method comprising: in a processor, identifying an initial graph comprising a plurality of vertices and a plurality of edges, wherein the initial graph is generated using data from a relational database; identifying a backbone graph within the initial graph at least in part by a graph creation module, wherein the backbone graph is identified at least in part by a locality threshold for the plurality of vertices; creating a subsequent graph comprising a scaled-down version of the initial graph, based at least in part on the backbone graph, at least in part by the graph creation module; in response to a reachability query for at least two vertices of the plurality of vertices, determining whether a distance of the at least two vertices of the plurality of vertices exceed the locality threshold; if the at least two vertices do not exceed the locality threshold, computing the reachability of the at least two vertices using the initial graph to respond to the reachability query; and if the at least two vertices do exceed the locality threshold, computing the reachability of the at least two vertices using at least the subsequent graph to respond to the reachability query. Appeal 2019-004445 Application 14/382,784 3 The prior art relied upon by the Examiner as evidence is: Name Reference Date He US 2006/0271304 A1 Nov. 30, 2006 Haustein US 2009/0077099 A1 Mar. 19, 2009 Vasseur US 2013/0188513 A1 July 25, 2013 Hao He et al. BLINKS: Ranked Keyword Searches on Graphs, SIGMOD ’07 305–16 2007 Jiefeng Cheng et al. Fast Graph Pattern Matching, IEEE 913–22 2008 Claims 1 and 14–16 stand rejected under 35 U.S.C. § 103 as being unpatentable over He, BLINKS, and Vasseur. Claims 12, 18, 21, and 22 stand rejected under 35 U.S.C. § 103 as being unpatentable over He and Vasseur. Claims 2–4 and 6–9 stand rejected under 35 U.S.C. § 103 as being unpatentable over He, BLINKS, Vasseur, and Haustein. Claims 10 and 11 stand rejected under 35 U.S.C. § 103 as being unpatentable over He, BLINKS, Vasseur, and Cheng. Claims 17 and 24 stand rejected under 35 U.S.C. § 103 as being unpatentable over He, Vasseur, and Cheng. Claim 23 stands rejected under 35 U.S.C. § 103 as being unpatentable over He, Vasseur, and Haustein. Throughout this decision, we make reference to the Appeal Brief (“Appeal Br.,” filed January 22, 2019), the Examiner’s Answer (“Ans.,” mailed March 18, 2019), and the Reply Brief (“Reply Br.,” filed May 20, 2019) for their respective details. Appeal 2019-004445 Application 14/382,784 4 ISSUES Does the combination of He, BLINKS, and Vasseur teach or suggest determining whether a distance of at least two vertices of a plurality of vertices exceeds a locality threshold; if the at least two vertices do not exceed the locality threshold, computing the reachability of the at least two vertices using an initial graph; and if the at least two vertices do exceed the locality threshold, computing the reachability of the at least two vertices using a subsequent graph? ANALYSIS Independent claim 1 recites, in pertinent part, determining whether a distance of the at least two vertices of the plurality of vertices exceed the locality threshold; if the at least two vertices do not exceed the locality threshold, computing the reachability of the at least two vertices using the initial graph to respond to the reachability query; and if the at least two vertices do exceed the locality threshold, computing the reachability of the at least two vertices using at least the subsequent graph to respond to the reachability query. The other two independent claims (12 and 21) also recite these limitations. Appellant argues that Vasseur does not supply a teaching of these elements, which the Examiner finds to be missing from He and BLINKS. Appeal Br. 7. Appellant contends that Vasseur is not concerned with reachability, and teaches only determining another next-hope node when the current next- hop node is not within a threshold distance. Appeal Br. 7. Appellant observes that the Examiner finds He to teach a first graph and a second graph, the second graph “embod[ying] reachability not covered by” the first Appeal 2019-004445 Application 14/382,784 5 graph. Id. at 8; He ¶ 46. Appellant argues that neither He nor Vasseur teaches a configuration where different graphs are used for reachability based on the locality of the two vertices. Appeal Br. 8. Appellant further contends that neither reference uses a conditional that determines when different graphs should be used in calculating reachability. Id. Appellant further argues against the combinability of He and Vasseur – “while He is targeted at determining the reachability between vertices, Vasseur is only concerned with the availability of a next hop node.” Appeal Br. 8. The Examiner finds that “Vasseur does teach the concept of reachability but does not teach the concept of reachability using different graphs, this is taught by He.” Ans. 3. “Vasseur teaches one or more routing metrics for reaching each particular neighbor node.” Id.; Vasseur ¶ 20. The Examiner further finds that Vasseur “teaches determining that the selected preferred next-hop node is suitable based on the preferred next-hop node being within a threshold distance from the local node.” Ans. 5; Vasseur claim 3, ¶ 56. “This further shows that Vasseur does teach the concept of reachability.” Ans. 4. Last, the Examiner finds that “Vasseur discloses a threshold distance that determines whether or not the local node can reach a preferred node.” Id. at 5. With respect to He, the Examiner finds that He teaches two different graphs that contain different reachability information. Id. at 4. “One of ordinary skill in the art would recognize that since the two graphs contain different reachability information, a determination would need to be made regarding which graph to use when determining reachability.” Id. Appeal 2019-004445 Application 14/382,784 6 We do not agree with the Examiner’s findings. He contains a definition of reachability: “Given two nodes u and v in G, is there a path from u to v? If the answer is yes, one can say that u can reach v.” He ¶ 4. Applying that definition, we agree with Appellant that the Examiner erred in finding that Vasseur “teach[es] the concept of reachability.” Ans. 4. Vasseur teaches only a determination that a next-hope node is suitable, i.e., “within a particular threshold distance (e.g., a certain signal strength or actual physical distance) of the local node.” Vasseur ¶ 56. Vasseur does not teach a determination whether there is a path at all from one node to another node, which the definition of “reachability” would require. Because we find that Vasseur does not teach a determination of reachability, we agree with Appellant that the combination of He and Vasseur is insufficient to teach or suggest all the elements of the claims. Specifically, we agree with Appellant that “Vasseur fails to relate the distance of two vertices to reachability of the two vertices and He fails to indicate that any attribute of the relevant vertices (such as distance) may trigger the use of one graph over another graph.” Reply Br. 3. We find that the Examiner erred in asserting the prima facie obviousness of claim 1 over He, BLINKS, and Vasseur, and of claims 12 and 21 over He and Vasseur. The Examiner does not argue that Haustein or Cheng remedy the deficiencies of He and Vasseur. Accordingly, we do not sustain the Examiner’s § 103 rejection of claims 1 and 14–16 over He, BLINKS, and Vasseur; the Examiner’s § 103 rejection of claims 12, 18, 21, and 22 over He and Vasseur; the Examiner’s § 103 rejection of claims 2–4 and 6–9 over He, BLINKS, Vasseur, and Haustein; the Examiner’s § 103 rejection of claims 10 and 11 over He, BLINKS, Vasseur, and Cheng; the Appeal 2019-004445 Application 14/382,784 7 Examiner’s § 103 rejection of claims 17 and 24 over He, Vasseur, and Cheng; or the Examiner’s § 103 rejection of claim 23 over He, Vasseur, and Haustein. CONCLUSION The combination of He, BLINKS, and Vasseur does not teach or suggest determining whether a distance of at least two vertices of a plurality of vertices exceeds a locality threshold; if the at least two vertices do not exceed the locality threshold, computing the reachability of the at least two vertices using an initial graph; and if the at least two vertices do exceed the locality threshold, computing the reachability of the at least two vertices using a subsequent graph. DECISION SUMMARY In summary: Claim(s) Rejected 35 U.S.C. § Reference(s)/ Basis Affirmed Reversed 1, 14–16 103 He, BLINKS, Vasseur 1, 14–16 12, 18, 21, 22 103 He, Vasseur 12, 18, 21, 22 2–4, 6–9 103 He, BLINKS, Vasseur, Haustein 2–4, 6–9 10, 11 103 He, BLINKS, Vasseur, Cheng 10, 11 17, 24 103 He, Vasseur, Cheng 17, 24 23 103 He, Vasseur, Haustein 23 Overall Outcome 1–4, 6–12, 14–18, 21–24 Appeal 2019-004445 Application 14/382,784 8 ORDER The Examiner’s decision to reject claims 1–4, 6–12, 14–18, and 21– 24 is reversed. REVERSED