System and method of determining and searching for patterns in a large database

[0002] The present invention generally relates to techniques for querying large databases and, more particularly, to query techniques which employ a user/computer interactive process including visual feedback in order to find the best responses to a given query.

[0003] In recent years, large databases have become very common because of the ability to store large amounts of information with the current advances in hardware technology. Such databases are often queried by users in order to find specific patterns of behavior. Finding the closest matching object is important for a number of applications. Examples include similarity searches in geometric databases, multimedia databases, and data mining applications such as fraud detection, information retrieval, among numerous other domains. Many of these domains contain applications in which the dimensionality of the representation is very high. For example, a typical feature extraction operation on an image will result in hundreds of dimensions. By way of another example, a data set which is inherently dimensionally high may be a demographic database in which the dimensions comprise information such as the name, age, salary, and other features which characterize a person.

[0004] Similarity retrieval problems are reasonably well solved for low dimensional applications for which efficient index structures have been proposed. A wide variety of multidimensional indexes have been proposed which work well for low dimensional data. For a comprehensive overview, see, e.g., V. Gaede et al., “Multidimensional Access Methods,” ACM Computing Surveys, vol. 30, no. 2, pp. 170-231, 1998, the disclosure of which is incorporated by reference herein. These structures can support a wide range of queries such as point queries, range queries, or similarity queries to a predefined target.

[0005] However, many empirical studies have shown that traditional indexing methods fail in high dimensional spaces, see, e.g., K. Beyer et al., “When is Nearest Neighbors Meaningful?,” Proceedings of the ICDT Conference, 1999; K. -I. Lin et al., “The TV-tree: An Index Structure for High Dimensional Data,” VLDB Journal, vol. 3, no. 4, pp. 517-542, 1992; N. Katayama et al., “The SR-Tree: An Index Structure for High Dimensional Nearest Neighbor Queries,” Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 369-380, 1997; R. Weber et al., “A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces,” VLDB, pp. 194-205, 1998; and S. Berchtold et al., “The X-Tree: An Index Structure for High-Dimensional Data,” Proceedings of the International Conference on Very Large Databases (VLDB'96), Bombay, India, pp. 28-39, 1996, the disclosures of which are incorporated by reference herein. In such cases, almost the entire index is accessed by a single query. In fact, the use of most indexes may be less efficient and/or effective than a sequential scan because of the simplicity of the latter. Furthermore, as recent results in the above-referenced K. Beyer et al. article show, it may often be difficult to determine the meaningfulness of the nearest neighbor for a query point. In fact, in many cases, it has been shown that the distance measurements to the target are not very meaningful with the use of traditional distance functions.

[0006] The present invention provides techniques for finding query responses from database queries using an interactive process between a user (e.g., a person entering a query to a database) and a computer system (e.g., a computing system upon which the database resides or which has access to the database). The interactive process comprises providing the user with one or more visual perspectives as feedback on the distribution of points in the database. These visual perspectives may be considered by the user in order for the user to provide feedback to the computer system. The computer system may then use the user-provided feedback to determine the best response to the query.

[0007] In one illustrative aspect of the invention, a method for resolving queries in large databases is provided which uses an interactive process. More specifically, in response to a user query to a database, the method comprises providing a user with different views of the data which the user can use in order to vote on the effectiveness of different sets of points which match the query the user entered. These responses may then be aggregated to determine the true sets of responses corresponding to the original user intent.

[0008] The conventional fully-automated systems discussed above are incomplete in their characterization of the data in terms of a single best distance function. However, the present invention realizes that different projections can provide different views of the data, all of which may be quite informative to a human in understanding the relationship between a query point and the rest of the data in a database. Furthermore, the present invention realizes that it is often easier for a human to make judgments on the viability of clusters of different shapes and sizes in a given view, or whether a view yields any useful information at all. That is, a computer cannot match the visual insight and intuition of a human in distinguishing useful patterns from the data. On the other hand, a human needs computational support in analyzing large volumes of high dimensional data in order to find the relevant characteristics of the data which relate the “query point” to the database. It is to be appreciated that, in one example, the query point may refer to a data record specified by a user that is used to locate patterns in a database that are closely related to the data record.

[0009] Accordingly, in accordance with an illustrative embodiment of the present invention, a computer provides an iterative visual feedback loop in which carefully chosen views of the data are presented to a user to illustrate the different clusters in the data. Once these views have been determined, then kernel density estimation may be used to provide a visual profile of the distribution of the data. These visual profiles are used to determine the clusters.

[0010] It is evident to those skilled in the art that the above method may be used in order to determine either the closest patterns to a given query point or the different clusters in the data. This can be done by finding the patterns close to multiple query points which are chosen randomly. These different patterns form the clusters in the data.

[0011] These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.

[0012] FIG. 1 is a block diagram illustrating a hardware implementation suitable for employing interactive query response methodologies according to an embodiment of the present invention;

[0013] FIG. 2 is a flow diagram illustrating an overall interactive query response methodology according to an embodiment of the present invention;

[0014] FIG. 3 is a flow diagram illustrating a process for providing a user with feedback according to an embodiment of the present invention;

[0015] FIG. 4 is a flow diagram illustrating a process used to obtain and aggregate user feedback to determine meaningful sets of responses to queries according to an embodiment of the present invention;

[0016] FIG. 5 is a flow diagram illustrating how user response in a single view can be used as an implicit determination of a set of votes of a user according to an embodiment of the present invention;

[0017] FIG. 6 is a flow diagram illustrating how user responses are used to create final responses to a given query according to an embodiment of the present invention;

[0018] FIG. 7A is diagram illustrating an example of a density estimate of a set of data points according to an embodiment of the present invention;

[0019] FIG. 7B is diagram illustrating a set of data points from which the density estimate of FIG. 7A has been constructed according to an embodiment of the present invention; and

[0020] FIG. 8 is a diagram illustrating an example of a user specification of a hyperplane which separates different density regions according to an embodiment of the present invention.

[0021] In order to describe illustrative techniques of the present invention, some technical background and definitions are now provided. An illustrative approach employed by the present invention is based on the use of kernel density estimation. As is known, kernel density estimation is a technique for creating visual profiles of data. Kernel density estimation is described in T. Zhang et al., “Fast Density Estimation Using CF-Kernel for Very Large Databases,” Proceedings of the ACM SIGKDD Conference, 1999, the disclosure of which is incorporated by reference herein.

[0022] The idea in kernel density estimation is to provide a continuous estimate of the density of some data at a given point. There are two kinds of methods of kernel density estimation: (i) parametric; and (ii) non-parametric. In parametric methods, it is assumed that the kernel function 𝑓(x) belongs to some parametric family of distributions. The parameters of this distribution are estimated using the data set at hand. In non-parametric methods, nothing is assumed about the nature of the data distribution. Rather, the value of the density at a given point is estimated as the sum of the smoothed values of kernel functions K′_h(.) associated with each point in the data set. Each kernel function is associated with a kernel width h which determines the level of smoothing created by the function. The kernel estimation based on n data points and kernel function K′_h(.) is defined as follows: $f\left(x\right)=\frac{1}{n}·\sum _{i=1}^n{K}_h^{\prime }\left(x-X_i\right)$

[0023] Thus, each discrete point X_iin the data set is replaced by a continuous function K′_hand has a variance which is determined by the smoothing parameter h. An example of such a distribution is a gaussian kernel with width h.

[0024] Further, $K_h^{\prime }\left(x-X_i\right)=\frac{1}{h\sqrt{2\pi }}·e^{-{\left(\frac{x-X_i}{h}\right)}^2}.$

[0025] Here, e is the exponential constant with a value of approximately 2.718 and π is the mathematical constant with a value of approximately 3.14159. The overall effect of kernel density estimation is to convert a discrete data set into a continuous density estimate by replacing each data point in the data set with a smoothed bump, whose width is determined by h. The density distribution at a given coordinate is equal to the sum of the contributions of all the bumps represented by the data points. The result is a continuous distribution in which the random artifacts are suppressed and the density behavior provides a global overview of the densely, as well as sparsely, populated regions of the data. The estimation error depends upon the kernel width h which is chosen in a data-driven manner. For the d-dimensional case, the kernel function is chosen to be the product of d identical kernels K′_h(.), each with its own smoothing parameter h(i). An example of a density estimate for a discrete set of data points will be described later.

[0026] Referring initially to FIG. 1, a block diagram illustrates a hardware implementation suitable for employing interactive query response methodologies according to an embodiment of the present invention. It is assumed that a user 10 and a computer system 20 interact in order to resolve queries effectively. The computer system 20, as shown, may comprise a processor 22, memory 24 and I/O devices 26.

[0027] It is to be appreciated that the term “processor” as used herein is intended to include any processing device, such as, for example, one that includes a CPU (central processing unit) and/or other processing circuitry. The term “memory” as used herein is intended to include memory associated with a processor or CPU, such as, for example, RAM, ROM, a fixed memory device (e.g., hard disk drive), a removable memory device (e.g., diskette), other disk storage devices, flash memory, etc. In addition, the term “input/output devices” or “I/O devices” as used herein is intended to include, for example, one or more input devices (e.g., keyboard, mouse, etc.) for inputting data to the processing unit, and/or one or more output devices (e.g., CRT display, printer, etc.) for presenting results associated with the processing unit. It is also to be understood that “processor” may refer to more than one processing device and that various elements associated with a processing device may be shared by other processing devices.

[0028] Accordingly, software components (e.g., one or more programs) including instructions or code for performing the interactive query response methodologies of the invention, as described herein, may be stored in one or more of the associated memory devices (e.g., ROM, fixed or removable memory) as an article of manufacture and, when ready to be utilized, loaded in part or in whole (e.g., into RAM) and executed by the processor.

[0029] More specifically, a query is entered by the user 10 into the computer system 20. The query comprises a target object. The user query may be entered using one or more of the I/O devices 26 (e.g., keyboard, mouse). The computer then uses data in the subject database stored in memory 24 (e.g., a data storage device) to perform an interactive process of presenting the user with the relationship between the stored data and the target object associated with the query. The presentation in the form of visual feedback from the computer system to the user may be made on one of more of the I/O devices 26 (e.g., a display screen) of the computer system. The processor 22 performs the necessary computations and other operations. The user enters feedback based on the data presented by the computer which is then stored in memory. The user feedback may be provided using one or more of the I/O devices 26 (e.g., keyboard, mouse). The user feedback is then used by the computer to determine the best response for the entered query.

[0030] It is to be understood that while FIG. 1 illustrates a single computer system being interacted with by the user, the invention is not so limited. That is, the database that is being queried may reside on one or more computer systems other than the computer system which receives the user's query. Also, query processing may be performed on more than one computer system.

[0031] Furthermore, the user may enter his query at one computer, e.g., client, which is remotely coupled to another computer, e.g., server, which performs all or a portion of the operations associated with the methodologies of the invention. Again, the database may be resident on the server or accessible by the server. The user then views results generated by the server on his client computer. The computers may be coupled via a network, e.g., Internet, private network, a local area network, or some other suitable network.

[0032] A detailed description of the interaction between the user 10 and the computer 20 will now be provided in the context of FIG. 2. Specifically, FIG. 2 is a flow diagram illustrating an overall interactive query response methodology according to an embodiment of the present invention. As shown, the overall method begins at block 200. In step 210, the user enters the target object, i.e., query, into the computer. In step 215, a counter is created for each data point in the database and is initialized to zero. The counters are successively updated corresponding to the user interaction in step 230.

[0033] In steps 220 through 240, the target object is used in conjunction with an interactive process to find the object in the database that is of most interest to the user. In step 220, the data obtained from the original query by the computer is analyzed and used to provide the user with a visual overview of the key aspects of the data, i.e., visual feedback. A detailed description of this process is provided below in the context of FIG. 3. In step 230, the user interacts with the visual feedback and enters preferences into the computer. These preferences comprise the user's votes as to the data points which are the best matches to the target. A detailed description of this process is provided below in the context of FIG. 4. The counters are also updated in step 230. In step 240, the computer asks the user for feedback on whether the process should terminate. It is to be appreciated that the user has the flexibility to make a decision based on any criteria he sees fit. For example, if one particular data point has many votes, he may choose to terminate. Accordingly, the user answers “yes” or “no.” If the user answers “no,” then the system returns to step 220. Typically, the response to step 240 is based on whether a sufficient number of 2-dimensional projections have been explored. If the user answers “yes” in step 240, then in step 250, all the entries made by the user are compiled together in order to determine the best search results. This process is described in detail below in the context of FIG. 5. The overall process ends at block 260.

[0034] It is evident to those skilled in the art that the inventive technique can be used for finding not just related patterns to a given query point, but also interesting patterns and clusters in the data. This can be achieved by picking multiple query points by randomly sampling the data and applying the process of FIG. 2. By this process, the clusters containing different data points will be effectively discovered.

[0035] Referring now to FIG. 3, a flow diagram illustrates a process for providing a user with feedback according to an embodiment of the present invention. It is to be understood that this process corresponds to step 220 in FIG. 2. More specifically, FIG. 3 illustrates a process used by the computer to generate a profile in response to the original query. In step 310, the computer picks two of the dimensions from the database at random. In step 320, a 2-dimensional database is created from the original database by using only the data in these two dimensions.

[0036] In step 330, density distributions of the data associated with the 2-dimensional database are created using the process of kernel density estimation which is generally explained above and otherwise well-known in the art. Assume that for each 2-dimensional point (a, b) in the database, the value of the density is equal to f(a, b). Then, the computer creates a 3-dimensional plot which illustrates the density of the data along with the different values of a and b. An example of such a density plot is illustrated in FIG. 7A. The query point 701 is illustrated in the same plot. Note that the peaks in this plot correspond to the densely populated regions, whereas the valleys in the plot correspond to the sparsely populated regions. This visual representation is provided to the user in step 335. FIG. 7B illustrates the set of data points which correspond to the plot in FIG. 7A. Note that the process of step 310 need not be implemented in a manner such that the dimensions from the database are chosen only at random. For example, the distribution of the data around the query point may be used to determine the nearest neighbors. The process ends at block 340.

[0037] Referring to FIG. 4, a flow diagram illustrates a process used to obtain and aggregate user feedback to determine meaningful sets of responses to queries according to an embodiment of the present invention. It is to be understood that this process corresponds to step 230 in FIG. 2. The feedback obtained from the user is valuable in determining the user's intentions in finding the most closely matching data point to the query. The process begins at block 400. In step 410, the density profile created from the method of FIG. 3 is viewed by the user. In step 420, the user then specifies a hyperplane which separates the different density regions in the profile from one another. An example of a hyperplane 801 which separates different density regions is illustrated in FIG. 8. Specification of the hyperplane represents the user's preference.

[0038] Next, in step 430, all the points which lie in the same density region as the query point 701 are found. In the example of FIG. 8, this includes all the points in the data whose density profile lies above the hyperplane 801. Note that in order to specify the hyperplane, the user preferably need only input the density value corresponding to the value of the density at which the hyperplane should be constructed (i.e., the value on the vertical axis). A detailed description of this step is provided below in the context of FIG. 5. The computer considers these points to be the points that the user is “voting” on as the points the user feels are the most likely matches to his query. The counters for these points are respectively incremented by one, in step 440. The process ends at block 450. Thus, the process of determining the user votes is an indirect one with the user specifying a simple density value which separates clusters of points in the density profile.

[0039] FIG. 5 is a flow diagram illustrating how user response in a single view (i.e., a single density profile shown to the user) can be used as an implicit determination of a set of votes of a user according to an embodiment of the present invention. It is to be understood that this process corresponds to step 430 in FIG. 4. More specifically, FIG. 5 illustrates how the hyperplane specified by the user may be used in order to determine the set of points which he has voted on. The process begins in block 500. In step 510, the contour of intersection between the peak containing the query point and the user-specified hyperplane is determined. For example, in FIG. 8, this contour corresponds to the contour of intersection between the peak visible above the hyperplane and the hyperplane itself. Once this contour has been determined, the set of data points which lie within this contour are determined in step 520. These are the points which are considered most relevant to the query and are reported, in step 530, as the set of user votes. The process ends at block 540.

[0040] It is to be appreciated that, as shown and discussed in the context of FIG. 2, an iterative loop exists between steps 220, 230 and 240. Thus, if the user determines that the process should not terminate, the method continues again with step 220, where the computer provides the user with another view of the data based on the hyperplane specified in the previous iteration of step 230. The user then may specify, another hyperplane so as to provide a set of votes on points in the second view. The interactive process of specifying a hyperplane and generation of an additional view based thereon may iterate as long as the user desires. Thus, the processes shown in FIGS. 3, 4 and 5 iterate as many times as the overall loop in FIG. 2 is iterated. As a result, votes over multiple hyperplanes must be aggregated in order to determine a final response. This aggregation process is shown in FIG. 6.

[0041] FIG. 6 is a flow diagram illustrating how user responses are used to create final responses to a given query according to an embodiment of the present invention. It is to be understood that this process corresponds to step 250 in FIG. 2. More specifically, FIG. 6 illustrates a process of user vote compilation. The overall effect of this step is to aggregate the user responses in order to find the best match to the query point. It is to be understood that the phrase “user responses” here refers to the votes associated with the user picking points (by specifying hyperplanes) in multiple regions of the data during the iterative process involving steps 220, 230 and 240 of FIG. 2. The process begins at block 600. In step 610, the votes made by the user for each of the data points are counted. In step 620, the data points which have the largest number of votes are determined. These data points are returned as the best responses to the user query, in step 630. The process ends at block 640.

[0042] Advantageously, in accordance with the present invention, techniques are presented for providing the user with different kinds of views of a large database and using these views in order to make the best decisions about the matching points to a query. The overall responses of the user are aggregated in order to find the best set of matches. These responses are used in order to find the best match for a given query. The invention provides responses to user queries which are significantly more effective than simple matches based on pre-defined distance functions.

[0043] Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be affected therein by one skilled in the art without departing from the scope or spirit of the invention.