You are here
Nearest Neighbors (NN) is a fundamental operation in many areas of scientific computing, including computer vision, machine learning, robotics, and data mining. It is the backbone of applications people use every day, such as Google Images. Images tend to be high-dimensional, and as the dimensionality of the data increases, the NN task becomes computationally more difficult. This is called the “curse of dimensionality” and it affects efforts to analyze and organize high-dimensional spaces.
Graduate student and MSI researcher Anoop Cherian, who works with MSI PI Professor Nikolaos Papanikolopoulos (Computer Science and Engineering), is developing a novel NN algorithm for image data. The goal is to develop an NN algorithm that is computationally tractable at high dimensions. Other needs for this algorithm include:
- state-of-the-art performance in accuracy
- good search speed
- robustness to data distortions
- storage efficiency
The algorithm is called Multi-Regularization Sparse Coding (MRSC) and is based on sparse coding and dictionary learning. The algorithm is showing great promise in accuracy, speed of retrieval, scalability, and robustness. Because of the huge computational demands that working with millions of data points requires, MSI resources are necessary for this work. The image above shows the results of a search using the MRSC algorithm on a database of images of Notre Dame (containing 1,500 images). The first column shows the query images and the other three columns are the first three nearest neighbors.
Mr. Cherian’s poster about this research was the Grand Prize winner at MSI’s Research Exhibition in April 2012 and has been submitted for publication.
Zeolites are porous silicate materials that are used in gas separation, catalysis, and other applications. Several MSI Principal Investigators are involved in a project to develop zeolite nanosheets—plate-like crystals—that are very desirable because of their packing and processing advantages. In 2011, Professor Matteo Cococcioni (MSI Associate Fellow), Professor Alon McCormick (MSI Fellow), Professor K. Andre Mkhoyan, and Professor Michael Tsapatsis, all of the Department of Chemical Engineering and Materials Science, and members of their research groups published a paper in Science (334:6052, 72-75, DOI: 10.1126/science.1208891) discussing the structures of these nanosheets, which constitute a new class of zeolite nanoparticle. The researchers use MSI for computational studies of the structures of the nanosheets, and are continuing their research with simulations that complement and explain experimental results. These methods may also be extended to other structures.
An additional paper about zeolite nanosheets by some of these researchers appeared in the journal Science in June 2012: "Synthesis of Self-Pillared Zeolite Nanosheets by Repetitive Branching," XY Zhang, DX Liu, DD Xu, S Asahina, KA Cychosz, KV Agrawal, Y Al Wahedi, A Bhan, S Al Hashimi, O Terasaki, M Thommes, and M Tsapatsis, 336:6089, 1684-1687, DOI: 10.1126/science.1221111 (2012).
Thanks to the advancement of computing hardware, researchers in all fields are able to generate huge datasets. Data processing, including analysis and visualization, has to tackle the problem of large-data throughput. Both the software and hardware architectures of current computational science have to evolve quickly to meet the volumes of data generated by current petascale computing. Additionally, recent years have seen an upsurge in the number of collaborative computing tools that are empowered and facilitated by the internet. Applications in the so-called “cloud” allow collaborators in distant locations to efficiently share information and work together to solve problems. While researchers routinely use visualization techniques on massive datasets and have begun web-based collaboration using software in the cloud, a need still exists for combining these two applications into a collaborative visualization system that can handle terabytes, or more, of data.
The research group of Professor David Yuen (Earth Sciences; MSI Fellow) is working on a client-server based approach to visualization. Group members who have worked on this project, known as WebViz, include Yichen Zhou, Cory Ruegg, Robin M. Weiss, Erik O.D. Sevre, Wei Jin, and Michael R. Knox. WebViz is a collaborative visualization system that allows users in different locations with different hardware platforms to share and interact with the same real-time visualization session. The image above shows how WebViz can be used on a variety of hardware platforms, including a Powerwall (left panel, 15 megapixel resolution) connected to a Linux server and an iPad 2 (right panel) that uses iOS (formerly iPhone OS, an operating system developed by Apple for hand-held devices). The visualization shows the Tohoku-oki tsunami waves. The Yuen group has tested WebViz at several locations around the globe that are located far from the WebViz servers at the University of Minnesota. These locations include locations in China such as Harbin (9,300 km from Minnesota), Beijing (10,200 km), Shanghai (10,900 km), and Lanzhou (10,800 km), plus Kiev, Ukraine (8,100 km) and Perth, Australia (17,100 km). All rendering processes were done within a couple of minutes.
This research has been supported by the CMG and OCI programs of the National Science Foundation. A longer article about WebViz and its capabilities can be found in the Spring 2012 Research Bulletin.
Gas flow over an object when there are few molecules in a given volume must be studied with different equations than with “thicker” gases. Aerospace engineers must take this into account when they are designing spacecraft that will enter a planet’s upper atmosphere at hypersonic speeds. Assistant Professor Thomas Schwartzentruber (Aerospace Engineering and Mechanics) and his research group have developed a new molecular-simulation tool that allows modeling under these conditions. The image on the left, above, shows a sample of this molecular simulation result for hypersonic flow over a satellite geometry resembling the MIR space station. The image to the right shows a simulation of hypersonic flow over a reentry capsule, with the contours showing the temperature increase through the shock wave ahead of the vehicle. It also shows the degree of surface heating, a maximum near the capsule shoulder. An article about this research appears in the Spring 2012 Research Bulletin.
MSI researchers presented posters of their work at the 2012 MSI Research Exhibition on Friday, April 13, 1-3:30 p.m., on the fourth floor of Walter Library. The posters were judged by a panel of MSI Principal Investigators and prizes were awarded. Light refreshments were served. We are very grateful to our sponsors, Dell and HP, for their support of this event. More information, including pictures of the competition winners, can be found on the 2012 Research Exhibition webpage. The images here were taken at the 2011 Research Exhibition.