Data processing: measuring – calibrating – or testing – Measurement system in a specific environment – Mechanical measurement system
Reexamination Certificate
2002-05-02
2003-12-02
Barlow, John (Department: 2863)
Data processing: measuring, calibrating, or testing
Measurement system in a specific environment
Mechanical measurement system
Reexamination Certificate
active
06658358
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a method and system for visualizing data and data objects. More specifically, the present invention pertains to a method and system for computing forces on data objects in physics-based visualization techniques.
BACKGROUND ART
The analysis of data objects can be facilitated by displaying them in multi-dimensional space. By displaying data objects in this manner, it is easier to visualize the relationships between the data objects while preserving the essential information in the data.
One technique known in the art for computing the layout of data objects in multi-dimensional space is generally referred to as a physics-based visualization system. Data objects are positioned in “space” according to how strongly the data objects are related. The relationship between data objects is characterized according to their “similarity” or “confidence level” and their “support.” Similarity (confidence level) and support are best defined by way of a market basket example: if 85 percent of the customers who bought a printer also bought paper, and 10 percent of all customers bought both a printer and paper, then similarity is 85 percent and support is 10 percent. Note that similarity is directional; that is, although 85 percent of the customers who bought a printer also bought paper, it is not necessarily true that 85 percent of the customers who bought paper also bought a printer.
In multi-dimensional space, the distance between a pair of data objects indicates their degree of support; the closer the objects, the greater their degree of support. The similarity between data objects is represented by a “link” or an “edge” between the objects. A link or edge is essentially a line between two data objects that have a degree of similarity that is greater than zero. The color of the link (edge) can be used to indicate the degree of similarity. Also, the link may include an arrow to show the direction of the association.
Physics-based visualization systems execute in a known manner to place data objects such that the distance between any two data objects is indicative of the degree of support between those two objects. Much as stars and planets exert forces on each other in astrophysical space, data objects in visualization space can be thought of as exerting “forces” on each other. In essence, these forces should be proportionate with the degree of support between each data object and the other data objects in the system. Data objects with higher degrees of support should exert higher forces on each other and thus should be placed closer together.
Thus, in a physics-based visualization system, one of the key procedures for determining the final placement of data objects is to calculate the forces applied to each data object by the other data objects in the system. To calculate the force for every data object, the simplistic approach is to compute the force for every possible pairing of data objects, and sum the results. However, this would result in a run time on the order of N
2
for a system of N data objects. Thus, the simplistic approach is computationally very expensive and can take a long time to complete, and so it is desirable to find a more efficient way of calculating the forces applied to each data object.
In astrophysics, techniques known in the art can be used to accelerate the force computations. One such technique, referred to herein as “Barnes-Hut,” is described in J. E. Barnes and P. Hut (1986), “A Hierarchical O(N log N) Force-Calculation Algorithm,” Nature, 324(6270) (pages 446-449), hereby incorporated by reference. Instead of a run time on the order of N
2
, the Barnes-Hut technique reduces run time to the order of N log N.
Techniques such as Barnes-Hut generally represent objects that are far away as a single, heavier object. For example, to calculate the force of a distant galaxy on a single star, the force is calculated considering the galaxy as a whole, rather than by calculating the force exerted by each individual star in the galaxy and summing the results.
In astrophysics, the force between objects is a function of the distance between the objects, and so the approximations introduced by Barnes-Hut can be readily applied. However, in physics-based visualization systems, the force between data objects is a function not only of the distance between objects (their degree of support), but also the similarity between objects. Because forces in a physics-based visualization system are dependent on both the distance between data objects and the similarity of the data objects, applying a computationally efficient force computation technique such as Barnes-Hut is problematic. This problem is illustrated by Prior Art FIG.
1
.
Prior Art
FIG. 1
shows data objects
10
,
12
,
14
,
16
and
18
represented in two-dimensional space. Here, similarity between data objects is represented as a normalized value between zero and one, with a value of zero indicating that there is no similarity and a value of one indicating the maximum degree of similarity. The object pairs
10
and
12
,
14
and
16
, and
16
and
18
each have a degree of similarity greater than (not equal to) zero, while the other object pairs (e.g.,
10
and
14
,
10
and
16
, and so on) have a degree of similarity equal to zero. In
FIG. 1
, a line (e.g., a link or edge) between data objects indicates that they are similar to some degree, while the absence of a line indicates a similarity of zero.
When calculating the force exerted on data object
12
using the Barnes-Hut technique, for example, data objects
14
and
16
can be represented as a single object, because these objects are far enough away from data object
12
while relatively close to each other. When calculating the force exerted on data object
18
, it is desirable to employ the same optimization; that is, it is desirable to represent data objects
14
and
16
as a single object. However, because in physics-based visualization systems the force between data objects is a function not only of the distance between objects but also the similarity between objects, the force exerted by data objects
14
and
16
on data object
12
are different from the force exerted by data objects
14
and
16
on data object
18
. Thus, application of computationally efficient force computation techniques such as Barnes-Hut to physics-based visualization systems is problematic because techniques such as Barnes-Hut implement optimizations that are dependent only on the distance between objects while physics-based visualization systems are dependent on more than one parameter (e.g., distance and similarity).
Accordingly, what is needed is a method and/or system for accelerating calculations of force in physics-based visualization systems. What is also needed is a method and/or system that can satisfy this need and that can account for the similarity between data objects. The present invention provides a novel solution to these needs.
DISCLOSURE OF THE INVENTION
A method and system thereof for computing forces on data objects in a physics-based visualization system are described. First forces exerted on a data object by other data objects in the plurality are determined without considering the similarity between data objects. Second forces exerted on the data object by a portion of the other data objects, each data object in the portion having a degree of similarity to the data object, are determined considering the similarity between data objects. The first forces are adjusted using the second forces to determine a net force on the data object. The net force is thus determined without having to consider similarity between all data objects in the plurality.
REFERENCES:
patent: 5493919 (1996-02-01), Frank et al.
patent: 5596511 (1997-01-01), Toyoda et al.
patent: 5625575 (1997-04-01), Goyal et al.
patent: 06-231115 (1994-08-01), None
Hao, M; Dayal, U; Hsu,M; Baker, J; D'Eletto, R;“A Java-Based Visual Mining Infrastructure And Applications”; Proceedings IEEE Symposium On Information Visualization; Oct. 24-29, 19
Dayal Umeshwar
Gross Markus
Hao Ming C.
Holenstein Thomas
Hsu Meichun
Hewlett--Packard Development Company, L.P.
Washburn Douglas N
LandOfFree
Method and system for computing forces on data objects for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for computing forces on data objects for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for computing forces on data objects for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136679