
![]()
![]()

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
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 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. 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). 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. 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.
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. 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. 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. 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. 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. 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. 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. 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|. 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. 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. 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. 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.
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.
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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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 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. 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. Jehoshua
Bruck, Jie Gao,
Anxiao Jiang, Weighted
Bloom Filter, 2006 IEEE
International Symposium
on Information Theory (ISIT'06), July, 2006. Bibtex.
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.
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.
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. 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 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.
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 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:
5/19/2009