Jie Gao

1415 Computer Science Building

Stony Brook University

Stony Brook, NY 11794

631-632-9169

369 CEWIT Building

631-632-5987

jgao at cs dot stonybrook dot edu

Short Bio:

I am an Associate Professor at Department of Computer Science, Stony Brook University. I received Ph.D degree from Department of Computer Science, Stanford University in 2004 and 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 and CS department Research Excellence Award in 2012.

Research Interests:

Algorithms, Networking, Computational Geometry

  A short research statement and my cv.

Teaching:

Fall 2014 CSE548/AMS542 Analysis of Algorithms (TuTh 10-11:20am CS2120)

Fall 2014 AMS345/CSE355 Computational Geometry (ThTh 11:30-12:50 Engineering 143)

Past teaching

Students:   

    My office hour in Fall 2014 is Tuesday Thursday 1:20-2:20pm. In case of emergency please email me or find me on skype (skype ID jiegao79). If you have questions about graduate student admission, proficiency in algorithms, please read this. I also collected a few tips on Latex, writing papers, and giving talks.

Graduated Ph.D students
Current Ph.D students
Xianjin Zhu (co-advised with Himanshu Gupta), May 2008. Dengpan Zhou, May 2012. Siming Li Kin Sum Liu
Yue Wang (co-advised with Joe Mitchell), May 2009. Xiaomeng Ban, December 2012. Jiemin Zeng
Sol Lederer, December 2009. Akshay Patil, August 2013 Golnaz Ghasemiesfeh
Rik Sarkar, May 2010.
Chien Chun Ni
Rupa Krishnan, August 2010.
Jiaxin Ding

  
Professional Activities:
 

Associate Editor for ACM Transactions on Sensor Networks (since 2009), IEEE Transactions on Automation Science and Engineering (since 2010),

Current Program Committee: INFOCOM'15, General chair of ALGOSENSOR'14, IPSN'15, EWSN'15, etc.

Recent Talks:

Publications: By topic | By date

Ad hoc communication and sensor networks

Surveys and Chapters
  1. Jie Gao, Leonidas J. Guibas, Geometric Algorithms for Sensor Networks, invited to Philosophical Transactions of the Royal Society A, vol. 370, no. 1958, 27-51, Janurary 2012.

  2. Jie Gao, Geometric Routing in Wireless Sensor Networks, invited to Guide to Wireless Sensor Networks, Springer-Verlag, 2009.

Social Network Analysis

  1. Xiaomeng Ban, Jie Gao, Arnout van de Rijt, Navigation in Real-World Complex Networks through Embedding in Latent Spaces, Workshop on Algorithm Engineering and Experiments (ALENEX10), 138-148, January, 2010. BibtexThis is an experimental paper. We take a number of real world complex networks, both social and non-social, and examine their embedding in Euclidean and hyperbolic spaces and the performance of greedy routing with the embedded coordinates. Surprisingly, even with standard techniques such as multi-dimensional scaling in constant dimensional spaces, greedy routing not only delivers a majority set of packets but also uses paths of length of roughly 6 hops at most.

  2. Akshay Patil, Juan Liu, Jie Gao, Predicting Group Stability in Online Social Networks, Proceedings of the 22nd International World Wide Web Conference (WWW'13), May 13-17, 2013. We studied the data set from World of Warcraft (WoW) and focus on the formation and destruction of guilds (groups) by the online players. 
  3. Golnaz Ghasemiesfeh, Roozbeh Ebrahimi, Jie Gao, Complex Contagion and The Weakness of Long Ties in Social Networks: Revisited, Proceedings of the 14th ACM Conference on Electronic Commerce (EC'13), June 16-20, 2013. Talk slides. Information, diseases or viruses could spread fast in a social network due to the small world property. These are "simple contagions" as one can be infected through a single contact. Other behavior changes such as technology innovation and immigration are "complex contagions" which requires multiple simultaneous contacts. We show that complex contagion is very slow (in polynomial # rounds) for Newman-Watts model but is still fast (in polylogarithmic # rounds) in Kleinberg's small world model and Kleinberg's hierarchical model. 

  4. Akshay Patil, Golnaz Ghasemiesfeh, Roozbeh Ebrahimi, Jie Gao, Quantifying Social Influence in Epinions, Proceedings of ASE/IEEE International Conference on Social Computing (SocialCom), September 8-14, 2013. It was also invited to ASE Science Journal.

  5. Akshay Patil, Juan Liu, Jianqiang Shen, Oliver Brdiczka, Jie Gao, John Hanley, Modeling Attrition in Organizations From Email Communication, Proceedings of ASE/IEEE International Conference on Social Computing (SocialCom), September 8-14, 2013.
  6. Roozbeh Ebrahimi, Jie Gao, Golnaz Ghasemiesfeh, Grant Schoenebeck, How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks, arXiv:1404.2668, 2014. We show that complex contagions spread in a preferential attachment graph, and in a more general family of time evolving graphs, if the initial seeds are chosen as the first few in the arriving order. Otherwise, if the initial seeds are randomly selected, unless there are \sqrt{n} of them, complex contagions do not spread to the entire graph.

  7. Roozbeh Ebrahimi, Jie Gao, Golnaz Ghasemiesfeh, Grant Schoenebeck, Complex Contagions in Kleinberg's Small World Model, arXiv:1408.2159, 2014. This is a followup of the EC'13 paper resolving almost all cases of Kleinberg's small world model. We show that there is a sweet spot interval for the parameter in the exponent of the distribution of random edges such that complex contagions spread in polylogarithmic number of rounds. Otherwise, the random edges are either too random or too short for complex contagions to spread fast.

Differential Geometry and Applications in Sensor Network Routing

  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. Here is a set of slides from a recent talk. We use Ricci flow to convert a sensor field with holes such that all the holes are circular --- greedy forwarding will never get stuck.

  2. Wei Zeng, Rik Sarkar, Feng Luo, Xianfeng David Gu, Jie Gao, Resilient Routing for Sensor Networks using Hyperbolic Embedding of Universal Covering Space, Proc. of the 29th Annual IEEE Conference on Computer Communications (INFOCOM'10), 1694-1702, March, 2010. Bibtex. Also presented at the 19th Fall Workshop on Computational Geometry, Nov 13-14, 2009. We show an embedding of a sensor network to many isometric patches in the hyperbolic spaces that are nicely glued along the boundaries, s.t. the paths connecting a source in one patch to different images in other patches represent paths in the original network with different homotopy types (i.e., getting around holes in different ways). Greedy routing can be used to route in the embedded space to find paths of a given homotopy type.  

  3. Rik Sarkar, Wei Zeng, Jie Gao, Xianfeng David Gu, Covering Space for In-Network Sensor Data Storage, Proc. of the 9th International Symposium on Information Processing in Sensor Networks (IPSN'10), 232-243, April, 2010. Bibtex. Here is a set of slides from a recent talk. This is a followup paper of our IPSN'09 paper. We first use Ricci flow to deform any sensor network such that the holes are all circular. Then we reflect the network against each circular hole (a special Mobius transformation) recursively to `fill up' the holes. The resulted covering space has applications in improving the load balancing performance of data-centric storage schemes (GHT, double rulings, etc) since the network shape is now regulated to be a circular, regular shape.

  4. Rik Sarkar, Jie Gao, Differential Forms for Target Tracking and Aggregate Queries in Distributed Networks, Proc. of the 16th Annual International Conference on Mobile Computing and Networking (MobiCom'10), 377-388, September, 2010. Bibtex. Journal version accepted to IEEE/ACM Transactions on Networking, 2012. Slides (pptx, pdf). In this paper we maintain differential 1-form on a planar graph for target tracking and queries. Each edge is given a weight such that the integration along any cycle gives the number of targets within the cycle. When a target moves from one face to an adjacent face, we simply subtract the weight of the target from the weight of the edge just crossed. Thus target motion only trigger local updates to the differential forms. 

  5. Xiaokang Yu, Xiaomeng Ban, Rik Sarkar, Wei Zeng, Xianfeng David Gu, Jie Gao, Spherical Representation and Polyhedron Routing for Load Balancing in Wireless Sensor Networks, Proc. of the 30th Annual IEEE Conference on Computer Communications (INFOCOM'11), 612-615, mini-conference, March, 2011. Also presented at 20th Fall Workshop on Computational Geometry, Oct 29-30, 2010. Bibtex. Slides (pptx).  In this paper we compute by using circle packing the Thurston embedding of a 3-connected planar graph as a skeleton graph of a convex polytope in 3D. This embedding is useful as it not only supports greedy routing with guaranteed delivery but also has nice load balancing properties -- as compared in the case of geographical routing that overloads the center of the network. . 
  6. Ruirui Jiang, Xiaomeng Ban, Mayank Goswami, Wei Zeng, Jie Gao, Xianfeng David Gu, Exploration of Path Space using Sensor Network Geometry, Proc. of the 10th International Symposium on Information Processing in Sensor Networks (IPSN'11), 49-60, April, 2011. Bibtex. Slides (pptx). This builts on top of our IPSN'09 paper and exploits the freedom of the Mobius transformation for (1) multipath routing (2) fast recovery of link failures. In our IPSN'09 paper we show how to embed a network into a circular domain such that all holes are circular. Such circular domains are not unique and differ by a Mobius transformation. By choosing a proper Mobius transformation we get multiple paths (with guaranteed delivery) and we can switch to a different path when encountering a link failure.

  7. Xiaokang Yu, Xiaotian Yin, Wei Han, Jie Gao, Xianfeng David Gu, Scalable Routing in 3D High Genus Sensor Networks Using Graph Embedding, Proc. of the 31st Annual IEEE Conference on Computer Communications (INFOCOM'12), mini-conference, 2681-2685, March, 2012. Slides (pptx). We use graph embedding technique to embed any graph onto a high genus surface. Then we cut the surfaces into "pants" on which hyperbolic routing can guarantee delivery. This method works for any arbitrary graph and is particularly interesting for low-density, topologically complex 3D sensor networks. 

  8. Xiaomeng Ban, Mayank Goswami, Wei Zeng, Xianfeng David Gu, Jie Gao, Topology Dependent Space Filling Curves for Sensor Networks and Applications, Proc. of the 32nd Annual IEEE Conference on Computer Communications (INFOCOM'13), April, 2013. By deforming a network into a regular shape (a disk, a torus or a torus with slits), one can generate a continuous, dense curve that covers the domain. This curve can be used as a "space filling curve" suitable for any network tasks requiring linearization.

  9. Siming Li, Wei Zeng, Dengpan Zhou, Xianfeng David Gu, Jie Gao, Compact Conformal Map for Greedy Routing in Wireless Mobile Sensor Networks, Proc. of the 32nd Annual IEEE Conference on Computer Communications (INFOCOM'13), April, 2013. This is to improve the IPSN'09 paper in the setting of a mobile network. The idea is to pre-compute a conformal map of the geometric domain on which mobile sensors are deployed. The map is encoded by a small number of parameters and pre-loaded to the mobile sensors so that each can compute its new coordinates directly under movement.  

  10. Rui Shi, Mayank Goswami, Jie Gao, Xianfeng David Gu, Is Random Walk Truly Memoryless - Traffic Analysis and Source Location Privacy Under Random Walks, Proc. of the 32nd Annual IEEE Conference on Computer Communications (INFOCOM'13), April, 2013. Slides. Random walk is often adopted to provide source location privacy, since a random walk longer than the mixing time converges to a random stationary distribution. We show that simply using random walk by itself may not protect location privacy at all -- by monitoring the how packets following random walk hit the boundary of a sensor network on a domain, we can infer the source location with good accuracy by integrating the harmonic measure along the boundary. 

  11. Mayank Goswami, Chien-Chun Ni, Xiaomeng Ban, Jie Gao, David Xianfeng Gu, Vamsi Pingali, Load Balanced Short Path Routing in Large-Scale Wireless Networks Using Area-Preserving Maps, Proc. of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc'14), August, 2014. We address load balanced routing in a network densely deployed inside a simply connected geometric region. We show first that an area preserving map f would keep the load balancing ratio of an algorithm by a factor of d^2, where d is the length stretch of f. Thus by mapping the given network to a disk we have bounds on both path stretch and the load balanced ratio. 

Landmark-based Routing
  1. 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. 

  2. 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. BibtexUsing distances to landmarks, it is easier to implement "pulling" from the landmarks rather than "pushing" away by the landmarks. This paper shows how to use "pulling forces" only to get bounded stretch greedy routing.

  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. Journal version under the title, Geodesic Delaunay Triangulations in Bounded Planar Domains, invited to a special issue of ACM Transactions on Algorithms (TALG), 6(4), 2010. This paper provides the theoretical foundations of "landmark Delaunay complex" used in routing (INFOCOM'05 paper by Q. Fang et.al) and localization (INFOCOM'08 paper by S. Lederer et. al). That is, how should landmarks be selected such that the landmark Delaunay complex captures the precise topological features of the underlying environment.

  4. Michael Biro, Jie Gao, Justin Iwerks, Irina Kostitsyna, Joseph S.B. Mitchell, Combinatorics of Beacon Routing and Coverage, Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG'13), August 8-10, 2013.
Other Geometric Routing Methods
  1. 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. 

  2. 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, 2766-2770, April, 2009. Bibtex. Also presented at 18th Fall Workshop on Computational Geometry, Oct 31-Nov 1, 2008. Here is a talk I gave on this and the IPSN'07 paper on spatial gossip. Journal version under title "Distributed and Compact Routing Using Spatial Distributions in Wireless Sensor Networks" accepted to ACM Transactions on Sensor Networks, 9(4), Nov, 2013. We store in routing tables 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.

  3. Jie Gao, Dengpan Zhou, Resilient and Low Stretch Routing Through Embedding into Tree Metrics, Proc. of the 12th Algorithms and Data Structures Symposium (WADS'11), 438-450, August, 2011. We show that by using two hierarchical separated trees (HSTs), one can approximate a metric with constant growth rate with constant distortion. This is applied for low stretch and resilient routing.

  4. Kan Huang, Chien-Chun Ni, Rik Sarkar, Jie Gao, Joseph Mitchell, Bounded Stretch Geographic Homotopic Routing in Sensor Networks, Proceedings of the 33rd Annual IEEE Conference on Computer Communications (INFOCOM'14), April, 2014. This paper presented a distributed algorithm that computes routing path of constant stretch for a given homotopy type.
Load Balanced Routing
  1. 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 versionSlides. BibtexWhen wireless nodes are located inside a narrow strip or on a line, we can find a local greedy algorithm that delivers packets with a constant stretch such that the maximum load of any node is within a constant factor of the optimal. in IEEE Transactions on Parallel and Distributed Systems, Special Issue on Localized Communication, vol. 17, no. 4, 377-388, April, 2006.

  2. 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 in IEEE Transactions on Parallel and Distributed Systems, 20(2), 171-179, 2009. 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. A tight bound is proved. 

Network Localization
  1. 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), 1-31, February, 2009. Slides. Bibtex. It is NP-hard to embed a unit disk graph even when the angles between adjacent edges are given. But, using only local angle information one can extract the restricted Delaunay graph, which is a planar graph including all Delaunay edges of length no more than 1.  

  2. 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. BibtexThis paper proves various versions of localization problem are NP-hard when noisy angle and distance information is given. It also uses a distributed algorithm that iteratively refines the feasible region of each node to find its possible locations. 

  3. 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.

  4. 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. Bibtex. 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. 

  5. 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), 2401-2409, 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.

Sensor Deployment
  1. Hua Huang, Chien-Chun Ni, Jie Gao, Xiaomeng Ban, Andrew Schneider, Shan Lin, Connected Wireless Camera Network Deployment with Visibility Coverage, Proc. of the 33rd Annual IEEE Conference on Computer Communications (INFOCOM'14), April, 2014.
In-network Processing, Storage and Query
  1. 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.  The information from a sensor is stored in a cascaded manner allowing users to answer range queries efficiently. We show almost tight upper and lower bound for range queries. 

  2. 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), 1-12, April, 2006. Bibtex. "Double rulings" refer to schemes where information is stored along a curve such that a user query along another curve will intersect the storage curve and retrieve the data. This paper combines the double ruling with a landmark hierarchy to provide efficient in-network data query. 

  3. 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 appeared in IEEE/ACM Transaction on Networking, 17(6), 1902-1915, December, 2009. Bibtex. 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. 

  4. 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. Journal version accepted to ACM Transactions on Sensor Networks, 8(1), Feb, 2012. 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 for all the sensors to build their respective multi-resolution aggregates is near linear.

  5. 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. Locally detected events sparsely spread in the network autonomously discover each other in a distributed fashion and form an aggregation structure that can be used to compute cumulants, moments, or other statistical summaries on the events. The total communication cost is O(log n) |MST|.

  6. 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.

  7. 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), 1197-1205, April, 2009. Bibtex 

  8. 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. SlidesWe 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). 

  9. Dengpan Zhou, Jie Gao, Maintaining Approximate Minimum Steiner Tree and k-center for Mobile Agents in a Sensor Network, Proc. of the 29th Annual IEEE Conference on Computer Communications (INFOCOM'10), 511-515, mini-conference, March, 2010. Bibtex. Also presented at the 19th Fall Workshop on Computational Geometry, Nov 13-14, 2009. We use the hierarchical well-separated tree (as shown in our previous paper in IPSN'09) to maintain a O(log n) approximate minimum Steiner tree & k-center for mobile agents such that each hop move for an agent incurs O(log n) message cost.

  10. Michele Albano, Jie Gao, In-Network Coding for Resilient Sensor Data Storage and Efficient Data Mule Collection, Proc. of the 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSOR'10), 105-117, July, 2010. Bibtex. SlidesThis paper uses spatial gossip for constructing random linear codes in sensor networks such that a data mule can simply pick up enough codewords from any nodes to reconstruct the original sensor data. The total communication cost for constructing the codewords is O(n polylogn).

  11. Navid Azimi, Himanshu Gupta, Xiaoxiao Hou, Jie Gao, Data Preservation Under Spatial Failures in Sensor Networks, Proc. of the 11th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'10), 171-180, September, 2010. Bibtex.

  12. Andreas Loukas, Marco Zuniga, Ioannis Protonotarios, Jie Gao, How to Identify Global Trends From Local Decisions? Spatial Event Detection on Mobile Networks, Proc. of the 33rd Annual IEEE Conference on Computer Communications (INFOCOM'14), April, 2014.
Topological Methods for Sensor Networks
  1. 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 locally with sensor location information.

  2. 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.   

  3. 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 appeared in ACM Transactions on Sensor Networks, 5(2), 1-32, 2009. BibtexWe segment a sensor field with irregular shape into nice near convex pieces such that data processing tasks can be done in each piece resulting in better overall performance. 

  4. 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.

  5. 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. 

  6. 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, 2911-2915, April, 2009. Bibtex.

  7. Pradipta Ghosh, Jie Gao, Andrea Gasparri, Bhaskar Krishnamachari, RiverSwarm: Topology-Aware Distributed Planning for Obstacle Encirclement in Connected Robotic Swarms, Proceedings of the First Workshop on Robotic Sensor Networks (RSN'14), April, 2014.

Sensor Network Security
  1. Sol Lederer, Jie Gao, Radu Sion, Collaborative Location Certification for Sensor Networks, invited to Proc. of the 2008 IEEE Sarnoff Symposium. April, 2008. Under the title "On Certifying Location claims in Sensor Networks" presented at the Conference of Applied Cryptography and Network Security (ACNS), industrial track, 2007. Journal version published in ACM Transactions on Sensor Networks (TOSN), 6(4), 2010. Bibtex. In a hostile environment, an adversary may capture a node and use it to report bogus events to the base station representing a fake location. We propose a collaborative scheme in which the sensor nodes certify location claims.

  2. 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. A wormhole attack causes far away nodes to appear to be directly connected, thus messing up the routing schemes. We observe that the fake wormhole links will violate packing properties in standard unit disk graph like models. Thus by detecting such forbidden structures one can identify and isolate bogus wormhole links using only local information.

  3. Xiaomeng Ban, Rik Sarkar, Jie Gao, Local Connectivity Tests to Identify Wormholes in Wireless Networks, Proc. of the 12th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'11), 13:1-13:11, May, 2011. We defined a wormhole as adding a bipartite subgraph to the legitimate  network topology. We also present a local, distributed algorithm to detect the bipartite subgraph structure and show that the tests are sufficient and necessary.  

  4. Khuong Vu, Rong Zheng, Jie Gao, Efficient Algorithms for K-Anonymous Location Privacy in Participatory Sensing, Proc. of the 31st Annual IEEE Conference on Computer Communications (INFOCOM'12), 2399-2407, March, 2012.

Other Networking Papers

    1. Rupa Krishnan, Harsha V. Madhyastha, Sridhar Srinivasan, Sushant Jain, Arvind Krishnamurthy, Thomas Anderson, Jie Gao, Moving Beyond End-to-End Path Information to Optimize CDN Performance, 2009 Internet Measurement Conference (IMC'09), 190-201, 2009. Received the Best Paper Award. Bibtex. The dataset is available here.

Computational Geometry, Data Structures, Algorithms

        Kinetic Data Structures

    1. 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.

    2. 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 approximate kd-trees. 

    3. 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.   

    4. 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.  This paper developed KDS for maintaining medians and centerpoints for points moving in 1D and 2D respectively.

    5. Pankaj K. Agarwal, Jie Gao, Leonidas Guibas, Haim Kaplan, Vladlen Koltun, Natan Rubin, Micha Sharir, Kinetic Stable Delaunay GraphProc. of the 26th ACM Symposium on Computational Geometry (SoCG'10), 127-136, June, 2010. BibtexIt is still an open question how many times a Delaunay triangulation changes, when the points are in motion. The best upper bound is nearly cubic and the lower bound is quadratic. This paper introduces a subgraph called the stable Delaunay graph that eliminates the Delaunay edges involved in nearly cocircular pairs of Delaunay triangles (i.e., those triangles that may die soon). This subgraph changes only quadratically many times and keeps many of the good properties of a Delaunay triangulation. 

Geometric Spanners, Well-Separated Pair Decompositions
  1. 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 and 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. 

  2. 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.  We also wrote an encyclopedia entry for this topic. 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.

  3. 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.

  4. Jie Gao, Dengpan Zhou, The Emergence of Sparse Spanners and Greedy Well Separated Pair Decomposition, Proc. of the the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'10), 50-61, June, 2010. Bibtex. Slides. Also presented at the 18th Fall Workshop on Computational Geometry, Oct 31-Nov 1, 2008. Journal version published in Journal of Computational Geometry, 3(1), 1-19, 2012.  We show the following algorithm outputs a 1+e spanner with O(n/ed) edges for n points inRd: 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).

Clustering Lines

    1. 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. SlidesJournal version appeared in Discrete and Computational Geometry, 40(4), 537-560, 2008. Bibtex.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.

    2. Jie Gao, Michael Langberg, Leonard Schulman, Clustering Lines in High Dimensional Space: Classification of Incomplete Data, ACM Transactions on Algorithms, accepted, 2009. Bibtex. 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.

Other Unclassified Work

  1. Jehoshua Bruck, Jie Gao, Anxiao Jiang, Weighted Bloom Filter, 2006 IEEE International Symposium on Information Theory (ISIT'06), July, 2006. BibtexA Bloom filter when the data entries have different popularity measures. 

Surveys and Thesis

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

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: 8/5/2014