DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP § 2146 et seq. for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The filing of a terminal disclaimer by itself is not a complete reply to a nonstatutory double patenting (NSDP) rejection. A complete reply requires that the terminal disclaimer be accompanied by a reply requesting reconsideration of the prior Office action. Even where the NSDP rejection is provisional the reply must be complete. See MPEP § 804, subsection I.B.1. For a reply to a non-final Office action, see 37 CFR 1.111(a). For a reply to final Office action, see 37 CFR 1.113(c). A request for reconsideration while not provided for in 37 CFR 1.113(c) may be filed after final for consideration. See MPEP §§ 706.07(e) and 714.13.
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The actual filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/apply/applying-online/eterminal-disclaimer.
Claims 1-8, 10-12, 14-20, 22-24, and 26 are rejected on the grounds of nonstatutory double patenting as being unpatentable over claims 1-11 of U.S. Patent No. US12164495B2. Although the claims at issue are not identical, they are not patentably distinct from each other because claim 1 of the Instant Application corresponds to claim 1 of U.S. Patent No. US12164495B2 (‘495), as set forth in the table below.
‘495
Instant Application
1. A computer implemented method comprising:
configuring, by a processor, a non-transitory memory according to a data structure, the data structure including:
an increment value;
a key array including a plurality of sorted data elements, wherein each data element comprises a key and is associated with a position in the key array; and a cluster element array including one or more cluster elements, each cluster element defined by one of one key from the key array or a plurality of continuous keys from the key array, wherein each cluster element is associated with a cluster code for determining the position of one or more keys in the key array;
determining, by the processor, the cluster code of each cluster element by subtracting the position in the key array where a first key associated with the cluster element is stored from the first key associated with the cluster element; and determining, by the processor, that two keys adjacently positioned in the key array are continuous if a subtraction of one of the two keys adjacently positioned in the key array from the other of the two keys adjacently positioned in the key array is equal to the increment value.
1. A computer implemented method comprising: configuring, by a processor, a non-transitory memory according to a data structure, the data structure including: an increment value; a key array including a plurality of sorted data elements, wherein each data element comprises a key and is associated with a position in the key array; and a cluster array stored in a binary tree including one or more cluster nodes, each cluster node defined by one or more continuous keys from the key array, wherein each cluster node is associated with a cluster code for determining the position of one or more keys in the key array; determining, by the processor, the cluster code of each cluster node by subtracting the position in the key array where a first key associated with the cluster node is stored from the first key associated with the cluster node; and determining, by the processor, that two keys adjacently positioned in the key array are continuous if a subtraction of one of the two keys adjacently positioned in the key array from the other of the two keys adjacently positioned in the key array is equal to the increment value.
Claims 14 and 26 correspond to claim 1 and are rejected accordingly.
Claims 2-8 and 15-20 correspond to claims 2-8 of ‘495 respectively and are rejected accordingly.
Claims 10-12 and 22-24 correspond to claims 9-11 of ‘495 respectively and are rejected accordingly.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1, 2, 8, 10, 11, 12, 14, 15, 20, 22, 23, 24, and 26 are rejected under 35 U.S.C. 103 as being unpatentable over Eleish (Pub. No. US 2017/0208073 A1, hereinafter “Eleish”) in view of Gunther (Pub. No. US 2007/0294502 A1, hereinafter “Gunther”).
Regarding claim 1, Eleish teaches:
configuring, by a processor, a non-transitory memory according to a data structure, the data structure including: (Eleish – see Fig. 5, 560 processor [0326] and Fig. 15 limited discrete index (i.e. data structure) [0167].)
a key array including a plurality of sorted data elements, wherein each data element comprises a key and is associated with a position in the key array (Eleish – Fig. 16 discloses a Base Index (i.e. key array) with sorted values 2, 5, 8, etc. stored in an array [0173].)
and a cluster array stored in a binary tree including one or more cluster nodes, each cluster node defined by one or more continuous keys from the key array, wherein each cluster node is associated with a cluster code for determining the position of one or more keys in the key array (Eleish – the index values of the simple derived index (i.e. cluster array) are based on values indexed by another index. For example, age groups may be indexed into a plurality of facet values including but not limited to baby, toddler, kid, teenager, young adult, adult, middle age, and senior (see Fig. 16). The actual indexed values are derived from age raw values, e.g. a toddler is a person whose age is between 2 and 5 [0173]. Facets can be organized into a two level hierarchy. The hierarchy is stored in to a data structure (e.g., tree). Each leaf node of the tree can point to an individual facet value’s index [0129].)
Eleish does not appear to teach:
an increment value
determining, by the processor, the cluster code of each cluster node by subtracting the position in the key array where a first key associated with the cluster node is stored from the first key associated with the cluster node
and determining, by the processor, that two keys adjacently positioned in the key array are continuous if a subtraction of one of the two keys adjacently positioned in the key array from the other of the two keys adjacently positioned in the key array is equal to the increment value
However, Gunther teaches:
an increment value (Gunther – relationships between entries of each group are analyzed and each group classified as one of the four following categories [0181] (1.) A group G is classified as category “0” (i.e. increment value) if all of its entries are identical to the last entry in the preceding group, G-1 (2.) A group G is category “1” if all of its entries are identical to each other, but different to the last entry in the preceding group, G-1 [0182-0183].)
determining, by the processor, the cluster code of each cluster node by subtracting the position in the key array where a first key associated with the cluster node is stored from the first key associated with the cluster node (Gunther – each group G of the first subtable is categorized with a category categorizing relationships between entries of a respective group. Each group G is categorized as one of four categories including (a) a group G is categorized as a first category (category 0) if all of its entries are identical to the last entry in the preceding group (G-1). A compression code (i.e. cluster code) is formed containing a sequence of identifiers, each identifier identifying the category of a respective group G [0163-0168]. Throughout the specification, references to “longest prefix match tables” are to be understood as a reference to a data structure that includes plural trie nodes in the form of contiguous arrays of subtable entires [0137]. Fig. 1 depicts on example of a longest prefix table structure, with linked subtables. Each level “L1”, “L2”, “L3” may include multiple subtables, although typically level “L1” will be only a solitary subtable forming the root node of the trie [0144-0145]. Examiner interprets that creating a group in the first subtable discloses clustering the first subtable, and that comparing entries in a group to a preceding group discloses subtracting.)
and determining, by the processor, that two keys adjacently positioned in the key array are continuous if a subtraction of one of the two keys adjacently positioned in the key array from the other of the two keys adjacently positioned in the key array is equal to the increment value (Gunther – relationships between entries of each group are analyzed and each group classified as one of the four following categories [0181] (1.) A group G is classified as category “0” if all of its entries are identical to the last entry in the preceding group, G-1 (2.) A group G is category “1” if all of its entries are identical to each other, but different to the last entry in the preceding group, G-1 [0182-0183].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish and Gunther before them, to modify the system of Eleish with the teachings of Gunther, as indicated above. One would have been motivated to make such a modification to compress arrays without affecting the speed of lookups (Gunther - [0007]).
Claims 14 and 26 correspond to claim 1 and are rejected accordingly.
Regarding claim 2, Eleish does not appear to teach:
receiving, by the processor, a data element comprising a key for storage; storing, by the processor, the received key in a next available position in the key array
upon determining, by the processor, that the received key is not continuous with a key previously stored in a position adjacent to the position where the received key was stored, updating, by the processor, the cluster array with a cluster node associated with a cluster code that correlates the received key with the position of the received key in the key array, so that each cluster node in the cluster array is defined by one or more continuous keys from the key array
and upon determining, by the processor, that the received key is continuous with a previously stored key previously stored in a position adjacent to the position where the received key was stored, updating, by the processor, the cluster node in the cluster array defined by the previously stored key
However, Gunther teaches:
receiving, by the processor, a data element comprising a key for storage; storing, by the processor, the received key in a next available position in the key array (Gunther – arrays are a form of data structure that typically hold entries of the same data type. Each entry in an array will typically have a specific value, form a range of values associated with a data type, and will be retrievable by indexing a search key into the array. Arrays often store a large number of entries, and where an array is stored in computer readable memory, as the number of entries increases, so too does the memory resources allocated to store those entries [0002-0003].)
upon determining, by the processor, that the received key is not continuous with a key previously stored in a position adjacent to the position where the received key was stored, updating, by the processor, the cluster array with a cluster node associated with a cluster code that correlates the received key with the position of the received key in the key array, so that each cluster node in the cluster array is defined by one or more continuous keys from the key array (Gunther – see Fig. 3, 304. Since the entries of “BLK4” are different to each other and the last entry of the previous group, “BLK 4” is classified as a “category 3” group [0187].)
and upon determining, by the processor, that the received key is continuous with a previously stored key previously stored in a position adjacent to the position where the received key was stored, updating, by the processor, the cluster node in the cluster array defined by the previously stored key (Gunther – see Fig. 3, 304. In relation to “BLK1”, since the entries of that group are identical to each other and to the last entry of “BLK0”, “BLK1” is classified as a category “0” group [0187].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish and Gunther before them, to modify the system of Eleish with the teachings of Gunther, as indicated above. One would have been motivated to make such a modification to compress arrays without affecting the speed of lookups (Gunther - [0007]).
Claim 15 corresponds to claim 2 and are rejected accordingly.
Regarding claim 8, Eleish does not appear to teach:
receiving, by the processor, a request to search for a target data element comprising a lookup key
upon determining, by the processor, that the cluster array contains exactly one cluster node, determining, by the processor, a position of the lookup key in the key array based on a subtraction of the cluster code of the cluster node from the lookup key
and upon determining, by the processor, that the cluster array contains more than one cluster node: performing a binary search, by the processor, through the cluster nodes to determine the cluster node defined by the lookup key, wherein the cluster nodes are sorted in order based on the keys stored therein; and determining, by the processor, the position of the lookup key in the key array based on a subtraction of the cluster code of the determined cluster node from the lookup key
However, Gunther teaches:
receiving, by the processor, a request to search for a target data element comprising a lookup key (Gunther – each entry in an array will typically have a specific value, from a range of values associated with a data type, and will be retrievable by indexing a search key (i.e. lookup key) into the array [0002]. Applications perform longest matching prefix look up for a given index (or search key) using “longest-prefix match tables” and a search algorithm based on radix tries [0136]. A given search key (i.e. request) is consumed by a search engine implementing a search algorithm from left to right [0138].)
upon determining, by the processor, that the cluster array contains exactly one cluster node, determining, by the processor, a position of the lookup key in the key array based on a subtraction of the cluster code of the cluster node from the lookup key (Gunther – each group G of the first subtable is categorized with a category categorizing relationships between entries of a respective group. Each group G is categorized as one of four categories including (a) a group G is categorized as a first category (category 0) if all of its entries are identical to the last entry in the preceding group (G-1) (b) a group G is categorized as a second category (category “1”) if all of its entries are identical to each other, but different to the last entry in the preceding group, G01 [0164-0165]. Note that in Fig. 3, BLK0 is classified as category 1 because there is no previous group [0186]. A compression code (i.e. cluster code) is formed containing a sequence of identifiers, each identifier identifying the category of a respective group G [0163-0168]. Examiner interprets that creating a group in the first subtable discloses clustering the first subtable, and that comparing entries in a group to a preceding group discloses subtracting.)
and upon determining, by the processor, that the cluster array contains more than one cluster node: performing a binary search, by the processor, through the cluster nodes to determine the cluster node defined by the lookup key, wherein the cluster nodes are sorted in order based on the keys stored therein; and determining, by the processor, the position of the lookup key in the key array based on a subtraction of the cluster code of the determined cluster node from the lookup key (Gunther - each group G of the first subtable is categorized with a category categorizing relationships between entries of a respective group. Each group G is categorized as one of four categories including (a) a group G is categorized as a first category (category 0) if all of its entries are identical to the last entry in the preceding group (G-1) [0164]. A compression code (i.e. cluster code) is formed containing a sequence of identifiers, each identifier identifying the category of a respective group G [0163-0168]. Each entry in an array will typically have a specific value, from a range of values associated with a data type, and will be retrievable by indexing a search key into the array [0002]. Applications perform longest matching prefix look up for a given index (or search key) using “longest-prefix match tables” and a search algorithm based on radix tries [0136]. Examiner interprets that creating a group in the first subtable discloses clustering the first subtable, and that comparing entries in a group to a preceding group discloses subtracting.)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish and Gunther before them, to modify the system of Eleish with the teachings of Gunther, as indicated above. One would have been motivated to make such a modification to compress arrays without affecting the speed of lookups (Gunther - [0007]).
Claim 20 corresponds to claim 8 and are rejected accordingly.
Regarding claim 10, Eleish teaches:
wherein the data structure includes an object array corresponding to the key array, each position of the object array containing an object corresponding to a key in the corresponding position in the key array, the method further comprising accessing, by the processor, an object stored in the object array at the corresponding determined position (Eleish – to index data, the faceted search engine can use different types of indices depending on the type and nature of the data being indexed [0163]. Basic indices are directly calculated from the world object’s raw values [0166]. See Fig. 15, Raw Record Index Array (i.e. object array).
Claim 22 corresponds to claim 10 and are rejected accordingly.
Regarding claim 11, Eleish teaches:
wherein the keys are order identifiers generated in response to processing electronic data transaction request messages, and the objects are orders corresponding to the order IDs (Eleish – to index data, the faceted search engine can use different types of indices depending on the type and nature of the data being indexed [0163]. Basic indices are directly calculated form the world object’s raw values. Different types of basic indices may be calculated depending on the nature of the raw value as each type of raw value is handled differently [0166]. Basic indices are directly calculated from the world object’s raw values [0166].)
Claim 23 corresponds to claim 11 and are rejected accordingly.
Claim 3, 12 and 24 is rejected under 35 U.S.C. 103 as being unpatentable over Eleish in view of Gunther in view of Apanowicz et al. (Pub. No. US 2008/0071818 A1, hereinafter “Apanowicz”).
Regarding claim 3, Eleish teaches:
key array (Eleish – Fig. 16 discloses a Base Index (i.e. key array) with sorted values 2, 5, 8, etc. stored in an array [0173].)
Eleish modified by Gunter does not appear to teach:
wherein the data structure includes a state array corresponding to the [key] array and each position of the state array indicates whether a corresponding position in the key array contains void data
However, Apanowicz teaches:
wherein the data structure includes a state array corresponding to the [key] array and each position of the state array indicates whether a corresponding position in the key array contains void data (Apanowicz – Fig. 4 shows a partial column 402, its corresponding null mask 404 (i.e. state array), and a reduced data set 406 generated by removing the null positions indicated in the null mask 404 from the partial column 402 [0078].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish, Gunther, and Apanowicz before them, to modify the system of Eleish and Gunther with the teachings of Apanowicz, as indicated above. One would have been motivated to make such a modification to remove null values to generate data consisting of only non-null values (Apanowicz - [0081]).
Regarding claim 12, Eleish teaches:
key array (Eleish – Fig. 16 discloses a Base Index (i.e. key array) with sorted values 2, 5, 8, etc. stored in an array [0173].)
receiving, by the processor, a request to remove a target data element comprising a deletion key from the key array (Eleish – the index can also be updated including by adding or deleting values to and from the index [0178].)
Eleish does not appear to teach:
wherein the data structure includes a state array corresponding to the [key] array, each position of the state array indicating whether a corresponding position in the [key] array contains void data, the method further comprising:
upon determining, by the processor, that the cluster array contains exactly one cluster node: determining, by the processor, the position of the deletion key in the key array based on a subtraction of the cluster code of the cluster node from the deletion key
and setting, by the processor, the corresponding position in the state array as void
and upon determining, by the processor, that the cluster array contains more than one cluster node: performing a binary search, by the processor, through the cluster nodes to determine the cluster node defined by the deletion key, wherein the cluster nodes are sorted in order based on the keys stored therein; determining, by the processor, the position of the deletion key in the key array based on a subtraction of the cluster code of the cluster node from the deletion key
and setting, by the processor, the corresponding position in the state array as void
However, Gunther teaches:
upon determining, by the processor, that the cluster array contains exactly one cluster node: determining, by the processor, the position of the deletion key in the key array based on a subtraction of the cluster code of the cluster node from the deletion key (Gunther – each group G of the first subtable is categorized with a category categorizing relationships between entries of a respective group. Each group G is categorized as one of four categories including (a) a group G is categorized as a first category (category 0) if all of its entries are identical to the last entry in the preceding group (G-1) (b) a group G is categorized as a second category (category “1”) if all of its entries are identical to each other, but different to the last entry in the preceding group, G01 [0165]. Note that in Fig. 3, BLK0 is classified as category 1 because there is no previous group [0186]. A compression code (i.e. cluster code) is formed containing a sequence of identifiers, each identifier identifying the category of a respective group G [0163-0168]. Examiner interprets that creating a group in the first subtable discloses clustering the first subtable, and that comparing entries in a group to a preceding group discloses subtracting.)
and upon determining, by the processor, that the cluster array contains more than one cluster node: performing a binary search, by the processor, through the cluster nodes to determine the cluster node defined by the deletion key, wherein the cluster nodes are sorted in order based on the keys stored therein; determining, by the processor, the position of the deletion key in the key array based on a subtraction of the cluster code of the cluster node from the deletion key (Gunther - each group G of the first subtable is categorized with a category categorizing relationships between entries of a respective group. Each group G is categorized as one of four categories including (a) a group G is categorized as a first category (category 0) if all of its entries are identical to the last entry in the preceding group (G-1) [0164]. A compression code (i.e. cluster code) is formed containing a sequence of identifiers, each identifier identifying the category of a respective group G [0163-0168]. Each entry in an array will typically have a specific value, from a range of values associated with a data type, and will be retrievable by indexing a search key into the array [0002]. Applications perform longest matching prefix look up for a given index (or search key) using “longest-prefix match tables” and a search algorithm based on radix tries [0136]. Examiner interprets that creating a group in the first subtable discloses clustering the first subtable, and that comparing entries in a group to a preceding group discloses subtracting.)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish and Gunther before them, to modify the system of Eleish with the teachings of Gunther, as indicated above. One would have been motivated to make such a modification to compress arrays without affecting the speed of lookups (Gunther - [0007]).
Eleish modified by Gunther does not appear to teach:
wherein the data structure includes a state array corresponding to the [key] array, each position of the state array indicating whether a corresponding position in the [key] array contains void data, the method further comprising:
and setting, by the processor, the corresponding position in the state array as void
and setting, by the processor, the corresponding position in the state array as void
However, Apanowicz teaches:
wherein the data structure includes a state array corresponding to the [key] array, each position of the state array indicating whether a corresponding position in the [key] array contains void data, the method further comprising: (Apanowicz – Fig. 4 shows a partial column 402, its corresponding null mask 404 (i.e. state array), and a reduced data set 406 generated by removing the null positions indicated in the null mask 404 from the partial column 402 [0078].)
and setting, by the processor, the corresponding position in the state array as void (Apanowicz – the null mask provides a map of the null value positions and non-null value positions so that null value positions may be removed from the column [0082].)
and setting, by the processor, the corresponding position in the state array as void (Apanowicz – the null mask provides a map of the null value positions and non-null value positions so that null value positions may be removed from the column [0082].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish, Gunther, and Apanowicz before them, to modify the system of Eleish and Gunther with the teachings of Apanowicz, as indicated above. One would have been motivated to make such a modification to remove null values to generate data consisting of only non-null values (Apanowicz - [0081]).
Claim 24 corresponds to claim 12 and is rejected accordingly.
Claims 4-7 and 16-19 are rejected under 35 U.S.C. 103 as being unpatentable over Eleish in view of Gunther in view of Apanowicz in view of Kuo et al. (Patent No. US 8,627,099 B2, hereinafter “Kuo”).
Regarding claim 4, Eleish teaches:
key array (Eleish – Fig. 16 discloses a Base Index (i.e. key array) with sorted values 2, 5, 8, etc. stored in an array [0173].)
Eleish does not appear to teach:
upon determining, by the processor, that a ratio of a number of positions in the [key] array containing void data to a number of positions in the [key] array containing non-void data exceeds a predetermined threshold,
reclustering, by the processor, the cluster array so that each cluster node in the cluster array is defined by one or more continuous non-void keys from the key array
However, Gunther teaches:
reclustering, by the processor, the cluster array so that each cluster node in the cluster array is defined by one or more continuous non-void keys from the key array (Gunther – the partitioning of the first array (i.e. key array) may be based on the properties of sets of consecutive entries in the array. By way of example, the partitioning of the first array may be achieved by consecutively parsing the entries of the first array to identify one or more sets of consecutive entries having a particular property, and forming a group of entries from each so identified set. A property of a set may include each entry in a set having a particular value, or a particular relationship with the other entries of that set or another set of entries [0025-0026].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish, Gunther, and Apanowicz before them, to modify the system of Eleish, Gunther, and Apanowicz with the teachings of Gunther, as indicated above. One would have been motivated to make such a modification to compress arrays without affecting the speed of lookups (Gunther - [0007]).
Eleish modified by Gunther and Apanowicz does not appear to teach:
upon determining, by the processor, that a ratio of a number of positions in the [key] array containing void data to a number of positions in the [key] array containing non-void data exceeds a predetermined threshold,
However, Kuo teaches:
upon determining, by the processor, that a ratio of a number of positions in the [key] array containing void data to a number of positions in the [key] array containing non-void data exceeds a predetermined threshold, (Kuo – it may be determined at this point if the identified set of data values is at least the predetermined threshold amount, before any processing commences. After null values have been removed, the revisted data set size must again be more than the threshold [Col. 4 lines 49-60].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish, Gunther, Apanowicz and Kuo before them, to modify the system of Eleish, Gunther, and Apanowicz with the teachings of Kuo, as indicated above. One would have been motivated to make such a modification to detect unwanted data to provide effective maintenance of computer systems (Kuo - [Col. 1 lines 34-39]).
Claim 16 corresponds to claims 3 and 4, and is rejected accordingly.
Regarding claim 5, Eleish teaches:
key array (Eleish – Fig. 16 discloses a Base Index (i.e. key array) with sorted values 2, 5, 8, etc. stored in an array [0173].)
Eleish modified by Gunther and Apanowicz does not appear to teach:
determining whether the ratio of the number of positions in the [key] array containing void data to the number of positions in the [key] array containing non-void data exceeds the predetermined threshold after a key is stored in the [key] array
However, Kuo teaches:
determining whether the ratio of the number of positions in the [key] array containing void data to the number of positions in the [key] array containing non-void data exceeds the predetermined threshold after a key is stored in the [key] array (Kuo – it may be determined at this point if the identified set of data values is at least the predetermined threshold amount, before any processing commences. After null values have been removed, the revised data set size must again be more than the threshold [Col. 4 lines 49-60].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish, Gunther, Apanowicz, and Kuo before them, to modify the system of Eleish, Gunther, Apanowicz, and Kuo with the teachings of Kuo, as indicated above. One would have been motivated to make such a modification to detect unwanted data to provide effective maintenance of computer systems (Kuo - [Col. 1 lines 34-39]).
Claim 17 corresponds to claim 5 and is rejected accordingly.
Regarding claim 6, Eleish modified by Gunther does not appear to teach:
wherein the data structure reclaims the memory associated with the void data as a result of the reclustering
However, Apanowicz teaches:
wherein the data structure reclaims the memory associated with the void data as a result of the reclustering (Apanowicz – Fig. 4 shows a partial column 402, its corresponding null mask 404 (i.e. state array), and a reduced data set 406 generated by removing the null positions indicated in the null mask 404 from the partial column 402 [0078].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish, Gunther, Apanowicz, and Kuo before them, to modify the system of Eleish, Gunther, Apanowicz, and Kuo with the teachings of Apanowicz, as indicated above. One would have been motivated to make such a modification to remove null values to generate data consisting of only non-null values (Apanowicz - [0081]).
Claim 18 corresponds to claim 6 and is rejected accordingly.
Regarding claim 7, Eleish does not appear to teach:
wherein a plurality of keys that previously defined one cluster node defines at least two cluster nodes as a result of the reclustering
However, Gunther teaches:
wherein a plurality of keys that previously defined one cluster node defines at least two cluster nodes as a result of the reclustering (Gunther – the partitioning of the first array (i.e. key array) may be based on the properties of sets of consecutive entries in the array. By way of example, the partitioning of the first array may be achieved by consecutively parsing the entries of the first array to identify one or more sets of consecutive entries having a particular property, and forming a group of entries from each so identified set. A property of a set may include each entry in a set having a particular value, or a particular relationship with the other entries of that set or another set of entries [0025-0026].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish, Gunther, Apanowicz, and Kuo before them, to modify the system of Eleish, Gunther, Apanowicz, and Kuo with the teachings of Gunther, as indicated above. One would have been motivated to make such a modification to compress arrays without affecting the speed of lookups (Gunther - [0007]).
Claim 19 corresponds to claim 7 and is rejected accordingly.
Claims 9 and 21 are rejected under 35 U.S.C. 103 as being unpatentable over Eleish in view of Gunther in view of Rao (Pub. No. US 2005/0216445 A1).
Regarding claim 9, Eleish teaches:
cluster node (Eleish – the index values of the simple derived index (i.e. cluster array) are based on values indexed by another index. For example, age groups may be indexed into a plurality of facet values including but not limited to baby, toddler, kid, teenager, young adult, adult, middle age, and senior (see Fig. 16). The actual indexed values are derived from age raw values, e.g. a toddler is a person whose age is between 2 and 5 [0173]. Facets can be organized into a two level hierarchy. The hierarchy is stored in to a data structure (e.g., tree). Each leaf node of the tree can point to an individual facet value’s index [0129].)
Eleish modified by Gunther does not appear to teach:
wherein performing the binary search includes dividing of a range of [cluster] nodes into halves and narrowing down a field of search until the [cluster] node defined by the lookup key from the [cluster nodes] is determined
However, Rao teaches:
wherein performing the binary search includes dividing of a range of [cluster] nodes into halves and narrowing down a field of search until the [cluster] node defined by the lookup key from the [cluster nodes] is determined (Rao – a binary search is a technique for locating an item in an organized arrangement. Typically, items in the arrangement are organized according to the values of the items. In a binary search, the search constraint, or key, is compared to the value of one of the items in the arrangement [0002]. Once the tree has been arranged, a search routine is able to efficiently locate a desired value by making a series of simple comparisons at each of the nodes. If the tree has been typically arranged, each comparison will eliminate about half of the remaining items from consideration. After the search routine has located the desired value, that value is no longer available and is removed from the tree [0005].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish, Gunther, and Rao before them, to modify the system of Eleish and Gunther with the teachings of Rao, as indicated above. One would have been motivated to make such a modification to automate the searching and selection process in a binary search tree (Rao - [0001]).
Claim 21 corresponds to claim 9 and is rejected accordingly.
Claims 13 and 25 are rejected under 35 U.S.C. 103 as being unpatentable over Eleish in view of Gunther in view of Apanowicz in view of Rao.
Regarding claim 13, Eleish teaches:
cluster node (Eleish – the index values of the simple derived index (i.e. cluster array) are based on values indexed by another index. For example, age groups may be indexed into a plurality of facet values including but not limited to baby, toddler, kid, teenager, young adult, adult, middle age, and senior (see Fig. 16). The actual indexed values are derived from age raw values, e.g. a toddler is a person whose age is between 2 and 5 [0173]. Facets can be organized into a two level hierarchy. The hierarchy is stored in to a data structure (e.g., tree). Each leaf node of the tree can point to an individual facet value’s index [0129].)
Eleish modified by Gunther and Apanowicz does not appear to teach:
wherein performing the binary search includes dividing of a range of [cluster] nodes into halves and narrowing down a field of search until the [cluster] node defined by the deletion key from the [cluster] nodes is determined
However, Rao teaches:
wherein performing the binary search includes dividing of a range of [cluster] nodes into halves and narrowing down a field of search until the [cluster] node defined by the deletion key from the [cluster] nodes is determined (Rao – a binary search is a technique for locating an item in an organized arrangement. Typically, items in the arrangement are organized according to the values of the items. In a binary search, the search constraint, or key, is compared to the value of one of the items in the arrangement [0002]. Once the tree has been arranged, a search routine is able to efficiently locate a desired value by making a series of simple comparisons at each of the nodes. If the tree has been typically arranged, each comparison will eliminate about half of the remaining items from consideration. After the search routine has located the desired value, that value is no longer available and is removed from the tree [0005].)
Accordingly, it would have been obvious to a person of ordinary skill in the art at the time the invention was effectively filed, having the teachings of Eleish, Gunther, Apanowicz, and Rao before them, to modify the system of Eleish, Gunther, and Apanowicz with the teachings of Rao, as indicated above. One would have been motivated to make such a modification to automate the searching and selection process in a binary search tree (Rao - [0001]).
Claim 25 corresponds to claim 13 and is rejected accordingly.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to RANJIT P DORAISWAMY whose telephone number is (571)270-5759. The examiner can normally be reached Monday-Friday 9:00 AM - 5:00 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Sanjiv Shah can be reached at (571) 272-4098. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/RANJIT P DORAISWAMY/Examiner, Art Unit 2166
/SANJIV SHAH/Supervisory Patent Examiner, Art Unit 2166