Contact Information

Physical Address: Network Dynamics and Simulation Science Laboratory
Virginia Bioinformatics Institute, Virginia Tech
CRC Research Building XV
1880 Pratt Drive, Blacksburg, VA 24061
Phone: +1 (540) 231-5359
Fax: +1 (540) 231-2891 [Attn: Maleq Khan]
Email: my_first_nameATvbi.vt.edu
Home page: http://staff.vbi.vt.edu/maleq/

Research Interest

Design and analysis of algorithms
Distributed algorithms
Randomized algorithms
Wireless ad hoc networks
Communication networks in general
Data mining

Education

• PhD in Computer Science, Aug 2007
  Purdue University, West Lafayette, Indiana, USA
  Thesis: Distributed Approximation Algorithms for Minimum Spanning Trees and Other Related Problems with Applications to Wireless Ad Hoc Networks.
  Thesis Advisor: Prof. Gopal Pandurangan
  Other Committee Members: Prof. Mikhail Atallah, Prof. Wojciech Szpankowski, and Prof. Suresh Jagannathan
• MS in Computer Science, Dec 2001
  North Dakota State University, Fargo, North Dakota, USA
  Thesis: Fast Distance Metric Based Data Mining Techniques Using P-trees
  Thesis Advisor: Prof. William Perrizo
  Other Committee Members: Prof. Bruce Erickson, Prof. John Martin, and Prof. Rao
• BS in Computer Science and Engineering, June 1996
  Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh
  Thesis: Performance Analysis of Multiprocessor Systems with Multilevel Cache

Awards

• Best Student Paper Award at the 20th International Symposium on Distributed Computing (DISC), Stockholm, Sweden, 2006. Here is a web story that appeared in the front page of Purdue Computer Science home page in Sep. 2006. Also mentioned in the ACM SIGACT News -- if you don't have access to the ACM DL, here is another copy.
• Bilsland Dissertation Fellowship, Purdue University, 2006-2007. Each year three graduate students are selected from the entire College of Science at Purdue University for this competitive fellowship.
• Merit Scholarship for securing 4th position in the competitive undergraduate entrance examination at Bangladesh University of Engineering and Technology, 1990. In Bangladesh, each year about 200,000 students in science graduate from high school and the best 4,000 among these 200,000 students get the opportunity to participate in this entrance exam.

Publications

New

1. Structural and Relational Properties of Social Contact Networks with Applications to Public Health Informatics. (Maleq Khan, V.S. Anil Kumar, Madhav Marathe, Zhao Zhao, Tridib Duta.)
2. Energy-Efficient Distributed Minimum Spanning Tree Construction: Tight Bounds and Algorithms. (Yongwook Choi, Maleq Khan, Anil Kumar, and Gopal Pandurangan.)

   Book Chapter

3. Theory of Communication Networks, Algorithms and Theory of Computation Handbook, second edition, CRC Press, Eds. Mikhail Atallah and Marina Blanton. a draft version. (Gopal Pandurangan and Maleq Khan.)

   Peer-Reviewed Journal Papers (articles marked with '*' have also a conference version)

4. *Energy-Optimal Distributed Algorithms for Minimum Spanning Trees, to appear in the Journal of Selected Areas in Communications, Vol. 27, No. 6, Sep 2009. (Yongwook Choi, Maleq Khan, Anil Kumar, and Gopal Pandurangan.)
5. Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, Pages 124-139, Vol. 20, No. 1, Jan 2009. (Maleq Khan, Gopal Pandurangan, and Anil Kumar.)
6. *A Fast Distributed Approximation Algorithm for Minimum Spanning Trees, Distributed Computing. Pages 391-402, Vol. 20, No. 6, Apr 2008. (Maleq Khan and Gopal Pandurangan.)
7. A Simple Randomized Scheme for Constructing Low-Weight k-Connected Spanning Subgraphs with Applications to Distributed Algorithms, Theoretical Computer Science, Pages 101-114, Vol. 385, No. 1-3, Oct. 2007. (Maleq Khan, Gopal Pandurangan, and Anil Kumar.)
8. *An Efficient Weighted Nearest Neighbor Classifier using Vertical Data Representation, International Journal of Business Intelligence and Data Mining, Vol. 2, No. 1, 2007. (William Perrizo, Qin Ding, Maleq Khan, Anne Denton, and Qiang Ding.)
9. Multimedia Data Transmission and Control using Active Networks, Journal of Computer Communications. Vol. 28, No. 6, Apr. 2005. (Bharat Bhargava, Sheng-Yih Wang, Maleq Khan and Ahsan Habib.)
10. Edge-to-Edge Measurement-Based Distributed Network Monitoring, Journal of Computer Networks, Vol. 44, No. 2, Feb. 2004. (Ahsan Habib, Maleq Khan, and Bharat Bhargava.)

    Peer-Reviewed Conference Papers (articles marked with '*' have also a journal version)

11. A Study of Information Diffusion over a Realistic Social Network Model, International Symposium on Social Computing Applications, Vancouver, Canada, Aug. 2009. (Andrea Apolloni, Karthik Channakeshava, Lisa Durbeck, Maleq Khan, Chris Kuhlman, Bryan Lewis, and Samarth Swarup)
12. Generation and Analysis of Large Synthetic Social Contact Networks, Winter Simulation Conference (WSC), Austin, Texas, Dec. 2009. (Christopher Barrett, Richard Beckman, Maleq Khan, V.S. Anil Kumar, Madhav Marathe, Paula Stretz, Tridib Dutta, and Bryan Lewis)
13. Bi-Criteria Approximation Algorithms for Power-Efficient and Low-Interference Topology Control in Unreliable Ad hoc Networks. 28th Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, Apr. 2009. (Maleq Khan, V.S. Anil Kumar, Madhav V. Marathe, Gopal Pandurangan, and S.S. Ravi.)
14. Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings. 27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, Aug. 2008. (Maleq Khan, Fabian Kuhn, Dahlia Malkhi, Gopal Pandurangan, and Kunal Talwar.)
15. *Energy-Optimal Distributed Algorithms for Minimum Spanning Trees. 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Munich, Germany, Jun. 2008. (Yongwook Choi, Maleq Khan, Anil Kumar, and Gopal Pandurangan.)
16. *A Fast Distributed Approximation Algorithm for Minimum Spanning Trees, 20th International Symposium on Distributed Computing (DISC), Sep. 2006, Stockholm, Sweden. Winner of the Best Student Paper Award -- a web story that appeared in the front page of Purdue Computer Science homepage in Sep. 2006. Also mentioned in the ACM SIGACT News -- if you don't have access to the ACM DL, here is another copy. (Maleq Khan and Gopal Pandurangan.)
17. *PINE - Podium Incremental Neighbor Evaluator for Classifying Spatial Data, ACM Symposium on Applied Computing (SAC), Melbourne, FL, USA, March 2003. (William Perrizo, Qin Ding, Anne Denton, Kirk Scott, Qiang Ding, and Maleq Khan.)
18. Fast k-Nearest Neighbor Classification on Spatial Data Streams Using P-trees, 6th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), Taipei, Taiwan, May 2002. (Maleq Khan, Qin Ding, and William Perrizo.)
19. The P-tree Algebra, ACM Symposium on Applied Computing (SAC), Madrid, Spain, March 2002. (Qin Ding, Maleq Khan, Amalendu Roy and William Perrizo.)

    Dissertation and Theses

20. Distributed Approximation Algorithms for Minimum Spanning Trees and Other Related Problems with Application to Wireless Ad Hoc Networks, Ph.D. dissertation, Department of Computer Science, Purdue University, West Lafayette, Indiana, 2007. (Maleq Khan)
21. Fast Distance Metric Based Data Mining Techniques Using P-trees, Masters thesis, Computer Science Department, North Dakota State University, Fargo, North Dakota, 2001. (Maleq Khan)
22. Performance Analysis of Multiprocessor Systems with Multilevel Cache, undergraduate thesis, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka, 1996. (Maleq Khan and Mahmud Hasan)

    Technical Reports

23. Energy-efficient distributed constructions of minimum spanning tree for wireless ad-hoc networks, Tech. Rep. CSD-TR-06-019, Department of Computer Science, Purdue University, October 2006. (Maleq Khan, Gopal Pandurangan, and V.S. Kumar)
24. Energy-Efficient Routing Schemes for Wireless Sensor Networks, Tech. Rep., CSD TR 03-013, Department of Computer Science, Purdue University, July 2003. (Maleq Khan, Gopal Pandurangan, and Bharat Bhargava)
25. Self-configuring Clusters, Data Aggregation, and Authentication in Microsensor Networks, Tech. Rep., CSD TR 03-005, Department of Computer Science, Purdue University, March 2003. (Maleq Khan, Bharat Bhargava, and Leszek Lilien)

Impact of Research

Talks

External Talks

• Efficient Distributed Approximation Algorithms via Probabilistic Tree Embeddings, at the 27th ACM Symposium on Principles of Distributed Computing (PODC), Toronto, Canada, Aug. 2008.
• Distributed Approximation Algorithms for Minimum Spanning Trees and Other Related Problems, Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, Virginia, July 2007.
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees, at the 20th International Symposium on Distributed Computing (DISC), Stockholm, Sweden, Sep 2006.
• Local Distributed Algorithms via Nearest Neighbor Tree
  -- invited talk at Bangladesh University of Engineering and Technology, Dhaka, Bangladesh, Jan 2005.
  -- at the 49th Midwest Theory Day, DePaul University, Chicago, Dec 2004.
• How to Learn Math and Science, for high-school students at a high school in Bangladesh, Jan 2005.
• Energy-Efficient Local Distributed Algorithms for Wireless Ad Hoc Networks, invited talk, as a guest lecturer for the graduate course CS 690B: Pervasive Systems", Fall 2004, Purdue University.
• Fast k-Nearest Neighbor Classification on Spatial Data Streams Using P-trees, at the 6th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), Taipei, Taiwan, May 2002.

  Talks given as Degree Requirements

• Distributed Approximation Algorithms for Minimum Spanning Trees and Other Related Problems with Applications to Wireless Ad Hoc Networks, PhD dissertation defense, Purdue University, Apr. 2007.
• Energy-Efficient Local Distributed Algorithms for Wireless Ad Hoc Networks, PhD preliminary examination, Purdue University, July 2004.
• Work-Efficient Distributed Algorithms, as a part of PhD qualifying examination, Purdue University, Jan. 2004.
• Fast Distance Metric Based Data Mining Techniques Using P-trees, MS thesis defense, North Dakota State University, Dec. 2001.

Professional Experience

• Virginia Bioinformatics Institute, Virginia Tech, Blacksburg, VA 24060
  Applied Computer Scientist, Postdoctoral Research Associate, Sep 2007 - current.
  Working on algorithmic and theoretical aspects of wireless ad hoc networks, social networks, and distributed algorithms.
• Purdue University, Department of Computer Sciences, West Lafayette, IN 47907
  -- Bilsland Dissertation Fellowship for research, Aug 2006 - July 2007
  -- Research Assistant, Jan 2002 - May 2006 (except Fall 2004 & Summer 2005) and Aug - Sep 2007;
  Research areas are distributed algorithms, algorithms for wireless ad hoc and sensor networks.
  -- Instructor, CS 235: Introduction to Organizational Computing, Summer 2005
  -- Teaching Assistant, CS 580: Algorithm Design, Analysis, and Implementation, Fall 2004
• ExaGrid Systems Inc., Westborough, MA 01581
  Summer Intern, May 2006 - Aug 2006
  I worked on their existing delta compression algorithm and code. I did research on this algorithm, improved the performance significantly and rewrote the code completely using C language in about 1600 lines. I worked under supervision of Dave Therrien, the Chief Technical Officer and Founder of the company.
• North Dakota State University, Computer Science Department, Fargo, ND 58105
  Research Assistant, Jan 2000 - Dec 2001
  The research work involved Data Mining of Remotely Sensed Image Data. Also worked on a development team of a web-based data mining software tool using Java.
• National University of Singapore, School of Computing, Singapore
  Research Assistant (full time job), Dec 1998 - Dec 1999
  The primary concern was using neural networks in data mining: using neural networks for classification, prediction, feature extraction, etc. Also developed a data-mining tool using Visual C++.
• American Int. University Bangladesh, Dept. of Computer Sc. & Engg., Dhaka, Bangladesh
  Lecturer, Sep 1998 - Nov 1998
  Courses taught: Discrete Mathematics, Introduction to Programming.
• East West University, Department of Computer Science, Dhaka, Bangladesh
  Lecturer, Mar 1997 - Aug 1998
  Courses taught: Discrete Mathematics, Mathematics for Computer Science, Structural Programming (Pascal), Programming with C and C++.
  Other responsibilities: creating class schedules, processing final grades of the students.
• North South University, Department of Computer Science, Dhaka, Bangladesh
  Teaching Assistant, Jun 1996 - Feb 1997

Professional Membership

• Member, Association for Computing Machinery (ACM)
• Member, SIGACT, ACM Special Interest Group on Algorithms and Computation Theory
• Member, Institute of Electrical and Electronics Engineers (IEEE)

Selected Projects

• Analysis and efficient implementation of a delta compression algorithm (data compression algorithm where difference between two versions of one or more files are found). 1600 lines of code was written in C and is in commercial use by ExaGrid Systems Inc.
• Implementation of scheduler, inter-process communication, semaphore, memory management, file systems, etc. for XINU operating system.
• Simulation of distributed MST algorithms for wireless networks.
• Secure routing in sensor networks.
• Implementation of back-forward function (multi-level undo-redoing of various kind of operations using a common button) in a web-based data mining tool for remotely sensed image data using Java.
• Design of a self-driving car.
• Construction of a neural network classifier and extraction of classification rules.
• Simulation and performance evaluation of multi-processor systems with multi-level cache and shared memory.
• Design and implementation of a 4-bit micro-computer.

Computer Skills

Courses

Graduate Courses

Related Undergraduate Courses

References

• Gopal Pandurangan (PhD advisor)
  Assistant Professor, Department of Computer Science
  Purdue University, West Lafayette, IN 47906
• Wojciech Szpankowski
  IEEE Fellow
  Professor, Department of Computer Science
  Purdue University, West Lafayette, IN 47906
• Mikhail Atallah
  ACM and IEEE Fellow
  Distinguished Professor, Department of Computer Science
  Purdue University, West Lafayette, IN 47906
• Madhav Marathe
  Deputy Director, Network Dynamics and Simulation Science Laboratory
  Professor, Virginia Bioinformatics Institute and Department of Computer Science
  Virginia Polytechnic Institute and State University, Blacksburg, VA 24061
• Leszek Lilien
  Assistant Professor, Department of Computer Science
  Western Michigan University, Kalamazoo, MI 49008
• Dave Therrien
  Chief Technical Officer and Founder
  ExaGrid Systems, Inc., Westborough, MA 01581