System for visualizing massive web transaction data sets without overlapping

[0001] The present disclosure relates generally to system analysis of web transaction data sets and more particularly to a system for visualizing massive web transaction data sets without overlapping.

[0002] The rapid increase in electronic transactions has led to the availability of massive volumes of web transaction data. Web transaction data generally refers to transaction data residing on World Wide Web (WWW) servers. WWW generally refers to all the resources and users on the Internet (a worldwide system of computer networks) using the Hypertext Transfer Protocol (HTTP).

[0003] Business research efforts have always focused on how to turn raw web transaction data into usable information. For example, by exploring web data access behavior, business system analysts may be able to find and retain their most valuable users and evolve their best service strategies.

[0004] A web transaction typically starts with a user clicking on a web page to request a web service or information. The request is passed through one or more web servers which respond to the user accordingly with the median server response being measured in milliseconds. In order to provide faster service, web system analysts need to analyze web transaction data and try to balance the workload among their web servers to prevent network bottlenecks. When the web transaction data set is fairly large, one problem faced by system analysts is how to visually analyze and correlate the performance of millions of web transactions.

[0005] A common technique for visualizing web access is a two-dimensional scatter plot. The scatter plot technique positions pairs of web clients and server response time on separate axes to visualize their relationships. However, visualizing massive web transaction data sets using a scatter plot is too restrictive. The scatter plot is typically capable of only showing a maximum of 10-20 data items without overlapping. When the number of data items is in the thousands, the scatter plot display becomes too cluttered. In such case, the scatter plot may exhibit too much overlapping which occurs due to high-density data, as generally shown in FIG. 7. Furthermore, scatter plots do not support user interactions such as zoom in/out, drill-down, etc. Scatter plots are not scalable when fairly large volumes of web transaction data are involved. Moreover, no real-time visual filtering is possible with scatter plots, i.e. data pre-processing is always needed when analyzing massive volumes of web transaction data.

[0006] The present invention is generally directed to a web transaction visualization system comprising at least one web transaction visualization (WTV) processor adapted to automatically extract massive amounts of web transaction data from at least one data source for visual classification based on at least one aggregate transaction metric and to display the classified web transaction data interactively in three dimensions without overlapping.

[0007] These and other aspects of the present invention will become apparent from a review of the accompanying drawings and the following detailed description of the preferred embodiments of the present invention.

[0017] Hereinafter, some preferred embodiments of the present invention will be described in detail with reference to the related drawings of FIGS. 1-8. Additional embodiments, features and/or advantages of the invention will become apparent from the ensuing description or may be learned by practicing the invention.

[0018] The drawings are not to scale with like numerals referring to like features throughout both the drawings and the description.

[0019] The following description includes the best mode presently contemplated for carrying out the invention. This description is not to be taken in a limiting sense, but is made merely for the purpose of describing the general principles of the invention.

[0020] Turning to FIG. 1, a system for visualizing massive web transaction data sets without overlapping, generally referred to by a reference numeral 9, preferably comprises a web transaction visualization (WTV) processor 10 adapted to extract web transaction data from e-service engines and/or data warehouses, such as e-service engine 16 and/or data warehouse 18, respectively, for processing, and to interact with users, such as user 12, for display of user input and/or processed web transaction data via a GUI (graphical user interface) 14. WTV processor 10 is preferably configured using Java®-based multi-threaded parallelism and adapted to process the extracted web transaction data in stages using a plurality of operatively coupled modules, such as, for example, data mapping and similarity computation module 20, data item correlation module 22, and grouping and encapsulation module 24, as generally illustrated in FIG. 2.

[0021] Data mapping and similarity computation (DMSC) module 20 is preferably programmed to map data items (e.g., URLs of web clients, web servers, etc.), extracted from web transaction data set(s) residing on e-service engine 16 and/or data warehouse 18, onto a spherical surface using standard spherical data mapping algorithms. More details on spherical data mapping algorithms may be found, for example, in Proceedings of the IEEE Information Visualization 1997, Arizona, entitled “Visualizing Information on a Sphere”, by M. H. Gross, T. C. Sprenger, and J. Finger. Specifically, the mapped data items are represented as vertices on a spherical surface, as generally depicted in the ‘initial placement’ portion of FIG. 4. The initial positions of the mapped data items (vertices) may be disposed at random on the spherical surface. To avoid random pre-grouping of initially mapped data items, DMSC module 20 is preferably adapted to distribute mapped data items in equally spaced positions based on standard Poisson Disc Sampling (PDS) approximation algorithms. More details on PDS approximation algorithms may be found, for example, in “Principles of Digital Image Synthesis”, by A. S. Glassner, published by Morgan Kaufman, San Francisco, 1995.

[0022] A web transaction data set may be in the form of a web log record containing information on the URLs (uniform resource locators) of web clients accessing a plurality of web servers, the URLs of the web servers being accessed, and the median server response time for each server. For example, M₁ may be designated as the median server response time for a web server W which is involved in a web transaction T₁ with a web client (data item) I_i; M₂ may be designated as the median server response time for web server W which is involved in a web transaction T₂ with a web client (data item) I₂; M₃ may be designated as the median server response time for web server W which is involved in a web transaction T₃ with a web client (data item) I₃ etc.

[0023] In accordance with a preferred embodiment of the present invention, DMSC module 20 (FIG. 2) is programmed to compute the similarity (correlation) between web clients (data items I_i, I_j) involved in web transactions with respective web servers using an aggregate transaction metric such as, for example, median server response time (M_i), and the following linear similarity mapping:
S_ij=min(1.0,μ/2|M_i−M_j|)
wherein

• • [0024] S_ij is defined as the similarity (correlation) between data items I_i and I_j;
  • [0025] ½ is a preferred scaling factor obtained from experimentation;
  • [0026] M_i is the median server response time for web transaction T_i involving data item I_i;
  • [0027] M_j is the median server response time for web transaction T_j involving data item I_j; and
  • [0028] μ is the average difference in median server response time associated with data items I_i
  • [0029] and I_j, and web transactions T_i and T_j, respectively.
    For example, the average difference in median server response time associated with data items I₁, I₂, and I₃, and web transactions T₁, T₂, and T₃, respectively, may be defined as follows:
    μ=[|M₁−M₂|+|M₁−M₃|+|M₂−M₃|]/3.

[0030] The computed similarity values may be arranged in a n×n similarity matrix {S_ij}, where i=[1, . . . , n], and j=[1, . . . , n]. To avoid large statistical deviations, DMSC module 20 may be programmed to store only similarity values which are less than a pre-set δ value, otherwise a zero value would be returned. For example, the value of δ may be set at about 20% of the maximum median server response time (M_max) in a web transaction data set. A person skilled in the art would readily recognize that other δ values and/or other scaling factors may be utilized in connection with the above-described similarity mapping, provided such other δ values and/or scaling factors, respectively, do not depart from the intended purpose, spirit and/or scope of the present invention.

[0031] In accordance with another preferred embodiment of the present invention, data item correlation (DIC) module 22 (FIG. 2) is adapted to correlate the computed similarity values for the spherically mapped data items with corresponding relative distances between data items on a three-dimensional graph (FIG. 4) in a series of computational iterations. Specifically, DIC module 22 is programmed to “connect” the spherically mapped data items with “springs” using a standard physics-based mass-spring engine whereby the stiffness of the connecting “springs” is defined by similarity matrix {S_ij}. The stiffness value of each connecting spring is correlated with a corresponding relative distance between two data items on a three-dimensional graph (FIG. 4). After many iterations the graph is “relaxed”, i.e. reaches a local minimum which corresponds, essentially, to moving similar data items close to each other and pushing dissimilar data items away from each other, as generally illustrated in FIG. 4. More details on physics-based mass-spring engine techniques may be found, for example, in T. C. Sprenger, M. H. Gross, “Ivory—An Object Oriented Framework for Physics-Based Information Visualization in Java”, IEEE InfoVis98, North Carolina.

[0032] In accordance with yet another preferred embodiment of the present invention, grouping and encapsulation (GE) module 24 (FIG. 2) uses K-means type algorithms to group the relaxed data item set into different categories according to similarity value such as, for example, “fast”, “medium”, or “slow”, and encapsulate (wrap) sub-groups of highly related (similar) data items with generally transparent ellipsoidal surfaces to produce the three-dimensional grouped graph layout of FIG. 5. The number of similar data items in a sub-group (ellipsoid) and their relative positions control the shape of the ellipsoidal surface. Grouping analysis is generally based on partitioning a collection of data points into a number of sub-groups, where the objects (data points) inside a sub-group show a certain degree of closeness or similarity. The K-means algorithm assigns each data point to one and only one of the sub-groups with a degree of membership equal to one, assuming well defined boundaries between the sub-groups. When boundaries between sub-groups are not well defined, a number of known grouping algorithms based on fuzzy extension of the least-square error criterion may be utilized. More details on K-means type algorithms may be found, for example, in J. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations”, The 5^th Berkeley symposium on mathematical statistics and probability, Berkeley, Calif., 1967.

[0033] To prevent two closely spaced sub-groups (ellipsoids) from being placed on top of each other, GE module 24 is preferably programmed to utilize a sub-group positioning algorithm which continuously computes relative distances on the spherical surface between respective sub-groups and automatically pushes away neighboring sub-groups (ellipsoids) with relative spacing on that spherical surface being less than a pre-set threshold to prevent overlapping (FIGS. 5-6). A person skilled in the art would recognize that the lack of overlapping offers significant advantages to the system analyst over the use of conventional web transaction visualization methods such as, for example, two-dimensional scatter plots which are normally employed for low density (100-200 data items) data sets. As the data set becomes fairly large, the standard scatter plot quickly becomes cluttered and difficult to visualize due to the presence of too much overlapping, as generally depicted in FIG. 7.

[0034] To improve visualization, color may be used to represent the degree of similarity between data items in respective sub-groups in accordance with another embodiment of the present invention. For example, the data items (schematically shown as cube-like structures in FIGS. 5-6, and 8) in each sub-group (ellipsoid) classified under the “low” category of FIG. 6 may be colored in gradual variations of green depending on similarity. Similarly, data items in sub-groups classified under the “medium” category of FIG. 6 may be colored in gradual variations of blue, while data items in sub-groups classified under the “high” category of FIG. 6 may be colored in gradual variations of burgundy. Also, data items in sub-groups classified under the “exceptional” category of FIG. 6 may be shown, for example, in solid black, etc. Other color configurations may be used, provided there is no deviation from the intended spirit and scope of the present invention.

[0035] In accordance with another embodiment of the present invention, WTV processor 10 preferably includes a multiple view link (MVL) module 26, and an automatic alarm system (AAS) module 28, as generally depicted in FIG. 3.

[0036] MVL module 26 is programmed to provide the three dimensional grouped graph layout with multiple linked views for interactive visual data analysis. In many instances, the web transaction data that needs to be visually analyzed consists of multiple relationships. With multiple linked views one can easily visualize correlations among the various data items. Whenever multiples views are presented, items across all the views are linked. For example, the data items in sub-group (ellipsoid) 32 (FIG. 6) are linked to a tree table 30 (FIG. 6) positioned at the left side of the graph allowing the user to easily look up web transaction information on each sub-group of data items, such as the average response time for sub-group 32 as well as the median response time for each client (data item) in that sub-group. As generally shown in FIG. 6, the table tree view may include vertical and/or horizontal selection sliders, such as selection sliders 31 and 33, respectively when the number of items exceeds what can be viewed on a single screen. The user can select one or more sub-group(s) and zoom in/out on the data items in each selected sub-group for system analysis, as needed.

[0037] A person skilled in the art should also recognize that the interactive three-dimensional graphical data item visualization display of the present invention, as generally shown in FIG. 6, is a significant improvement over traditional non-interactive two-dimensional scatter plot visualization layouts. For example, the user cannot select, or zoom in/out on any portion of the data displayed on the scatter plot of FIG. 7.

[0038] AAS module 28 is programmed to automatically notify the user in a generally conspicuous visual manner whenever exceptional data items or sub-group(s) of data items are detected. Exceptional data items may refer to web clients associated with very short or unusually long median server response time(s). The visual notification may be in the form of a flashing or highlighted sub-group (ellipsoid) of data items, or data item, or the exceptional data items or sub-group(s) of data items may be circled in a contrasting color. For example, data item 35 (FIG. 8) is shown as being the slowest client of the web transaction data set of FIG. 8 with a distinctive pop-up description dialog box 35a presenting pertinent information such as URL, median response time, and number of web transactions optionally displayed proximate thereto. Similarly, data item 36 (FIG. 8) is shown as being the fastest client of the web transaction data set of FIG. 8 with associated dialog box 36a displaying pertinent information such as URL, median response time, and number of web transactions displayed proximate thereto. Other ways of notifying the user of exceptional events may be used, such as by audible means, provided there is no deviation from the intended purpose of the present invention.

[0039] Certain embodiments of the present invention may be made, sold, and or used in the form of a computer usable medium (such as a hard drive, compact disk (CD) and/or other suitable recording medium) which includes computer readable program code tangibly embodied therein for controlling the above-described process of visualizing massive web transaction data sets without overlapping, as generally illustrated in FIGS. 1-6, 8.

[0040] Such an embodied computer readable program code may include program modules or software routines for mapping data items extracted from at least one data source onto a spherical surface and computing the similarity values between the spherically mapped data items based on at least one aggregate transaction metric such as, for example, median server response time (M), for correlating the computed similarity values for the spherically mapped data items with corresponding relative distances between data items on a three-dimensional graph in a series of computational iterations until the data item set is relaxed, and for grouping the relaxed data item set into categories according to similarity value and encapsulating sub-groups of substantially related data items for web transaction visualization on the three-dimensional graph. Moreover, the embodied program code may also include routines for continuously computing relative distances between the sub-groups and pushing away neighboring sub-groups with relative spacing being less than a pre-set threshold value to eliminate overlapping, for providing the three-dimensional graph with multiple linked views for interactive visual data analysis, and for detecting exceptional data items and/or exceptional sub-groups of data items and providing corresponding notification to the user, as generally shown in FIG. 3, 6, and 8.

[0041] A person skilled in the art would undoubtedly appreciate that the above-described novel interactive web transaction visualization system may be used with massive web transaction data set(s) with the overlapping problem of prior setups being eliminated in its entirety. In accordance with one exemplary embodiment of the present invention, the interactive web transaction visualization system of the present invention has been used to classify a data set containing over 35,000 web transactions with thousands of web clients and URLs. The novel web transaction visualization system also provides fast and interactive means for easily navigating through large volumes of web transactions for the purpose of locating network bottlenecks and/or to enhance overall network performance. Furthermore, the interactive web transaction visualization system of the present invention greatly enhances the quality of end-user experience and may be easily scaled up for massive web transaction data sets. Also, the novel web transaction visualization system may be easily adapted to allow real-time visual filtering thereby eliminating the need for data pre-processing as customarily practiced in the prior art.

[0042] Other components and/or configurations may be utilized in the above-described embodiments, provided such other components and/or configurations do not depart from the intended purpose and scope of the present invention. While the present invention has been described in detail with regards to one or more preferred embodiments, it should also be appreciated that various modifications and variations may be made in the present invention without departing from the scope or spirit of the invention. In this regard it is important to note that practicing the invention is not limited to the applications described hereinabove. Other applications and/or alterations may become apparent to those skilled in the art.

[0043] It should be appreciated by a person skilled in the art that features illustrated or described as part of one embodiment may also be used in other embodiments. It is, therefore, intended that the present invention cover all such modifications, embodiments and variations as long as such modifications, embodiments and variations remain within the scope of the appended claims and their equivalents.