Research

Large relational data are the primary sources of data in the real world. The analysis, exploration, and walk-through of large relational data have immediate applications in many areas. By large, we mean a data set that is too large to be loaded into main memory in its entirety. Large relational data present technical challenges to both data visualization in the front-end and data query support in the back-end. Correspondingly, our research on visual data exploration has two parts:

• The first part is on data query support, which focuses on how to efficiently organize large relation data on the secondary storage to facilitate typical database operations incurred by interactive data visualization and exploration. These operations include browsing/panning, overview-and-drill-down, and brushing/picking. The efficient execution of these non-traditional database operations requires the data be aggregated (to provide fast overview of data), be organized into multiple resolutions (to facilitate zooming and drill-down), and be spatially indexed in data space (to support range queries for data selection and panning). These operations call for new common representation of data between database and visualization clients. Our solution to this problem is to have the data aggregated in multiresolutions and to have the aggregated data piggybacked on internal nodes of a high dimensional tree index. We call this data structure data aggregation tree.

• The second part is on extending existing visualization techniques and/or creating new ones that may take data aggregation tree as input. Data aggregation tree provides a multiresolution compact representation of large relational data. A visualization technique should take full advantage of this data representation. We have developed two primary visualization techniques: 3D projection using footprint splatting and density-based parallel coordinates. Both work by visualizing data aggregation information at multiple resolutions.

1. Multiresolution Data Aggregation

Data aggregated at multiple resolutions should be organized into a hierarchical structure for the purpose of efficient organization and data access. A high dimensional tree index offers an excellent way to piggyback the aggregated data. Such a high dimensional tree index must meet all of the following requirements: (1) it provides a point access method (PAM) instead of a spatial access method (SAM) (because data records are assumed as points in high dimenisonal space); (2) regions represented by sibling nodes are disjoint with each other (no data point is counted more than once); (3) the region represented by a node is totally covered by union of the regions represented by its child nodes (no data point is missing). In short, the high dimensional tree index we choose to piggyback multiresolution data aggregation must be a partition-based PAM. Such a tree index has two functions: (1) to organize multiresolution data aggregation; (2) to accelerate high dimensional range queries. We call such a tree index a data aggregation tree.

We have chosen kdB-tree as the tree index. Each page in a kdB-tree represents a hyperrectangle and contains a binary tree that partitions the hyperrectangle into smaller hyperrectangles. Each leaf node of the binary tree keeps aggregate values of data records in the region represented by the node. Leaf node also contains a PageID pointer, which points to a child page. Binary tree nodes are stored in the page in a pre-order sequence so that the binary tree can be exactly reconstructed. Major data operations (data aggregation, browsing and zooming, and range queries) in visual data exploration can be properly implemented by index-only queries on such an indexing structure.

For data insertion, the original kdB-tree suffers from a cascading split problem. We have modified the page splitting strategy of kdB-tree for data insertion: when a page is full, it splits by following the first partition of the region represented by the page. This strategy avoids cascading splits at the cost of creating an unbalanced tree. In addition, if a leaf page is full and has to split, it splits along the longest dimension of the hyperrectangle it represents. This way of splitting keeps hyperrectangles as hypercubic as possible which helps maintain consistent resolutions in all dimensions.

As an intermediate representation of large relational data between visualization client and database, data aggregation tree  facilitates both range query and multiresolution data aggregation and, thus, makes visualization tools scalable to a large number of data records. Data aggregation tree has potential applications in query processing, OLAP, and new data mining algorithms using density data as input. In addition, data aggregation tree supports privacy-preservation of individual data records. Permission can be given to each user according to data resolutions. The tree enables restriction to each user to access the data down to a specific resolution and, therefore, preserves the privacy of individual data records.

2. Visualization Techniques

Multiresolution data aggregation represents a new input data format for visualization. We have chosen two example visualization techniques, 3D footprint splatting and parallel coordinates, to support this input data format.

3D footprint splatting is implemented through the integration of several multidimensional data visualization techniques. The basic idea is to combine direct volume rendering with 3D data projection to deal with high dimensional aggregated data. A 3D projection orthogonally transforms high-dimensional data into 3D. A user may choose interesting projections through projection pursuit. A sequence of projections can be rendered with smooth transitions by using grand tour. We have developed multidimensional footprint splatting to render high dimensional data hyperrectangles using a two-step bootstrapping technique. The first step generates a footprint by sampling a high dimensional reconstruction kernel and by applying the splatting algorithm to the samples. The second step visualizes the data by applying the same splatting algorithm to the footprints of data hypercubes. Opacity of each footprint is assigned as a function of the number of data points in the corresponding data hyperrectangle. 3D texturing of footprints greatly accelerates rendering speed and improves interactivity.

Parallel coordinates provide another excellent metaphor to visualize high dimensional data by horizontally arranging vertical coordinates, one for each dimension. Data hyperrectangles represented by internal nodes of a data aggregation tree can be perfectly displayed as horizontal bands. The location and extend of a band across each coordinate depend on the low and high values of the corresponding data hyperrectangle in that dimension. The opacity of each band depends on the number of data records in its corresponding data hyperrectangle. Bands of all hyperrectangles are blended to produce the final image. Zooming and drill-down are supported by accessing aggregated data at deeper levels of the tree index. Parallel coordinates allow a user to specify a horizontal data selection band (the gray band in the figure below). The data selection band represents a query region in data space. This allows the user to visualize a subset of data in various levels of detail.

3D footprint splatting and density-based parallel coordinates are two techniques that can be easily extended to work with multiresolution data aggregation. In general, multiresolution data aggregation calls for new algorithms and techniques in data visualization and user interaction. For example, 2D elevation maps and 3D isosurface rendering would help a user to quantitatively explore high dimensional data. In addition, data mining techniques could be used to guide visual exploration of data. Visual exploration would also benefit from techniques for data pre-fetching and buffer management. These issues are under investigation.

Publications

• Li Yang. Visual exploration of large relational datasets through 3D projections and footprint splatting. IEEE Transactions on Knowledge and Data Engineering, 15(6):1460-1471, November/December 2003. (Color figures in the paper are available here)

• Li Yang. Visualizing large relational datasets by combining grand tour with footprint splatting of high dimensional data cubes. Proceedings of 2003 International Conference on Computational Science and Its Applications (ICCSA 2003), Montreal, Canada, May 2003. Lecture Notes in Computer Science 2667, pages 11-20, Springer

• Li Yang. n23Tool: A tool for exploring large relational data sets through 3D dynamic projections. Proceedings of the 9th International Conference in Information and Knowledge Management (CIKM 2000), pages 322-327, Washington, DC, November 2000

• Li Yang. Interactive exploration of very large relational datasets through 3D dynamic projections. Proceedings of the 6th ACM International Conference on Knowledge Discovery and Data Mining (KDD 2000), pages 236-243, Boston, MA, August 2000

• Li Yang. 3D grand tour for multidimensional data and clusters, in Advances in Intelligent Data Analysis, 3rd International Symposium, IDA'99. Amsterdam, Netherlands, August 1999. Lecture Notes in Computer Science 1642, pages 173-184, Springer.

Figures: Footprint splatting of aggregated data (left) versus density-based parallel coordinates (right). Data hyperrectangles are retrieved by visiting internal nodes of data aggregation tree. In each figure, opacity of the visualization of a data hyperrectangle is a function of number of data points within the data hyperrectangle.

We are interested in visualization and visual exploration of data mining results. Unlike relational data, data mining results are presented as facts and rules, which can not be easily treated as distributions in Euclidean space. For example, one interesting topic is how to prune and visualize many frequent itemsets, each of which contains many items, and many many-to-many association rules derived from such frequent itemsets. The fundamental challenge comes from the word "many": the first problem is how to present many itemsets or rules; the second problem comes from the lack of an effective visual technique to describe many-to-many relationships.

For the first problem, we have noticed that frequentness is a monotone Boolean function on the itemset lattice. Therefore, the problem becomes how to present the long border of support in the itemset lattice. Our idea is to introduce a boolean displayable property of itemsets. This displayable property is also monotone on the itemset lattice. Therefore, it introduces another border, called the displayable itemset border, which separates displayable itemsets from undisplayable ones on the itemset lattice. The value of this border is that only those displayable frequent itemsets will be visualized. In this way, we can selectively visualize frequent itemsets by interactively changing the displayable itemset border.

Frequent itemsets and association rules can be selectively visualized by changing the displayable itemset border. A key issue is how to meaningfully change the border through visual interaction. We have developed an approach to do this through the visualization of item taxonomy. We can control the displayable itemset border in the itemset lattice by selectively displaying items in the item taxonomy. Only those displayable frequent itemsets will be visualized. 

For the second problem on visualizing many-to-many relationships, we have found a novel use of parallel coordinates as visual metaphor. An association rule is visualized by connecting its items, one on each parallel coordinate. The connection can be made by using polynomial curves, for example, Bezier curves, to distinguish itemsets or rules sharing parts (as shown in the figure below). In the presence of item taxonomy, an item taxonomy tree can be used as coordinate and can be expanded or shrunk by user interaction. This interaction introduces a displayable border in the generalized itemset lattice. Only those frequent itemsets on the border are displayed. By changing the border through user interaction, we can selectively visualize frequent itemsets and association rules.

In summary, the resulting 3D visualization has the following features: (1) It is capable of visualizing large itemsets and many-to-many association rules; (2) It is capable of visualizing a large number of frequent itemsets and association rules by displaying only those ones whose items are selected by the user; (3) The closure properties of frequent itemsets and association rules are inherently supported by this visualization such that the implied ones are not visualized.

Future work will be focused on rule pruning and better exploitation of user interaction. One topic is how to prune uninteresting itemsets and rules. Some redundant itemsets or rules may be more interesting than their respective displayed ones. This raises the concern that some potentially interesting patterns are not accorded perceptual places in the visualization even though they are implied. Summarization techniques would be needed to better summarize and prune the discovered itemsets and rules. Another topic is to explore other alternatives in addition to item taxonomy to selectively visualize itemsets or rules.

Publications

• Li Yang. Pruning and visualizing generalized association rules in parallel coordinates. IEEE Transactions on Knowledge and Data Engineering. 17(1):60-70, January 2005.

• Li Yang. Interactive visualization of frequent itemsets and association rules. Proceedings of the 3rd International Workshop on Visual Data Mining, pages 85--95, Melbourne, FL, November 2003.

• Li Yang. Visual exploration of association rules (Poster). Proceedings of the 14th IEEE Visualization Conference (VIS'2003), Seattle, WA, October 2003.

• Li Yang. Visualizing many-to-many association rules. Proceedings of the 2003 International Conference on Information and Knowledge Engineering (IKE'03), pages 92-95, Las Vegas, NV, June 2003.

• Li Yang. Visualizing frequent itemsets, association rules and sequential patterns in parallel coordinates. Proceedings of 2003 International Conference on Computational Science and Its Applications (ICCSA 2003), Montreal, Canada, May 2003. Lecture Notes in Computer Science 2667, pages 21-30, Springer.

Figures: A screen snapshot of visualization of frequent itemsets (Fig 1) and a screen snapshot of visualizing association rules (Fig 2). In Fig 2, the left two coordinates (with item names annotated on the left) represent the left-hand sides of the rules. The right two coordinates (with item names annotated on the right) represent the right-hand sides of the rules.

The problem of data embedding comes from the usual practice of dimensionality reduction, that is, to project high dimensional data into a low space so that the resulting low dimensional configuration reflects intrinsic structure of the data and performs better in future processing. Traditional linear approaches such as principal component analysis (PCA) and linear discriminant analysis (LDA) are special cases of data embedding.

Data embedding has been extensively studied with many algorithms proposed. In summary, these algorithms work by taking one or both of the following two ideas:

• The first idea is to ignore the dimensionality of input data points by taking inter-point distances as input. It tries to find a low dimensional Euclidean space such that the inter-point distances are best preserved. Distance preservation is done through minimizing an error measure. Distances can be Euclidean or geodesic. The error measure may prefer the preservation of local distances or the preservation of long distances.

• The second idea is to take a bottom-up approach by taking two major steps. The first step collects local neighborhood information and the second step consolidates the local information in deriving global information which gives final configuration of data. Both steps are linear although their combination is nonlinear. Approaches using this idea often start with defining neighborhoods of data points. Local information consolidated in the second step can be local distances, local coordinates, or weights of a linear combination of neighbor points.

Our research on data embedding has focused on the following three topics:

Construction of Connected Neighborhood Graphs

Data embedding approach using the second idea starts by defining neighbor points of each data point. It requires that the closure of neighbor points of each data point covers all data points. Otherwise, the approach would fail in deriving global information. If we use every data point as a vertex and connect every point to each of its neigbors by an edge, we obtain a neighborhood graph of all data points. The neighborhood graph must be a connected graph.

Neighborhood graph construction is a key step for the success of data embedding algorithms using the second idea. For example, Isomap requires a connected neighborhood graph so that the geodesic distance between any pair of data points could be estimated by the length of the shortest path between the pair. However, neither the k-NN approach (k-nearest neighbor) nor the epsilon-neighbor approach (all points within the distance epsilon) guarantees the connectedness of the constructed neighborhood graph. We have proposed four approaches, k-MST, Min-k-ST, k-EC, and k-VC, to construct connected neighborhood graphs. k-MST, Min-k-ST, and k-EC construct k-edge-connected neighborhood graphs and k-VC constructs k-connected neighborhood graphs. k-MST works by repeatedly extracting minimum spanning trees (MSTs) from the complete Euclidean graph of all data points. The rest three approaches use greedy algorithms. Each of them starts by sorting all edges in non-decreasing order of edge length. Min-k-ST works by finding k edge-disjoint spanning trees the sum of whose total lengths is a minimum. k-EC works by repeatedly adding each edge in non-decreasing order of edge length to a partially formed neighborhood graph if end vertices of the edge are not yet k-edge-connected on the graph. k-VC works in a similar way as k-EC. However, it adds an edge to a partially formed neighborhood graph if two end vertices of the edge are not yet k-connected on the graph. Experiments show that these approachs outperform the k-NN and the epsilon-neighbor approachs, especially when the input data is undersampled or unevenly distributed where the two conventional approachs would fail. 

Locally Multidimensional Scaling

A p-dimensional manifold locally resembles a p-dimensional Euclidean space. Therefore, data observations that lie on a manifold can be approximated by a collection of overlapping local patches, the alignment of which in a low dimensional Euclidean space would provide an embedding of the data. This idea suggests a data embedding method using classical multidimensional scaling or principal component analysis as local model. Our algorithm works by first identifying a minimum set of overlapping neighborhoods that cover all data points. This is done by applying a greedy approximation algorithm of minimum set cover. Classical multidimensional scaling is then applied to each neighborhood to derive a low dimensional patch. Overlapping local patches are finally aligned to derive the final data embedding result in order to minimize a residual measure. The residual measure has a quadratic form in terms of the resulting global coordinates and therefore can be minimized by using an eigensolver. We call this method locally multidimensional scaling (LMDS).

The overall idea of LMDS resembles that of locally linear embedding (LLE). Similar to LLE, the LMDS algorithm consists of two linear steps, the second of which solves an eigenvalue problem. The solution is globally minimized and does not suffer from the problem of local minima. Unlike LLE, however, LMDS produces locally isometric embedding results. The size of the eigenvalue problem scales with the number of patches rather than the number of data points. In addition, LMDS requires only local distances within each neighborhood as input.

Our current research in data embedding focuses on the development of robust and reliable embedding techniques, making these embedding techniques applicable to large relational data, making them work incrementally with growing data and data streams, and applications in multimedia information processing. In basic research, data embedding may play an instrumental role in extending theories of data and signal processing in Euclidean space to manifolds. These are the areas that we are interested in.

Publications

• Li Yang. Locally multidimensional scaling for nonlinear dimensionality reduction. Proceedings of the 18th International Conference on Pattern Recognition (ICPR'06), volume 4, pages 202-205, Hong Kong, China, August 2006

• Li Yang. Building connected neighborhood graphs for locally linear embedding. Proceedings of the 18th International Conference on Pattern Recognition (ICPR'06), volume 4, pages 194-197, Hong Kong, China, August 2006

• Dongfang Zhao and Li Yang. Incremental construction of neighborhood graphs for nonlinear dimensionality reduction. Proceedings of the 18th International Conference on Pattern Recognition (ICPR'06), volume 3, pages 177-180, Hong Kong, China, August 2006

• Li Yang. Building k-connected neighborhood graphs for isometric data embedding. IEEE Transactions on Pattern Analysis and Machine Intelligence. 28(5):827-831, May 2006

• Li Yang. Building k edge-disjoint spanning trees of minimum total length for isometric data embedding. IEEE Transactions on Pattern Analysis and Machine Intelligence. 27(10):1680-1683, October 2005

• Li Yang. Building k-edge-connected neighborhood graphs for distance-based data projection. Pattern Recognition Letters. 26(13):2015-2021, October 2005

• Li Yang. Building connected neighborhood graphs for isometric data embedding. Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'2005), pages 722-728, Chicago, IL, August 2005

• Li Yang. Data embedding techniques and applications. Proceedings of the 2nd International Workshop on Computer Vision meets Databases (CVDB 2005), Baltimore, MD, June 2005

• Li Yang. Distance-preserving projection of high dimensional data for nonlinear dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence. 26(9):1243-1246, September 2004

• Li Yang. Sammon's nonlinear mapping using geodesic distances. Proceedings of the 17th International Conference on Pattern Recognition (ICPR'04), volume 2, pages 303-306, Cambridge, UK, August 2004

• Li Yang. k-edge connected neighborhood graph for geodesic distance estimation and nonlinear data projection. Proceedings of the 17th International Conference on Pattern Recognition (ICPR'04), volume 1, pages 196-199, Cambridge, UK, August 2004

• Li Yang. Evaluation of distance-based techniques for data projection and dimensionality reduction. Proceedings of 2004 International Conference on Information and Knowledge Engineering (IKE'04), Las Vegas, NV, June 2004

• Li Yang. Distance-preserving projection of high dimensional data. Pattern Recognition Letters. 25(2):259-266. January 2004

• Li Yang. Distance-preserving mapping of patterns to 3-space. Pattern Recognition Letters. 25(1):119-128. Jannary 2004

• Li Yang. Tetrahedron mapping of points from n-space to three-space. Proceedings of the 16th International Conference on Pattern Recognition (ICPR 2002), volume 4, pages 343-346, Quebec City, Canada, August 2002.

Figs. (a) A Swiss-roll data set superimposed with local patches, (b) 2D embedding by aligning the local patches.