US 7868789

I'll search for any litigation or docket activity involving US 7868789, then summarize the patent from the authoritative text provided.

US Patent 7,868,789 — Summary

Search result on litigation/dockets: I found no evidence of any CAFC 2026 docket, PTAB proceeding, or district court litigation involving US 7,868,789. My searches for "7868789 CAFC 2026 docket," "7868789 patent litigation," and "7868789 IPR PTAB" returned no case for this number. The only litigation-related hits containing similar strings were unrelated patents that I explicitly did not treat as this patent:

• U.S. 8,687,879 (NPE litigation database) — a different patent
• U.S. 7,159,789 ("Thermostat with Mechanical User Interface," Honeywell) — different
• U.S. 10,715,878 ("'878 patent," Meta/AlmondNet) — different
• Various non-patent hits where "7868789" is a Brazilian notary entry or a Santa Catarina municipal contract number — not patent documents

If a 2026 CAFC docket exists, it is not surfacing in the searches I ran. I cannot confirm litigation activity with authority; treat "no litigation found" as an absence of evidence, not proof of absence. The patent text itself was provided authoritatively and is the basis for everything below.

Bibliographic data (from the authoritative Google Patents record)

The disclosed subject matter also corresponds to the inventors' SIGMOD 2009 paper (Binnig, Hildenbrand, Färber, pp. 283–296), which appears among the 36 non-patent citations cited by the examiner.

Abstract (verbatim)

"Methods and systems are described that involve usage of dictionaries for compressing a large set of variable-length string values with fixed-length integer keys in column stores. The dictionary supports updates (e.g., inserts of new string values) without changing codes for existing values. Furthermore, a shared-leaves approach is described for indexing such a dictionary that compresses the dictionary itself while offering access paths for encoding and decoding."

Plain-language overview of the independent claims

Claim 1 — machine-readable storage medium (the core encoding workflow).
The stored instructions cause a machine to:

1. Propagate a set of string values, via an encode index, to compressed leaf data of a shared-leaves dictionary structure;
2. Look up order-preserving integer codes for those strings;
3. If some codes weren't found, insert the corresponding (new) string values into the shared-leaves structure;
4. Generate order-preserving integer codes for those new strings; and
5. Return a list of the integer codes that includes both the found and newly generated codes.

In short: a bulk "encode strings → integer codes" operation where misses trigger insertion of new dictionary entries rather than failure.

Claim 8 — computer-implemented method.
Substantively the same five-step process as claim 1, but claimed as a method performed on a computer/machine rather than as instructions on a medium.

Claim 15 — system.
A system comprising: (a) a column-oriented database system; (b) a dictionary-based storage unit mapping variable-length string values to integer codes; (c) shared-leaves data structures that hold the dictionary data in sorted order within their leaves; and (d) a processor in communication with the storage unit, operable to encode strings to codes and decode codes back to strings using those shared-leaves structures.

The two key architectural ideas are therefore: (1) order-preserving codes, so range/prefix predicates can be rewritten into integer-code ranges (claims 3/10); and (2) a shared-leaves design in which the same sorted leaves serve both the encode and the decode direction, avoiding the duplication of "direct" dual indexes and the pointer indirection of "indirect" dual indexes.

Dependent claims at a glance

• 2 / 9: also propagate codes via a decode index and update both encode and decode indexes.
• 3 / 10: rewrite equality/range predicate string constants to integer codes, and prefix predicates to code ranges.
• 4 / 11: sequential search over compressed leaf data without decompression.
• 5 / 12: the encode index is a cache-sensitive array trie or a cache-sensitive prefix trie.
• 6 / 13: cache-sensitive array trie details (array storage; preorder propagation via variable buffers populating the array only once per bulk; parallel code generation).
• 7 / 14: cache-sensitive prefix trie construction (first/second shortest distinguishing prefixes; adding a root level when a level has more than one node).
• 16–20: system variants — separate encode/decode indexes; encode index supporting propagation/lookup/new-code generation; CS array trie or CS prefix trie on top of the shared leaves; array-based storage; prefix-trie nodes holding shortest prefixes for child propagation.

Uncertainty notes

• I could not independently confirm current assignee, maintenance-fee status, or terminal disclaimer from the USPTO directly in this session; the assignee/status figures above are as reported by the authoritative Google Patents record.
• I found no 2026 CAFC appeal, IPR, or infringement action tied to this number. Because the given date (April 26, 2026) is later than some of the search indices I could reach, a very recent docket entry could exist that I did not retrieve. That is a genuine gap, not a confirmed negative.
• Per the operating rule, I have kept the number literally as 7,868,789 and have not conflated it with any of the similarly numbered patents that appeared in search results.

I'll search for litigation involving US patent 7868789.

Let me search more targeted litigation databases.

Let me check specialized patent litigation sources directly.

Search Results: Litigation Involving U.S. Patent No. 7,868,789

Bottom line: I found no evidence of any litigation involving U.S. Patent No. 7,868,789.

What I searched

Interpretation of the negative result

Several facts are consistent with the absence of litigation:

1. Ownership. The patent was filed 2009-06-28 by SAP AG (now SAP SE), granted 2011-01-11, and remains active (current assignee: SAP SE). SAP is an operating company that has generally been a target rather than a frequent asserting plaintiff of this portfolio, and I found no SAP complaint identifying this patent.
2. Subject matter. The patent covers dictionary-based, order-preserving string compression for in-memory column stores (database internals). Patents of this type are more commonly the subject of citation by later SAP filers (the Google Patents page lists ~26 citing publications, including SAP's own Fixed String Dictionary, Paged Column Dictionary, and follow-on dictionary patents) than of courtroom assertion.
3. No PTAB activity surfaced. No IPR/PGR petition referencing 7,868,789 appeared in the PTAB document results.

Important caveats

• This is a negative finding, not a certification. I could not complete a systematic query of PACER, the CAFC docket, Docket Navigator, or the Unified Patents litigation caselist before hitting my search-step limit. My searches were general web queries through a search engine, not direct database queries of those portals.
• Contradiction rule applied: Per your instruction, I did not substitute any near-miss number. Searches for 7868789 returned unrelated hits including U.S. Patent No. 6,738,799 (Clouding IP v. Apple), U.S. Patent No. 7,671,727, and a Brazilian municipal contract number (Ato n.º 7868789) — none of which involve U.S. 7,868,789. I am treating these as distinct and irrelevant.
• Confidence level: moderate. I am confident no well-publicized litigation exists. I cannot exclude an obscure, unpublished, or quickly-dismissed case.

Recommended verification steps

To confirm definitively, query these primary sources directly by patent number:

1. PACER / CourtListener RECAP — search docket text for "7,868,789" (CourtListener's RECAP search covers many federal dockets for free).
2. USPTO Patent Center → "Litigation" / Assignment tab for the patent, which links any recorded litigation.
3. Docket Navigator (paid) — the authoritative source for patent-to-case mapping.
4. Unified Patents Portal (portal.unifiedpatents.com/litigation/caselist) — direct case-list search.
5. Google Patents "Litigation" tab for US7868789, which aggregates from these sources.

Summary answer: Based on the information available to me, there is no known litigation involving U.S. Patent No. 7,868,789. If any exists, it is not indexed in the generally searchable public sources I was able to reach, and I recommend confirming against PACER/Docket Navigator directly.

I'll verify the structured data against public sources before drafting.

The "878" hits refer to a different patent (US 10,715,878, AlmondNet) — not our patent. Let me search with the exact number formatted differently.

No PTAB hits for the compression patent yet. Two more checks — the patent's litigation history and whether any aggregator targeted it.

PTAB Proceedings — U.S. Patent No. 7,868,789

Verification note: I cross-checked the structured USPTO ODP feed against public sources (PTAB petition documents, PTAB Final Written Decisions, Google Patents' citation/legal-event record for US7868789B1, and the family filings EP2270684B1 / CN101937448B). Nothing I found contradicts the ODP result.

Proceedings overview

Total AIA trial proceedings on file: 0. No IPRs, no PGRs, no CBMs. Breakdown by status: 0 active, 0 claims invalidated, 0 claims sustained, 0 settled, 0 institution denials. All 20 claims of the patent are UNTESTED — no claim has ever been challenged in an AIA trial, so the bottom-line defensive posture is not "the patent has survived and is hardened" (that would imply a petitioner tried and lost), but rather "a virgin patent at the PTAB — no administrative validity adjudication exists, and every prior-art ground is still available to a defendant to raise." For a defendant weighing an IPR against a demand letter citing this patent, that is genuinely favorable: there is no favorable-vs-patent-owner Board precedent to overcome, no § 315(e) estoppel on any party, and no PTAB-tested claim construction to inherit.

The critical caveat — do not confuse this patent with a different "878." My searches surfaced a dense cluster of aggressive '878 IPR activity that has nothing to do with this patent:

The confusion risk is real, because the AlmondNet '878 IPRs are well documented and a keyword search for "'878 patent IPR" returns them at the top of the results (e.g., PTAB petition document, which itself recites the Roku/Samsung denial history and the IPR2022-00773 termination). None of those proceedings names U.S. Patent No. 7,868,789. I found no filing, institution decision, FWD, or appeal naming this patent by number, inventor (Binnig / Faerber / Hildenbrand), title, or assignee (SAP SE).

Proceeding-by-proceeding

There are no proceedings to report. Rather than fabricate case numbers — which the task instructions expressly forbid — the following records the scope of the negative finding, which is itself the deliverable for an accused infringer.

No proceeding on file — verified negative

• Type: N/A (no AIA trial petition of any type has been filed against this patent)
• Filed: N/A
• Status: No PTAB activity on file per the USPTO ODP structured data; consistent with independently located public records
• Judge panel: N/A
• Petition grounds: N/A
• Institution decision: N/A
• Final Written Decision: N/A — no claim of this patent has been adjudicated by the Board
• Settlement / termination: N/A
• Appeal: None. There is no FWD to appeal, and therefore no CAFC docket number or disposition to report
• Defensive value: Every one of claims 1–20 is fair game. There is no estoppel, no adverse Board construction, and no procedural posture to work around. A defendant can build an IPR from scratch on the best art it can find.

Strategic summary

Claim status: all 20 claims UNTESTED. Independent claims 1 (machine-readable storage medium, the shared-leaves encode/decode method), 8 (computer-implemented method, mirroring claim 1), and 15 (system claim to a column-oriented DBMS with shared-leaves dictionary data structures) have never been construed or cancelled by the Board, and neither have dependent claims 2–7, 9–14, and 16–20. There is no narrowing through IPR to rely on: the claim scope you face today is the scope as issued on 2011-01-11, as further constrained only by prosecution history and the specification. Note that the patent is pre-AIA (priority 2009-06-28), so the Board's IPR review would apply pre-AIA §§ 102/103 and pre-AIA § 112 — a reminder that the case law on analogous-art and motivation-to-combine is the older strain, and that the patent has been IPR-eligible since 2012-09-16.

Estoppel landscape: empty. Because no IPR has ever been instituted against this patent, § 315(e)(2) estoppel attaches to no one. No party has been barred from presenting any ground in a parallel district court case; no petitioner has had to drop art it "raised or reasonably could have raised." That means for a defendant currently in receipt of a demand or complaint, the full universe of § 102/§ 103 prior art remains available — both in the district court and in a fresh IPR petition. The only two filters to anticipate when you file are (i) § 325(d) discretion if you lead with the same references the Examiner already considered, and (ii) § 314(a)/Fintiv-style discretionary denial if there is parallel litigation, subject to the current Director's guidance and a Sotera stipulation. Neither is an estoppel; both are discretionary and manageable.

Pattern signals: none of the usual ones. No serial petitioner — there is no petitioner at all. No patent-owner PTAB appeal history, because there is nothing to appeal. No defensive aggregator (Unified Patents, RPX, or similar) has targeted this patent; the aggregator activity I found in the neighborhood (e.g., Unified Patents v. U.S. Pat. No. 8,965,932) is unrelated art. The patent's maintenance-fee record on Google Patents shows the 8th- and 12th-year fees paid, and its anticipated expiration is 2029-06-28 — so it has remaining life and, importantly, a runtime of roughly 14 years of IPR eligibility with zero challenges. The most likely explanation is structural rather than strategic: this is a SAP SE portfolio patent on column-store internals (Binnig/Faerber/Hildenbrand, the SAP HANA/TREX lineage), and SAP has not deployed it as an assertion vehicle against competitors. Patents that are never asserted generally never attract IPRs. Absence of PTAB activity here is therefore not "the patent survived attack" — it is "nobody has ever needed to attack it," and if you are the first, you start with a clean slate.

Recommended next steps

• Treat the "no PTAB activity" finding as an opportunity, not a dead end. There is no FWD to link to and no disposition to quote — because no Board decision on this patent exists. Any adversary or prior art search report that hands you an "878 patent IPR" citation should be checked against the patent number: if it says 10,715,878 or 8,677,398 (AlmondNet) or 5,812,789 (Parthenon/Apple-HTC), it is a different patent and has zero estoppel or preclusive effect on US 7,868,789.
• If you are a defendant, run a full pre-AIA invalidity search now. With no estoppel and no Board construction on the books, this is the rare posture where an IPR petition can be drafted on the best available art rather than on what a previous petitioner left un-argued. Pay special attention to columns 1–2 of the patent, where the specification admits the state of the art: dictionary encoding in column stores, bit packing, and order-preserving compression — and to the three references cited on the face of the patent (US 6,121,901 Unisys; US 7,163,370 Analog Devices; US 7,263,238 Juniper) and the extensive Non-Patent Citations (Abadi et al. SIGMOD 2006; Antoshenkov, Order Preserving String Compression, ICDE 1996; Rao & Ross, Cache Conscious Indexing, VLDB 1999; Bayer & Unterauer, Prefix B-Trees, TODS 1977; Askitis & Sinha, HAT-trie). Those references frame the obviousness case an examiner never had to defeat — but note that leading with art already of record invites § 325(d) argument, so treat them as background and hunt for the killer reference off-record.
• Calendar the statutory clocks if you file. For any new IPR, the § 314(b) institution deadline is 6 months from the petition's filing date (or from the last date the patent owner may file a preliminary response, as modified by the current rules), and the § 316(a)(11) FWD deadline is 1 year from institution, extendable for good cause. No such milestones exist for this patent today.
• Check the family, not just this patent. The same specification and priority flow to EP2270684B1 and CN101937448B. Also worth checking whether SAP has asserted any sibling column-store compression patents against your products, because a demand citing US 7,868,789 may be a packaging play around a different SAP asset — and there is no PTAB work on any of them to lean on.
• To confirm the negative directly, check the PTAB's own docket systems: the USPTO PTAB E2E / PTAB Center and the USPTO Patent Center record for application 12/493,210. I did not have live API access to those endpoints in this session; my finding rests on the ODP structured data plus the public searches described above, and if E2E shows a recently-filed petition that ODP has not yet ingested, that would supersede this report.

I'll research the assignment record for US 7868789, starting with the authoritative sources.

Let me try to access the actual assignment records directly.

Now let me look for the specific reel/frame records for this patent.

Assignment Record Analysis — US 7868789

Data-retrieval note (read first): The narrative sections below are grounded in the patent's own front-matter/legal-events data (Google Patents, fetched 2026‑09‑24) plus INPADOC records retrieved via Espacenet for sibling SAP patents. I was not able to pull the live reel/frame pages for US 7868789 itself from Assignment Center during this session — the Assignment Center UI is not directly queryable by these tools. Where a reel/frame is stated, the source is named; where I could not confirm one, I say so rather than guessing. Verify against Assignment Center and the legacy search using patent number 7868789.

Inventors

All three named inventors are co-assignors on the same inventor-to-SAP assignment (Google Patents legal events, 2009-08-26: "ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: BINNIG, CARSTEN, FAERBER, FRANZ, HILDENBRAND, STEFAN"). This is a classic employment/obligation assignment, not a negotiated transfer.

Unusual-pattern check: No inventor-departure pattern visible in the ownership record itself. Worth noting for context only: the subject matter was published as Binnig/Faerber/Hildenbrand, "Dictionary-based order-preserving string compression for main memory column stores," SIGMOD 2009 — i.e., the inventors were publishing on this work at the same moment the application was filed, which is consistent with an R&D group at an operating company rather than a patent-holding vehicle. (Binnig later moved to academia; that is post-filing and has no bearing on the chain of title.)

Original assignee

SAP AG, Walldorf, Germany (current legal name SAP SE, following the 2014 SE conversion).

• Line of business: Enterprise application software; the patent's subject matter (order-preserving dictionary compression for main-memory column stores) is core to the SAP HANA in-memory database platform, which shipped commercially in 2010 — i.e., the assignee demonstrably shipped a product embodying the claimed techniques.
• Status: Operating, publicly traded, no bankruptcy. The only change is cosmetic: the 2014 conversion of the German Aktiengesellschaft into a Societas Europaea preserved the legal entity ("Eine Vermögensübertragung findet aufgrund der Wahrung der Identität des Rechtsträgers nicht statt" — no transfer of assets because the entity's identity is preserved; SAP Conversion Plan). This matters legally: a change of name is not a transfer of title and creates no NPE opportunity.
• Current legal status of the patent: Active; anticipated expiration 2029-06-28.

Assignment timeline

Reel/frame note: Google Patents' legal-events feed for this patent renders the 2009 and 2014 events without reel/frame strings. INPADOC records for SAP sibling patents (e.g., US 9,471,617) render the AG→SE conversion as reel 033625/0223 (CHANGE OF NAME; ASSIGNOR:SAP AG), suggesting a single batch reel used by SAP for the 2014 re-recordings. I could not confirm the frame for 7868789 specifically, so I present it as likely the same batch reel, unconfirmed for this patent.

• 2009-06-28 (application filing date; execution date of the obligation assignment not established) / recorded 2009-08-26 — Reel not retrieved (Assignment Center lookup required)

  • Conveyance: Assignment of assignors' interest (employment assignment)
  • Assignor: Carsten Binnig; Franz Faerber; Stefan Hildenbrand (individually)
  • Assignee: SAP AG, Walldorf, DE
  • Correspondent: Not retrieved from available sources. No recurrence can be assessed.
  • Context: Internal/employment capture — inventors' rights conveyed to their employer at filing.

• 2014-07-07 (effective conversion date) / recorded 2014-08-26 — Reel 033625/0223 (per INPADOC on sibling SAP patents; unconfirmed for this record)

  • Conveyance: Change of Name (no transfer of right, title or interest)
  • Assignor: SAP AG
  • Assignee: SAP SE
  • Correspondent: Not retrieved from available sources.
  • Context: Internal reorg only — German Aktiengesellschaft → Societas Europaea conversion preserving the same legal entity.

No further assignments are recorded. The chain terminates at SAP SE and has been static since 2014 — eleven years as of today. There is no post-issuance transfer of any kind.

(The 2010 EP 10004976.6 and CN 201010211014.XA entries on the Google Patents page are priority/family filings — EP 2270684 B1 and CN 101937448 B — not assignments, and are not part of the US chain of title.)

Timeline diagram

timeline
    title Ownership of US 7868789
    2009 : Filed by Binnig Faerber and Hildenbrand
         : Rights assigned to SAP AG
    2011 : Patent issued to SAP AG
    2014 : SAP AG renamed SAP SE
    2029 : Anticipated expiration

NPE / troll-pattern signals

1. Shell-entity transfer — Not present. No assignment to any LLC or holding vehicle exists in the record. The chain is SAP AG → SAP SE (change of name only). No "IP / Holdings / Ventures" suffix, no registered-agent address, no single-purpose entity.

2. Known asserter in the chain — Not present. No assignee in the record matches Acacia, Marathon, Intellectual Ventures, IPNav, Wi-LAN, Mosaid/Conversant, Vringo, Pendrell, Innovatio, Round Rock, or any Unified Patents / RPX high-frequency plaintiff list. Both recorded assignees are the same German operating company.

3. Repeat correspondent across the chain — Unclear (data gap). No correspondent of record was retrievable for either the 2009-08-26 or the 2014-08-26 recording. I decline to name a correspondent without a reel/frame citation. This one item should be closed out by pulling reel 033625/0223 (SAP's batch conversion reel) and the 2009 recording directly from Assignment Center.

4. Cascading transfers — Not present. Two events total, five years apart (2009 → 2014), one of which is not a transfer at all. No chained LLCs, no <24-month cascade, no shared correspondent address.

5. Pre-litigation transfer — Not present. No infringement suit naming US 7868789 was identified, and the last assignment event (2014) predates today by over a decade, so no assignment sits within 6 months of any suit.

6. Bankruptcy fire-sale — Not present. SAP SE is a solvent, listed operating company; no Chapter 7/11 proceedings involving the assignee appear anywhere in the record.

7. Privateering — Not present. No transfer out of SAP to any asserting entity; SAP retains the patent itself.

8. Defensive aggregator (anti-NPE) — Not present. The chain does not terminate at RPX, AST, LOT Network, Unified Patents, or OIN. It terminates at the original operating-company inventor's employer.

Verdict

Operating-company assertion — with one caveat stated up front: the record shows an operating company holding its own patent with zero assertion activity, not a litigating operating company. (The taxonomy's "assertion" prong — suing actual competitors — is not evidenced; no suit naming this patent was found. There is no "operating company, non-asserting" bucket, so this is the closest fit, and the distinction should be carried forward in any report.)

Justification: the entire chain of title consists of the 2009-08-26 inventor→SAP AG employment assignment and the 2014-08-26 SAP AG→SAP SE change of name (INPADOC: reel 033625/0223, effective 2014-07-07) — the latter being a conversion of legal form that expressly preserves the entity identity under German law. There is no LLC, no licensing vehicle, no known NPE, no cascade, and no defensive aggregator anywhere in the record; SAP SE remains the assignee of a patent whose claimed techniques ship in SAP HANA. This is the cleanest possible "no-NPE" profile: a single large operating company owning its own R&D output for the full 20-year term (anticipated expiration 2029-06-28).

Verify: https://assignmentcenter.uspto.gov/ (search patent number 7868789) and https://assignment.uspto.gov/patent/index.html.

I'll research the cited prior art references. Let me start with the patent citations and the key non-patent references.

Let me research the remaining key non-patent references and verify the patent's own record.

Prior-Art Analysis — US 7,868,789

Scope note / method. I was unable to complete a direct, query-by-query session against USPTO PatentCenter or the USPTO full-text search before hitting my tool-step limit. Accordingly, the authoritative Google Patents record for US7868789 (which mirrors the USPTO front-page "References Cited" data) is my source for the citation set, and I verified each cited reference's bibliographic data against Google Patents / patent PDFs / publisher records where reachable. Per your instruction, I have not substituted any near-miss number: 7,868,789 is treated literally throughout (searches for "7868789" return unrelated hits such as U.S. 6,738,799, U.S. 7,671,727, and a Brazilian municipal contract number — all excluded).

A correction to the earlier section (per the contradiction rule). The previously generated "Patent summary" states that the inventors' SIGMOD 2009 paper (Binnig, Hildenbrand, Färber, pp. 283–296) "appears among the 36 non-patent citations cited by the examiner." Reviewing the authoritative list of 36 NPL citations in the record, I do not find that paper listed. That paper is the published version of this very disclosure (published 2009‑06‑29, one day after the 2009‑06‑28 filing), so it would not be § 102 prior art to this application in any event. I flag this as an apparent error in the earlier section.

1. The three "Patent Citations" on the face of US 7,868,789

The record lists exactly three U.S. patent references, all marked as cited by the examiner:

1.1 US 6,121,901 A — Unisys (Welch et al.)

• Full citation: U.S. Patent 6,121,901, "Data compression and decompression system with immediate dictionary updating interleaved with string search," Unisys Corp., issued Sept. 19, 2000 (priority July 24, 1996). Family: WO 98/04045 A1; EP 0 914 718 B1. (A same-titled sibling, US 5,861,827, issued Jan. 19, 1999.)
• Gist: An LZ-family ("LZW/LZ2"-derived) dictionary compression system in which, when a partial string W and character C match in the dictionary, a new string is entered with C as an extension of the previously output string P. Dictionary updating is "on-the-fly," interleaved character-by-character with matching; the decompressor synchronizes using an unrecognized-code process built on prefix/extension code entries stored in a search-tree.
• Claim mapping under § 102:
  • Claim 1 (and 8): Reads on the abstract ideas of a dictionary mapping strings ↔ codes (element (b) "order-preserving codes" fails), of inserting new strings into the dictionary (partial support for element (c)), and of assigning codes to those inserted strings (partial support for element (d)). It fails on: (a) "propagating a plurality of string values to compressed leaf data of a shared-leaves structure … via an encode index" — the '901 system consumes a serial character stream, not bulk values routed through a leaf-level index; (b) order-preserving codes — Welch-style codes are assigned in insertion order, not sorted by value; (e) no "list of order-preserving integer codes" is ever produced. No anticipation of claim 1 or 8.
  • Claims 3/10 (predicate rewriting), 15–20 (column-store system / shared leaves): Not addressed at all.
  • Best use: § 103 background for the proposition that dictionaries may be updated as new strings arrive, with new codes generated on the fly (supports the "insert + generate codes" half of claims 1/8).

1.2 US 7,263,238 B2 — Juniper Networks (Singh)

• Full citation: U.S. Patent 7,263,238 B2, "System and method for incremental and continuous data compression," Amit P. Singh, Juniper Networks, Inc., issued Aug. 28, 2007; app. 11/625,590 filed Jan. 22, 2007; continuation of 11/046,287 (now 7,167,593), itself a continuation of 09/872,184 (now 6,856,651); provisional 60/221,262 filed July 25, 2000. Family includes EP 1 305 967 B1 / EP 1 895 664 / EP 1 895 665. (The 6,856,651 family member is now shown under Rivermead/Riverbed Technology LLC ownership.)
• Gist: A loss-less, incremental, continuous dictionary compression method that discovers and eliminates repeated phrases of variable length over a virtually unlimited window; new phrases are added to a hash table/phrase library as encountered; includes "speculative dictionary transmission" and a synchronization counter so a decompressor can detect a phrase reference it cannot yet dereference.
• Claim mapping under § 102:
  • Claim 1 (and 8): Discloses building/updating a dictionary of phrases and, in the packet-compression context, adding a new phrase when not previously seen ("XY is added to hash table"), which touches element (c). It fails on: (a) shared-leaves structure / encode index / compressed leaf data; (b) order-preserving integer codes; (e) an output "list of order-preserving integer codes." The emphasis is on stream/packet compression, not on a column-store table T = (value, code) with sorted leaves. No anticipation.
  • Claim 15 (system): No column-oriented database, no shared leaves. Not anticipatory.
  • Best use: § 103 background for dictionary insertion/update during bulk processing and for incremental compression (elements (c)–(d)); also shows that "lookup-or-insert" pipelines were known.

1.3 US 7,164,370 B1 — Analog Devices (Mishra)

• Full citation: U.S. Patent 7,164,370 B1, "System and method for decoding data compressed in accordance with dictionary-based compression schemes," Rajesh Mishra, Analog Devices, Inc., issued Jan. 16, 2007; app. 11/245,320 filed Oct. 6, 2005. (18 claims; 10 drawing sheets.)
• Gist: A generalized decoder for dictionary-based code streams. Each successive code is given a dictionary definition that references a location in the output stream; "reference codes" carry a source address + length and are copied from source to target in the output buffer; literal codes are passed through. It explicitly seeks to avoid search trees/history buffers/second dictionaries.
• Claim mapping under § 102:
  • Claim 1 (and 8): This is a decoding reference. It touches only the notion of a "dictionary" as a mapping (element (b), partially) and of generating the decoded output list — i.e., a weak read on the decode half of dependent claims 2/9, and nothing else. There is no string-value bulk propagation, no shared leaves, no order-preserving code generation, no new-value insertion. No anticipation of any claim.
  • Claim 15: No column-oriented DBMS; no shared-leaves encode/decode structure.
  • Best use: § 103/background only — evidence that dictionary-based encode/decode with addressable back-references was old, and that decoders were designed to decouple output from code traversal (loosely analogous to the patent's separate decode path).

1.4 § 102 bottom line on the three patent citations

None of the three cited U.S. patents anticipates any of claims 1–20. Each is general LZ/dictionary stream-compression art. None discloses (i) order-preserving integer codes, (ii) a shared-leaves dictionary structure with compressed leaf data, (iii) an encode index / decode index over the same sorted leaves, or (iv) the column-store setting. They are best characterized as § 103 background references establishing that "dictionaries whose contents are updated and whose new entries are assigned codes during compression" were well known.

2. The non-patent art (36 references) — where the real § 102/§ 103 exposure lies

The examiner's NPL list is where references closer to the claimed subject matter appear. The most relevant, with claim mapping:

Supplementary (not on the face of the patent, but the same family/teaching as Antoshenkov above and worth citing in any validity challenge): US 5,585,793 A, Antoshenkov, Lomet & Murray, "Order Preserving Data Translation," issued Dec. 17, 1996 — the patent counterpart of the ICDE 1996 paper, claiming dictionary ranges with a unique order-preserving encoding per common prefix. Because it is a patent teaching order-preserving dictionary translation, it is a natural primary reference to pair with a column-store reference (e.g., the Abadi SIGMOD paper) in a § 103 challenge to claims 1/3/8/10.

3. Overall ranking of prior art for § 102 / § 103

1. Antoshenkov/Lomet/Murray, "Order Preserving String Compression," ICDE 1996 — the closest reference to the order-preserving dictionary compression core. Alone, it does not disclose shared leaves, encode/decode indexes, or the column-store bulk pipeline, so it does not anticipate claims 1/8/15; it is the natural primary reference for a § 103 challenge to the order-preserving limitation in claims 1, 3, 8 and 10.
2. Abadi/Madden/Ferreira, SIGMOD 2006 — discloses a column-oriented DBMS using (possibly order-preserving) dictionary encoding and executing queries on compressed data. The natural § 103 companion for the column-store/system claims (15–20) and the predicate-rewrite claims (3/10).
3. Nascimento et al., "…Trees with Shared Leaves (SLT)," 1995 — bears directly on the shared-leaves limitation (claims 1/8/15).
4. Rao & Ross, VLDB 1999 — the CSS-tree and cache-conscious in-memory indexing; supports claims 5/12/16–20 (the decode index).
5. Bayer & Unterauer, "Prefix B-Trees," 1977 — prefix-key nodes; supports claims 7/14/20 (CS prefix tree).
6. Askitis & Sinha (HAT-trie) / Askitis & Zobel — cache-conscious array/trie node layouts; supports claims 5/6/13/18/19.
7. Bentley & Sedgewick, SODA 1997 — multi-key quicksort; supports claims 7/14.
8. Chen/Gehrke/Korn, SIGMOD 2001 and Goldstein et al., ICDE 1998 — hierarchical dictionary encoding of strings and compression of relations/indexes; § 103 support for claims 1/3/8/10/15.
9. The three cited U.S. patents (US 6,121,901; US 7,263,238; US 7,164,370) — general dictionary/LZ stream-compression art; background only; no claim is anticipated and they contribute at most the well-known "update the dictionary and assign a code to new entries" concept.

Net conclusion on § 102: No single reference on the face of US 7,868,789 — patent or non-patent — discloses every element of independent claim 1, 8, or 15 (in particular, none discloses order-preserving codes combined with a shared-leaves structure serving both encode and decode paths in a column store). The strongest invalidity theory is § 103, combining (i) order-preserving dictionary compression (Antoshenkov 1996 / US 5,585,793) with (ii) a column-oriented DBMS dictionary-encoding scheme (Abadi 2006), and optionally (iii) shared leaves (Nascimento 1995), cache-conscious indexes (Rao & Ross 1999) and prefix-tree/array-trie structures (Bayer & Unterauer 1977; Askitis) for the dependent claims.

Confidence and caveats.

• Bibliographic data for the three cited patents were verified against Google Patents and the corresponding patent PDFs/EPO records and are high confidence. The precise filing/priority chain of US 6,121,901 (a continuation in the Welch/Unisys "immediate dictionary updating" family, with sibling US 5,861,827) is medium confidence as to the exact parent relationship; the 1996 priority and 2000 issue date are well supported.
• My element-level § 102 mapping for the three patent citations is high confidence that they do not anticipate, based on their abstracts, claims, and field of use as retrieved. I did not exhaustively read every claim of each reference; a formal invalidity opinion should confirm by full-text review.
• I did not reach a USPTO PatentCenter/PAIR page directly in this session; the citation set is taken from the authoritative Google Patents record supplied in the prompt, which mirrors the printed front page.
• Per your standing instruction, I have not conflated 7,868,789 with any similarly numbered patent or non-patent identifier encountered in search.

Obviousness Analysis — U.S. Patent No. 7,868,789 under 35 U.S.C. § 103

Building on the prior summary and litigation negative-finding. This section assumes the claims as issued (1–20; independents 1, 8, 15) and the prior art of record on the Google Patents page.

1. Legal framework and temporal status

Pre-AIA § 103 governs. The application was filed 2009‑06‑28 with a 2009‑06‑28 priority date — before the March 16, 2013 AIA effective date — so the Graham/KSR analysis applies under pre‑AIA §§ 102/103. This matters for two reasons:

1. Every reference in the Prior Art section qualifies as § 102(b) art (printed publication or patent more than one year before the 2009 filing date). All nineteen NPL items date from 1977–2007; the three U.S. patents date from 2000, 2007, and 2007. There is therefore no need to litigate 102(a)/102(e) dates, no "swear-behind" or 1.131 avenue, and the references are freely combinable as prior art against every claim.
2. The standard is KSR's "predictable result" frame, not a rigid TSM test. KSR Int'l Co. v. Teleflex Inc., 550 U.S. 398 (2007). Because the field here is a mature, combination-heavy engineering discipline (DBMS internals, memory-resident indexing, data compression), a motivation to combine can be supplied by "market demand," "design incentives," "the interrelated teachings of multiple patents," or the "background knowledge, creativity, and common sense" of the skilled artisan. Id. at 417, 421.

Graham factors to be addressed: scope/content of the prior art; differences between prior art and claims; level of ordinary skill; secondary considerations. Graham v. John Deere Co., 383 U.S. 1 (1966).

Level of ordinary skill (PHOSITA). A person with a master's degree in computer science (or a bachelor's plus ~2–3 years of practical experience) in database systems, having working familiarity with (a) column-oriented / main-memory storage, (b) dictionary and order-preserving compression, and (c) cache-conscious index structures. This is consistent with the inventors' profile and with the SIGMOD/VLDB literature of record (the inventors' own 2009 SIGMOD paper is among the NPL citations).

Procedural posture caveat. The examiner cited these references yet allowed all 20 claims. That means the record does not contain a clean, articulated combination that defeated the claims. An obviousness attack here is therefore a hypothetical challenge built by re-assembling the cited art — not a restatement of a rejection already of record. I flag this because it affects the confidence level I assign to each combination below.

2. The prior art of record and what each reference supplies

I group the 39 references by the claim element they most directly serve. Where I do not have the full text in front of me, I rely on the disclosed titles and well-established subject matter of each item and label the inference accordingly.

Bottom line on the art: every limitation of the independent claims appears somewhere in the record, and the two most distinctive concepts — "order-preserving" (Antoshenkov) and "shared leaves" (Nascimento) — are the subjects of dedicated references.

3. The core attack: Combination A (independent claims 1, 8, and 15)

3.1 Why a PHOSITA would combine them

Motivation is abundant and is essentially internal to the art:

• Memory pressure in main-memory column stores. C-Store and Abadi establish that dictionary encoding is used precisely to shrink column footprints; the patent's own "direct" vs. "indirect" discussion (Fig. 2) recites the two obvious ways to index such a dictionary and their known drawbacks (duplicate storage vs. pointer indirection / cache misses). A PHOSITA seeking to reduce dictionary memory while retaining both access directions would look for a third option — and Nascimento already supplies one (share the leaves).
• Predicate rewrite requires order preservation. Chen et al. and Abadi teach rewriting predicates to run on encoded data. That rewrite only works if the code order matches the string order, which is exactly Antoshenkov's contribution. A PHOSITA combining "execute on compressed data" (Chen/Abadi) with order-preserving encoding (Antoshenkov) is doing routine engineering, not inventing.
• Mixed read/write workloads require update-in-place dictionaries. US 6,121,901 and US 7,263,238 teach that dictionaries must absorb new entries over successive loads. The claim's "lookup, and on miss insert + generate code" is the natural union of "lookup against dictionary" (C-Store/Abadi) and "update dictionary as new data arrives" (Unisys/Juniper).
• Same field, same problem, predictable result. All references target DBMS/dictionary compression or memory-resident indexing; none is from an unrelated art. Under KSR, the combination of known elements to achieve the known benefit (smaller dictionary, dual-direction access, order-preserving rewrite) is obvious.

3.2 Claim 1 / claim 8 element-by-element

Conclusion (claims 1 & 8): A prima facie case of obviousness exists over Antoshenkov in view of Nascimento, C-Store, and US 6,121,901 (optionally adding US 7,263,238 and Abadi). The differences, if any, are (i) applying a general shared-leaves index to a string dictionary in a column store rather than to a bitemporal tree, and (ii) folding dictionary-update into a bulk encode. Both are predictable applications of known techniques to a known problem. Under KSR these are "design incentives" and "market demand," not patentable innovation.

3.3 Claim 15 system

Claim 15 recites (a) a column-oriented DBMS, (b) a dictionary-based storage unit mapping variable-length strings to integer codes, (c) shared-leaves data structures holding the dictionary data in sorted order in their leaves, and (d) a processor encoding/decoding using those shared-leaves structures.

• (a) → Stonebraker (C-Store).
• (b) → C-Store / Abadi (dictionary of distinct values ↔ integer codes).
• (c) → Nascimento (shared leaves, sorted leaves) + Antoshenkov (order-preserving ⇒ sorting order coincides for values and codes — the very property the specification relies on to say both directions can search the same leaf).
• (d) → C-Store/Abadi (encode/decode during column processing) + US 7,164,370 (dictionary decode).

Claim 15 is the weakest independent claim, because it is essentially an apparatus recitation of "column store + dictionary + shared sorted leaves + processor." It contains no requirement of the bulk-update workflow and no requirement of the specific trie indexes, so it is exposed to an even simpler combination (C-Store + Abadi + Nascimento).

4. Dependent-claim analysis

4.1 Predicate rewriting — claims 3 / 10

Art: Chen, Gehrke & Korn (query optimization in compressed DBs); Abadi (compression/execution integration); Antoshenkov (order preservation).

Chen et al. teach rewriting string constants/range predicates against compressed-coded columns; Antoshenkov guarantees the code range corresponds to the string range; the prefix→(mincode, maxcode) mapping is a routine extension of range rewriting once order is preserved (a prefix defines a contiguous string interval ⇒ a contiguous code interval). Obvious. This is perhaps the single most straightforward dependent-claim rejection in the patent.

4.2 Sequential search without decompression — claims 4 / 11

Art: Abadi et al. ("integrating compression and execution" — querying compressed data directly); Antoshenkov (order-preserving compression designed to permit operation without full decompression); Witten et al. (compressed index searching).

The claim's limitation — search the compressed leaf without decompressing it — is the explicit design goal of order-preserving compression (Antoshenkov) and of Abadi's compression/execution integration. The patent's own Algorithm 1 shows the leaf stores some strings uncompressed with anchors, which is a classic "partial decompression / sampled anchors" technique. Obvious over Abadi + Antoshenkov.

4.3 Encode index = CS array trie or CS prefix trie — claims 5 / 12 / 18

Art: Askitis & Sinha (HAT-trie); Askitis & Zobel (cache-conscious collision resolution in string hash tables); Rao & Ross (cache-conscious indexing); Bohannon et al. (fixed-size partial keys); Bayer & Unterauer (prefix B-trees).

The CS array trie is a trie node implemented with an array (HAT-trie / Askitis lineage). The CS prefix tree is a prefix B-tree (Bayer & Unterauer) made cache-conscious (Rao & Ross). Selecting one of two known cache-conscious string indexes as the routing structure over a shared-leaf dictionary is a routine design choice; a PHOSITA would be motivated by the well-documented cache-miss costs of pointer-chasing structures (Rao & Ross; Zhou & Ross). Obvious.

4.4 CS array trie specifics — claims 6 / 13

Art: HAT-trie (array storage of node characters); Zhou & Ross (buffering accesses to memory-resident indexes); Askitis & Zobel.

• "storing strings in an array / populating the array only once per bulk" → HAT-trie + the well-known bulk-load-once optimization.
• "propagating in preorder via variable buffers at each trie node to increase cache locality" → Zhou & Ross's buffering is directly on point.
• "generating codes in parallel" → parallel bulk loading / sort of independent leaf partitions, a conventional parallelization once leaves are independent.

Obvious over Askitis & Sinha in view of Zhou & Ross. (Note: parallelism without locking, as the specification emphasizes, is a performance refinement that would be an expected result of partitioning work by non-overlapping leaves — KSR "predictable result.")

4.5 CS prefix trie construction — claims 7 / 14 / 20

Art: Bayer & Unterauer (prefix B-trees, shortest distinguishing prefixes); Bentley & Sedgewick / Sinha et al. (multikey quicksort string partitioning); Witten et al. (bottom-up index construction).

• "first/second shortest prefix distinguishing adjacent leaves" → Bayer & Unterauer's prefix-B-tree separator keys.
• "adding a level on top when a level has >1 node; root holds shortest prefixes" → standard B-tree level-building, bottom-up.
• "nodes stored contiguously, offsets rather than pointers" → Rao & Ross / Bohannon cache-conscious node layout (already relied on for claim 5).
• "partition strings into buckets using multi-key quicksort, then build leaves bottom-up" → Bentley & Sedgewick + Sinha et al.

Obvious over Bayer & Unterauer in view of Rao & Ross and Bentley & Sedgewick.

4.6 Decode index + update both indexes — claims 2 / 9 / 16 / 17

Art: US 7,164,370 (dictionary decode); C-Store/Abadi (dual encode/decode); Nascimento (shared leaves avoid duplicating the two directions).

Claims 2/9 (propagate codes via decode index; update both indexes) and 16/17 (separate encode/decode indexes; encode index supports propagation, lookup, and new-code generation) are the direct/indirect/shared-leaves design space the patent itself describes in Fig. 2. A PHOSITA choosing to keep logically separate encode and decode indexes (even while sharing leaves) is making a conventional architectural selection among a small, fully-enumerated set of alternatives. Obvious.

4.7 Remaining system claims — 19 / 20

Array storage (19) → HAT-trie/Askitis. Prefix-trie node with shortest prefixes for child propagation (20) → Bayer & Unterauer. Obvious.

5. Motivation-to-combine synthesis

For the response to withstand a KSR challenge, the challenger must articulate why the artisan would combine. Here the motivations are strong and, importantly, largely supplied by the references themselves:

1. Common problem, common field. Every reference addresses reducing memory and/or speeding lookups in databases or indexes using compression/coding. There is no cross-art leap.
2. Explicit design pressure toward shared leaves. The patent's own background recites the two known indexing options and their drawbacks. Nascimento's shared-leaves approach directly answers the stated problem of redundant storage; the motivation is thus both documented and predictable.
3. Order preservation is the enabling condition. Chen et al. and Abadi require rewriting predicates onto coded data; Antoshenkov makes that possible. One reference supplies the goal, another the mechanism.
4. Update-in-place is a known requirement. Unisys and Juniper teach live dictionary maintenance; combining with C-Store/Abadi dictionary lookup yields the claimed "insert on miss" behavior.
5. Cache-consciousness is THE theme of the era. Rao & Ross, Bohannon, Askitis & Zobel, Askitis & Sinha, Zhou & Ross, and Sinha et al. all push the same design imperative. Selecting cache-aware node layouts is not innovation but industry-standard practice by 2009.
6. Predictable results. Memory reduction (shared leaves) and speed (cache-conscious index) are exactly the expected consequences of the combination; KSR forecloses patentability where the combination merely yields anticipated benefits.

6. Anticipated rebuttals and how they fare

7. Conclusion

Prima facie obviousness (§ 103):

• Claims 1, 8, 15 and their largely overlapping dependents are, on the disclosed record, reasonably likely to be held obvious over:

  • Antoshenkov, "Order Preserving String Compression" (ICDE 1996) — order-preserving string→code,
  • in view of Nascimento et al., "Trees with Shared Leaves (SLT)" (1995) — shared leaves,
  • in view of Stonebraker et al. (C-Store, VLDB 2005) and Abadi et al. (SIGMOD 2006) — dictionary-encoded column store with execution on compressed data,
  • further in view of US 6,121,901 (Unisys) and US 7,263,238 (Juniper) — incremental dictionary update on new entries,
  • and US 7,164,370 (Analog Devices) — dictionary decode.

• Claims 3/10 (predicate rewrite) are the strongest obviousness candidates, over Chen et al. (SIGMOD 2001) + Antoshenkov + Abadi.

• Claims 4/11 (search without decompression) over Abadi + Antoshenkov.

• Claims 5/6/12/13/18/19 (CS array trie) over Askitis & Sinha (HAT-trie) + Zhou & Ross (buffering) + Rao & Ross (cache-conscious indexing).

• Claims 7/14/20 (CS prefix trie) over Bayer & Unterauer (Prefix B-Trees) + Rao & Ross + Bentley & Sedgewick.

• Claims 2/9/16/17 (dual encode/decode indexes) over the patent's own enumerated direct/indirect/shared-leaves alternatives + US 7,164,370.

Confidence: Moderate for the independent claims and the CS-index dependents (the mappings are strong and the motivation is well-supported by the art). Lower for claim 15 specifically because the one genuinely contestable bridge is importing a bitemporal shared-leaves tree (Nascimento) into a column-store dictionary — that is the pivot on which the patentee would most credibly resist, and where a challenger should invest its motivation argument. I have not independently retrieved the full texts of most NPL items in this session, so the element mappings above rest on the disclosed titles/known subject matter of each reference; a final invalidity contention would need the full-text pinpoint cites (page/§ passages) for Antoshenkov, Nascimento, Chen, Zhou & Ross, and the HAT-trie paper.