Decision Maker

University of Southern California

Viterbi School of Engineering

EE 579 Final Project

Group 8: Wanlong Cui, Juanyi Feng, Wei Sun

Introduction

This is a client-server based application which can help to divide a large group of users into sub-groups based on their common preferences, and also make the decision for each sub-group.

This application can be quite useful when a large group people are gathering together and need to decide some certain things to form smaller groups.

In our app, we’ve built three scenarios – Restaurant, Movie and Customize.

In the restaurant scenario, the application will automatically get the restaurants’ name near user’s current location and allows user to enter his/her on preference (rate each restaurant on the list).

In the movie scenario, the application will automatically get the movies’ title which are in theater near user’s current location and allows user to enter his/her on preference (rate each movie on the list).

In the customize scenario, the application will allow the user to enter the option list.

Once each user has entered their preference list, the server will run K-Means clustering algorithm to generate the grouping result.

After each user gets the result, users can enter a chat room to communicate with other users within the same sub-group.

Block Diagram Overview

Figure 1. Project Structure

Video Demo

Open Source

Fork this project at this github link!

Some More Detail

Client Side

Once the user opens this application, the screen is shown as Figure 2. We can see that there are two buttons. One is for user to create a new event; the other is for user to join an existing event.

Figure 2. Home Welcome Page

If the user entered his user name and clicked “Create a new event” button, the app will go to the page shown in Figure 3. There are three tags, each represents for a scenario (restaurant, movie, customize).

Figure 3. Create an Event

For the first two scenarios, the user can just simply click “Get Your Location” button, and the application will automatically get the user’s current location’s zip code. This is done by ZipCodeHolder class. The program will use Andriod’s locationManager to get the current longtitute and latitute and initial an HTTP request to http://maps.google.com . Google’s HTTP server will response with all the detial of this location in JSON format. Our progem will extract the zip code form the JSON formatted data.

Once the user click “submit” button, our app will initial an HTTP request to the Apache Http Server running on http://cs-server.usc.edu:1053. The perl code running on apache can retrieve page source from yelp.com and flixster.com, and return the related resturaunt name or movie title. Once the client side received these infomations, it will set up a new socket connection with the socket server, and send all these options information to the socket server.

For the third scenario, the user can enter his/her own options. Once th user click ”Submit” button, the app will send these option informations to the socket server via socket connection.

Now, for this user, he/she can enter his/her preference (rate all the possible options) as shown in Figure 4.

Figure 4. Rating

Now if other users want to join this event, they just need to click “Join an existing event” button on app’s homepage in their android phones. Then, the app will ask the socket server “how many events are there?”, and the server will send back all the existing events to the client as shown in Figure 5.

Figure 5. Join an event

The user just need to choose which event he is going to join. The event name is the sequence number plus the event host’s user name. Once the user joins an existing event, the server will send all the possible options to the client so that the user can enter his/her preference list.

Once the user has entered his/her preference list, the app will jump to the page shown in Figure 6. There are two buttons on this screen – “Get GroupingInfo” button and “Chat!” button. Once the server gets all the clients’ preference list, the user just need to click “Get GroupingInfo” button to get the grouping result displayed on the screen. The app will show the user all the sub-groups. And then, the user can click “Chat!” button to enter a chat room specially set up for his/her own groups which is shown in Figure 7. In this chat room, users within the same sub-group can communicate with each other. The chat service is done by Tomcat web server.

Figure 6. Get Result

Figure 7. Chat Room

Server Side

Apache Http Server

We are using the Apache Http Server to extract the data from certain website to get the restaurant name and movie title as the options for our app.

The Perl code running on this server basically does the following two things:

1. Retrieve page source from yelp.com and flixster.com

2. Use regular expression to filter information(restaurant names and movies name)

Once the client sends it a HTTP request with its current zip code, it will parse the user’s query and get the zip code.

Then it will retrieve page source from yelp.com or flixster.com according to user’s query.

Finally it will use regular expression to get all the restaurant names or movie titles.

So basically, the apache http server is used for get the information for the first two scenarios. It transforms the data from the html source code of yelp.com and flixster.com to our app as shown in Figure 8.

Figure 8. Get the options

Socket Server

The Socket Server contains the key features of our project. It handles all the requests by the clients. We are using the two classes – Socket and ServerSocket provided by java.net package to implement the client side of the connection and the server side of the connection, respectively.

Because we need to deal with multiple clients at the same time, so our socket server is a multithread server. For each client, we will start a service thread to service the client requests. Starting a thread also lets our Server accept multiple connections simultaneously.

Every time the server receives a message send from client, it will calls “private String processInput(String msg)” function to process the message and generate the output message.

The messages from clients are all written in certain format. Basically the message should be like “Request Type; Perameter1; Parameter 2; Parameter 3; …”.

Request Type should be an Integer range from 1 to 6. Each number represents a type of message：

1. The client is creating an event; it sends the server its own username and all the possible options. The server will generate an event ID and return it to the client. The message should be like this:

1; username; option 1; option 2; option 3; option 4; … option N;

2. The client wants to see all the events stored on the server. The server will return all the existing events’ event ID to the client. The message should be simply like this:

2;

3. The client wants to join a certain event. It sends the server its username and the desired event’s event ID. Server will send the client all the options of this event. The message should be like this:

3; username; event ID;

4. The client is sending its preference list to server. It sends the server its username, event ID and the preference list. As the preference list is the rating information of all options, it is represented as numbers separated by “#”. The message should be like this:

4; username; event ID; preference list (i.e. “5#2#3.5#4#5”);

5. The client is requesting for the grouping result. It sends the server the event ID. The server will run grouping algorithm to generate the result and send it back to the client. The message should be like this:

5; event ID;

6. The client is asking the servers which sub-group it is divided into. It sends the server the username and event ID. The server returns its sub-group number. The message should be like this:

6; event ID; username;

Once the server receives a message it first extracts the message type information and then based on certain message type, it performs certain logic to handle the request.

We use hash tables to store the user’s information and grouping result.

Grouping Algorithm

The key grouping algorithm in our project is similar to K-Means Clustering algorithm. Because each user enters his/her own preference list, we need to group these users based on these preference lists.

The algorithm is shown as follow:

1. Create an N-dimensional space.

2. N is the number of options.

3. Consider each user’s preference as an N-dimensional vector.

4. Set N initial decision points.*

5. Calculate the distances from each user to N decision points.

6. For each user, find its closest decision point.

7. Users are divided into the same sub-group if they share the same closest decision points.

8. For each sub-group, calculate the mean for all the users’ Coordinate values, update the decision point for this sub-group as the mean coordinate value.

9. Repeat Step 6,7,8 until the decision points are no longer changed.

The socket server can display all the messages that are transmitting between the client and the server. The admin can monitor what is happening at the server side and also check the decision points’ location as shown in Figure 9.

Figure 9. Server side Console

Tomcat Web Server

We use Tomcat Web Server to set up the chat service once the decision is made. The java servlet running on Tomcat will handle user’s chatting message requests.

Each time the user is sending a message to others in the chat room, the app will generate a HTTP request with the message content to Tomcat. The servlet will handle the request and store the message on the server. At the same time, each client user belongs to that chat room will continuously read all the messages stored at the server. Thus, if a user sends a message, others will get them immediately.

System Evaluation

We are using Hashtables as database at server side, this can help us gain fast access which is very efficient.

We are using Socket Connection and HTTP Connection between server and clients. They are flexible, sufficient.

The multithread socket server guarantees to handle multiple clients at the same time.

Apache HTTP Server and Tomcat Web Server can handle multiple clients too.

Related Works

There are several projects/applications shared some similar ideas with us.

Recently there is a newly launched Chinese smartphone application that can help people decide which restaurant to go to have meals. (http://www.lehe.com/)

We also find out that there are some android applications that can help user to list all the pros and cons of certain choices and help user make decisions. (http://www.appbrain.com/app/mobile-decision-maker/com.broadreachsoftware.decision)

We also know that there are several websites help people scheduling meetings and other appointments such as http://www.doodle.com/. But these sites are more like a voting calculator. They calculate the votes, tell us the results and that it.

All the above applications don’t contain the function to divide users into sub-groups. Our project combine making decisions and grouping together, it also provides a chatting service at the end, these are quite useful and interesting.

Contact

Wanlong Cui : wcui(at)usc(dot)edu

Juanyi Feng: juanyife(at)usc(dot)edu

Wei Sun: weisun(at)usc(dot)edu