CSC352 Project Page 2013

This page is an growing collection of information pertaining to the 2013 CSC352 Parallel and Distributed Processing seminar of Fall 2013. It is maintained by the students and its contents may change daily.

---

Class Page|Piazza

---

Introduction

A seminar on parallel programming, CSC352 starts by introducing students to working in parallel and to reading and presenting technical papers, before working together to conduct research and ultimately write about some topic in parallelism. This year the topic is organizing all the images in Wikipedia visually in some fairly cohesive fashion, hopefully in a manner so that it can be applied to any version of Wikipedia in any language, using parallelism to hasten the otherwise considerable 2D packing problem.

NOTE: Someone please elaborate on/fix this. It seemed too sad not to have an introduction to our class!—but I missed all of the fabulous planning you guys did this week, and so (because of that at the very least!) I'm sure there's more to say.

--Glevyhas 00:32, 4 October 2013 (EDT)

Student Project Pages

• Danaë's project page
• Gavi's project page
• Julia's project page
• Sharon Pamela's project page
• Yoshie's project page
• Emily's project page

---

Class Page|Piazza

---

Project Presentations

PowerPoint presentations

• Julia
• Gavi
• File:Ssantana final proj prez.pdf

Image Repository

• Go to this page for information relating to the image repository
• The images are also available in a MySQL database on Hadoop0, in a database called enwiki_images, in a table called images2.

Accessing the Repository in a MySQL Database

• A simple Java program to list the first 20 files in this table is shown below. You will have to run this program on hadoop0 and change the user and password to reflect your credentials.
• You need to add these lines to the end of your .bashrc file, located in your home directory on hadoop0:

# CLASSPATH for Java JDBC
CLASSPATH=$CLASSPATH:/usr/share/java/mysql.jar:/usr/share/java/mysql-connector-java.jar
export CLASSPATH
 

then you need to force the O.S. to reload all the settings in the .bashrc file:

source ~/.bashrc

• Source code:

// JDBCTest.java
//
// To compile and run from the command line: 
// javac JDBCTest.java 
// java JDBCTest
import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.ResultSet;
import java.sql.Statement;
import java.sql.SQLException;

class JDBCTest {

    private static String     user ="yourUserName";    // <=== change this!
    private static String     password = "yourPassword";   // <=== change this!
    private static String     database = "enwiki_images";    // (change if necessary)
    private static Connection con=null;
    private static Statement  st=null;
    private static ResultSet  rs=null;
    private static String     hostName ="localhost";

    public static void main(String args[])throws Exception {
	try {
	    Class.forName("com.mysql.jdbc.Driver");
	    con = DriverManager.getConnection("jdbc:mysql://"
					      + hostName 
					      + "/" + database, 
					      user, password);
	}
	
	catch (Exception e) {
	    System.out.println( e );
	}
	
	try{
	    st=con.createStatement();
	    rs=st.executeQuery("select * from images2 limit 20;" );
	    
	    while(rs.next()) 
		System.out.println(rs.getString( "name" ) );
	}
	
	finally {
	    try {
		if (rs != null) {
		    rs.close();
		}
		if (st != null) {
		    st.close();
		}
		if (con != null) {
		    con.close();
		}
	    }
	    catch (SQLException e) {
		System.out.println(e);
	    }
	}
    }
}

The output of the program

dominique@Hadoop0:~/JavaMySQL$ javac JDBCTest.java 
dominique@Hadoop0:~/JavaMySQL$ java JDBCTest
Aloha_orig.png
Yuvan_Yuvathi.jpg
New_Image_v2.png
Crulic_film_poster.jpg
Their_Complete_General_Recordings.jpg
Robert_Bruce_Merrifield.jpg
Jacob_Young_as_JR.png
Stanley_Park_Greenery.jpg
MiamiHeatOld.png
Album_ma_fleur_cover.jpg

Food for Thought

(I'm wondering if it wouldn't be better to start organizing this as a collage, 3 images across, in a tall table. What do you think? I think it might even be better in its own page... --Thiebaut 09:06, 4 October 2013 (EDT))

833 Candidate Planets for Life

NASA’s premier planet-hunting scope turns up 647 possible Earth-size worlds in the Milky Way. It is interesting to see how they decided to show all the planets in the poster.

Photo from Seti.

Design of Artistic Packing Layouts

This is a video of some recent research presented at SIGGRAPH Asia 2013. The main link to this research is here. See how the packing not only finds a tight formation for the various shapes, but also sorts them in some way. A graph (very likely) is used to keep the relationship between the different shapes. Taken from the YouTube snipet: "We propose an approach to "pack" a set of two-dimensional graphical primitives into a spatial layout that follows artistic goals. We formalize this process as projecting from a high-dimensional feature space into a 2D layout. Our system does not expose the control of this projection to the user in form of sliders or similar interfaces. Instead, we infer the desired layout of all primitives from interactive placement of a small subset of example primitives. To produce a pleasant distribution of primitives with spatial extend, we produce a pleasant distribution of primitives with spatial extend, we propose a novel generalization of Centroidal Voronoi Tesselation which equalizes the distances between boundaries of nearby primitives. Compared to previous primitive distribution approaches our GPU implementation achieves both better fidelity and asymptotically higher speed. A user study evaluates the system's usability." (Added by --Thiebaut 09:42, 23 October 2013 (EDT))

PickPacks

Published on Feb 4, 2013, this is an introduction to the PicPaks program that is used to pack PNG objects into a background mask PNG file to make artistic pictures. This does relate to our project in the way the program allows the user to move items around. Interesting is the idea of having a mask and packing inside the mask. (Added by --Thiebaut 09:42, 23 October 2013 (EDT))

Mosaic Photo Books

Interactive Memories's Mosaic Photo Books: An app that will create a collage of your photos in a rectangular shape.

Pavillon de l'Arsenal: Paris in the Making

Paris in the Making: The model was developed using Liquid Galaxy software and Google Earth, the leading geographical navigation software, downloaded over a billion times around the globe. The 37m² digital model, for the first time, enables visitors to view the city in HD.

Word Placement

mathematica.stackexchange.com: This is a page on Mathematica Stack Exchange that deals with different ways of packing words. There might be some placement-algorithm ideas here...

GigaPan

GiganPan: From their Web site: "Gigapans are gigapixel panoramas, digital images with billions of pixels. They are huge panoramas with fascinating detail, all captured in the context of a single brilliant photo. Phenomenally large, yet remarkably crisp and vivid, gigapans are available to be explored at Gigapan.com. Zoom in and discover the detail of over 50,000 panoramas from around the world."

Most-Pixels-Ever

• Most-Pixels-Ever Processing. A library developed by Daniel Shiffman of NYU for displaying large Processing applets on multiscreens.

	djibnet
Texas Advanced Computing Center and their version of Most-Pixels-Ever, coined Massive-Pixel-Environment.
	"Massive Pixel Environment is a library for the Processing programming language. It allows you to sketch interactions and visualizations and scale them across multiple displays. We've scaled Processing sketches up to 328 megapixels with Massive Pixel Environment."

Faces of Facebook

The Faces of Facebook

Cleveland Art Museum Display

digitialSignageConnection.com on the Cleveland Art Museum and its use of Christie MicroTiles Video Walls.

Visual Structure of Millions of User-Generated Photos

Visual Structure of Millions of User Photos

Bill Cunningham and Photographing Fashion

Bill Cunningham has been photographing fashion for many years and publishes a collage of photos he's taken in the streets of New York City (mostly) in the New York Times regurlarly.

Zoom.it

Formally "Dragon" from Microsoft, now Zoom.it. Allows a user to supply many jpg files that are algorithmically pushed to the browser as the user moves around the large image and starts zooming in.

Many ways to display a wall of photos

This St. Louis Today article explores the different approaches of two artistic “local experts” - an art installation specialist (Heil) and the owner of a frame shop (Shoults) - as they collaborate to hang a collection of picture frames on a wall. The two create three collages together (one casual, one formal, and one in columns) from the same set of images. The formal and column collages focus more on the visual composition of each image than the casual collage. Some ideas that our class can take from these frame-collage experts: don’t overload one side with one color; odd numbers of rows and lines look better than even ones; aim for symmetry; keep the central “idea” as the core - build around it; tell a story; take into account the human eye, and the order it craves.

Project Ideas

Packing

• Study the performance trade-offs associated with different data-structures for holding the lines and segments used by the packing heuristic. The analysis should look at alternatives to red-black trees.
• Study multithreaded approaches for the packing heuristic. How can the packing be divided up between different thread to best take advantage of multicore architectures?
• Implement the Most-Pixels-Ever system as a proof-of-concept and display a dynamic collage on several screens at the same time.
• Explore Massive-Pixel-Environment from Texas Advanced Computing Center, and set it up on a cluster of computers.
• Create a new algorithm for positioning images on the area to pack before the packing actually starts. And idea could be to add a fake border around the images to pre-pack and pack them using the known heuristic. Another idea is to use some predefined path, such as a spiral, or a set of concentric circles and place images on these paths.
• Modify the packing algorithm so that an image can shrink or grow slowly, forcing all the neighboring images to get repacked automatically.
• Add an extra constraint to the packing algorithm so that rectangles that are "close" to each other through some metric (maybe they belong to the same category, or represent entities that are close to each other in some group) get placed close to each other in the packing.
• Using the idea of the PickPacks program, propose a new parallel algorithm for packing rectangles inside a mask that is not rectangular (or outside a mask that is not rectangular). (added --Thiebaut 09:41, 23 October 2013 (EDT))

Image Processing

• Figure out possible fast ways to reduce the size of jpg, gif, png files (and whatever other format Wikipedia allows) by 4, by 8, by 16. The keyword "Thumbnail" or "Thumb" is the key here. There should be algorithms out there to create thumbnail images. We need to be able to generate such thumbnails for a good subset of the 3,000,000 images in Wikipedia.

Wikipedia

• Write programs that automatically 1) download the raw Wikipedia image dumps or access statistics 2) unpack and filter them of unnecessary information, 3) create a new database on a MySQL server, 4) and store the information in an easy to use format in one or several MySQL table.
• Write programs that pick the N most important images from file or from a database according to some criteria.
• Create a graph of the relationships that exist in all the wikipedia pages through internal links. Generate possible weights for each page, based on various statistics:
  • How many pages point to a given page (that would be similar to the philosophy of the Page rank algorithm used by Google)
  • How many visits/views a given page has received
  • etc.
• Suggest your own...

Museum Visit

• visit of the SCMA with Maggie Lind, Associate Educator for Academic Programs
• visit of the Cunningham Center in the SCMA with Maggie Kurkoski, Brown Post-Baccalaureate Fellow

Accession Number	Maker	Title	Materials	Date Made
SC 1946:2-1	Rothschild, Judith	Harbour	red, black, gray and white paper collaged with black ink on printed paper from magazine	n.d.
SC 1950:53-21	Muybridge, Eadweard	Animal Locomotion: Plate 21	photogravure on paper mounted on paperboard	1887
SC 1959:65	Schwitters, Kurt	Kynast-Fest	collage of paper and fabric on paper	1919
SC 1972:42-1	Bauermeister, Mary	Eighteen Rows	pebbles and epoxy on linen covered board	1962-1968
SC 1983:8	Rauschenberg, Robert	Commemorative Artwork	lithograph printed in color on white wove paper	1981
SC 1992:2	Simpson, Lorna	Counting	photogravure with silkscreen on paper	1991
SC 1994:11-48	Ryan, Anne	Untitled No. 368	paper and cloth collage elements on paper	ca. 1948-1954
SC 2006:56-5	Barrow, Thomas	Destructive Interference	unique spray-painted photogram	1988/1990
SC 2008:40-1	Young, Thomas Steven	Chin & Eyes / Recycled Realities	gelatin silver print	ca. 2000
SC EL 1:2010	Kim, In Sook	Saturday Night	C-print	2007

Images

• Barrow, Thomas. Destructive Interference, 1988/1990. Unique spray painted photogram. Gift of Nicole Moretti Ungar, class of 1982, and Jon Ungar. Photograph by Petegorsky/Gipe. SC 2006:56-5.

• Kim, In Sook. Saturday Night, 2007. C-print. Lent by Rora Tanaka, class of 1988. SC EL 1:2010.

• Muybridge, Eadweard. Animal Locomotion: Plate 21, 1887. Photogravure on paper mounted on paperboard. Gift of the Philadelphia Commercial Museum. Photograph by Petegorsky/Gipe. SC 1950:53 21.

• Schwitters, Kurt. Kynast-Fest, 1919. Collage of paper and fabric on paper. Purchased with the Eleanor Lamont Cunningham, class of 1932, Fund. Photograph by Petegorsky/Gipe. SC 1959:65.

• Simpson, Lorna. Counting, 1991. Photogravure with silkscreen on paper. Purchased with the Janice Carlson Oresman, class of 1955, Fund. Photograph by Petegorsky/Gipe. SC 1992:2.

• Rauschenberg, Robert. Commemorative Artwork, 1981. Lithograph printed in color on white wove paper. Gift of the AFL CIO. Photograph by Petegorsky/Gipe. SC 1983:8.

• Rothschild, Judith. Harbour, n.d. Red, black, gray and white paper collaged with black ink on printed paper from magazine. Purchased. Photograph by Petegorsky/Gipe. SC 1946:2-1.

• Ryan, Anne. Untitled No. 368, ca. 1948 1954. Paper and cloth collage elements on paper. Gift of Mr. and Mrs. William A. Small Jr. (Susan Spencer, class of 1948). Photograph by Petegorsky/Gipe. SC 1994:11-48.

• Young, Thomas Steven. Chin & Eyes / Recycled Realities, ca. 2000. Gelatin silver print. Gift of Jeanne and Richard S. Press. Photograph by Petegorsky/Gipe. SC 2008:40-1.

Barrow, Thomas, 1958-65	Barrow, Thomas, 2006-56-5	This section is only visible to computers located at Smith College Kim In Sook, Saturday Night, 2007 (taken from http://www.dirkahlgrim.com/wordpress/?p=669)
Muybridge, Eadweard, 1950-53-21	Rauschenberg, Robert, 1983-8	Rothschild, Judith, 1946-2-1
Ryan, Anne, 1994-11-48	Simpson, Lorna, 1992-2	Young, Thomas Steven, 2008-40-1

Whiteboard Brainstorming

10/3/13

Transcriptions:

Image one:

Input: 3 million images

Output: an organized collage of images

• placement algorithm
• database for statistics
  • link to image provided
• access images

Image two:

Images --> organized by width (like pinterest) organized by color for overall effect

• dynamic updates --> real time
• responsive by user input
  • search
  • mouse-over
  • click to see original page
  • re-pack in real time to show a certain category

Image three:

• organized by topic?
  • grab category tags?
  • know info about pages
• connect images to source pages
• graph of images
• comparisons across different wikipedias
• deal w/redundancy
• image weight based on how many pages link to it

Image four:

Initial weight:

• Number of pages link to it
• re-weighted after user clicks

Sizes: 1px x 1px, ...?

=> page view statistics?

images 2.3 TB

stats MB

--> image resizing?

• 3-4s per image? ImageMagic <-- time sink
• preprocess images in >1 sizes
• zoom progressively? ...probably not? maybe?

Image five:

preprocess -->

• resize
• placement
• pack
• dynamic
• weight
  • page?
  • pageview?

resize

determine weight

• statistics

cinnamon bun heuristic

Image six:

• place?

1. weight images and resize
2. pack in a nice way
3. make dynamic

Image seven:

9 million pages --> discard all w/no images

--> 3 million images

graph

• matrix
• adjacent list

image:

• tiny
• small
• large
• number pages displayed on
• categories
• number of views
• number of pages link to pack

weight: sum of page views

danaë's page

• Go here to see Danae's page.

News Sites

• Parallelism
  • TechWorld: Parallel Processing News
  • HPCwire: Parallelism

Earth Collage

Cat collage

---

Class Page|Piazza

---

santa cat collage

mark zuckerberg collage

Project Plan In-class Discussion

The picture above was drawn by Prof. Thiebaut when he was explaining what's to come in the project. All the parts of the projects are drawn on the board and students (or a pair of students) should pick a section of the project they would like to work on.

Notes:

• There is a paper to be written about the section chosen and worked on
• There is a mini presentation about the work done
• Help with writing is available from Prof. Thiebaut before final grading.

Stardust Collage

Check these beautiful collages resembling human features made out of galaxies, stars, and universe pictures.

They are part of a project by Sergio Albiac and you can be part of it if you want!! For more information please visit his website:

http://www.sergioalbiac.com/wall/stardust.html

Breaking Down The Final Project

On Oct. 12 2013, the class had a discussion about possible project ideas and the following pictures are from the board after tossing a few ideas around.