Patent Publication Number: US-2003231209-A1

Title: Data processing system

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
     [0001] This application is based upon and claims priority to European Patent Application No. 02 007 742.6, filed in the European Patent Office Apr. 5, 2002, and U.S. Provisional Patent Application No. 60/376,474, filed Apr. 29, 2002, the contents of both of which are incorporated herein by reference. 
    
    
     
       FIELD OF THE INVENTION  
       [0002] The present invention relates to data processing systems, and in particular, to a method for displaying information, a data processing system for displaying information, a computer program stored on a computer usable medium, and to a computer program directly loadable into an internal memory of a digital computer.  
       BACKGROUND OF THE INVENTION  
       [0003] A data processing system may be an individual computer comprising a processor, an internal memory, a storage, a display and an operating system to interconnect these elements such that they are interacting with each other. A data processing system may also be a communications network through which a number of computers may interconnect and communicate. The largest and best known computer communications network today is the Internet, a computer communications network based on worldwide data and telephone networks. The Internet is a network of networks, all available for the exchange of information. A combination of the Internet with interconnecting computers results in a web, the best known one is commonly referred to today as the worldwide web (“WEB”). The Internet interconnects every computer on the Internet with every other computer on the Internet. The computers connected to a network have various functions and purposes. Some of the interconnected computers are functioning as part of the network itself, i.e., controlling the routing and passage of data to and from various network nodes. Other interconnecting computers have files of information that are accessible by other computers connected to the network. Other computers are connected to the network by a user to obtain such files of information.  
       [0004] In large networks, such as the WEB, the amount of information available is substantial because of the number of sites on the WEB that provide information. In recent years, the amount of information available over the WEB has grown exponentially and will probably continue to do so for the foreseeable future. The challenge is how to find a specific item of information hidden in the enormous amount of information available. Thus, the interactive visualization of very large, hierarchically structured document collections or information collections, as well as a visualization of results of retrieval operations executed on such collections, has recently received much attention. With the ever-increasing number of documents and/or kinds of information stored on the WEB, or, alternatively, within corporate intranets, flat repositories containing the documents and/or information are increasingly and inevitably replaced by hierarchical structures for organizing documents and/or information into collections. As used herein, “flat repositories” typically comprise single-file applications that include a single, large address space. A “hierarchical structure” typically includes a plurality of data sources that link records together.  
       [0005] There are two basic approaches focusing on the interactive visualization of very large document collections available.  
       [0006] The first approach focuses on inter-documents similarity. However, this approach is only applicable for flat, unstructured repositories. A document corpus is represented by using maps or landscapes and a similarity of documents is shown by a proximity of these documents in these maps or landscapes. However, as already mentioned, this first basic approach is only applicable for flat repositories and unable for handling hierarchies.  
       [0007] The second basic approach focuses on navigation in hierarchically organized repositories such as documents classified according to a library classification scheme. Hierarchical structures may also be inferred from more heavily interlinked structures such as the WEB or computer networks.  
       [0008] U.S. Pat. No. 5,619,632 describes a two-dimensional tree browser which utilizes hyperbolic geometry to display an entire hierarchy on a two-dimensional display. The tree is laid out by using hyperbolic axes (which are infinite) and are then mapped to a two-dimensional unitary disk for display. Areas in a center of the disk are in focus and are clearly visible. However, areas in the proximity of the margin of the disk become infinitely small and are no longer discernible.  
       [0009] US 2001/0035885 A1 describes a graphical gateway to a computer network providing a text representation on any WEB or network directory on a two-dimensional surface. Various distinct categories included within the network directory are spread across the two-dimensional surface used as display screen and circled by polygon-shaped borders. The result is a “state” map created from a directory tree that has been mapped. A similarity or dissimilarity with respect to the content of two sites is expressed by a distance between these two sites.  
       [0010] All of the approaches presented above, are insufficient with respect to a representation of visualization of very large (up to millions of entities of information or documents) hierarchically structured information repositories.  
       SUMMARY OF THE INVENTION  
       [0011] It is an object of the present invention to provide a method and means for the easy handling of very large hierarchically structured information repositories.  
       [0012] This object is solved with a method for displaying information comprising a plurality of information elements on a display, the information being organized in a collection comprising a first subcollection and a second subcollection, the first subcollection comprising a first number of information elements of the plurality of information elements and the second subcollection comprising a second number of information elements of the plurality of information elements, the method comprising: (a) determining a first similarity between the first subcollection and the second subcollection; (b) determining first coordinates for the first subcollection and the second subcollection in accordance with the first similarity; (c) allocating a first area having first boundaries to the collection such that a first size of the first area is related to a number of information elements of the information; (d) allocating a second area having second boundaries to the first subcollection such that a second size of the second area is related to the first number; (e) allocating a third area to the second subcollection such that a third size of the third area is related to the second number; (f) positioning the second and third areas within the first boundaries of the first area in accordance with the first coordinates; (g) determining a second similarity between a first information element of the first number of information elements and a second information element of the first number of information elements; and (h) positioning the first information element and the second information element within the second boundaries in accordance with the second similarity.  
       [0013] Preferably the first number of information elements is related to the total number of information elements comprised in a first subcollection, comprised in any collection comprised in the first subcollection and/or is comprised in any further subcollection comprised in the first subcollection. So is the second number of information elements.  
       [0014] Advantageously, this method allows one to explore very large hierarchically structured repositories containing information elements. The hierarchical organization of the information and inter-information similarity is represented within a single, consistent visualization. Furthermore, according to the method of claim 1, a global and a local view of the information elements on the two-dimensional display is integrated into one seamless visualization.  
       [0015] Furthermore, the above object is solved by a data processing system for displaying information, comprising a display, and an operating system, wherein the information comprises a plurality of information elements, wherein the information is organized in a collection comprising a first subcollection and a second subcollection, the first subcollection comprising a first number of information elements of the plurality of information elements and the second subcollection comprising a second number of information elements of the plurality of information elements, the data processing system comprising: (a) means for determining a first similarity between the first subcollection and the second subcollection; (b) means for determining first coordinates for the first subcollection and the second subcollection in accordance with the first similarity; (c) means for allocating a first area having first boundaries to the collection such that a first size of the first area is related to a number of information elements of the information; (d) means for allocating a second area having second boundaries to the first subcollection such that a second size of the second area is related to the first number; (e) means for allocating a third area to the second subcollection such that a third size of the third area is related to the second number; (f) means for positioning the second and third areas within the first boundaries of the first area in accordance with the first coordinates; (g) means for determining a second similarity between a first information element of the first number of information elements and a second information element of the first number of information elements; and (h) means for positioning the first information element and the second information element within the second boundaries in accordance with the second similarity.  
       [0016] Advantageously, the data processing system according to the present invention is very stable.  
       [0017] The above object is also solved by a computer program product stored on a computer usable medium, comprising: (a) computer readable program means for causing a computer to display information on a display, the information being organized in a collection comprising a first subcollection and a second subcollection, the first subcollection comprising a first number of information elements of the plurality of information elements and the second subcollection comprising a second number of information elements of the plurality of information elements; (b) computer readable program means for causing the computer to determine a first similarity between the first subcollection and the second subcollection; (c) computer readable program means for causing the computer to determine first coordinates for the first subcollection and the second subcollection on the basis of the first similarity; (d) computer readable program means for causing the computer to allocate a first area having first boundaries to the collection such that a first size of the first area is related to a number of information elements of the information; (e) computer readable program means for causing the computer to allocate a second area having second boundaries to the first subcollection such that a second size of the second area is related to the first number; (f) computer readable program means for causing the computer to allocate a third area to the second subcollection such that a third size of the third area is related to the second number; (g) computer readable program means for causing the computer to position the second and third areas within the first boundaries of the first area on the basis of the first coordinates; (h) computer readable program means for causing the computer to calculate a second similarity between a first information element of the first number of information elements and a second information element of the first number of information elements; and (i) computer readable program means for causing the computer to position the first information element and the second information element within the second boundaries in accordance with the second similarity.  
       [0018] Furthermore, the above object is solved by a computer program product directly loadable into an internal memory of a digital computer with the features of claim. 
     
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
     [0019] For the purpose of illustrating the invention, there is shown in the drawings a form which is presently preferred, it being understood, however, that the invention is not limited to the precise arrangement shown, in which:  
     [0020]FIG. 1 is an exemplary embodiment of the data processing system according to the present invention;  
     [0021]FIG. 2 shows a further exemplary embodiment of the data processing system according to the present invention;  
     [0022]FIG. 3 shows a flow chart of an exemplary embodiment of the method for displaying information according to the present invention;  
     [0023]FIG. 4 shows a flow chart concerning an exemplary embodiment of steps S 4  and S 10  of FIG. 3;  
     [0024]FIG. 5 shows a flow chart concerning an exemplary embodiment of steps S 5  and S 11  of FIG. 3;  
     [0025]FIG. 6 shows a flow chart concerning an exemplary embodiment of step S 6  of FIG. 3;  
     [0026]FIG. 7 shows a Voronoi diagram for further explaining step S 6  of FIG. 3;  
     [0027]FIG. 8 shows a further Voronoi diagram for further explaining step S 6  of FIG. 3;  
     [0028]FIG. 9 shows an exemplary embodiment of an image displayed on a display according to the present invention;  
     [0029]FIG. 10 shows another exemplary embodiment of an image displayed on the display according to the present invention;  
     [0030]FIG. 11 shows another exemplary embodiment of an image displayed on the display according to the present invention; and  
     [0031]FIG. 12 shows yet another exemplary embodiment of an image displayed on the display according to the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS OF THE PRESENT INVENTION  
     [0032]FIG. 1 shows a first exemplary embodiment of the data processing system for displaying information according to the present invention. Preferably, the information includes information elements. Information elements are any kind of structured or unstructured information carrying entities for which a similarity to other information elements can be computed. Examples of information elements are pictures, audio information, customer records, personal records, database records, tactile information or biometric information. In a preferred embodiment of the present invention, information elements are documents.  
     [0033] For the following explanation, it is assumed that the documents are organized in a hierarchy of collections and subcollections. Such a hierarchy is referred to herein as a “collection hierarchy.” Documents, subcollections and collections can be members of more than one parent collection. However, cycles are, preferably, explicitly disallowed. Such a structure is called a directed acyclic graph. In such a directed acyclic graph, no path starts and ends at the same vertex and edges of such a graph are ordered pairs of vertices. As used herein, a graph is referred to as a list of vertices of a graph where each vertex has an edge from it to the next vertex. A vertex is also often referred to as a node. An example for such a collection hierarchy is a classification scheme such as IPC. For example, such a taxonomy is usually maintained manually by an editorial staff. However, the collection hierarchy could also be generated or extracted semi-automatically or automatically.  
     [0034] Documents are assumed to have significant textual content, which may be extracted if necessary with respective tools. Documents are typically electronics, such as ADOBE PDF documents, HTML documents or MICROSOFT WORD documents, but may also comprise spread sheets, tables or graphics.  
     [0035] Referring now to the drawing figures, in which like numerals refer to like elements, there is shown in FIG. 1 a display  1  that displays a collection  2  comprising three subcollections,  3 ,  4  and  5 . The collection  2  is displayed by means of a first polygon having a first area corresponding to the number of documents, information elements, subcollections and collections comprised therein. This first area is subdivided by means of bisectors  6 ,  7  and  8  in the areas of the subcollection  3 ,  4  and  5 , respectively, and are shown centroids  9 ,  10  and  11 . An exemplary embodiment of a method for generating such an image on display  1  will be described below with reference to FIGS.  3  to  8 . Further, examples of images visualizing collections will be described with reference to FIGS.  9  to  12 .  
     [0036] The display  1  is connected to a calculating section  12 . The calculating section  12  preferably comprises an operating system  13  and a processing section  14 . Furthermore, communication connection between the processing section  14 , the operating system  13  and the display  1  is provided. The processing section  14  comprises means  15  for determining a first similarity between a first subcollection and a second subcollection.  
     [0037] The means  15  for determining the first similarity between the first subcollection and the second subcollection comprises means  16  for calculating a first centroid for a first subcollection and a second centroid for the second subcollection, means  17  for determining the first similarity between the first subcollection and the second subcollection by calculating a third similarity and means  18  for calculating the first coordinates.  
     [0038] Furthermore, processing section  19  comprises means for determining first coordinates for the first subcollection and the second subcollection. The means  19  for determining first coordinates for the first subcollection and the second subcollection comprise means  20  for determining a fourth force, means  21  for determining a third force, means  22  for determining a second force and means  23  for generating second coordinates.  
     [0039] Furthermore, the processing section  14  comprises means for positioning the first information element and the second information element. As shown in FIG. 1, reference number  25  refers to means for controlling the display  1 . Reference number  26  refers to means for allocating a third area to the subcollection.  
     [0040] The processing section  14  furthermore comprises means  27  for allocating a second area having second boundaries to the first subcollection and means  28  for allocating a first area having first boundaries to the collection.  
     [0041] Furthermore, the processing section  14  comprises means  29  for calculating a second similarity between a first information element and a second information element. The means  29  for calculating a second similarity between a first information element and a second information element comprise means  30  for calculating the third coordinates, means  31  for generating force coordinates, means  32  for determining a sixth force, means  33  for determining a seventh force  33  and means  34  for determining an eight force.  
     [0042] The processing section  14  furthermore comprises means  35  for positioning the second and third areas. The means  35  for positioning the second and third areas comprises means  36  for arranging, means  37  for determining which of the first and second weights is smaller and means  38  for determining a center.  
     [0043] In an alternative exemplary embodiment, all or some elements of the processing section  14  may be realized as computer readable program means, for example, as modules of program written in a specific programming language. It is also possible, to use programmable chips such as FPGAs or EPLDs, e.g. the FPGAs/EPLDs made by ALTERA, for the elements comprised in the processing section  14 .  
     [0044]FIG. 2 shows a further exemplary embodiment of the data processing system for displaying information according to the present invention. In FIG. 2, reference number  50  designates a server which is connected to a network  51  which is connected to a client  52 . Such a structure is usually referred to as client-server architecture. The server  50  comprises a hierarchical document repository  53  which is connected to a generator  54  which is connected to a geometry database  55 . The hierarchical document repository  53  and the geometry database  55  are connected to a server section  58 . The server  50  transmits a geometry generated by the server section  58  via network  51  to an API  56  at the client&#39;s side of the network  51 . On the client&#39;s site, there is further provided a geometry cache  57 . The client  52  and the server  50  exchange queries via network  51 . If the first embodiment of FIG. 1 is realized in a client server architecture as shown in FIG. 1, all elements of the processing section  14  are preferably in the server  50  whereas the display, preferably, would be on the client&#39;s site.  
     [0045]FIG. 3 shows an exemplary embodiment of the method for displaying information according to the present invention. Reference number  100  designates an argument. The argument  100  comprises a collection. The collection can comprise a plurality of collections, subcollections and information elements, such as documents. Each of the subcollections and collections comprised in the collection may comprise further collections, subcollections or information elements.  
     [0046] In the following, a preferred embodiment of the method for displaying information according to the present invention is described with a collection, comprising a first subcollection and a second subcollection, the collection comprising a plurality of information elements. The first subcollection comprises a first number of information elements and the second subcollection comprises a second number of information elements.  
     [0047] The numbering of the subcollections and information elements is used for distinguishing the subcollections and information elements from each other and is not intended as a limitation with respect to the number of subcollections or information elements.  
     [0048] Continuing with reference to FIG. 3, in step S 1  a process called geometry generation starts with reading the argument. Then the process preferably proceeds to step S 2 , where child collections of the collection are read from a knowledge repository  101 . In the present example, the first and the second subcollections are child-collections of the collection. As noted above, generally a collection may also contain documents. In such a case, an additional artificial subcollection is generated and the documents are placed in this additional artificial subcollection. Then, from step S 2 , the method proceeds to step S 3 .  
     [0049] In step S 3 , there is a determination made whether there are child collections present or not. In case the question in S 3  is answered with YES (i.e. there are child collections), the method continues to step S 4 . In step S 4  a force-directed placement (“FDP”) is carried out for the child collections. The FDP is an iterative method for mapping a set of high-dimensional vectors to a low-dimensional space while preserving a high-dimensional relation as far as possible. The algorithm calculates force vectors from similarities between respective elements. In the present example, in step S 4 , force-vectors are calculated from the similarities between a first centroid of the first subcollection and a second centroid of the second subcollection. A centroid is a respective center of gravity of the respective subcollection. In step S 4 , there are generated normalized coordinates for the centroids of the child collections, that is in the present example, normalized coordinates for the centroids of the first and second collections. Step S 4  is described with further detail with reference to FIG. 4.  
     [0050] After step S 4 , the method proceeds to step S 5  where a geomap procedure is carried out for the centroids of the child collections. In the present example, the geomap procedure is carried out for the centroids of the first and second subcollections. The purpose of the geomap procedure is to efficiently use an area allocated to the respective collection or respective subcollection. In the geomap procedure, areas are assigned to the child collections and the coordinates calculated for the centroids of the child collections are inscribed into these areas. Preferably these areas are polygons. With respect to the present example, a first area is assigned to the first subcollection and a second area is assigned to the second subcollection. A size of the first area corresponds to a number of information elements comprised in the first subcollection and a size of the second area corresponds to a number of information elements comprised in the second subcollection. In case the first subcollection comprises a further collection and a further subcollection, a total amount of information elements comprised in the first subcollection is calculated and is the basis for a size of the first area. The geomap procedure outputs new positions for the centroids of the child collections. Hence, with reference to the present example, the geomap procedure calculates new positions within the first and second areas for the centroid of the first and second subcollections. The geomap procedure carried in S 5  is described below in more detail, with reference to FIG. 5.  
     [0051] After step S 5 , the method proceeds to step S 6 , where an area division is carried for the centroid of child collections. With reference to the present example, an area division is carried out for the centroid of the first and second collection. In other words, in step S 6 , all assigned areas comprising the respective information elements and centroids with the positions determined in step S 5  are arranged such that the size of the respective area corresponds to the number of information elements comprised in the area, and such that all areas are inscribed into one “parent-area” assigned to the collection. With respect to the present example, the first and second areas are inscribed into a third area which was allocated to the collection. Step S 6  is described below in more detail with respect to FIG. 6.  
     [0052] After S 6 , the method proceeds to S 7  where the results of S 6  are saved in a geometry database  102 . Then, the method continues to step S 8  where the geometry generation is called again for the child collections. Thus, from step S 8 , the method recursively continues to step S 1  which is carried out in the same way as before. The method continues then to step S 2  which is carried out in the same way as before. And, in step S 3 , the query is carried out, whether there are child collections present or not. In case there are child collections, the method continues to steps S 4  and step S 4  to S 8  are carried out as described above. In case there are no child-collections present, the method continues to step S 9 .  
     [0053] In step S 9 , the information elements comprised in the collection are gathered from the knowledge repository  101 . With respect to the present example, the information elements comprised in the first and second subcollections are gathered from the knowledge repository  101 . Then, the method proceeds to step  
     [0054] In step S 10 , an FDP is carried out for the information elements. This is carried out in the same way as described with reference to step S 4 , except that the FDP in step S 10  is carried out for the information elements and not for the centroids of child collections, as in step S 4 . The FDP is described below in more detail with reference to FIG. 4. Then, the method proceeds to step S 11 .  
     [0055] In step S 11 , the geomap procedure is carried out for calculating coordinates and respective areas for the information elements. This is carried out in the same way as described above with reference to step S 5 , except that the geomap procedure in step S 11  is carried out for the information elements. The geomap procedure is described below in more detail with reference to FIG. 5. Then, the method proceeds to step S 12 .  
     [0056] In step S 12 , a geometry of the information elements is stored in the geometry database  102 . With respect to the present example, coordinates of the information elements of first and second subcollections are stored in the geometry data base. Then, the method proceeds to step S 13  where the method ends.  
     [0057] The force-directed placement is now described in more detail with reference to FIG. 4.  
     [0058] As already indicated with reference to FIG. 3, the method steps of FIG. 4 are performed in step S 4  of FIG. 3 and in step S 10  of FIG. 3. Since, in step S 4 , the FDP is carried out for centroids of child collections and, in step S 10 , for information elements, the term “object” is used to generally refer to the centroids and the information elements. In other words, if the method steps of FIG. 4 carried for step S 4  of FIG. 3, the objects are centroids of child collections and if the steps of FIG. 4 are carried out for step S 10  of FIG. 3, the objects are information elements.  
     [0059] Steps S 20  to S 24  of FIG. 4 are an iterative method for mapping a set of high-dimensional vectors to a low-dimensional space, while preserving the high-dimensional relations as far as possible. These method steps determine force vectors from similarities between objects. These force vectors and further, custom-defined vectors influence positions i.e. coordinates of points representing the object at each iteration, for example, in this message.  
     [0060] The FDP starts in step S 20  with reading the argument, namely a list of the respective objects. Then, the method continues to step S 21  where necessary values are precalculated. This will be described with further detail in the following.  
     [0061] The high-dimensional vector representation allows comparison of a pair of objects by computing a similarity between them. Here, a cosine similarity metric is used. If D i  and D j  are documents to be compared, L is the dimensionality of the high-dimensional space and x iq  is the q&#39;th component of the term vector which represents the object D i . The cosine similarity of two objects D i , D j  is given by:  
         sim        (       D   i     ,     D   j       )       =           ∑     k   =   1     L          (       x     i   ,   k            x     j   ,   k         )             ∑     k   =   1     L            x     i   ,   k     2            ∑     k   =   1     L          x     j   ,   k     2               .                   
 
     [0062] In the above equation, x i  and x j  are feature vectors where vector components correspond to different features. Apart from the cosine similarity, other similarity coefficients can be used, for example, Dice and Jaccard.  
     [0063] In a preferred embodiment, all inter-object similarity values, i.e. all similarities between all objects, are precalculated and subsequently stored in a similarity matrix. With respect to the present example, in step S 4  of FIG. 3, a similarity value is calculated for the centroids of the first and second subcollections. With respect to step S 10  of FIG. 3 according to the present example, similarity values are calculated for the information elements. Then, the method continues to step S 23 .  
     [0064] In step S 22 , objects are initially placed randomly in a low-dimensional space and are then moved based on forces between the objects, wherein the forces are determined on the basis of the similarities between the objects. A low-dimensional space corresponds to the space of the display, i.e., the low-dimensional space is 1 dimensional for a 1 dimensional display, 2 dimensional for a 2 dimensional display and 3 dimensional for a 3 dimensional display, etc. The forces preferably may respectively comprise an attractive component and a repulsive component. In the following, this is described for an exemplary embodiment for a two-dimensional space wherein forces between two respective objects are respectively calculated.  
     [0065] The force force(D i  D j ) between two objects has three components: An attractive component proportional to the similarity sim(D i , D j ) d  between the two objects, a repulsive component 1/(dist(D i , D j )) inversely proportional to a two-dimensional distance between these two objects and a weak gravitational component grav:  
         force                   (       D   i     ,     D   j       )       =       sim                     (       D   i     ,     D   j       )     d       -     w     dist                   (       D   i     ,     D   j       )         +     grav   .                     
 
     [0066] The first component, namely the attractive component pulls objects with similar content together. d&gt;=1 is a discriminator which is adjusted to characteristics of the similarity matrix calculated in step S 21 . With the discriminator d, a separation of a layout of the elements on the display can be improved significantly. The factor w is 1 in the case of placing documents (S 10 ) and in the case of centroids (S 4 ) proportional to the weight of the centroid, e.g. to the numbers of documents recursively contained in the corresponding collection.  
     [0067] The second component, i.e. the repulsive component pushes two objects apart and prevents them from coming too close. The third component, namely the gravitational component is a weak but constant gravitational force which provides cohesion to the object set by ensuring that even very dissimilar objects attract each other once they become very distant.  
     [0068] New coordinates of objects are calculated by letting one object interact with other objects from the list of objects followed by a subsequent averaging of the results over all interactions. For example, D i .x, a new x-coordinate of object D i , is calculated with the following equation. The other coordinates are calculated accordingly.  
           D   i     ·   x     =         1     N   -   1              ∑       j   =   1     ,     j   ≠   i       N          force                   (       D   i     ,     D   j       )     *       D   j     ·   x           +       (     1   -     force        (       D   i     ,     D   j       )         )     *       D   i     ·     x   .                         
 
     [0069] Thus, at each iteration a new position is computed for every object and the iteration continues until a termination condition is satisfied. A commonly used termination condition of mechanical stress is computationally intensive. Therefore, a more light-weight, adaptive condition is used which can be summarized as: an execution terminates when object positions are stabilized sufficiently or when a maximum number of iterations is reached.  
     [0070] Assuming a set of N objects, for the calculation of an influence of every object with respect to every other object, each object would have to interact with M=N−1 other objects. This results in a quadratic time complexity for each iteration. However, if M may be held constant, a linear execution time (per iteration) can advantageously be reached. To do this, a method described in Chalmers (1996).  A Linear Iteration Time Layout Algorithm for Visualizing High - Dimensional Data. In Proc. Visualization &#39; 96, pages 127-132, San Francisco, Calif. (1996).  IEEE Computer Society.  http://www.dcs.gla.ac.uk/{tilde over ()}matthew/papers/vis96.pdf which uses stochastic sampling, is used where each object maintains two small sets of constant size. A first set, which may also be called the random set, is filled with random elements during every iteration. And a second set, which may also be called neighbor set, maintains a list of similar, neighboring objects. In each iteration, members of the neighbor set are compared to new samples in the random set and are replaced by objects which are more similar. The combination of this processing combination with the invention method allows a very stable and fast calculation. Hence, a calculation time of the invention method is minimized and use of computing resources for the data processing system according to the present invention are minimized.  
     [0071] For performance reasons, the invention method preferably does not use any velocities or viscosities. As a result of the above described random sampling, a certain amount of jitter is introduced. This jitter can cause a small inaccuracy of the computed position of the respective objects. However, this jitter proved to be useful for avoiding local minima. In other words, the sampling described above introduces little computing overhead, but requires the same number or fewer iterations than a method without sampling in order to reach a stable layout.  
     [0072] Once a layout satisfying the termination condition has been calculated with the sampling procedure, a number of iterations are performed by using the process without sampling. The number of iterations without sampling is in relation to an amount of interactions performed by the sampling procedure. The effect is that the calculation time is not significantly increased. The performance of a few iterations with the process without sampling almost eliminates the layout inaccuracy introduced by the sampling, without compromising the time complexity.  
     [0073] By step S 22  (FIG. 4), centroids having a smaller weight are placed close to the center of the surrounding boundary polygon. Centroids having a higher weight are placed in a ring midway between the center of the polygon and its boundary. Thus, advantageously, a correspondence between the weight of the centroid and the size of the allocated area is achieved.  
     [0074] Once the force-directed placement (FDP) of all objects is finished in step  22  and all respective coordinates are calculated for the object, the method continues to step S 23  where the coordinates calculated in step S 22  are normalized. After the normalization step S 23 , the method continues to step S 24  where the FDP process ends.  
     [0075] The geomap procedure carried out in step S 5  of FIG. 3 for centroids of child collections and in step S 11  of FIG. 3 for information elements is now described in further detail with reference to FIG. 5. As mentioned with respect to FIG. 4, the term “objects” is used to refer to both information elements and centroids of child collections. In step S 30 , where the geomap procedure begins, the argument of the procedure, namely the list of objects and the respective areas belonging to these objects are read. Then, in a precalculation step S 31 , area vertices are transformed into the same normalized space as the FDP coordinates. Then, the method continues to step S 32  where new positions are calculated such that each object is assigned a position which falls within the boundaries defined by the vertices. After new positions are calculated by moving each existent position along the way from the center of the respective area as performed in step S 32 , the method of FIG. 5 proceeds to step S 33  where it ends.  
     [0076] Referring now to FIG. 6, the area division carried out in accordance with step S 6  of FIG. 3 is described in more detail. The task performed in the area division may be described as follows: considering one level of the collection hierarchy in the repository, there are N points p i  of known weight w i  representing the objects on this level in the current collection. As mentioned with respect to FIG. 4, the objects may be collections, subcollections, information elements or documents. These points p i  are placed within a given polygonal area A which is read in step S 40 . The polygonal area A represents the area of the collection. The task performed in steps S 41  and S 42  is to find a partition of area A into N subareas A i  which satisfies the following condition:  
     p i εA i    
     [0077] A i  being convex  
     [0078] A i ˜W i , and  
     [0079] A i  having a size not smaller than a preset minimum value.  
     [0080] With respect to the example used with reference to FIG. 3, steps S 41  and S 42  in FIG. 5 would be for the calculation of a partition of the area of the collection into the first area for the first collection at the second area for the second collection period. In step S 11  of FIG. 3, steps S 41  and S 42  would be for the calculation of partitions of the first and the second areas of the first and second subcollections in respective areas corresponding to the information elements respectively comprised in the first and second subcollections.  
     [0081] The determination of area subdivisions may be accomplished by using e.g. an additively weighted power Voronoi diagram. The additively weighted Voronoi diagram is known for example from Ukabi, A. Boots, B. Sugihara K., and Chew S. N.(2000)  Spatial Tessellations: Concepts and Applications of Voronoi diagrams . Wiley, Second Edition. According to the Voronoi diagram, an area of each polygon assigned to each object is related to the weight of the respective object. For example, an object p 0  with a weight of 20 is allocated a larger area than an object p 2  with a weight of 15, and they are both assigned an area larger than an area of an object p 1  having a weight of 10.  
     [0082] For two points p and p i , the additively weighted power distance is given by:  
       d   pw ( p, p   i   ; w   i )=∥ {right arrow over (p)}−{right arrow over (p)}   i ∥ 2   −w   i .  (equation A)  
     [0083] This equation may used for determining a position of a bisector b (p, p i ) perpendicular to the interconnecting line between p and p i , the bisector forming an edge of the polygon around p.  
     [0084] However, the additively weighted power distance calculated in accordance with the above equation has the disadvantage that if the weight difference between two objects is very large and these objects are close to each other, the object having smaller weight may be placed on the wrong site of the bisector and hence outside its own area. Thus, in order to ensure that each objects p i  lies within its own area A i , according to the present invention, each w i  is scaled with a global factor f such that all bisectors b (p i , p j ) are placed between p i  and p j :  
       d   pw ( p, p   i   ; w   i )=∥{right arrow over (p)}−{right arrow over (p)} i ∥ 2   −fw   i .  (equation B)  
     [0085] Instead of equation B, a number of other distance equations may be used, such as the multiplicatively weighted Voronoi distance, or the additively weighted Voronoi distance. Advantageously, equation B leads to polygons with straight boundaries which are easy to display. The factor f of the above equation is defined as maximum scale factor which can be uniformly applied to all weights without causing a bisector to overrun. The factor f is calculated in accordance with the above modified equation in step S 41 . However, since the outer polygon boundaries are fixed and only the inner boundaries (bisectors) can slide, the introduction of the scale factor f may cause that an area A i  is no longer exactly related to its weight w i  corresponding to the total number of information elements within this area. This may occur when relatively light objects are placed close to the margin of the polygon or are placed in between a number of other objects. Such a case is shown in FIG. 7.  
     [0086] In FIG. 7, there is shown a collection having an area  120  which defines outer boundaries of the area of the collection. The area  120  has a form of a polygon. Within the boundaries of area  120 , there is a subcollection  121  having a centroid p 2 . The centroid p 2  is the geometrical point of gravity of the subcollection  121 . The subcollection  121  has a weight of 20 and thus should have an area within the area of the collection  120  corresponding to the weight of 20. Reference number  122  designates a collection within the area of the collection  120 . The centroid, i.e. the graphical center of gravity of the collection  122  is p 3 . The weight of the collection  122  is 30. Thus, an area corresponding to 30 should be assigned to the collection  122 . Reference number  123  designates a further subcollection having a weight of 50 and having the centroid p 0 . Reference number  124  designates a further subcollection having a weight of 10. By following the above known equation (equation (A)), as can be clearly seen from FIG. 7, the area of the subcollection  124  has approximately the same size as the area of the subcollection of the area  123 . However, according to the weight of the subcollection  124  and the subcollection  123 , the area of the subcollection  124  should only be one fifth of the area of the subcollection  123 .  
     [0087] In addition to that, as shown in FIG. 7, the centroid p 1  is located on the bisector b (p 0 , p 1 ) which forms the boundary between the subcollection  124  and the subcollection  123 . According to one aspect of the present invention, by using the scale factor f (equation B), a centroid being located too close to the bisector, or on the bisector as shown in FIG. 7, is avoided.  
     [0088] Advantageously, by step S 22  of FIG. 4, centroids having a smaller weight are placed close to the center of the surrounding boundary polygon. Objects having a higher weight are placed in a ring midway between the center of the polygon and its boundary.  
     [0089]FIG. 8 shows the result of placing objects with a smaller weight close to the center of the surrounding boundary polygon while putting heavier objects in a ring midway between the center of the boundary polygon and the center and the use of equation B. In the polygon of the area of the collection  150 , there is a subcollection  151  with a centroid p 1  having a weight of 10, a subcollection  152  having a weight of 200 and a centroid p 2 , a subcollection  153  having a weight of 10 and a centroid p 3 , a subcollection  154  having a weight of 50 and a centroid p 4 , a subcollection  155  having a weight of 10 and a centroid p 5 , and a subcollection  156  having a weight of 1000 and a centroid p 0 .  
     [0090] As can be clearly taken from FIG. 8, subcollections  156 ,  152  and  154  having a higher weight are placed close to the boundaries of the collection  150 . In contrast, the subcollections  151 ,  153  and  155  having a significant lighter weight are placed close to the center of the area of the collection  150 . In addition, a relation of the size of the respective subcollection and the weight is kept. As shown in FIG. 8, the area of the subcollection  156  is significantly bigger than, for example, the area of the subcollection  155 . Furthermore and advantageously, the centroids of the respective subcollection  151  to  156  are always within the boundaries of the respective areas, and there is a sufficient distance between the respective centroid and its boundary.  
     [0091] After the calculation step S 42 , the method of FIG. 6 proceeds to step S 43  and ends.  
     [0092]FIG. 9 shows an image or layout as displayed on the display  1  (FIG. 1) according to the present invention. As shown in FIG. 9, the objects, documents or information elements are displayed in the form of a “galaxy.” Single objects are visualized as stars with similar objects forming clusters of stars. Collection or subcollections are visualized as polygons bounding clusters and stars, resembling the boundaries of constellations in the night sky. Collections featuring similar content are placed close to each other as far as the hierarchical structure of the repository allows. Empty areas remain where objects are hidden, for example, due to access restrictions for a particular user, and resemble dark nebulas as found quite frequently within real galaxies. As can be seen in the upper left corner of FIG. 9, there is provided an overview over the whole night sky. In the main polygon shown in FIG. 9 which has approximately the form of a circle, there are collections and subcollections relating to “Bayern,” “Berlin,” “Hessen,” “Brandenburg,” “Nordrhein-Westfalen,” “Neue Bundesländer” and “Thüringen.” The image shown in FIG. 9 was derived from a collection of approximately 100,000 articles in the German language which were published during the years 1997 to 2000 in the Süddeutsche Zeitung, which is a German daily newspaper. These articles have been classified thematically by the newspaper editorial staff into around 9,000 collections and subcollections up to 15 levels deep. In FIG. 9, the constellation boundaries and labels are shown for the topmost level of the hierarchy.  
     [0093] As obvious from FIG. 9, approximately 50% of the articles relate to “Bayern” which is the state of Germany where the Süddeutsche Zeitung is published. The number of articles relating to other states of Germany is significantly less. The galaxy itself is complete in the sense that it displays all the stars, i.e. objects or information elements it contains, down to the bottommost level of the hierarchy. However, as shown in FIG. 9, no individual stars are discernable in the figures. The clusters forming the galaxy consist of thousands of stars which, in accordance with a metaphor of a telescope, can only be resolved individually at a higher magnification.  
     [0094] In the following, the telescope metaphor is described in more detail. For example, a user is interested in further information on a specific cluster of stars, and the user points his telescope to the bright cluster of stars just underneath the “Bayern.” Then, with an increased magnification, the user sees this cluster in more detail as shown in FIG. 10.  
     [0095] As shown in FIG. 10, this very bright cluster relates to the city of Munich which is the city where the Süddeutsche Zeitung is published. Within this cluster, revealed by the increased magnification, further collections and subcollections are now visible. For example, within “München,” there are visible subcollections or collections relating to “Wirtschaftsraum München” which can be translated as “the economic area of Munich,” “Kriminalität in München” which can be translated into “criminality in Munich,” “Kultur in München” which can be translated into “culture in Munich,” “Verkehrswesen in München,” which can be translated into “traffic in Munich” and “Sozialstruktur in München,” which can be translated into “social structure in Munich.” 
     [0096] If the user pinpoints his telescope to the cluster “Kultur in München,” the user may see an image such as the one in FIG. 11. In FIG. 11, there are big subcollections relating to “Ausstellungen in München” which may be translated into “exhibitions in Munich,” “Festspiele in München” which can be translated into “Festivals in Munich,” “Kunstszene in München,” which can be translated into “Art in Munich” and “Musicszene in München,” which can be translated into “the music scene of Munich.” As can further be seen from FIG. 11, the subcollections having a smaller weight are arranged in the center of these polygons and are not explicitly discernable with this magnification. In case the user is interested in the subcollections in the center of FIG. 11, the user has to pinpoint the telescope on this area. The zooming performed by the metaphoric telescope is performed by a zooming option on the display one of FIG. 1 which may be activated by use of a zooming button which can be activated by the user by means of a cursor device.  
     [0097]FIG. 12 shows an image where the user has selected a very high resolution which shows the individual information elements or documents which are labeled by the respective meta information comprising for example author, publication date and title.  
     [0098] With exemplary embodiments of the present invention, it is possible to visualize very large (millions of entities), such as hierarchically structured document repositories (scalability). Furthermore, advantageously, both the hierarchical organization of the documents and the inter-document similarity may be presented within a single, consistent visualization (hierarchy plus similarity). In addition, both a global and a local view of the information space are integrated into one seamless visualization (focus plus context). Also, advantageously, with, for example, the “telescope,” simple, intuitive navigation, exploration, and manipulation facilities are provided (interaction). In addition to that, with the exemplary embodiments of the present invention it is possible to support a single, consistent view of the document space for all users, regardless of the access rights of each individual user, thus providing a common frame of reference for all parties, and providing a united view.  
     [0099] The design of the visualization metaphor in accordance with exemplary embodiments of the present invention, advantageously may allow the visualization to display a maximum number of document properties and relationships without requiring the user to take action. For example, it is possible to show an age of documents with different colors or different shapes in the visualization. Thus, advantageously, exemplary embodiments of the present invention may allow a location of documents without specifying a query, by simply browsing the information space. Furthermore, the exemplary embodiments of the present invention may feature a number of additional information channels to which users may map document properties of their choice, again replacing explicit queries with navigation.  
     [0100] As a paramount advantage, exemplary embodiments of the present invention may facilitate memorability, in the sense of enabling users to visually recall locations within the information space, without having to remember long document names or lengthy path information. Advantageously, according to exemplary embodiments of the present invention, the visualization remains basically unchanged at a global level even if changes occur to the underlying document repository on a local level. Also, according to exemplary embodiments of the present invention it is possible to present the same visualization to different users in collaborative work environments, where each user might have different access rights. If every user were presented with a different visualization of the same information space, communication between users could not be based on the same frame of reference, strongly reducing its practical usability.