Data compression, store, and search system

Various embodiments for a data compression store and search system are described herein. An embodiment operates by receiving a query to search a plurality of documents. It is determined that the plurality of documents are stored in a compressed format comprising a plurality of shells and a plurality of snippets. A first snippet that includes the query identifier is identified, and a first shell including a reference to the first snippet is identified. A readable version of a first document of the plurality of documents is assembled from the first shell. The assembled readable version of the first document is provided responsive to the query.

BACKGROUND

Data storage and maintenance are expenses for many organizations, both computationally and financially. As the amount of data being stored grows, these expenses also increase. The more data that is being stored, more data that has to be maintained and managed, and consequently the more storage capacity, computing resources, and personnel that will be required to maintain and manage the stored data. One way organizations can try and reduce the amount of data storage required is by using compression. However, compression has its own drawbacks, because compression often reduces the usability of the data by making searching and accessing the data slow and cumbersome, which can detrimentally impact efficiency and slow down the business of the organization.

DETAILED DESCRIPTION

Data storage and maintenance are expenses for many organizations, both computationally and financially. As the amount of data being stored grows, these expenses also increase. The more data that is being stored, more data that has to be maintained and managed, and consequently the more storage capacity, computing resources, and personnel that will be required to maintain and manage the stored data. One way organizations can try and reduce the amount of data storage required is by using compression. However, compression has its own drawbacks, because compression often reduces the usability of the data by making searching and accessing the data slow and cumbersome, which can detrimentally impact efficiency and slow down the business of the organization.

FIG.1is a block diagram100illustrating a data compression store and search system (DCS)102, according to some example embodiments. In some embodiments, DCS102may provide efficient data compression techniques and formats, which both reduces the amount of storage capacity required to store the data (in an uncompressed format), while also providing for the usability of compressed data, by allowing for more efficient searching on the compressed data, and subsequent, efficient data access and decompression.

In some embodiments, DCS102may have or may have access to a document store104. Document store104may include any set of memory, databases, servers, or other storage devices that are storing data, such as a set of documents106. For simplicity, a small set of documents106is illustrated, however DCS102may process any number of documents106, including millions or billions of documents106with the techniques and technologies described herein.

In some embodiments, document106may include a JSON (Javascript Objection Notation) formatted document. JSON is an example of a data format that allows for data exchange and communications between different computing devices, such as mobile devices operating web applications and servers. For simplicity, the examples described herein will focus on JSON documents, but one skilled in the art will appreciate other data storage formats, including but not limited to JSON, may be used for the documents106. In some embodiments, the documents106may be sorted or arranged into different subsets, and each subset may have its own unique storage format.

In some embodiments, document106may include an object110and each object110may include one or more key-value pairs (illustrated as key112and key value114). Object110may be a set of one or more key-value pairs. In some embodiments, a first object110may include additional or nested objects110inside of the first object110. In some embodiments, document106may include multiple different objects110, each with one or more key-value pairs.

FIGS.2A-2Dillustrate examples of compression, storage, and other processing operations that may be performed by DCS102, according to some embodiments. InFIG.2A, the document206, may be an example of document106(ofFIG.1). In document206, the objects110may be customer, address, and order. In some embodiments, the object110may be similar to a key without a corresponding value.

The key-value pairs (comprising keys112and their corresponding key values114) may be [street-“Main Street100” ], [city-“Hamburg” ], and [productID-471100]. The illustrated document206may be a simple example of how customer information may be stored as a document206.

Generally speaking JSON documents are individually stored in conventional systems, which makes compression impossible or inapplicable. While this separate and individual storage of different documents may allow for quick access to the content of the documents, the amount of storage required to store the JSON documents will often outweigh any gains that may be realized from storing full documents (e.g., without any compression or reuse), and as the number of documents increase, the cost of storage and maintenance of the documents continues to increase. Also, at a certain point, storing full documents can make searching more resource intensive as well. While it is possible to compress many documents using compression algorithms known from zip archives or similar, the consequence is that all of the compressed documents then have to be subsequently decompressed prior to searching for a specific document with a specific key-value pair.

Returning toFIG.1, DCS102may reduce the cost of storage and maintenance by identifying redundancies amongst documents106in document store104, generating one or more snippets108(which encapsulate those redundancies and are reusable across multiple different documents106), and storing snippets108and shells116(instead of full documents106) that still allow for efficient search and data access. DCS102reduces the cost of ownership, storage, maintenance, and even search of for data from documents106while simultaneously providing for efficient search and access to the data of the originally stored documents106, which can be deleted or removed from document store104after the generation of a corresponding shell116.

Snippet108may indicate a redundancy that DCS102has identified across two or more of the documents106(or multiple portions of a single document). The redundancy which may be captured in a snippet108may include repeated objects110, repeated data values, repeated keys112, repeated key values114, and/or repeated key-value pairs. The snippets108may be used across different documents106and enable the reuse of data, and enables redundancies to be deleted from storage thus saving storage space and maintenance costs.

Shell116may include a structure or arrangement of data and/or snippets108that can be used to assemble the original document106. In some embodiments, DCS102may store shells116in document store104in lieu of the full versions of various documents106which may have been previously stored (which may include redundancies). In some embodiments, document store104may still include one or more documents106when there are no identified redundancies (e.g., snippets108) in those documents106.

Returning toFIG.2Aexamples of snippet108are illustrated as snippets208A-C (referred to generally as snippet208). In the example illustrated, each snippet208may correspond to a different object110identified in document206, and may include the object(s)110, key(s)112and/or key value(s)114included in the corresponding object110.

For example, snippet208A includes the key-value pair of name-Marcus, but also includes a nested snippet, or reference to snippet 2 (snippet208B). Snippet208B includes the key-value pairs in the corresponding ‘address’ object110identified from document206.

Shell216is an example of shell116. Shell216is an example of what may be stored in document store104in lieu of document206, which may be deleted after the generation of shell216. Shell216includes references to two separate snippets (1 and 3, which correspond to snippets208A and208C respectively). As may be seen, from shell216, snippets208A-208C can be reassembled back into the original document206(which may have been removed or deleted from storage after the generation of shell216).

Returning toFIG.1, in some embodiments, if a document access, search request, or other query118is received for document106for which a corresponding shell116has already been generated and the document106removed from storage, a document assembler120may identify the corresponding shell116and may re-assemble the document106from shell116as assembled document122. Assembled document122may visually appear identical to and/or include identical information as the original document106.

For example, inFIG.2A, document assembler120may identify and begin assembling document206, from shell216. From shell216, it may be seen that the first part of the document206may include the data, text, and structure from snippet208A (‘snippet 1’), followed by snippet208C (‘snippet 3’).

Snippet208A includes a reference to snippet208B which document assembler120may import into the snippet208A (replacing the reference to “Snippet2”), followed by the text and data of snippet208C (‘snippet 3’). This snippet form of compression captures text and data, as well as the structure of document106, including both additional punctuation and spacing, and other elements of structure of document106, across one or more objects110. Data assembler120, from shell216, may generate an assemble document122which may be or appear identical to the originally stored document206.

FIG.2BtoFIG.2Dillustrate a step-by-step example of how a second document206B is being added by the assembler120to the snippets108, and the use super snippets126and shells116.FIG.2Bis similar toFIG.2A, except thatFIG.2Bincludes a second document206B. Snippet208B includes a modification, which now includes a parameter224, which may be an example of parameter124ofFIG.1. Parameter124may be a variable that is passed to a snippet108that is used as a key value114within the snippet108.

As may be seen document206A (which is the same as document206fromFIG.2A, just re-labeled) and document206B, may both include an address object110, which includes the key112street, and key-value pair of city-Hamburg. However, DCS102may detect that the values114for street may be different. To account for this difference, and maximize or increase the reusability of snippet208B which includes the street key112, DCS102may replace the actual key value114with a variable or parameter224“a”. By using parameter224, DCS102allows snippet208B to be reused with different values for parameter224“a” across different documents (206A,206B).

FIG.2Cis similar toFIG.2B, except thatFIG.2Cincludes increased compression with a new parameter224A and a new shell216B, as generated by DCS102. For example, as illustrated, DCS102has identified a new parameter224A to account for the varying values for the key112name, in the two documents206A,206B.

As can be seen in shells216A and216B, the calls to snippet 1 include values to be used in the various parameters224A and224B in snippets208A and208B.

FIG.2Dis similar toFIG.2C, except thatFIG.2Dincludes an increased compression via a new super snippet226, as generated by DCS102. DCS102may detect that both shells216A,216B (fromFIG.2C) have a similar structure or calls to similar snippets208A-C. For example, both shells216A,216B include a reference to snippet 1 followed by a reference to snippet 3. These redundancies in calling the same snippets in the same order may be accounted for by DCS102by generating a super snippet226(which may be an example of super snippet126fromFIG.1). It can be appreciated that as the number of documents106,206grows and the number of shells referring to particular snippets208and super snippets226grows, the savings in time, resources, and increase in efficiency grows as well.

A super snippet126may be a snippet that includes calls or references to other snippets108, without any direct references to another (non-snippet) object110, key112, key value114, or key-value pair. Super snippet226illustrates an example super snippet126. As may be illustrated, super snippet226includes calls to snippet 1 and snippet 3, each of which may take parameters124‘a’, the values of which are provided in the shells216A,216B. Meanwhile, snippets108have a list of super snippets126that refer them. As you can see inFIG.2D, with the introduction of super snippet226, snippets208A and208C got enriched or further compressed with a reference to “SuperSnippet1”.

As also illustrated, the use of a super snippet226further reduces how much data is stored for shells216A and216B (e.g., relative to the shells216A,216B illustrated inFIG.2C). From shells216A,216B, document assembler120may regenerate or assemble both documents206A and206B in their original forms using the snippets208A-C, and super snippet226which may be stored in a datastore128(as illustrated inFIG.1), replacing the parameters224A,224B with the provided values. Datastore128may include any storage device(s) where snippets108, parameters124, and/or super snippets126are stored, modified, and accessed.

FIG.3Ais similar toFIG.2D, except that an additional document has been added, the snippets have been modified, and to increase the speed of the search, the shells and snippets and super snippets are ordered or sorted. Documents306A-C are examples of original documents106and/or assembled documents122that may be later generated by document assembler120, shells316A-C are corresponding shells for the documents306A-C. Snippets308A-D are examples of snippet108and super snippet326is an example of super snippet126used to regenerate or assemble the original documents306A-C.

In the example illustrated, once the snippets308A-D, super snippet(s)326(if any), and shells316A-C have been generated by DCS102, from documents306A-C, DCS102may order the shells316A-C, snippets308A-D, and super snippets326to improve the speed of searches or query processing that may be performed by DCS102.

In the example illustrated, the shells316A-C may be ordered based on which snippets and super snippets are being referred to in the shells. In the example illustrated, the first shell316C may include a reference to a snippet without any references to a super snippet, so may appear first. If there are multiple shells without references to a super snippet, then those shells may be sorted numerically by the smallest snippet reference in those shells. For example, if a first shell includes a reference to snippet 2, and a second shell includes a reference to snippet 3 and snippet 1, the second shell may be arranged first because of the reference to snippet 1.

Snippets316B and316A may both include references to super snippet 1 (e.g.,326). But since both shells316A,316B include the same reference to super snippet 1, shells316A and316B may be ordered alphabetically by the first parameter (Frank v. Marcus), since there are no other snippets referenced in either shell.

DCS102may also order the snippets308A-D alphabetically by their first referenced identifier or key112. Since the super snippets326do not include identifiers or keys112, they may be ordered separately after the snippets by their reference number or name. DCS102may be able to search super snippets326separately from snippets308A-D. This alphabetic and numeric ordering of the shells316A-C, snippets308A-D, and super snippets326may make search and access (assembly) of documents306A-C faster.

FIG.3Billustrates the operations of a search functionality, responsive to a query318, according to some example embodiments. Query318is an example of query118, and may include both identifiers130and values132. Identifiers130and values132may include what is being searched for through the query118. In some embodiments, identifier130may correspond to an object110or key112, and value132may correspond to a key value114.

In the example query318, the first identifier130may be “customer”, referencing a “customer” object110. DCS102may search the datastore128for the first identifier130(“customer”) of the query318. DCS102may identify that both snippet308A and308B include the “customer” identifier130from query318. This search is made faster because, as described above with respect toFIG.3A, the snippets308A-D have been alphabetically ordered and hence logarithmic search may be applied.

The next identifier132may be the “address” object110, for which DCS102may perform a search of the snippets308A-D in datastore128. DCS102may identify that the “address” object110, as indicated in query318, is in snippet308C.

DCS102may then compare or cross-reference the results from the first search for the “customer” object as indicated by query318, and with the second search for the “address” object, to identify any overlaps between the searches (e.g., any snippets that include both the “customer” and “address” objects). As indicated by arrow305, snippet2(a) (308C that includes address) is referenced by snippet 1 (308A), and is not referenced by snippet308B, so snippet308B can be removed from the search results. Snippet308A would be the resulting snippet including both the “customer” and “address” objects of query318. In some embodiments, the shells may be searched for a reference to the outer “customer” snippet. In the given example, there is no such shell.

Arrow307indicates that snippet 1 (308A) is a child snippet of a super snippet326. DCS102may determine then that the result will include super snippet326. DCS102may then search the shells316A-C stored in document store104, which have been arranged in numerical order by first snippets and then super snippets as described above with respect toFIG.3A. This ordering improves the speed of the search, especially as the number of shells316and/or documents grows.

As indicated by arrows309A and309B, DCS102may identify that both shells316B and316A meet the requirements of query318thus far, including super snippet326. DCS102may then continue query processing in which the key-value pair of street-“Braymore Road200” is being searched for amongst the shells316B and316A. DCS102may then determine that shell316B satisfies the query318. It may be seen that as a result of the sorting, searches may be executed with logarithmic complexity.

In some embodiments, DCS102may reassemble the original document306B from shell316, as an assembled doc322B as indicated by arrow311. For example, document assembler120may assemble document322B from the corresponding snippets308A-D and super snippets and values referenced by shell316B. DCS102may then display or otherwise provide assembled doc322B to another system for access or processing.

FIG.4is a flowchart400illustrating a process for a data compression store and search system (DCS), according to some embodiments. Method400can be performed by processing logic that can comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (e.g., instructions executing on a processing device), or a combination thereof. It is to be appreciated that not all steps may be needed to perform the disclosure provided herein. Further, some of the steps may be performed simultaneously, or in a different order than shown inFIG.4, as will be understood by a person of ordinary skill in the art. Method400shall be described with reference to the figures.

In410, a query to search a plurality of documents is received. For example, DCS102may receive query118to search the content of documents106. The query118may include a query identifier130and a query value132corresponding to the query identifier132. Another example query318is illustrated onFIG.3B.

In420, it is determined that the plurality of documents are stored in a compressed format comprising a plurality of shells and a plurality of snippets. For example, DCS102may determine that document store104includes shells116, in lieu of documents106. DCS102may also determine that data store128includes a plurality of snippets108. The snippets108may correspond to one or more detected or identified objects110and/or keys112from the previously stored documents106.

In some embodiments, each snippet108may correspond to an object110that has been used across two or more of the originally received or stored documents106. In other embodiments, another threshold may be used. For example, if there were one million original documents106, the threshold for reuse (for which DCS102may generate a corresponding snippet108) may be a higher number, such as ten. In some embodiments, DCS102may perform an initial scan of the various available documents106to identify any and all redundancies that meet any corresponding thresholds. Each of the shells116may include references to one or more of the snippets108and/or the super snippet(s)126.

In430, a first snippet, of the plurality of snippets, that includes the query identifier is identified. For example, inFIG.3B, snippets308A and308B both include the query identifier “customer” and snippet308C includes the query identifier “address. DCS102may further determine that super snippet326includes the various query identifiers from query318.

In440, a first shell including a reference to the first snippet is identified. For example, DCS102may identify both shells316A and316B includes the identified super snippet326, DCS102may then identify that shell316B includes the query value from query318.

In450, a readable version of a first document of the plurality of documents is assembled from the first shell. For example, DCS102may assemble document322B from shell316B and the references super snippet326and various other snippets308A-C, plugging into the identified values for any parameters124.

In460, the assembled readable version of the first document is provided responsive to the query. For example, DCS102may provide assembled document122back to the person, system, or device from which query118was received. In some embodiments, assembled document122may be provided to a system for display, or use in other processing tasks.

Various embodiments and/or components therein can be implemented, for example, using one or more computer systems, such as computer system500shown inFIG.5. Computer system500can be any computer or computing device capable of performing the functions described herein. For example, one or more computer systems500can be used to implement any embodiments, and/or any combination or sub-combination thereof.

Computer system500includes one or more processors (also called central processing units, or CPUs), such as a processor504. Processor504is connected to a communication infrastructure or bus506. Computer system500may represent or comprise one or more systems on chip (SOC).

One or more processors504can each be a graphics processing unit (GPU). In some embodiments, a GPU is a processor that is a specialized electronic circuit designed to process mathematically intensive applications. The GPU can have a parallel structure that is efficient for parallel processing of large blocks of data, such as mathematically intensive data common to computer graphics applications, images, videos, etc.

Computer system500also includes a main or primary memory508, such as random access memory (RAM). Main memory508can include one or more levels of cache. Main memory508has stored therein control logic (i.e., computer software) and/or data.

Computer system500can also include one or more secondary storage devices or memory510. Secondary memory510can include, for example, a hard disk drive512and/or a removable storage device or drive514. Removable storage drive514can be a floppy disk drive, a magnetic tape drive, a compact disk drive, an optical storage device, tape backup device, and/or any other storage device/drive.

Removable storage drive514can interact with a removable storage unit518. Removable storage unit518includes a computer usable or readable storage device having stored thereon computer software (control logic) and/or data. Removable storage unit518can be a floppy disk, magnetic tape, compact disk, DVD, optical storage disk, memory card, and/any other computer data storage device. Removable storage drive514reads from and/or writes to removable storage unit518in a well-known manner.

According to an exemplary embodiment, secondary memory510can include other means, instrumentalities or other approaches for allowing computer programs and/or other instructions and/or data to be accessed by computer system500. Such means, instrumentalities or other approaches can include, for example, a removable storage unit522and an interface520. Examples of the removable storage unit522and the interface520can include a program cartridge and cartridge interface (such as that found in video game devices), a removable memory chip (such as an EPROM or PROM) and associated socket, a memory stick and USB port, a memory card and associated memory card slot, and/or any other removable storage unit and associated interface.

Computer system500can further include a communication or network interface524. Communication interface524enables computer system500to communicate and interact with any combination of remote devices, remote networks, remote entities, etc. (individually and collectively referenced by reference number528). For example, communication interface524can allow computer system500to communicate with remote devices528over communications path526, which can be wired and/or wireless, and which can include any combination of LANs, WANs, the Internet, etc. Control logic and/or data can be transmitted to and from computer system500via communication path526.

In some embodiments, a tangible apparatus or article of manufacture comprising a tangible computer useable or readable medium having control logic (software) stored thereon is also referred to herein as a computer program product or program storage device. This includes, but is not limited to, computer system500, main memory508, secondary memory510, and removable storage units518and522, as well as tangible articles of manufacture embodying any combination of the foregoing. Such control logic, when executed by one or more data processing devices (such as computer system500), causes such data processing devices to operate as described herein.

It is to be appreciated that the Detailed Description section, and not the Summary and Abstract sections, is intended to be used to interpret the claims. The Summary and Abstract sections can set forth one or more but not all exemplary embodiments as contemplated by the inventors, and thus, are not intended to limit this disclosure or the appended claims in any way.