Embodiments sort a plurality of documents in an increasing order of frequency updates, create multiple recursive partitions of the plurality of sorted documents, compute a cost of the multiple recursive partitions, choose a partition with a smallest cost from computed costs of the multiple recursive partitions, and merge the plurality of documents based on the partition with the smallest cost.

BACKGROUND

Aspects of the present invention relate generally to merge-based computation and, more particularly, to systems and methods of merge-based computation to create a final index for documents in vector databases.

In vector databases, an update or delete operation of a document is achieved by keeping a mapping of a name of a document chunk to a respective identification. Further, the mapping of the name of the document chunk to the respective identification is maintained externally from the vector databases.

SUMMARY

In a first aspect of the invention, there is a computer-implemented method including: sorting, by a computing device, a plurality of documents in an increasing order of frequency updates; creating, by the computing device, multiple recursive partitions of the plurality of sorted documents; computing, by the computing device, a cost of the multiple recursive partitions; choosing, by the computing device, a partition with a smallest cost from computed costs of the multiple recursive partitions; and merging, by the computing device, the plurality of documents based on the partition with the smallest cost.

In another aspect of the invention, there is a computer program product including one or more computer readable storage media having program instructions collectively stored on the one or more computer readable storage media. The program instructions are executable to: receive a plurality of documents for indexing into a vector database system; sort the plurality of documents in an increasing order of frequency updates; create multiple recursive partitions of the plurality of sorted documents; compute a cost of the multiple recursive partitions; choose a partition with a smallest cost from computed costs of the multiple recursive partitions; merge the plurality of documents based on the partition with the smallest cost; and create a final vector database which comprises the merged plurality of documents.

In another aspect of the invention, there is a system including a processor, a computer readable memory, one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media. The program instructions are executable to: receive a plurality of documents for indexing into a vector database system; sort the plurality of documents in an increasing order of frequency updates; create multiple recursive partitions of the plurality of sorted documents based on a Monte Carlo algorithm; compute a cost of the multiple recursive partitions; choose a partition with a smallest cost from computed costs of the multiple recursive partitions; merge the plurality of documents based on the partition with the smallest cost; and create a final vector database which comprises the merged plurality of documents.

DETAILED DESCRIPTION

Aspects of the present invention relate generally to merge-based computation and, more particularly, to systems and methods of merge-based computation to create a final index for documents in vector databases. Aspects of the present invention minimize a rate for merging documents in a vector database in response to an update or delete operation being performed for at least one document in the vector database. In particular, embodiments of the present invention simplify the code used in updating the vector database in response to a document being changed within the vector database. Aspects of the present invention also improve parallelism during re-computation of the vector database in comparison to the complex process of using a mapping approach using identified chunks within documents of the vector database. Embodiments of the present invention also improve generative artificial intelligence (AI) searching of the vector databases by minimizing the rate for merging documents within the vector database. In particular, aspects of the present invention improve a retrieval augmented generation (RAG) method that is used in providing an accurate response to AI queries.

According to more specific aspects of the invention, the computer-implemented method includes: sorting documents in an increasing order of frequency updates for placement in a vector database; generating multiple recursive partitions of the sorted documents; identify a lowest cost partition from the generated multiple recursive partitions; and merge the documents based on the identified lowest cost partition.

Accordingly, implementations of the present invention provide an improvement in the technical field of merging documents within a vector database. In further embodiments, embodiments of the present invention minimize a rate for performing merging of documents within the vector database. Further, aspects of the present invention simplify the code used to perform merging of the documents within the vector database. Embodiments of the present invention also improve parallelism during merging of the documents within the vector database. In contrast, known systems require an external mapping between a name of a document chunk and a respective identification. In particular, known systems require additional code to implement introspection of the vector database and regeneration of the mapping in response to any loss of the external mapping. Further, known systems are not able to address external databases or indexes being incorporated in the vector database for querying. Accordingly, known systems and methods require additional steps of splitting documents into multiple chunks and then either mapping the chunks to a respective identification or creating chunkified embeddings from chunkified documents which then have to be merged into a final vector database. In contrast, embodiments of the present invention bypass splitting of documents into multiple chunks by minimizing the rate for performing merging of the documents within the vector database.

Implementations of the present invention are thus necessarily rooted in computer technology. For example, the steps of sorting documents by increasing order of frequency updates, creating multiple recursive partitions of the sorted documents using at least one of a Monte Carlo algorithm or simulated annealing, computing a cost of each partition of the multiple recursive partitions, identifying a lowest cost partition of the multiple recursive partitions, and merging the documents into a final vector database based on the identified lowest cost partition are computer-based and cannot be performed in the human mind. For example, creating multiple recursive partitions using at least one of a Monte Carlo algorithm or simulated annealing is, by definition, performed by a computer and cannot practically be performed in the human mind (or with pen and paper) due to the complexity and massive amounts of calculations involved. Given the scale and complexity of creating multiple recursive partitions using at least one of a Monte Carlo algorithm or simulated annealing, it is simply not possible for the human mind, or for a person using pen and paper, to perform the number of calculations involved in creating multiple recursive partitions in real-time, amongst other features described herein that are also root in computer technology.

It should be understood that, to the extent implementations of the invention collect, store, or employ personal information provided by, or obtained from, individuals (for example, users associated with service tickets), such information shall be used in accordance with all applicable laws concerning protection of personal information. Additionally, the collection, storage, and use of such information may be subject to consent of the individual to such activity, for example, through “opt-in” or “opt-out” processes as may be appropriate for the situation and type of information. Storage and use of personal information may be in an appropriately secure manner reflective of the type of information, for example, through various encryption and anonymization techniques for particularly sensitive information.

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

Referring now to FIG. 1, a schematic of an example of a cloud computing node is shown. Cloud computing node 10 is only one example of a suitable cloud computing node and is not intended to suggest any limitation as to the scope of use or functionality of embodiments of the invention described herein. Regardless, cloud computing node 10 is capable of being implemented and/or performing any of the functionality set forth hereinabove.

As shown in FIG. 1, computer system/server 12 in cloud computing node 10 is shown in the form of a general-purpose computing device. The components of computer system/server 12 may include, but are not limited to, one or more processors or processing units 16, a system memory 28, and a bus 18 that couples various system components including system memory 28 to processor 16.

Computer system/server 12 typically includes a variety of computer system readable media. Such media may be any available media that is accessible by computer system/server 12, and it includes both volatile and non-volatile media, removable and non-removable media.

Program/utility 40, having a set (at least one) of program modules 42, may be stored in memory 28 by way of example, and not limitation, as well as an operating system, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. Program modules 42 generally carry out the functions and/or methodologies of embodiments of the invention as described herein.

Computer system/server 12 may also communicate with one or more external devices 14 such as a keyboard, a pointing device, a display 24, etc.; one or more devices that enable a user to interact with computer system/server 12; and/or any devices (e.g., network card, modem, etc.) that enable computer system/server 12 to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interfaces 22. Still yet, computer system/server 12 can communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter 20. As depicted, network adapter 20 communicates with the other components of computer system/server 12 via bus 18. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with computer system/server 12. Examples, include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.

Referring now to FIG. 2, illustrative cloud computing environment 50 is depicted. As shown, cloud computing environment 50 comprises one or more cloud computing nodes 10 with which local computing devices used by cloud consumers, such as, for example, personal digital assistant (PDA) or cellular telephone 54A, desktop computer 54B, laptop computer 54C, and/or automobile computer system 54N may communicate. Nodes 10 may communicate with one another. They may be grouped (not shown) physically or virtually, in one or more networks, such as Private, Community, Public, or Hybrid clouds as described hereinabove, or a combination thereof. This allows cloud computing environment 50 to offer infrastructure, platforms and/or software as services for which a cloud consumer does not need to maintain resources on a local computing device. It is understood that the types of computing devices 54A-N shown in FIG. 2 are intended to be illustrative only and that computing nodes 10 and cloud computing environment 50 can communicate with any type of computerized device over any type of network and/or network addressable connection (e.g., using a web browser).

Referring now to FIG. 3, a set of functional abstraction layers provided by cloud computing environment 50 (FIG. 2) is shown. It should be understood in advance that the components, layers, and functions shown in FIG. 3 are intended to be illustrative only and embodiments of the invention are not limited thereto. As depicted, the following layers and corresponding functions are provided:

Hardware and software layer 60 includes hardware and software components. Examples of hardware components include: mainframes 61; RISC (Reduced Instruction Set Computer) architecture based servers 62; servers 63; blade servers 64; storage devices 65; and networks and networking components 66. In some embodiments, software components include network application server software 67 and database software 68.

Virtualization layer 70 provides an abstraction layer from which the following examples of virtual entities may be provided: virtual servers 71; virtual storage 72; virtual networks 73, including virtual private networks; virtual applications and operating systems 74; and virtual clients 75.

In one example, management layer 80 may provide the functions described below.

Resource provisioning 81 provides dynamic procurement of computing resources and other resources that are utilized to perform tasks within the cloud computing environment. Metering and Pricing 82 provide cost tracking as resources are utilized within the cloud computing environment, and billing or invoicing for consumption of these resources. In one example, these resources may comprise application software licenses. Security provides identity verification for cloud consumers and tasks, as well as protection for data and other resources. User portal 83 provides access to the cloud computing environment for consumers and system administrators. Service level management 84 provides cloud computing resource allocation and management such that required service levels are met. Service Level Agreement (SLA) planning and fulfillment 85 provide pre-arrangement for, and procurement of, cloud computing resources for which a future requirement is anticipated in accordance with an SLA.

Workloads layer 90 provides examples of functionality for which the cloud computing environment may be utilized. Examples of workloads and functions which may be provided from this layer include: mapping and navigation 91; software development and lifecycle management 92; virtual classroom education delivery 93; data analytics processing 94; transaction processing 95; and merge-based computation 96.

Implementations of the invention may include a computer system/server 12 of FIG. 1 in which one or more of the program modules 42 are configured to perform (or cause the computer system/server 12 to perform) one of more functions of the merge-based computation 96 of FIG. 3. For example, the one or more of the program modules 42 of the merge-based computation 96 may be configured to: sort documents by increasing order of frequency updates, create multiple recursive partitions of the sorted documents using at least one of a Monte Carlo algorithm or simulated annealing, compute a cost of each partition of the multiple recursive partitions, identify a lowest cost partition of the multiple recursive partitions, and merge the documents into a final vector database based on the identified lowest cost partition. In particular, the cost of each partition corresponds with a number of operations that need to be performed to merge documents.

FIG. 4 shows a block diagram of a merge computation system in accordance with aspects of the invention. In embodiments, the merge computation system 100 comprises a merge computation environment 105 which includes a sorting module 110, a recursive partitioning module 115, a cost computation module 120, and a merging module 125, each of which may comprise one or more program modules such as program modules 42 described with respect to FIG. 1 and the merge-based computation 96.

The merge computation system 100 may include additional or fewer modules than those shown in FIG. 4. In embodiments, separate modules may be integrated into a single module. Additionally, or alternatively, a single module may be implemented as multiple modules. Moreover, the quantity of devices and/or networks in the environment is not limited to what is shown in FIG. 4. In practice, the environment may include additional devices and/or networks; fewer devices and/or networks; different devices and/or networks; or differently arranged devices and/or networks than illustrated in FIG. 4.

In embodiments of FIG. 4, the sorting module 110 receives a plurality of documents for indexing into a vector database system and sorts the plurality of documents in an increasing order of past frequency updates. For example, the plurality of documents includes document_1, document_2, . . . , document_k, in which k is an integer which represents the last document of the plurality of documents. Therefore, the sorting module 110 sorts the plurality of documents such that the sorted documents S=(document_with_lowest_frequency f1, document_with_second_lowest_frequency f2, . . . , document_with_highest_frequency fk), in which fk corresponds to a highest frequency of a document in the plurality of documents). The sorting module 110 then outputs the sorted documents S to the recursive partitioning module 115.

In FIG. 4, the recursive partitioning module 115 receives the sorted documents S and creates multiple recursive partitions P of the sorted documents S. In embodiments, the recursive partitioning module 115 creates multiple recursive partitions using at least one of a Monte Carlo algorithm or simulated annealing. For example, the recursive portioning module 115 creates a first partition p_1 in the sorted documents S when k=10:

In the first partition p_1 above, the recursive partitioning module 115 creates a database for a sequence of documents being surrounded by square brackets (e.g., [f1,f2,f3]) and maintains the database for merging with the rest of the documents outside of this grouping in the first partition p_1 (e.g., f4, f5, f6, f7, f8, f9, and f10). The recursive partitioning module 115 may repeat the process for other sequences of documents being surrounded by square brackets in the first partition p_1.

In another example of FIG. 4, the recursive partitioning module 115 creates a second partition p_2 in the sorted documents S when k=10:

In the second partition above, the recursive partitioning module 115 creates another database for the sequence of documents being surrounded by square brackets (e.g., [f1,f2]) and maintains the database for merging with the rest of the documents outside of this grouping in the second partition p_2 (e.g., f3, f4, f5, f6, f7, f8, f9, and f10). The recursive partitioning module 115 then repeats the process for other sequences of documents being surrounded by square brackets in the first partition p_2.

The recursive partitioning module 115 may repeat the process above with respect to partitions p_1, p_2 for remaining partitions of the multiple recursive partitions P. Accordingly, the recursive partitioning module 115 creates the multiple recursive partitions P as shown below when k=10:

Still referring to FIG. 4, the recursive partitioning module 115 sends the multiple recursive partitions P to a cost computation module 120. The cost computation module 120 receives the multiple recursive partitions P and computes a cost of each partition in the multiple recursive partitions P. For example, the cost of the first partition is shown below:

As shown above, the total cost of the first partition c(p_1) is 16 operations. In particular, there are five operations for f1, f2, and f3, 4 operations for f4, f5, four operations for f6, f7, and f8, and three operations for f9, f10. Details of both the first partition p_1 and the total cost of the first partition c(p_1) will be described in detail in FIG. 5.

In another example of FIG. 4, the cost of the second partition is shown below:

As shown above, the total cost of the second partition c(p_2) is 16 operations. In particular, there are four operations for f1, f2, five operations for f3, f4, and f5, four operations for f6, f7, and f8, and three operations for f9, f10. Details of both the second partition p_2 and the total cost of the second partition c(p_2) will be described in detail in FIG. 6.

The cost computation module 120 then repeats the process above with respect to the cost of the partitions c(p_1), c(p_2) for remaining partitions of the multiple recursive partitions P. The cost computation module 120 chooses a partition p_small with a smallest cost c(p)_small and then sends the partition p_small with the smallest cost c(p)_small to the merging module 125.

In FIG. 4, the merging module 125 implements the merging of the plurality of documents using the partition p_small with the smallest cost c(p)_small. The merging module 125 creates a final vector database with a result of the merging of the plurality of documents and outputs the final vector database to the vector database system. In comparison to known systems, aspects of the present invention reduce a total cost by merging the plurality of documents in a more efficient manner using a smallest cost partition. Further, embodiments of the present invention reduce an overhead of re-calculating costs in comparison to known systems.

FIG. 5 shows an example of the first partition of the merge computation system in accordance with aspects of the present invention. In FIG. 5, a diagram 200 is shown which corresponds with the first partition p_1 shown below:

In the diagram 200 for FIG. 5, there are two operations for [f1,f2,f3], one additional operation for combining [f1,f2,f3] with [f4,f5], and then two additional operations for [[f1,f2,f3], [f4,f5]] combined with [f6,f7,f8] and [f9, f10]. Thus, the total operations for [f1,f2,f3] is five operations. Further, in the diagram 200, there is one operation for [f4,f5], one additional operation for combining [f4,f5] with [f1,f2,f3], and then two additional operations for [[f4,f5], [f1,f2,f3]] combined with [f6,f7,f8] and [f9, f10]. Thus, the total operations for [f4,f5] is 4 operations.

Still referring to FIG. 5, there are two operations for [f6,f7,f8], one additional operation for [f6,f7,f8] combined with [f9,f10], and then one additional operation for [f6,f7,f8] combined with [f9,f10] combined with [[f4,f5], [f1,f2,f3]]. Thus, the total operations for [f6,f7,f8] is four operations. Further, in the diagram 200, there is one operation for [f9,f10], one additional operation for [f9, f10]] and [f6,f7,f8], and then one additional operation for [f9, f10]] combined with [f6,f7,f8] combined with [[f4,f5], [f1,f2,f3]]. Thus, the total operations for [f9,f10] is three operations. In view of the above, the total cost of the first partition is shown below:

FIG. 6 shows an example of the second partition of the merge computation system in accordance with aspects of the present invention. In FIG. 6, a diagram 300 is shown which corresponds with the second partition p_2 shown below:

In the diagram 300 for FIG. 6, there is one operation for [f1,f2], two additional operations for combining [f1,f2] with [f3,f4,f5], and then one additional operation for [[f1,f2], [f3, f4,f5]] combined with [f6,f7,f8] and [f9, f10]. Thus, the total operations for [f1,f2] is four operations. Further, in the diagram 200, there is two operations for [f3,f4,f5], one additional operation for combining [f3, f4,f5] with [f1,f2], and then two additional operations for [[f3,f4,f5], [f1,f2]] combined with [f6,f7,f8] and [f9, f10]. Thus, the total operations for [f3, f4,f5] is five operations.

Still referring to FIG. 6, there are two operations for [f6,f7,f8], one additional operation for [f6,f7,f8] combined with [f9,f10], and one additional operation for [f6,f7,f8] combined with [f9,f10] combined with [[f3,f4,f5], [f1,f2]]. Thus, the total operations for [f6,f7, f8] is four operations. Further, in the diagram 300, there is one operation for [f9,f10], one additional operation for [f9, f10]] and [f6,f7,f8], and then one additional operation for [f9, f10] combined with [f6,f7,f8] combined with [[f3,f4,f5], [f1,f2]]. Thus, the total operations for [f9,f10] is three operations. In view of the above, the cost of the second partition is shown below:

FIG. 7 shows a timeline of the merge computation system in accordance with aspects of the present invention. In FIG. 7, the timeline 400 shows that a time to, the merge computation system 100 determines a partition p_1 and estimates f1, . . . , fk. Further, after T days, at a time t1, the merge computation system 100 determines a partition p_2 and again estimates f1, . . . , fk due to a change in an update frequency (e.g., f_i) of the partitions. After another T days, at a time t2, the merge computation system determines a partition p_k and also estimates f1, . . . , fk due to another change in the update frequency of the partitions. As shown in FIG. 7, the merge computation system 10 re-calculates the partitions and the cost of partitions over time due to changing of the update frequency of the partitions.

FIG. 8 shows a flowchart of an exemplary method of the merge computation system in accordance with aspects of the present invention. Steps of the method may be carried out in the environment of FIG. 4.

At step 805, the system receives a plurality of documents for indexing into a vector database system. In embodiments and as described with respect to FIG. 4, the sorting module 110 sorts the plurality of documents in an increasing order of past frequency updates and sends the sorted documents to the recursive partitioning module 115.

At step 810, the system creates, at the recursive partitioning module 115, multiple recursive partitions of the sorted documents. In embodiments, and as described with respect to FIG. 4, the recursive partitioning module 115 creates the multiple recursive partitions using at least one of a Monte Carlo algorithm or simulated annealing. In further embodiments, and as described with respect to FIG. 4, the recursive partitioning module 115 sends the multiple recursive partitions to the cost computation module 120.

At step 815, the system computes, at the cost computation module 120, a cost of each partition in the multiple recursive partitions. At step 820, the system chooses, at the cost computation module 120, a partition with a smallest cost. In embodiments, and as described with respect to FIG. 4, the cost computation module 120 sends the partition with the smallest cost to the merging module 125.

At step 825, the system merges, by the merging module 125, the plurality of documents based on the partition with the smallest cost. At step 830, the system creates, at the merging module 125, a final vector database with the merged plurality of documents based on the partition with the smallest cost. In embodiments, and as described with respect to FIG. 4, the merging module 125 sends the final vector database to the vector database system.

FIG. 9 shows a flowchart of an exemplary method of the merge computation system in accordance with aspects of the present invention. Steps of the method may be carried out in the environment of FIG. 4.

At step 905, the system determines that the plurality of documents have changed frequency updates. In embodiments, and as described with respect to FIG. 4, the sorting module 110 determines that the plurality of documents have changed frequency updates based on database operations such as an update operation or a delete operation. At step 910, the sorting module 110 re-sorts the plurality of documents in an increasing order of past frequency updates based on the changed frequency updates of the plurality of documents and sends the sorted documents to the recursive partitioning module 115.

At step 915, the system creates, at the recursive partitioning module 115, multiple recursive partitions of the sorted documents. In embodiments, and as described with respect to FIG. 4, the recursive partitioning module 115 creates the multiple recursive partitions using at least one of a Monte Carlo algorithm or simulated annealing. In further embodiments, and as described with respect to FIG. 4, the recursive partitioning module 115 sends the multiple recursive partitions to the cost computation module 120.

At step 920, the system computes, at the cost computation module 120, a cost of each partition in the multiple recursive partitions. At step 925, the system chooses, at the cost computation module 120, a partition with a smallest cost. In embodiments, and as described with respect to FIG. 4, the cost computation module 120 sends the partition with the smallest cost to the merging module 125.

At step 930, the system merges, by the merging module 125, the plurality of documents based on the partition with the smallest cost. At step 935, the system creates, at the merging module 125, a final vector database with the merged plurality of documents based on the partition with the smallest cost. In embodiments, and as described with respect to FIG. 4, the merging module 125 sends the final vector database to the vector database system.