Source: https://patents.google.com/patent/US8229900
Timestamp: 2018-07-20 23:57:07
Document Index: 198989027

Matched Legal Cases: ['art 24', 'art 36', 'art 38', 'art 26', 'art 24', 'art 36', 'art 26', 'art 34', 'art 36', 'art 38', 'art 46', 'art 40', 'art 40', 'art 44', 'art 28', 'art 28', 'art 44', 'art 42', 'art 42', 'art 40', 'art 40', 'art 26', 'art 38', 'art 28', 'art 42', 'art 42', 'art 42']

US8229900B2 - Generating a data structure for information retrieval - Google Patents
Generating a data structure for information retrieval Download PDF
US8229900B2
US8229900B2 US12062411 US6241108A US8229900B2 US 8229900 B2 US8229900 B2 US 8229900B2 US 12062411 US12062411 US 12062411 US 6241108 A US6241108 A US 6241108A US 8229900 B2 US8229900 B2 US 8229900B2
US12062411
US20090006378A1 (en )
A computer system for generating data structures for information retrieval of documents stored in a database. The computer system includes: a neighborhood patch generation system for defining patch of nodes having predetermined similarities in a hierarchy structure. The neighborhood patch generation subsystem includes a hierarchy generation subsystem for generating a hierarchy structure upon the document-keyword vectors and a patch definition subsystem. The computer system also comprises a cluster estimation subsystem for generating cluster data of the document-keyword vectors using the similarities of the patches.
Similarity search (also known as proximity search) is one in which items of a database are sought according to how well they match a given query element. Similarity (or rather, dissimilarity) is typically modeled using some real- or integer-valued distance
‘metric’ dist: that is,
Current information retrieval methods often uses vector space modeling to represent the documents of databases. In such vector space models, each document in the database under consideration is associated with a vector, each coordinate of which represents a keyword or attribute of the document; details of the vector space models are provided elsewhere (Gerald Salton, The SMART Retrieval System—Experiments in Automatic Document Processing, Prentice-Hall, Englewood Cliffs, N.J., USA, 1971).
For more information regarding data dimension and the curse of dimensionality, see (for example) Chavez et al. (op cito)), Pagel et al. (Bernd-Uwe Pagel, Flip Korn and Christos Faloutsos, Deflating the dimensionality curse using multiple fractal dimensions, Proc. 16th International Conference on Data Engineering (ICDE 2000), San Diego, USA, IEEE CS Press, 2000, pp. 589-598.), Pestov (Vladimir Pestov, On the geometry of similarity search: dimensionality curse and concentration of measure, Information Processing Letters, 73, 2000, pp. 47-51.), and Weber et al. (Roger Weber, Hans-J. Schek and Stephen Blott, A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces, Proc. 24th VLDB Conference, New York, USA, 1998, pp. 194-205).
In a hierarchical agglomerative clustering, each data point is initially considered to constitute a separate cluster. Pairs of clusters are then successively merged until all data points lie in a single cluster. The larger cluster produced at each step contains the elements of both merged subclusters; it is this inclusion relationship that gives rise to the cluster hierarchy. The choice of which pairs to merge is made so as to minimize some inter-cluster distance criterion.
G. Shared-Neighbor Methods
One of the criticisms of simple distance-based agglomerative clustering methods is that they are biased towards forming clusters in regions of higher density. Well-associated groups of data in regions of low density risk not being discovered at all, if too many pairwise distances fall below the merge threshold. More sophisticated (and expensive) distance measures for agglomerative clustering have been proposed, that take into account the neighborhoods of the data elements. Jarvis et al. (R. A. Jarvis and E. A. Patrick, Clustering using a similarity measure based on shared nearest neighbors, IEEE Transactions on Computers C-22, 11, November 1973, pp. 1025-1034.) defined a merge criterion in terms of an arbitrary similarity measure dist and fixed integer parameters k>r>0, in which two data elements find themselves in the same cluster if they share at least a certain number of nearest neighbors. The decision as to whether to merge clusters thus does not depend on the local density of the data set, but rather as to whether there exists a pair of elements, one drawn from each, that share a neighborhood in a substantial way.
Jarvis and Patrick's method (op. cito) is agglomerative, and resembles the single-link method in that it tends to produce irregular clusters via chains of association. More recent variants have been proposed in an attempt to vary the qualities of the clusters produced: for example, by Guha et al. (S. Guha, R. Rastogi and K. Shim, ROCK: a robust clustering algorithm for categorical attributes, Information Systems 25, 5, 2000, pp. 345-366.); by Ertoz et al. (Levent Ertoz, Michael Steinbach and Vipin Kumar, Finding topics in collections of documents: a shared nearest neighbor approach, University of Minnesota Army HPC Research Center Preprint 2001-040, 8 pages, 2001.); by Ertoz et al. (Levent Ertoz, Michael Steinbach and Vipin Kumar, A new shared nearest neighbor clustering algorithm and its applications, Proc. Workshop on Clustering High Dimensional Data and its Applications (in conjunction with 2nd SIAM International Conference on Data Mining), Arlington, Va., USA, 2002, pp. 105-115.); by Daylight Chemical Information Systems Inc., in URL address (http://www.daylight.com/); and by Barnard Chemical Information Ltd., in URL address (http://www.bci.gb.com/). Nonetheless, all variants still exhibit the main characteristics of agglomerative algorithms, in that they allow the formation of large irregularly-shaped clusters with chains of association bridging poorly-associated elements.
a neighborhood patch generation part for generating groups of nodes having similarities as determined using a search structure, the patch generation part including a part for generating a hierarchical structure upon the document-keyword vectors and a patch defining part for creating patch relationships among said nodes with respect to a metric distance between nodes; and
a cluster estimation part for generating cluster data of the document-keyword vectors using the similarities of patches.
According to the present invention, the computer system comprises a confidence determination part for computing inter-patch confidence values between the patches and intra-patch confidence values, and the cluster estimation part selects the patches depending on the inter-patch confidence values to represent clusters of the document-keyword vectors.
According to the present invention, the cluster estimation part estimates sizes of the clusters depending on the intra-patch confidence values.
invoking the hierarchy data and the patches to compute inter-patch confidence values between the patches and intra-patch confidence values, and storing the values as corresponding lists in an adequate storage part; and
a neighborhood patch generation part for generating groups of nodes having similarities as determined using a hierarchical structure, the patch generation part including a part for generating a hierarchical structure upon the document-keyword vectors and a patch defining part for creating patch relationships among said nodes with respect to a metric distance between nodes; and
a cluster estimation part for generating cluster data of the document-keyword vectors using the similarities of patches; and
a graphical user interface part for presenting the estimated cluster data on a display means.
According to the present invention, the information retrieval system comprises a confidence determination part for computing inter-patch confidence values between the patches and intra-patch confidence values, and the cluster estimation part selects the patches depending on the inter-patch confidence values to represent clusters of the document-keyword vectors. According to the present invention, the cluster estimation part estimates sizes of the clusters depending on the intra-patch confidence values. According to the present invention, the system further comprises a user query receiving part for receiving the query and extracting data for information retrieval to generate a query vector, and an information retrieval part for computing similarities between document-keyword vectors and the query vector to select the document-keyword vectors. The clusters are estimated using the retrieved document-keyword vectors with respect to the user input query.
According to the present graphical user interface, the computer comprises a neighborhood patch generation part for generating groups of nodes having similarities as determined using a search structure, the neighborhood patch generation part including a part for generating a hierarchical structure upon the document-keyword vectors and a patch defining part for creating patch relationships among the nodes with respect to a metric distance between nodes; and
a cluster estimation part for generating cluster data of the document-keyword vectors using the similarities of patches. Further according to the present invention, the computer comprises a confidence determination part for computing inter-patch confidence values between the patches and intra-patch confidence values, and the cluster estimation part selects the patches depending on the inter-patch confidence values to represent clusters of the document-keyword vectors and the cluster estimation part estimates sizes of the clusters depending on the intra-patch confidence values.
Part I—Processes of the Method
Hereinafter, the present invention will be explained in the context of information retrieval of documents; however, the present invention is not limited thereto and the algorithm of the present invention can be adapted for any application for which a pairwise dissimilarity measure is used that satisfies the properties of a distance metric (with the possible exception of the triangle inequality), and for which each data element has keywords or other information that can be used for annotation purposes. One example of such an application is a data mining system for multimedia databases (e.g., databases with contents which consist of text, audio, video, still images, graphics images, graphics videos, and/or gif animations, etc.) having contents for which such a pairwise dissimilarity metric exists.
A flowchart of the general method according to the present invention is shown in FIG. 1. Although the present invention is primarily explained using an application to for texts, a person skilled in the art may understand that the methods of the present invention are easily adapted to any database with contents which may be modeled with a clearly defined metric that enables computation of distances between any two elements so that pairs of elements which are “closer” (with respect to the metric) are more similar than pairs of elements that are “further apart”.
Document-keyword vectors may be computed from given keywords and documents using any of several known techniques. In a particular embodiment of the present invention, appropriate weighting is used to digitize the documents; details of the digitization has been provided elsewhere (e.g. Salton et al., op. cito), and therefore are not explained in the present invention.
FIG. 2 shows a general procedure for constructing the hierarchical structure of the document-keyword vectors known as a spatial approximation sample hierarchy, or SASH. The process begins at the step S28 after receiving the result of the step S10 of FIG. 1 to generate a random assignment of vectors to nodes of the SASH using, for example, any well-known random number generating program. The levels are numbered from 0 to h, where each level contains roughly twice as many vector nodes as the one following it. The level numbered 0 contains roughly half the vector nodes of the data set, and the level numbered h contains a single node, called the top node. The top node of the SASH structure is determined randomly using any random number generation means included elsewhere in the computer system. Next, in the step S30, a hierarchy level reference L is initialized to h. The process proceeds to the step S32 to decrease the hierarchy level L by 1 and in the step S34 level L nodes are connected to a set of level L+1 nodes depending on distances between the nodes. In the above connection, the nodes at level L+1 become parent nodes and the nodes at level L become child nodes. The connection is performed by choosing parents of a node from level L from among the closest nodes from level L+1, and then connecting these parent-child node pairs so that each parent is connected to a predetermined number of its closest children. Further details on how the connections are performed are given elsewhere, by Houle et al. (op. cito). The process proceeds to the step S36 and determines whether or not the hierarchy level reaches to the lowest level (0), and if so (yes), the construction of the SASH is completed and the SASH structure is stored in an adequate memory area such as memory or a hard disk. The process continues to the step S38 to construct patches of nodes. If not so (no), the process reverts to the step S32 to repeat until an affirmative result in the step S36 is obtained.
The method of the present invention uses a novel model for clustering that borrows from both information retrieval and association rule discovery herein named the “patch model”. The patch model assumes that data clusters can be represented as the results of neighborhood queries based on elements from the data set, according to some measure of (dis)similarity appropriate to the domain. More formally, let S be a database of elements drawn from some domain D, and now, let “dist” be a pairwise distance function defined on D satisfying the properties of a metric, as defined earlier. Further now, let R be a subset of S. For any given query pattern q□D, let NN(R, q, k) which denote a k-nearest neighbor set of q, drawn from R according to dist, and chosen subject to the following conditions:
R, then NN(R, q, 1)={q}, that is, if q is a member of the data set, then q is considered to be its own nearest neighbor.
FIG. 4 illustrates a collection of patches (a 7-patch 401, a 12-patch 403, and an 18-patch 405) of a database. The dashed circle 407 represents the entire document space.
CONF(Ci,Cj)=|Ci∩Cj|/|Ci|=|NN(R,qi,ki)∩NN(R,qj,kj)|/ki.
FIG. 5 shows an essential function of CONF to the clusters Ci and Cj which include 8 and 10 vectors, respectively. Two vectors are in the common intersection of Ci and Cj, and therefore when the function CONF is applied to the patches in the order Ci, Cj, that is, CONF (A, B), the result is 0.25 or 25%. When the function is applied in the order Cj, Ci, that is, CONF (Cj, Ci), the result is 0.2 or 20%. The function CONF can be applied to any two patches drawn from a common underling sample of the database.
A natural assessment of association within patches is also possible in terms of the notion of confidence. Let Cq=NN(R, q, k) be a patch cluster candidate. Here the constituent patches of Cq is defined to be the set of those patches of the form Cv=NN(R, v, k), for all elements v□Cq. If Cq has a high degree of internal association, then one can reasonably expect strong relationships between Cq and its constituent patches. On the other hand, low internal association would manifest itself as weak relationships between Cq and its constituent patches. Therefore, internal association within a patch cluster candidate in terms of its self-confidence is obtained and is defined as the average confidence of the candidate patches with respect to its constituent patches:
SCONF ⁡ ( Cq ) = ⁢ ( 1 /  Cq  ) * Σv ⁢ ⁢ included ⁢ ⁢ within ⁢ ⁢ Cq ,  Cv  = ⁢  Cq  ⁢ CONF ⁡ ( Cq , Cv ) = ⁢ ( 1 / k ⁢ ⁢ 2 ) * Σv ⁢ ⁢ included ⁢ ⁢ within ⁢ ⁢ Cq ⁢ ⁢  NN ⁡ ( R , q , k ) ⋂ NN ⁡ ( R , v , k )  .
max a≦k≦bRSCONF(Cq,k,φ),
RSCONF ⁡ ( Cq , k , φ ) = ⁢ SCONF ⁡ ( Cq , k ) - SCONF ⁡ ( Cq , φ ⁡ ( k ) ) = ⁢ SCONF ⁡ ( NN ⁡ ( R , q , k ) ) - ⁢ SCONF ⁡ ( NN ⁡ ( R , q , φ ⁡ ( k ) ) ) , ⁢
In the present invention, the RSCM method as presented allows for many variations in the way the outer patch size depends on the value of k (k is integer.). Although the simple choice φ(k)=2 k is ideal in that it provides the best balance between membership and non-membership of outer patch elements with respect to the inner patch, other considerations may influence the choice of φ(k). For example, the cost of computing boundary sharpness values may encourage the use of a maximum patch size m<2b. In this case, the outer patch size could be chosen to be φ(k)=min{2 k, m}, provided that the smallest ratio m/b between outer and inner patch sizes is still substantially greater than 1.
E[k]=μ=|R|/|S|
Even when the RSCM method promotes a proxy patch NN(Ri, q, ki) as a cluster estimator, there is no precise way of inferring the size of the corresponding cluster in S. However, following the principle of maximum likelihood estimation, the value c=E[k] |S|/|Ri| at which E[k]=ki constitutes a natural estimate of the true cluster size. The smallest cluster size that can be estimated with respect to sample Ri is therefore (a|S|)/|Ri|.
Further in the present invention, by virtue of the proximity of their members to a common query element, clusters produced by the RSCM method tend to be much more cohesive than those produced by agglomerative clustering methods, a desirable trait in the context of text mining. In particular, query clusters are biased towards shapes that are spherical relative to the pairwise distance metric.
The proposed total clustering strategy, the function PatchCluster constructs a query cluster relationship (QCR) graph drawn from a collection of uniform random samples {R0, R1, R2, . . . } such that Ri within Rj for all j<i and |Ri|=ceil(|S|/2i) for 0≦i<log 2|S|. The graph structure depends on several parameters resembling the confidence and support thresholds used in association rule generation:
iv) (association scale) a maximum threshold ε on the difference in scale between two associated clusters (that is, the difference |i−j|, where Ri and Rj are the samples from which the clusters derive).
1. QCR Node Set:
For each 0≦t<log 2|S|, from the elements of sample Rt, generate a collection of query clusters QCt={C1, C2, . . . , C|Rt|}, with each cluster Ci=NN(Rt, qi, ki) based at a different query element of Rt, and a≦|Ci|≦b. Choose the membership of QCt in greedy fashion from among the available query clusters according to RSCONF values, where i<j=>RSCONF(Ci)≧RSCONF(Cj), subject to two conditions:
ii. (cluster quality) RSCONF(Ci)≧α for all 1≦i≦|Rt|.
2. QCR Edge Set:
Another variation of the PatchCluster method involves the control of the number of clusters. As described above, the number of clusters produced is controlled by specifying a threshold a on the relative self-confidence of the query clusters reported. Instead, the user may be given the option of determining the number of clusters for each data sample separately. For a given level t, this can be done by:
i) specifying a minimum threshold at on the relative self-confidence of the query clusters to be reported from level t, or
Also the maximum patch size should be chosen to be as small as possible for reasons of efficiency. However, it should be chosen to be substantially larger than b. The choice φ(b)=2b is ideal; however, the choice φ(b)=1.25b can also give good results. In the best embodiment of the present invention, a=25, b=120, and φ(k)=min {2 k, 150} were preferred because satisfactory results were obtained with many data sets.
The maximum threshold β on the confidence between any two clusters from a common sample should be set to roughly 0.4, regardless of the data set. Experimentation showed that overlapping query clusters from a common sample tend either to overlap nearly completely, or only slightly. The clustering produced by the PatchCluster method is relatively insensitive to the exact choice of b.
(b) The minimum threshold α on the confidence between associated clusters in the QCR graph (not necessarily drawn from a common sample level). Values in the range 0.15□γ□0.2 are recommended; the smaller the value, the greater the number of edges of the graph.
i) (Elimination of transitive edges between levels.) For example, assume the graph contains cluster nodes C1=NN(Ru, q1, k1), C2=NN(Rv, q2, k2), and C3=NN(Rw, q3, k3), where u<v<w, and association edges (C1,C2), (C2,C3) and (C1,C3). Then edge (C1,C3) can be hidden from the user, since he or she would still be able to navigate from C1 to C2 via (C1,C2) and (C2,C3).
If dimensional reduction techniques such as COV or LSI are being used, the original unreduced document vectors may no longer be available, or may be expensive to store and retrieve. Nevertheless, meaningful term lists can still be extracted even without the original vectors. Note first that the i-th term can be associated with a unit vector zi=(zi,1, zi,2, . . . , zi,d) in the original document space, such that zi,j=1, if i=j, and zi,j=0 otherwise. Now, let μ be the average of the document vectors belonging to the query cluster NN(R, q, k). Using this notation, the score for the i-th term can be expressed simply as zi□μ. However, since □zi□=1 and μ is a constant, ranking the terms according to these scores is equivalent to ranking them according to the measure as below:
zi□xμ/∥μ∥=cos angle(zi,μ)=cos θi,
With dimensional reduction, the pairwise distance cos angle(v, w) between vectors v and w of the original space is approximated by cos angle(v′, w′), where v′ and w′ are the respective equivalents of v and w in the reduced dimensional space. Hence we could approximate cos angle(zi,μ) by cos angle(z′i, μ′), where z′i and μ′ are the reduced-dimensional counterparts of vectors zi and A, respectively. The value cos angle(z′i, μ′) can in turn be approximated by cos angle(z′i, μ″), where μ″ is the average of the reduced-dimensional vectors of the query cluster. Provided that the vectors z′i have been precomputed for all 1≦i≦d, a ranked set of terms can be efficiently generated by means of a nearest-neighbor search based on μ″ over the collection of reduced-dimensional attribute vectors. As d is typically quite small, the cost of such a search is negligible compared to the cost of generating the cluster itself.
iii) If λ is the desired number of labels for the cluster, compute the λ-nearest-neighbors of μ″ in W, according to decreasing values of the cos angle measure.
Optionally, the values of cos angle themselves can be displayed to the user. Also optionally, approximate nearest neighbors can be used as produced using a SASH or other similarity search method.
FIG. 11 shows detailed functional blocks implemented in the computer 10. The computer 10 generally comprises a vector generation part 24, a SASH generation part 36, a confidence determination part 38 for creating the SCONF list, and a patch definition part 26. The vector generation part 24 executes vector generation using a keyword list or predetermined rules from the documents stored in a database 18, and stores generated document-keyword vectors in an appropriate storage area such as a memory or a database with adequate links or references to the corresponding documents. The SASH generation part 36 and the patch definition part 26 constitute the neighborhood patch generation part 34 according to the present invention.
The SASH generation part 36 constructs the SASH structure using the algorithm shown in FIG. 2 and the generated SASH structure is stored in the memory area 30 for the processing described hereinafter in detail. The SASH is made available to a confidence determination part 38 to compute confidence values such as CONF, SCONF, and RSCONF so as to generate a SCONF list according to the above described algorithm. The generated patch data and the confidence values are stored in a hard disk 32, as shown in FIG. 7.
The query vector generation part 46 accepts search conditions and query keywords and creates a corresponding query vector, and stores the generated query vector in an adequate memory area. The query may be of two types; one is to extract cluster structures already computed and stored in the database 32, and the other is to retrieve cluster structures that may not yet have been computed and stored. The user input query vector is first transmitted to a retrieval part 40. In the described embodiment, the retrieval part analyses the query type. If the query instructs the retrieval part 40 to retrieve cluster structures already computed and stored, the query is performed on the SASH structure stored in the memory area 30, and the queried patch generation part 44 transmits the retrieved data to the cluster estimation part 28. The cluster estimation part 28 invokes the patch data and associated SCONF list from the hard disk 32 upon receiving the retrieved data, and performs cluster estimation using intra-cluster confidences SCONF and RSCONF, and inter-cluster confidences CONF, respectively. The nodes used in the queried patch generation part 44 may be an arbitrarily selected node or a node retrieved by the user input query.
The derived cluster data are transmitted to a GUI data generation part 42 to construct data for graphically presenting the cluster graph structure on a display screen of a display part (not shown). Many display embodiments of the cluster graph structure are possible in the present invention. One representative embodiment is to align the clusters horizontally along with significant keywords (for example, the largest numeral values) included in the clusters while aligning the clusters vertically with estimated cluster size. When such display is provided on the display screen, the GUI data generation part 42 may sort the cluster data from the patch repository 32, and store the sorted data in an adequate memory area therein such as a display buffer (not shown), or elsewhere in the computer 10.
In an specific embodiment of the present invention, when the retrieval part 40 determines that the query instructs the retrieval of clusters that have not already been computed and stored, the retrieval part 40 invokes the SASH data 30, and retrieves the appropriate node vectors of the SASH by computing similarities between the document-keyword vectors and the query vectors. The retrieved data vectors are then themselves used as queries within the SASH data 30, to obtain a list of similar node vectors for every vector retrieved by the original query. Each list of node vectors is sent to the patch definition part 26 and thence to the confidence determination part 38 to produce patches, which may then be added to the patch repository 32. The retrieved patches are then transmitted to the cluster estimation part 28 together with their corresponding SCONF lists to estimate the cluster comprising nodes retrieved in the original query, and the computed cluster data are transmitted to the GUI data generation part 42 for graphical presentation of the queried results.
The GUI data generation part 42 may transmits sorted cluster data to a display device (not shown) directly connected to the computer 10 to display the searched cluster data on a display screen. Alternatively, when the system provides the searched results via the Internet using a browser software, the GUI data generation part 42 generates graphical data of the interrelation of the clusters in a format suitable to the browser software, such as an HTML format.
Next, the algorithm of Scenario A proceeds to the step S54 to create connections between the clusters having the association confidence values larger than or equal to the predetermined threshold γ. This data structure is shown in FIG. 16. These results of connection together with the cluster labels and corresponding keywords are provided graphically in the step S56 as a graphical representation such as that shown in FIG. 17. In FIG. 17, a portion of a cluster graph produced according to Scenario A (on an earlier run with γ=0.2) is shown in FIG. 17 for the case in which COV dimensional reduction was used. In the figure, cluster nodes (shown as ovals) are marked with a pair of numbers x/y, where x indicates the estimated size of the cluster and y indicates the associated sample patch size. Keyword labels are shown for each cluster—boxes have been drawn around those connected subsets of clusters sharing identical label sets (with perhaps minor differences in the label ordering). The cluster corresponding to the node marked 106/53 is shown in FIG. 17. This cluster is particularly interesting, as it consists of news articles in the intersection of two larger sets of clusters, involving canyons and their development and conservation issues on the one hand, and garbage dumps and landfills on the other.
iv) For all 0≦t≦h, for each element v□St, compute and store an approximate m-nearest-neighbor list (m-patch) NN(Rt, v, m) for that element, where m=φ(b).
(a) The choice of patch range delimiters a=25, b=120, and φ(k)=min {2 k, 150}.
(b) For document nearest-neighbor searches, the use of a time scaling factor μ′=1.25μ=1.25 φ(b)
No Dim- COV Dim-
TIME COSTS Reduction Reduction
SASH Performance Reduction Reduction
Estimated Cluster Size (low-high) Reduction Reduction
1600-7680  8 8
200-960  70 84
100-480  206 135
When a SASH structure is used for approximate similarity queries, the asymptotic time required by PatchCluster for a total clustering of data set S is in O(|S| log 2|S|+c2), where c is the number of clusters produced (typically much smaller than |S|). The former term covers the cost of producing profiles and ranking candidate query clusters according to their RSCONF values. The elimination of duplicate clusters and the generation of graph edges can all be performed in O(|S|+c log 2|S|+c2) time.
The bottleneck in the construction of a query cluster graph lies in the precomputation of nearest-neighbor patches. However, the clustering method does not require perfectly-accurate nearest-neighbor lists in order to detect approximate cluster boundaries and overlaps. It is far more cost effective to use one of the emerging techniques, such as the SASH, for fast generation of approximately-correct nearest-neighbor lists instead. For the L.A. Times news article data set using COV dimensional reduction, the SASH offers speedups of roughly 40 times over sequential search at almost 95% accuracy. The asymptotic complexity of precomputing patches is dominated by the total cost of the SASH operations, which is in O(|S| log 2|S|).
a computer processor configured to store documents in a database;
a cluster subsystem configured to convert documents in a database into vectors;
a construction subsystem configured to construct a hierarchical structure for the vectors by randomly assigning the vectors to nodes;
a comparison subsystem configured to generate for each one of a plurality documents in the database a patch comprising a list of the documents in the database most similar to the respective one of a plurality of documents in the database;
a confidence subsystem configured to generate self-confidence values for each of the generated patches such that the generated self-confidence values comprise the proportion of documents of a first one of the generated patches that are also in a second one of the generated patches,
the confidence subsystem being configured to use weighted self-confidence values to compute relative self-confidence values for each of the generated patches;
a cluster estimation subsystem configured to determine best size of a cluster of each of the generated patches, and
a graphical subsystem for displaying the generated patches.
2. The system of claim 1, wherein said system includes a confidence determination subsystem for computing inter-patch confidence values between said patches and intra-patch confidence values, and said cluster estimation subsystem being configured to select said patches depending on said inter-patch confidence values to represent clusters of said document-keyword vectors;
and wherein one of the patches is created for each of a plurality of elements in the hierarchical structure.
3. The system of claim 1, wherein said cluster estimation subsystem estimates sizes of said clusters depending on said intra-patch confidence values.
4. The system of claim 1, wherein said system further comprises a user query receiving subsystem for receiving said query and extracting data for information retrieval to generate a query vector, and an information retrieval subsystem for computing similarities between said document-keyword vectors and said query vector to select said document-keyword vectors.
5. The system of claim 4, wherein said best size of a cluster is estimated using said vectors with respect to said user query.
6. A graphical user interface system for graphically presenting estimated clusters on a display device in response to a user input query, said graphical user interface system comprising:
a computer for generating document-keyword vectors for said documents stored in said database and for estimating clusters of documents in response to said user input query; and
a display for displaying on screen said estimated clusters together with confidence relations between said clusters and hierarchical information pertaining to cluster size.
a neighborhood patch generation subsystem configured to generate groups of nodes having similarities as determined using a search structure, said neighborhood patch generation subsystem including a subsystem configured to generate a hierarchical structure upon said document-keyword vectors;
a patch defining subsystem configured to create patch relationships among said nodes with respect to a metric distance between nodes, wherein a size of one of the patches is based on a cost of patch boundary sharpness;
a cluster estimation subsystem configured to generate cluster data of said document-keyword vectors using said similarities of patches; and
a cluster defining subsystem configured to increase cluster size and reduce the number of clusters of a smallest size.
8. The system of claim 7, including a computer that comprises a confidence determination subsystem for computing inter-patch confidence values between said patches and intra-patch confidence values, said cluster estimation subsystem being configured to:
select said patches depending on said inter-patch confidence values to represent clusters of said document-keyword vectors;
determine a size of a best subset of each of the patches to serve as a cluster candidate;
estimate sizes of said clusters depending on said intra-patch confidence values; and
eliminate redundant cluster candidates.
US12062411 2002-12-19 2008-04-03 Generating a data structure for information retrieval Expired - Fee Related US8229900B2 (en)
JP2002-368276 2002-12-19
US10736273 US7428541B2 (en) 2002-12-19 2003-12-15 Computer system, method, and program product for generating a data structure for information retrieval, and an associated graphical user interface
US10736273 Division US7428541B2 (en) 2002-12-19 2003-12-15 Computer system, method, and program product for generating a data structure for information retrieval, and an associated graphical user interface
US20090006378A1 true US20090006378A1 (en) 2009-01-01
US8229900B2 true US8229900B2 (en) 2012-07-24
US7007019B2 (en) 1999-12-21 2006-02-28 Matsushita Electric Industrial Co., Ltd. Vector index preparing method, similar vector searching method, and apparatuses for the methods
US7428541B2 (en) 2008-09-23 grant