Research

Autopolis: Automatic Creation of Realistic Cities

Given terrain information and user preferences such as desired city size, Autopolis generates commercial and industrial centers, and grows areas surrounding these centers. The program also creates streets and highways, and assigns a land-use for each parcel.

Autopolis has several very attractive features that makes it effective for practical use. Compared to previous methods, Autopolis is able to quickly generate cities of unprecedented realism and detail, including highways, major and minor streets, and more detailed classification of land-use (skyscraper, historical, government, residential, civic, ports, industrial etc.). Compared to previous methods, Autopolis also takes into consideration more factors that influence city development, such as water proximity, slope, elevation, and optimal distance between industrial/commercial centers and ports.

Visualizing Internet Routing Data

Detecting Anomalous Origin AS Changes

Internet connectivity is defined by a set of routing protocols which let the routers that comprise the Internet backbone choose the best route for a packet to reach its destination. One way to improve the security and performance of Internet is to routinely examine the routing data. In our project, named ELISHA, we show how interactive visualization of Border Gateway Protocol (BGP) data helps examine Origin AS Changes (OASCs).

Analyzing routing stability

A key component in the Internet security effort is the routine examination of Internet routing data, which unfortunately can be too large and complicated to browse directly. We have developed an interactive visualization process which proves to be very effective for the analysis of Internet routing data. We show how each step in the visualization process helps direct the analysis and glean insights from the data. These insights include the discovery of patterns, detection of faults and abnormal events, understanding of event correlations, formation of causation hypotheses, and classification of anomalies.

We have updated our system to visualize statistical and signature-based anomaly detection on BGP data. In this way, automated and interactive visual methods are combined effectively, complementing one another, to facilitate validation, quick searches, analysis, and finding desired threshold values.

Visual Classification and Intrusion Detection

StarClass

Classification operations in a data-mining task are often performed using decision trees. The visual-based approach to decision tree construction has gained increasing popularity. We developed StarClass, a new interactive visual classification method. This method maps multi-dimensional data to the visual display using star coordinates, allowing the user to interact with the display to create a decision tree. Preliminary evaluation indicates that this new technique is as effective as state-of-the-art algorithmic classification methods, and more effective than the previous visual-based methods. StarClass also offers additional advantages such as improving the user's understanding of the data.

PaintingClass

PaintingClass introduces a new decision tree exploration mechanism, to give users understanding of the decision tree as well as the underlying multi-dimensional data. This is important to the user-directed decision tree construction process as users need to efficiently navigate the decision tree to grow the tree. PaintingClass extends the technique proposed to StarClass so that datasets with categorical attributes can also be classified. Many real-world applications use data containing both numerical and categorical attributes; therefore PaintingClass is much more useful than StarClass. We show the effectiveness of PaintingClass in classifying some benchmark datasets by comparing accuracy with other classification methods.

We also extended the work to perform intrusion detection, by incorporating visual anomaly detection. We allow the user to visualize the test data together with the training data. However, the test data is not colored, so as not to reveal their classes. For real-world applications, this corresponds to finding out where the density distribution of test data differs from normal data, and flagging these as intrusions. Using this method, we are able to classify the KDD Cup '99 data with great accuracy. Visual exploration also found special patterns in the attack data.

Tree Visualization

The project RINGS develops a technique for visualizing large trees. We introduce a new ringed circular layout of nodes to make more efficient use of limited display space. RINGS provides the user with the means to specify areas of primary and secondary focus, and is able to show multiple foci without compromising understanding of the graph. The strength of RINGS is its ability to show more area in focus and more contextual information than existing techniques. We demonstrate the effectiveness of RINGS by applying it to the visualization of a Unix file directory.