Jie Gao

1415 Computer Science Building

Stony Brook University

Stony Brook, NY 11794
Phone: 631-6329169

jgao at cs dot sunysb dot edu

 

 






Short Bio:

I am an assistant professor at Department of Computer Science, State University of New York, Stony Brook since Fall 2005. I obtained my Ph.D degree from Department of Computer Science, Stanford University in 2004 and my B.S. degree from the Special Class for the Gifted Young at University of Science and Technology of China in 1999. I spent the academic year 2004-2005 at Center for the Mathematics of Information, California Institute of Technology. I received NSF CAREER award in 2006.

Research Interests:

Algorithms, Networking, Computational geometry

   For more information, here is a short research statement.

Students: 

   My office hour for Summer 2009 is on Monday and Thursday. If you want to work with me on an independent study project, or you have an interesting problem to discuss, or simply chat a bit, please drop by my office. If you need a substantial chunk of my time, email me for an appointment.

If you have questions about graduate student admission, proficiency in algorithms, please read this.

Teaching:

Fall 2009 Wireless and Mobile Networks (Graduate)

Past teaching

Professional Activities:

Program Committee:

Publications: By topic | By date

Ad hoc communication and sensor networks

  1. Rik Sarkar, Xiaotian Yin, Jie Gao, Feng Luo, Xianfeng David Gu, Greedy Routing with Guaranteed Delivery Using Ricci Flows, Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN'09), 121-132, April, 2009. Bibtex. We use Ricci flow to convert a sensor field with holes such that all the holes are perfectly circular --- greedy forwarding will never get stuck.

  2. Jie Gao, Leonidas J. Guibas, Nikola Milosavljevic, Dengpan Zhou, Distributed Resource Management and Matching in Sensor Networks, Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN'09), 97-108, April, 2009. Bibtex. Slides. We study the problem of distributed matching of events (e.g., cars) with resources (e.g., empty parking spots) detected by a sensor network with the objective of minimizing the sum of distances of the matching. The key is to extract a hierarchical separated tree (HST) and apply greedy matching algorithm on the tree (match the closest pair, remove them and continue). 

  3. Yue Wang, Sol Lederer, Jie Gao, Connectivity-based Sensor Network Localization with Incremental Delaunay Refinement Method, Proc. of the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09), April, 2009. Also presented at 18th Fall Workshop on Computational Geometry, Oct 31-Nov 1, 2008. Bibtex. Slides. This is a follow-up paper of our INFOCOM'08 paper. We developed an incremental method to select landmarks such that the resulted combinatorial Delaunay complex is rigid and well represents the sensor field shape, which is then used for anchor-free connectivity-based localization of the network.

  4. Dengpan Zhou, Jie Gao, Opportunistic Processing and Query of Motion Trajectories in Wireless Sensor Networks, Proc. of the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09), April, 2009. Bibtex.  

  5. Xianjin Zhu, Rik Sarkar, Jie Gao, Topological Data Processing for Distributed Sensor Networks with Morse-Smale Decomposition, Proc. of the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09), Mini-conference, April, 2009. Bibtex.

  6. Rik Sarkar, Xianjin Zhu, Jie Gao, Spatial Distributions in Routing Table Design for Sensor Networks, Proc. of the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09), Mini-conference, April, 2009. Bibtex. Also presented at 18th Fall Workshop on Computational Geometry, Oct 31-Nov 1, 2008. Here is a recent talk I gave on this and another IPSN'07 paper. We store in routing table the paths selected with a geometric spatial distribution such that the average routing table size is \sqrt{n} and 1+\eps routing path can be achieved with local greedy routing.

  7. Huijia Lin, Maohua Lu, Nikola Milosavljevic, Jie Gao, Leonidas J. Guibas, Composable Information Gradients in Wireless Sensor Networks, Proc. of the International Conference on Information Processing in Sensor Networks (IPSN'08), 121-132, April, 2008. Bibtex. We propose to build a potential field with harmonic functions at data sources such that greedy routing with the potential is guaranteed to reach a source.

  8. Xianjin Zhu, Rik Sarkar, Jie Gao, Joseph S. B. Mitchell, Light-weight Contour Tracking in Wireless Sensor Networks, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 960-967, May, 2008. Bibtex. Slides. Also presented in the 17th Fall Workshop on Computational and Combinatorial Geometry, Nov, 9-10, 2007. 

  9. Rik Sarkar, Xianjin Zhu, Jie Gao, Leonidas J. Guibas, Joseph S. B. Mitchell, Iso-Contour Queries and Gradient Descent with Guaranteed Delivery in Sensor Networks, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 1175-1183, May, 2008. Bibtex. Slides. Also presented in the 17th Fall Workshop on Computational and Combinatorial Geometry, Nov, 9-10, 2007. A distributed algorithm to build a contour tree in a sensor network and the applications in iso-contour queries.

  10. Anand Prabhu Subramanian, Pralhad Deshpande, Jie Gao, Samir R. Das, Drive-by Localization of Roadside WiFi Networks, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 718-725, May, 2008. Bibtex. Use directional antennas mounted on moving vehicles to localize WiFi access points.

  11. Sol Lederer, Yue Wang, Jie Gao, Connectivity-based Localization of Large Scale Sensor Networks with Complex Shape, Proc. of the 27th Annual IEEE Conference on Computer Communications (INFOCOM'08), 789-797, May, 2008. Bibtex. Slides. Journal version in ACM Transactions on Sensor Networks, 5(4), November, 2009. The main challenge in anchor-free localization is to avoid flip ambiguities -- a part of the network folds on top of the other. We extract a combinatorial Delaunay complex on landmarks selected in a sensor network to help network localization. The insight is that two adjacent Delaunay triangles must be embedded side-by-side. An algorithm is developed to construct a globally rigid Delaunay complex for localization of a large sensor network with complex shape.  

  12. Jie Gao, Leonidas J. Guibas, John Hershberger, Nikola Milosavljevic, Sparse Data Aggregation in Sensor Networks, Proc. of the International Conference on Information Processing in Sensor Networks (IPSN'07), 430-439, April, 2007. Bibtex. We developed an algorithm to aggregate simultaneously emerging eveaqnts sparsely located in a sensor network, with a total communication cost of O(log n) |MST|. 

  13. Rik Sarkar, Xianjin Zhu, Jie Gao, Hierarchical Spatial Gossip for Multi-Resolution Representations in Sensor Networks, Proc. of the International Conference on Information Processing in Sensor Networks (IPSN'07), 420-429, April, 2007. Bibtex, Slides. We use spatial gossip to build, for each sensor v, the aggregation of all the sensors within 2^i hop from v, for i=0, ..., log n. The total communication cost is near linear.

  14. Xianjin Zhu, Rik Sarkar, Jie Gao, Shape Segmentation and Applications in Sensor Networks, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 1838-1846, May, 2007. Bibtex. Slides. Also presented in the 16th Fall Workshop on Computational and Combinatorial Geometry, Nov, 10-11, 2006. Journal version under the title Segmenting a Sensor Field: Algorithms and Applications in Network Design in ACM Transactions on Sensor Networks, 2009. We segment a sensor field with irregular shape into nice near convex pieces. 

  15. Ritesh Maheshwari, Jie Gao, Samir R. Das, Detecting Wormhole Attacks in Wireless Networks Using Connectivity Information, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 107-115, May, 2007. Bibtex. Poster presented at IEEE SECON 2006, Sep, 2006. 

  16. An Nguyen, Nikola Milosavljevic, Qing Fang, Jie Gao, Leonidas J. Guibas, Landmark Selection and Greedy Landmark-descent Routing for Sensor Networks, Proc. of the 26th Annual IEEE Conference on Computer Communications (INFOCOM'07), 661-669, May, 2007. Bibtex.

  17. Rik Sarkar, Xianjin Zhu, Jie Gao, Double Rulings for Information Brokerage in Sensor Networks, The 12th Annual International Conference on Mobile Computing and Networking (MobiCom'06), 286-297, September, 2006. Bibtex. Slides. Journal version accepted to IEEE/ACM Transaction on Networking, 2009. We hash data to circles in a sensor network such that retrieval along other circles are guaranteed to find the data with cost O(d) with d as the true distance between data source and query node. 

  18. Yue Wang, Jie Gao, Joseph S.B. Mitchell, Boundary Recognition in Sensor Networks by Topological Methods, The 12th Annual International Conference on Mobile Computing and Networking (MobiCom'06), 122-133, September, 2006. Bibtex, Slides. Detect network boundaries by detecting cut locus -- the collection of points with multiple shortest paths to a single source.  

  19. Amitabh Basu, Jie Gao, Joseph S.B. Mitchell, Girishkumar Sabhnani, Distributed Localization by Noisy Distance and Angle Information, Proc. of the Seventh ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'06), 262-273, May, 2006. Bibtex.

  20. Qing Fang, Jie Gao, Leonidas J. Guibas, Landmark-Based Information Storage and Retrieval in Sensor Networks, The 25th Conference of the IEEE Communication Society (INFOCOM'06), April, 2006. Bibtex. 

  21. Jehoshua Bruck, Jie Gao, Anxiao Jiang, MAP: Medial Axis Based Geometric Routing in Sensor Networks, Proc. of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom’05), 88-102, August, 2005. Journal version invited to Wireless Networks (WINET) special issue from MobiCom'05. Slides. Bibtex. Use medial axis to build a routing map for routing around holes. 

  22. Jehoshua Bruck, Jie Gao, Anxiao Jiang, Localization and Routing in Sensor Networks by Local Angle Information, Proc. of the Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05), 181-192, May, 2005. Journal version in ACM Transactions on Sensor Networks, 5(1), February, 2009. Slides. Bibtex. It is NP-hard to embed a unit disk graph even when the angles between adjacent edges are given.  

  23. Jie Gao, Leonidas J. Guibas, An Nguyen, Distributed Proximity Maintenance in Ad Hoc Mobile Networks, Proc. of the IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS'05), 4-19, June, 2005. Here is the full version. Slides. Bibtex. Maintain a distributed spanner among mobile nodes. 

  24. Qing Fang, Jie Gao, Leonidas J. Guibas, Vin de Silva, Li Zhang, GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks, Proc. of the 24th Conference of the IEEE Communication Society (INFOCOM'05), volume 1, pages 339-350, March, 2005. Slides. Bibtex. We select landmarks in a sensor network and build the combinatorial Delaunay graph to capture the network holes. The distance vector to the landmarks are used to implement greedy point to point routing. 

  25. Jie Gao, Li Zhang, Tradeoffs between Stretch Factor and Load Balancing Ratio in Routing on Growth Restricted Graphs, Proc. of the 23rd ACM Symposium on Principles of Distributed Computing (PODC'04), 189-196, July, 2004. Journal version accepted to IEEE Transactions on Parallel and Distributed Systems, 2008. Slides. Bibtex. In a graph where the growth rate is bounded (the number of nodes within k hops grows as a polynomial of k), the stretch factor and load balancing ratio are inversely proportional. 

  26. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, Fractionally Cascaded Information in a Sensor Network, Proc. of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN'04), 311-319, April, 2004. Bibtex.

  27. Jie Gao, Li Zhang, Load Balanced Short Path Routing in Wireless Networks, The 23rd Conference of the IEEE Communications Society (INFOCOM), vol. 23, no. 1, 1099-1108, March, 2004. Journal version in IEEE Transactions on Parallel and Distributed Systems, Special Issue on Localized Communication, vol. 17, no. 4, 377-388, April, 2006. Slides. Bibtex.

  28. Qing Fang, Jie Gao, Leonidas J. Guibas, Locating and Bypassing Routing Holes in Sensor Networks, The 23rd Conference of the IEEE Communications Society (INFOCOM), vol. 23, no. 1, 2458-2468, March 2004. Journal version in MONET Special Issue on Foundations of Mobile Computing, 11, 187-200, 2006. Bibtex. Detect network holes with location information. 

  29. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu, Geometric Spanner for Routing in Mobile Networks, Proc. of the 2nd ACM Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc'01), 45-55, October 2001. Journal version in IEEE Journal on Selected Areas in Communications Wireless Ad Hoc Networks (J-SAC), 23(1), 174-185, January, 2005. Bibtex. Use restricted Delaunay graph (RDG) in GPSR. RDG is a planar graph that contains all the Delaunay edges of length no greater than 1. 

Computational Geometry, Data Structures, Algorithms

  1. Jie Gao, Dengpan Zhou, The emergence of Sparse Spanners and Greedy Well Separated Pair Decomposition, arXiv, 2009. Presented at the 18th Fall Workshop on Computational Geometry, Oct 31-Nov 1, 2008. We show the following algorithm outputs a 1+e spanner with O(n/ed) edges for n points in Rd: each node p builds an edge pq if and only if there is no edge p'q' with p',q' within distance O(e)|pq| from p,q  respectively. If we select an arbitrary pair not yet covered and put a `dumb-bell' around it as a well-separated pair. Repeat this greedy algorithm until all pairs of points are covered, we get a well-separated pair decomposition with size O(n).

  2. Jie Gao, Michael Langberg, Leonard Schulman, Clustering Lines in High Dimensional Space: Classification of Incomplete Data, ACM Transaction on Algorithms, under submission, 2009. This is a followup of our SODA'06 paper. We propose 2+e approximation algorithms for 2-center and 3-center problem of lines in Rd with Ố(nd) running time. To do this, we develop a new Helly theorem for crosses: if any n crosses have no common intersection, then there is a subset of O(1/e) crosses, each contracted by a factor of 1-e, that have no common intersection.

  3. Jie Gao, Leonidas J. Guibas, Steve Y. Oudot, Yue Wang, Geodesic Delaunay Triangulation and Witness Complex in the Plane, Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA'08), 571-580, January, 2008. Bibtex.

  4. Jehoshua Bruck, Jie Gao, Anxiao Jiang, Weighted Bloom Filter, 2006 IEEE International Symposium on Information Theory (ISIT'06), July, 2006. Bibtex.

  5. Jie Gao, Michael Langberg, Leonard Schulman, Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem, Proc. of ACM-SIAM Symposium on Discrete Algorithms (SODA'06), 464-473, January, 2006. Slides. Bibtex. Journal version appeared in Discrete and Computational Geometry, 40(4), 537-560, 2008. For n lines L in Rd, if any three lines can be intersected by a ball of radius r, then all the lines can be intersected by a ball of radius 2r. We also find a coreset of size O(1/e) such that the minimum radius ball intersecting the coreset is at least 1-e that of L. This leads to an algorithm of near linear running time (i.e., O(nd)) to find a 1-center of a set of lines with approximation ratio 1+e.

  6. Pankaj K. Agarwal, Mark de Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-Peled, Staying in the Middle: Exact and Approximate Medians in R1 and R2 for Moving Points, Proc. of the 17th Canadian Conference on Computational Geometry (CCCG'05), 42-45, August, 2005. Here is the full version. Slides. Bibtex.  

  7. Jie Gao, Leonidas J. Guibas, An Nguyen, Deformable Spanners and Applications, Proc. of the 20th ACM Symposium on Computational Geometry (SoCG'04), 190-199, June, 2004. Journal version invited to Computational Geometry : Theory and Applications, 35, 2-19, 2006. Slides. Bibtex. A kinetic data structure to maintain a 1+e spanner with O(n) edges for moving points.   

  8. Jie Gao, Li Zhang, Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and its Applications, Proc. the 35th ACM Symposium on Theory of Computing (STOC'03), 483-492, June, 2003. Journal version appeared in SIAM J. Computing, 35(1), 151-169, 2005. Slides. Bibtex. For a unit disk graph, one can find a well-separated pair decomposition with O(nlogn) pairs. This is useful to speed up graph problems on UDGs.

  9. Pankaj K. Agarwal, Jie Gao, Leonidas J. Guibas, Kinetic Medians and kd-trees, Proc. of the 10th Annual European Symposium on Algorithms (ESA'02), Lecture Notes in Computer Science 2461, 5-16, September 2002. Bibtex. A kinetic data structure to maintain kd-trees. 

  10. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, An Zhu, Discrete Mobile Centers, Proc. of the 17th ACM Symposium on Computational Geometry (SoCG'01), 188-196, June 2001. Journal version invited to Discrete and Computational Geometry, 30(1), 45-65, 2003. Bibtex. A kinetic data structure to maintain a clustering of moving points. Every point is within distance 1 of at least one center. The number of cluster centers is a constant approximation of the minimum possible.

Thesis

  1. Jie Gao, Hierarchical Data Structures for Mobile Networks, Ph.D dissertation, Stanford University, August 2004. Bibtex.

    2.

Disclaimer: The materials published on this site are for non-commercial use such as research and teaching. They are under various copyright. Please refer to ACM copyright policy for an example.

Last updated: 5/19/2009