Method of merging large databases in parallel5717915Abstract The semantic integration problem for merging multiple databases of very large size, the merge/purge problem, can be solved by multiple runs of the sorted neighborhood method or the clustering method with small windows followed by the computation of the transitive closure over the results of each run. The sorted neighborhood method works well under this scheme but is computationally expensive due to the sorting phase. An alternative method based on data clustering that reduces the complexity to linear time making multiple runs followed by transitive closure feasible and efficient. A method is provided for identifying duplicate records in a database, each record having at least one field and a plurality of keys, including the steps of sorting the records according to a criteria applied to a first key; comparing a number of consecutive sorted records to each other, wherein the number is less than a number of records in said database and identifying a first group of duplicate records; storing the identity of the first group; sorting the records according to a criteria applied to a second key; comparing a number of consecutive sorted records to each other, wherein the number is less than a number of records in said database and identifying a second group of duplicate records; storing the identity of the second group; and subjecting the union of the first and second groups to transitive closure. Claims We claim: Description FIELD OF THE INVENTION
TABLE 1
______________________________________
SSN Name (First, Initial, Last)
Address
______________________________________
334600443
Lisa Boardman 144 Wars St.
334600443
Lisa Brown 144 Ward St.
525520001
Ramon Bonilla 38 Ward St.
525250001
Raymond Bonilla 38 Ward St.
0 Diana D. Ambrosion
40 Brik Church Av.
0 Diana A. Dambrosion
40 Brick Church Av.
0 Colette Johnen 600 113th St. apt. 5a5
0 John Colette 600 113th St. ap. 585
850982319
Ivette A Keegan 23 Florida Av.
950982319
Yvette A Kegan 23 Florida St.
______________________________________
EXAMPLE 1 Example of Matching Records Detected by an Equational Theory Rule Base The Sorted Neighborhood Method Two approaches are available to obtain efficient execution of any solution: utilize parallel processing, and partition the data to reduce the combinatorics of matching large data sets. Hence, a means of effectively partitioning the data set in such a way as to restrict attention to as small a set of candidates for matching as possible is required. Consequently, the candidate sets may be processed in parallel. Furthermore, if the candidate sets can be restricted to a small subset of the data, quadratic time algorithms applied to each candidate set may indeed be feasible, leading to perhaps better functional performance of the merge task. One possible method for bringing matching records close together is sorting the records. After the sort, the comparison of records is then restricted to a small neighborhood within the sorted list. This technique is referred herein as the sorted neighborhood method. The effectiveness of this approach is based on the quality of the chosen keys used in the sort. Poorly chosen keys will result in a poor quality merge, i.e., data that should be merged will be spread out far apart after the sort and hence will not be discovered. Keys should be chosen so that the attributes with the most discriminatory power should be the principal field inspected during the sort. This means that similar and matching records should have nearly equal key values. However, since it is assumed that the data contains corruptions, and keys are extracted directly from the data, then the keys could also be corrupted. Thus, it is expected that a substantial number of matching records will not be caught. In fact, experimental results, demonstrate this to be the case. Given a group of two or more database tables, they can first be concatenated into one sequential list of records and then processed according to the sorted neighborhood method. The sorted neighborhood method for solving the merge/purge problem can be summarized in three phases: Create Keys: Compute a key for each record in the list by extracting relevant fields or portions of fields. Sort Data: Sort the records in the data list using the key of step 1. Merge: Move a fixed size window through the sequential list of records limiting the comparisons for matching records to those records in the window. If the size of the window is w records, then every new record entering the window is compared with the previous records to find "matching" records. The first record in the window slides out of the window. When this procedure is executed serially, the create keys phase is an O(N) operation, the sorting phase is O(N log N), and the merging phase is O(wN), where w is the number of records in the database. Thus, the total time complexity of this method is O(N log N) if w<›log N!, O (wN) otherwise. However, the constants in the equations differ greatly. It could be relatively expensive (i.e. require substantial computational resources to solve a problem having a high computational complexity) to extract relevant key values from a record during the create key phase. Sorting requires a few machine instructions to compare the keys. The merge phase requires the matching of a large number of rules to compare two records, and thus has the largest constant factor. Note, however, the dominant cost will be the number of passes over the data set during sorting (possibly as many as log N passes), an I/O bounded computation. Clustering the Data First Since sorting the data is the dominant cost of the sorted-neighborhood method, it is desirable to reduce the number of records that are sorted. An easy solution is to first partition the data into clusters using a key extracted from the data. The sorted-neighborhood method is then applied to each individual cluster. This approach is called the clustering method. Given a group of two or more databases, these can first be concatenated into one sequential list of records. The clustering method can be summarized as a two phase process: Cluster Data: Scan the records in sequence and for each record extract an n-attribute key and map it into an n-dimensional cluster space. For instance, the first three letters of the last name could be mapped into a 3D cluster space. Sorted-Neighborhood Method: The sorted-neighborhood method is applied independently on each cluster. It is not necessary, however, to recompute a key (step 1 of the sorted neighborhood method). The key extracted above for sorting may be employed. When this procedure is executed serially, the cluster data phase is an O(N) operation, and assuming the data is partitioned into C equal sized clusters, the sorted-neighborhood phase is O(N log (N/C)). Clustering data as described above raises the issue of how well partitioned the data is after clustering. If the data from which the n-attribute key is extracted is distributed uniformly over its domain, then it can be expected that all clusters will have approximately the same number of records in them. But real-world data is very unlikely to be uniformly distributed and thus, it must be expected that it will be necessary to compute very large clusters and some empty clusters. Sometimes the distribution of some fields in the data is known, or can be computed as the data is inserted into the database. For instance, a database may contain a field for names. Lists of person names are available from which, e.g., the distribution Of the first three letters of every name can be computed, thus providing a cluster space of bins (26 letters plus the space). If such a list is unavailable, the name field of the database tables may be randomly sampled to have an approximation of the distribution of the first three letters. In any case, it is easy to create a frequency distribution histogram for several fields in the databases. All of this information can be gathered off-line before applying the clustering method. Assuming the data is divided into C clusters using a key extracted from a particular field. Given a frequency distribution histogram with B bins for that field (C.ltoreq.B), those B bins (each bin represents a particular range of the field domain) may be divided into C subranges. Let b.sub.i be the normalized frequency for the i.sup.th bin of the histogram: ##EQU1## Then for each of the C subranges the expected sum of the frequencies over the subrange is close to 1/C (e.g., if bins s to e, 1.ltoreq.s.ltoreq.e.ltoreq.B are assigned to one cluster then it is expected: ##EQU2## Each subrange will become one of the clusters and, given a record, the key is extracted from the selected field, and map the key into the corresponding subrange of the histogram. The complexity of this mapping is, at worst, log B. Equational Theory The comparison of records, during the merge phase, to determine their equivalence is a complex inferential process that considers much more information in the compared records than the keys used for sorting. For example, suppose two person names are spelled nearly (but not) identically, and have the exact same address. It might be inferred they are the same person. On the other hand, supposing two records have exactly the same social security numbers, but the names and addresses are completely different, it could either be assumed that the records represent the same person who changed his name and moved, or the records represent different persons, and the social security number field is incorrect for one of them. Without any further information, the latter might perhaps be assumed more likely. The more information there is in the records, the better inferences can be made. For example, Michael Smith and Michele Smith could have the same address, and their names are "reasonably close". If gender information is available, it could be inferred that Michael and Michele are married or siblings. What is needed to specify for these inferences is an equational theory that dictates the logic of domain equivalence, not simply value or string equivalence. There are of course numerous methods of specifying the axioms of the theory, including assembler code (presumably for speed). Users of a general purpose merge/purge facility will likely benefit from higher level formalisms and languages permitting ease of experimentation and modification. For these reasons, it is preferred to employ a natural approach to specifying an equational theory and making it practical, using a declarative role language. Rule languages have been effectively used in a wide range of applications requiring inference over large data sets. Much research has been conducted to provide efficient means for their evaluation, and this technology can be exploited here for purposes of solving merge/purge. This technology is known to those skilled in the art. As an example, a simplified role in English that exemplifies one axiom of the equational theory relevant to merge/purge applied to the idealized employee database is shown below: Given two records, r1 and r2. IF the last name of r1 equals the last name of r2, AND the first names differ slightly, AND the address of r1 equals the address of r2 THEN r1 is equivalent to r2. The implementation of "differ slightly" specified here in English is based upon the computation of a distance function applied to the first name fields of two records, and the comparison of its results to a threshold. The selection of a distance function and a proper threshold is also a knowledge intensive activity that demands experimental evaluation. An improperly chosen threshold will lead to either an increase in the number of falsely matched records or to a decrease in the number of matching records that should be merged. A number of alternative distance functions were implemented and tested including distances based upon edit distance, phonetic distance and "typewriter" distance. The results presented below are based upon edit distance computation since the outcome of the program did not vary much among the different distance functions. For the purpose of experimental study, an OPS5 rule program consisting of 26 rules for this particular domain of employee records was used over relatively small databases of records. See C. L. Forgy, "OPS 5 user's manual", Technical Report CMU-CS-81-135, Carnegie Mellon University (July 1981). Once the performance of the rules is deemed satisfactory, distance functions, and thresholds, the program was recoded with rules written directly in C to obtain speed-up over the OPS5 implementation. Table 1 demonstrates a number of actual records this program correctly deems equivalent. Although compilers for rule languages exist, see D. P. Miranker, B. Lofaso, G. Farmer, A. Chandra, and D. Brant. "On a TREAT -based production system compiler", Proc. 10th Int'l Conf. on Expert Systems, pp 617-630, (1990), there is still a significant gap in performance forcing the inevitable conversion to C. However, OPS5 provided an especially useful prototyping facility to define an equational theory conveniently. Using the Transitive Closure Over the Results of Independent Runs Once an equational theory is specified for matching database records and converted to a program, the matching program is applied to a small subset of data, e.g., those records presently in the window of the sorted list. The program output thus depends upon whether matching records appear in a window. Consequently, the effectiveness of the sorted neighborhood method highly depends on the key selected to sort the records. A key is defined to be a sequence of a subset of attributes, or substrings within the attributes, chosen from the record. (For example, the last name of the employee record may be chosen as a key, followed by the first non blank character of the first name field followed by the first six digits of the social security field, and so forth.) In general, no single key will be sufficient to catch all matching records. Keys give implicit priorities to those fields of the records occurring at the beginning of the sequence of attributes over others. If the error in a record occurs in the particular field or portion of the field that is the most important part of the key, there is little chance this record will end up close to a matching record after sorting. For instance, if an employee has two records in the database, one with social security number 193456782 and another with social security number 913456782 (the first two numbers were transposed), and if the social security number is used as the principal field of the key, then it is very unlikely both records will fall under the same window. Thus, the records will not be merged. The number of matching records missed by one run of the sorted neighborhood method can be comparatively large. To increase the number of similar records merged, two options can be explored. The first is simply widening the scanning window size by increasing w. Clearly this increases the complexity, and, as discussed in the next section, does not increase dramatically the number of similar records merged (unless of course the window spans the entire database, which as noted corresponds to an infeasible N.sup.2 operation). The alternative strategy is implemented to execute several independent runs of the sorted neighborhood method, each time using a different key and a relatively small window. For instance, in one run, the social security number might be used as the principal part of the key while in another run the last name of the employee might be used as the principal part of the key. Each independent run will produce a set of pairs of records which can be merged. The transitive closure is then applied to those pairs of records. The results will be a union of all pairs discovered by all independent runs, with no duplicates, plus all those pairs that can be inferred by transitivity. In the following, several independent runs of the sorted neighborhood method are combined with the transitive closure of the results, which drastically improves the results of one run of the sorted neighborhood method. A drawback of this combination is the need of several runs of the sorted neighborhood method. However, each independent run requires only a small search window. No individual run produced comparable results with large windows. Thus, the complexity of the merge phase for the sum total of these independent runs is smaller than the complexity of one run with a large window while its functional performance was far superior. Experimental Results Generating the Databases All databases used to test the sorted neighborhood method and the clustering method were generated automatically by a database generator program. This database generator allows the selection among a large number of parameters including, the size of the database, the percentage of duplicate records in the database, and the amount of error to be introduced in the duplicated records. The principal benefit of the generator is to perform controlled studies and to establish the functional performance of the solution method. Each record generated consists of the following fields, some of which can be empty: social security number, first name, initial, last name, address, apartment, city, state, and zip code. The names are chosen randomly from a list of 63000 real names. The cities, states, and zip codes (all from the U.S.A.) come from publicly available lists. The noise introduced in the duplicate records can go from small typographical changes, to complete change of last names and change of addresses. When setting the parameters for the kind of typographical errors, known frequencies from studies in spelling correction algorithms were used. See K. Kukich, "Techniques for automatically correcting words in text", ACM Computing Surveys, 24(4):377-439 (1992). For this study, the generator selected from 10% to 50% of the generated records for duplication with noise. Pre-processing the Generated Database Pre-processing the records in the database prior to the merge/purge operation might increase the chance of finding two duplicate records. For example, names like Joseph and Giuseppe match in only three characters, but are the same name in two different languages, English and Italian. A nicknames database or name equivalence database could be used to assign a common name to records containing identified nicknames. Since misspellings are introduced by the database generator, the results can probably be improved by running a spelling correction program over some fields before submitting the database to the sorting neighborhood method. Spelling correction algorithms have received a large amount of attention for decades. See Kukich, Supra. Most of the spelling correction algorithms considered use a corpus of correctly spelled words from which the correct spelling is selected. A corpus for the names of the cities in the U.S.A. (18670 different names) is available and can be used to attempt correcting the spelling of the city field. The algorithm described by Bickel in M. A. Bickel. "Automatic correction to misspelled names: a fourth-generation language approach", Communications of the ACM, 30(3):224-228 (1987) was selected for its simplicity and speed. The use of spell corrector over the city field improved the percent of correctly found duplicated records by 1.5%-2.0%. A greater proportion of the effort in matching resides in the equational theory rule base. Running the Sorted Neighborhood Method The purpose of this first experiment was to see how many duplicate records the sorted neighborhood method could find. Three independent runs of the sorted neighborhood method were run over each database, and a different key was used during the sorting phase of each independent run. On the first run the last name was the principal field of the key (i.e., the last name was the first attribute in the key). On the second run, the first name was the principal field of the key. Finally, in the last run, the street address was the principal field of the key. The selection of the keys was purely arbitrary, and could have used the social-security number instead of, say, the street address. The data generator is assumed to be controlled, such that all fields are noisy and therefore it should not matter which fields are selected. FIG. 1 shows the effect of varying the window size from 2 to 50 records in a database with 1,000,000 records and with an additional 1423644 duplicate records with varying noise. A record may be duplicated more than once. Each independent run found between 50 and 70% of the duplicated pairs. Increasing the window size does not help much and taking in consideration that the time complexity of the procedure goes up as the window size increases, it is obviously fruitless to use a large window size. The line marked as X-closure over 3 keys in FIG. 1 graph shows the results when the program computes the transitive closure over the pairs found by the four independent runs. The percent of duplicates found goes up to almost 90%. A manual inspection of those records not found as equivalent revealed that most of them are pairs that would be hard for even a human to identify without further information (e.g., both records do not have a social security number, the names are the same or very close, the street addresses are the same but in different states). However, the equational theory is not completely accurate. It can mark two records as similar when they are not the same real-world entity (false-positives). FIG. 2 shows the percent of those records incorrectly marked as duplicates as a function of the window size. The percent of false positives is almost insignificant for each independent run and grows slowly as the window size increases. The percent of false positives after the transitive closure is used is also very small, but grows faster than each individual run alone. This suggests that the transitive-closure may not be effective if the window size is very large. The number of independent runs needed to obtain good results with the computation of the transitive closure depends on how corrupt the data is and the keys selected. The more corrupted the data, more runs might be needed to capture the matching records. Although not shown in FIG. 1, the sorted-neighborhood method, conducted with only two independent runs and computing the transitive closure over the results of those two runs, produced a percentage of detected duplicate records of between 70% to 80%. The transitive closure, however, is executed on pairs of record id's, each at most 30 bits in the present example, and in general log N bits, and fast solutions to compute transitive closure exist. See R. Agarawal and H. V. Jagadish, "Multiprocessor transitive closure algorithms", Proc. Int'l Symp. on Databases in Parallel and Distributed Systems, pp 56-66 (December 1988). From observing real world scenarios, the size of the data set over which the closure is computed is at least one order of magnitude smaller than the matching database of records, and thus does not contribute a large cost. But note there is a heavy price due to the number of sorts of the original large data set. Analysis The approach of using multiple sorts followed by the transitive closure is referred to as the multi-pass approach. The natural question posed is when is the multi-pass approach superior to the single sorted neighborhood case? The answer to this question lies in the complexity of the two approaches for a fixed accuracy rate. The accuracy rate, as defined herein is the total percentage of "mergeable" records found. The complexity of the multi-pass approach is given by the time to create keys, the time to sort r times, wherein the present example r=3 times, and window scanning r times (of window size w) plus the time to compute the transitive closure: T(multi-pass)=c.sub.1 rN+c.sub.2 rN logN+c.sub.3 rwN+T (TC) where r is the number of passes, and T(TC) is the time for the transitive closure. The constants depict the costs for comparison only and are related as c.sub.1 .ltoreq.c.sub.2 <<c.sub.3 =.alpha.c.sub.2, where .alpha.>1. From analyzing the experimental program, the window scanning phase contributes a constant, c.sub.3, which is at least .alpha.=3 times as large as the comparisons performed in sorting, while the create keys constant, c.sub.1, is roughly comparable to the comparisons used in sorting. Thus, for the purposes of the present analysis, it is assumed that c.sub.1 =c.sub.2, while c.sub.3 =.alpha.c.sub.2. Hence, the constants are replaced in terms of the single constant c. The complexity of the closure is directly related to the accuracy rate of each pass and is certainly dependent upon the duplication in the database. However, it is assumed the time to compute the transitive closure on a database that is orders of magnitude smaller than the input database to be less than the time to scan the input database once (i.e. less than linear in N, and contributes a factor of c.sub.4 N<N). Thus, T(multi-pass)=crN+crN logN+.alpha.crwN+c.sub.4 N=(c+cr logN+.alpha.crw)N+c.sub.4 N for a window size of w. The complexity of the single pass sorted neighborhood approach is similarly given by: T(singIe-pass)=cN+cN logN+.alpha.cWN=(c+c logN+.alpha.cW)N for a window size of W. For a fixed accuracy rate, the question is then for what value of W for the single pass sorted neighborhood method does the multi-pass approach perform better in time, i.e. ##EQU3## In the experiments performed and reported in the following sections, N=2.sup.20 records, .alpha. is approximately 3, c is approximately 8.times.10.sup.-5, w=10, and T(TC)=c4 N.ltoreq.180 seconds. Thus, the multi-pass approach dominates the single sort approach when W>45. FIG. 3 shows the time required to run each independent run of the sorted-neighborhood method on one processor, and the total time required for the multi-pass approach. As shown in FIG. 1, the multi-pass approach was found to produce an accuracy rate of 86.1% using a window size of 10. The time performance of the single pass run is similar to the time performance of the multi-pass approach with w=10 when W.congruent.56, a little over what was estimated above. But, the performance ratios of all single-pass runs in FIG. 1, at W=50, are from 17% to 28%, well below the 86.1% performance of the multi-pass approach. To study how large the window size W must be for one of the single-pass runs to achieve the same level of performance as the multi-pass approach, the rule based equational theory was replaced with a stub that quickly tells us if two records within the window are actually equal (thus the "ideal" performance is studied). The results, depicted in FIG. 4, show that any single-pass run would need a window size larger than W=50,000 to achieve the same performance level as the multi-pass approach using w=10. The "real" performance lines in FIG. 4 are those of FIG. 1, which are included to provide a sense of how effective the present rule-based equational theory is when compared with the ideal case. Thus, the multi-pass approach achieves dramatic improvement in time and accuracy over a single-pass approach. Further, the multi-pass approach may also be parallelized, clearly making the multi-pass the dominate method. EXAMPLE 2 The Clustering Method The same experiment was repeated using the clustering method to first partition the data into clusters, using the same three keys used above for the sorted-neighborhood method and ran three independent runs, one for each key. Then the transitive closure over the results of all independent runs was computed. The results are depicted in FIG. 1. Comparing the performance results in FIG. 3, it is noted that the performance level is almost the same for both methods. The timing results for these experiments are shown in FIG. 3. EXAMPLE 3 Parallel Implementation With the use of a centralized parallel or distributed network computer, a linear speedup over a serial computer is sought to be achieved. The Sorted-Neighborhood Method The parallel implementation of the sorted-neighborhood method is as follows. Let N be the number of records in the database. The implementation is presumed to have P processors, each processor being able to store M+w records, where w is the size of the merge phase window, and M is a blocking factor. Furthermore, since very large databases are the subject of this example, it is assumed that P<<N and MP<N. First, the input database is sorted in parallel using the well known technique of parallel merge sorting. Then, the sorted database is divided into N/MP blocks. Each of the N/MP blocks is processed in turn as follows. Let r.sub.i represent record i in a block, 0.ltoreq.i.ltoreq.MP-1. Each processor p receives records r.sub.(p-1)M, . . . , r.sub.pM-1, . . . , r.sub.pM+w-2, for 1.ltoreq.p.ltoreq.P, (i.e., each processor gets a partition of size M records plus the w-1 records of the next partition of the block). Then matching records can be searched independently at each processor using a window of size w. This process is then repeated with the next block of records. The time for the merge phase process under this scheme is, in theory, O(wN/P). Each independent run of the sorted-neighborhood method is independent of other independent runs. Therefore, given n times more processors, independent runs may be executed concurrently and at the end compute the transitive closure over the results. The sorted-neighborhood method was implemented on an HP cluster consisting of eight HP9000 processors interconnected by a FDDI network. FIG. 5 shows the total time taken for each of the three independent runs from FIG. 1 as the number of processors increases. The window size for all these runs was 10 records. FIG. 5 also includes the time it will take the sorted-neighborhood method to execute all three independent runs over three times the number of processor and then the computation of the transitive closure of the results. Using the system described above, enough processors to run all sorted-neighborhood runs concurrently were unavailable, so that the time taken for all of the runs must be estimated from results of each independent run. All independent runs were run serially and the results were stored on disk. The transitive closure was then computed over the results stored on disk and the time measured for this operation. The total time if all runs are executed concurrently is, approximately, the maximum time taken by any independent run plus the time to compute the closure. The speed-ups obtained as the number of processors grows are not exactly linear. The main reason for this is the inherent sequentialities in the process like reading and broadcasting the data to all processes. EXAMPLE 4 The Clustering Method The parallel implementation of the clustering method works as follows. Let N be the number of records in the database, P the number of processors and C the number of clusters to be formed per processor. Given a frequency distribution histogram, its range is divided into CP subranges as described above. Each processor is assigned C of those subranges. To cluster the data, a coordinator processor reads the database and sends each record to the appropriate processor. Each processor saves the received records in the proper local cluster. Once the coordinator finishes reading and clustering the data among the processors, all processors sort and apply the window scanning method to their local clusters. Load balancing of the operation becomes an issue when more than one processor is used and the histogram method does a bad job of partitioning the data. The present system attempts to do an initial static load balancing. The coordinator processor keeps track of how many records it sent to each processor (and cluster) and therefore it knows, at the end of the clustering stage, how balanced the partition is. It then redistributes the clusters among processors using a simple longest processing time first (LPT) strategy. See R. Graham, "Bounds on multiprocessing timing anomalies", SIAM Journal of Computing, 17:416-429 (1969). That is, move the largest job in an overloaded processor to the most underloaded processor, and repeat until a "well" balanced load is obtained. Elements of this technique are known. See H. M. Dewan, M. A. Hernandez, J. Hwang, and S. Stolfo, "Predictive dynamic load balancing of parallel and distributed rule and query processing", Proceedings of the 1994 ACM Sigmod Conference (1994). The time results for the clustering method are depicted in FIG. 5. These results are for the same database used to obtain the timing results for the sorted neighborhood method, a window size of 10 records, and 100 clusters per processor. Comparing the results in FIG. 5 it is noted that the clustering method is, as expected, faster than the sorted-neighborhood method. EXAMPLE 5 Scaling Up Finally, the sorted-neighborhood method and clustering method are demonstrated herein to scale well as the size of the database increases. The present example is limited, by virtue of limitations in disk space in the experimental system, to databases up to about 3,000,000 records. Of course, larger systems could be implemented without this limitation by providing more disk space. Again, three independent runs were run using the sorted-neighborhood method (and the clustering method), each with a different key, and then computed the transitive closure of the results. This was performed for the 12 databases as shown in Table 2 and ran all the experiments assigning 4 processors to each independent run. The results are shown in FIG. 6. As expected, the time increases linearly as the size of the databases increase.
TABLE 2
______________________________________
Original
number Total records Total size (Mbytes)
of records
10 30 50 10 30 50
______________________________________
500000 584495 754354 924029
45.4 58.6 71.8
1000000 1169238 1508681 1847606
91.3 118.1
144.8
1500000 1753892 2262808 2770641
138.1
178.4
218.7
1750000 2046550 2639892 3232258
161.6
208.7
255.7
______________________________________
Using the graphs in FIG. 6, the time it will take to process 1 billion records using both methods may be estimated, assuming the time will keep growing linearly as the size of the database increases. For the sorted-neighborhood method, let us consider the last point of the "30" graph. Here, a database with 2,639,892 records was processed in 2172 seconds. Thus, given a database with 1,000,000,000 records, approximately 1.times.10.sup.9 .times.(2172/263892) s=8.2276.times.10.sup.5 s.congruent.10 days will be needed. Doing the same analysis With the clustering method, a database of size 2,639,892 records was processed in 1621 seconds. Thus, given a database with 1,000,000,000 records, it is expected that approximately 1.times.10.sup.9 .times.(1621/2639892) s=6.1404.times.10.sup.5 .congruent.7 days will be required. Of course, doubling the speed of the workstations and the channels used (which is possible today since the HP processors are slow compared to, for example, a DEC Alpha workstation, a RISC processor-based computer) would produce a total time that is at least half the estimated time. The present system may preferably be applied to data relating to employee records, mailing lists, credit and credit cards, consumer preferences determined in retail environments or at the point of sale (POS). Data, such as point of sale data, is of particular value only when appropriate database records are merged, and the circumstances relating to the gathering of this type of data may also create a high likelihood of errors in the identifying information. Therefore, the present invention will improve the operation of systems processing various large databases including, e.g. consumer related data, due to its ability to efficiently process large numbers of database records and merge corresponding records in the database. The above description, figures and preferred embodiments are provided not to limit the invention but to assist one skilled in the art in better understanding the invention contained herein. The inventor is not thereby limited to the preferred embodiments, but is only limited by the scope of the claims below. One of reasonable skill in the art can also practice the invention through other and equivalent methods, compositions and techniques which are, as well, included within the scope of the invention, to the extent set forth in the appended claims.
|
Same subclass Same class Consider this |
||||||||||