CREW'03 at Santa Clara University

Project: Topology-Based Balanced Search Tree

Advisor:

• Prof. Silvia Figueira

Students:

• Mehwish Ahtasham
• Tuong-Van Vu

Student Profile/Biography:

• Mehwish Ahtasham
  Mehwish currently lives in the bay area and is a senior at Santa Clara University. She'll be receiving her Bachelor of Science in Computer Science in June 2004. She also plans to complete her Master of Science in Software Engineering by June 2005. Mehwish is a member of the Math Sorority Pi Mu Epsilon, in which she participates by tutoring math and CS students. She is also a member of the National Society of Collegiate Scholars.
• Tuong-Van Vu
  Born in Vietnam, Van came to the United States when she was seven. She has been residing in San Jose since. Van is currently a senior at Santa Clara University and will be completing her Bachelor of Science in Computer Science in the Fall of 2003. Van also works at Santa Clara University, Department of Education, as a web manager. Her area of interest includes computer graphics, network, and security.

Project Description:

Abstract:
Search trees are extremely useful in several areas, such as databases. These trees keep the elements sorted according to a key to ease the search process. Balanced search trees are trees in which all the paths from the root to a leaf have roughly the same number of links. When using a balanced tree in a distributed system, such as a distributed database, the tree structure is used to form the overlay network, through which the search operations flow. Each node in the tree represents a participating machine, which communicates with its neighbors (parent and children) in the tree only. A balanced tree built over a heterogeneous network, in which machines are connected by links with different capacities, is a tree in which all the paths from the root to each leaf have roughly the same communication cost, i.e., latency and/or bandwidth. This project involves developing strategies to create topology-based balanced search-tree overlay networks. Different strategies will be investigated and compared.

Full Description

Project Status:

Summer 2003 - Report:

In the early part of our summer, we focused on AVL trees and Message Passing Interface. To familiarize ourselves with MPI, we implemented a MPI-based parallel version of the jacobi algorithm. We then shifted towards writing an iterative version of a blindly generated binary tree that recalculates the cost of each path after a node is inserted or deleted. We are currently working on implementing a topology based balanced search tree. It will take into account the cost of each path before inserting or deleting a node. Once we succeed in implementing the iterative version, we will then work on the dynamic version using MPI.

Fall'03/Winter'04 - Report:

We implemented a weighted binary search, in which the weight of a node is the added cost of the right and the left subrees. This weight determines if the tree needs to be balanced once a node is inserted or deleted. If the tree is off balance, according to the weight, rotations may occur to rebalance the tree. The first algorithm results in rotations of the tree at all times when the tree is off balance. After running some tests, however, we discovered that at some instances the resulting tree may be worst after rotations. Thus, we developed a new algorithm, in which rotations will occur only when they result in improvements of the tree. At this moment, we are verifying the results obtained with this new strategy.