Subhash Suri - US grants

This project investigates the topic of approximation algorithms in computational geometry, with focus on the two problems: polyhedral surface modeling and Euclidean shortest paths. In surface modeling, one tries to construct a polyhedral model of a complex surface, based on a set of unordered sample points. The complexity of constructing and manipulating the model depends on its number of vertices and faces, and therefore a natural optimization goal is to minimize these features in the model without exceeding a pre-specified error tolerance. The project studies various surface-modeling problems within the formal framework of computational geometry, and analyzes the issues of computational complexity. The problem of computing shortest paths is central to robotics and autonomous navigation. The research investigates approximation algorithms for shortest path problems in two and three dimensions. In two dimensions, the query version of the shortest path problem is studied: preprocess a set of polygonal obstacles so that given two points p and q, the distance between them can be determined in polylogarithmic time. In three dimensions, the goal is to design simpler and more practical alternatives to the exact algorithms for shortest paths among polyhedral solids or on a polyhedral surface.

Looking up the route to send a message is a major bottleneck in traditional
Internet Routers. Traditional routers only use the destination address in
a message to determine how to forward the message. However, in the last
few years, there have been proposals for more sophisticated routers that
are capable of what is called Layer 4 Switching. We believe that the
capabilities provided by Layer 4 Switching in terms of security, quality of
service, and guaranteed service will make Layer 4 Switching an integral
part of the Next Generation Internet.

In Layer Four switching, the route and resources allocated to a packet are
determined by the destination address as well as other header fields of the
packet (such as source address, TCP port numbers etc.). Layer Four
Switching unifies a number of recent trends (such as firewall processing,
resource reservation, providing virtual private networks) into a single
framework. The forwarding database of this new kind of router consists of
a potentially large number of filters on key header fields. A given packet
header can match multiple filters; thus each filter is given a cost, and
the packet is forwarded using the least cost filter that matches the packet
headers.

The flexibility and service differentiation provided by Layer 4 Switching
comes at a cost. Given that traditional Internet forwarding based only on
destination addresses is itself a challenge to implement at Gigabit speeds,
Layer 4 Switching at Gigabit speeds is a difficult problem for next
generation routers. In this proposal, we address the question of designing
and implementing fast algorithms for Layer 4 Switching that can be
implemented at Gigabit speeds even with hundreds of thousands of filters.
We introduce three promising candidate algorithms (cross-producting, Grid
of Tries, and Tuple Search). We propose to implement, evaluate, and
fine-tune these new ideas, consider combination schemes, and to search for
other fast algorithms for fast filter matching. As part of our proposal we
plan to design a chip capable of doing Layer 4 Switching at Gigabit speeds.

Electronic markets are emerging as a primary medium of trade in business-to-business, business-to-consumer, and consumer-to-consumer settings. In order to design viable electronic marketplaces, a host of novel interrelated game-theoretic and computational issues must be
addressed. With a team of interdisciplinary researchers from multiple institutions, this project will develop a unified theory of games and computing to guide and facilitate the growth of such markets. Specific research directions of the project include the following: (1) Market designs will be generalized to incorporate combinatorial bidding, multi-attribute preferences, multi-stage mechanisms, continuous mechanisms, and multi-unit sale; (2) New algorithms for clearing, quoting, incentive-compatible pricing as well as new incentive-compatible tractable mechanisms will be designed with particular emphasis on online and incremental updating of market states; (3) Bounded rationality of the agents will be investigated under a wide spectrum of models of computations, equilibrium concepts of game theory, and trade-offs between centers and agents; and (4) Novel approaches to relaxing the classic common prior assumption will be explored in order to develop practically useful models for ecommerce. The successful completion of this project will make significant contributions to both theory and practice in the areas of electronic commerce, multi-agent systems, algorithms, computational complexity theory, and game theory.

Computational geometry algorithms traditionally have been designed for centralized data settings, where the data are available to algorithms locally and in a persistent form. Yet, a growing number of emerging applications no longer fit such a conventional data model. For instance, in sensor networks and location-aware mobile computing, data is geographically distributed, and in high-volume data monitoring, such as analysis of Internet traffic or web clicks, data must be processed as a stream, without being stored. Motivated by these technological trends, the investigator develops distributed algorithms for geometric computing.

Designing mathematically grounded geometric algorithms for distributed or streaming data is challenging because the algorithms must operate with limited computational resources. In particular, nodes in a sensor network have very limited battery power, memory, and bandwidth, and so collecting data from the network requires nodes to construct approximations of their spatial measurements. Similarly, data stream algorithms must process the data in a single pass and compute synopsis data structures that summarize important features of the data. This research develops novel geometric algorithms and data structures that deal with insufficient resources (bandwidth, memory, power) in a graceful manner, so that the solution quality adapts to the resources available --- the better the resources, higher the solution quality. In particular, the research proposes such resource-adaptive methods to discover epsilon-cuts in sensor networks, compute bounded-memory approximations of sensor observations, discover hierarchical heavy hitters in multi-dimensional data streams, and shape-preserving clustering methods for geometric streams. Many challenges of national importance concern the protection of our physical as well as cyber infrastructures. Being able to monitor these systems remotely and analyze their data with flexible, resource-adaptive, and programmable software tools is critically important. Because many of these systems deal with distributed or streaming data, this research has direct relevance to those applications.

The workshop takes place at the University of California, Santa Barbara, during May 25-25, 2006. It serves as a forum for research leaders from computational geometry and topology on the one side, and sensor and ad hoc networks on the other, to discuss problems at the interface of these disciplines. By bringing together experts from these areas, this workshop helps provide a fuller understanding of possible areas and avenues of collaboration between these fields, to stimulate cross-disciplinary research by enabling face-to-face interactions between researchers that do not normally meet, and to generate a agenda for future joint efforts in the study and exploitation of the geometric aspects of sensor networks.

The results of the workshop will be widely disseminated by means of the internet, with talk abstracts and a list of problems and issues raised. A version of the workshop report will also be published in technical journals with wide distribution in the communities of interest, such as the Communications of the ACM, the ACM Transactions on Sensor Networks, or the IEEE Transactions on Networking.

Proposal Number: Collaborative Research: 0626954, 0626151, and 0627155
PI: Ramesh Govindan, Leonidas Guibas, Subhash Suri
Institution: USC, Stanford, UCSB
Title: NeTS-NOSS: Lightweight Monitoring Tools for Sensor Networks

Abstract:

Networks of tiny and inexpensive smart sensors have ushered a new generation of low-cost, large-scale, high-resolution, real-time sensing and actuation. As their economic importance grows along with their size and complexity, it becomes critical to ensure their operational health and robustness through continuous monitoring. With that motivation, this project develops lightweight monitoring algorithms and tools for sensor networks that allow the network operators to observe the large-scale behavior of the network and detect significant anomalies in network attributes or performance. The tools themselves are generic and can be composed to provide tailored solutions to meet various application-specific needs.

The design of these monitoring tools requires inferring global aspects of the network through local information available at individual nodes. In order to synthesize a global summary from local views in a lightweight, energy-efficient manner, the project employs three methods: (1) intelligent sampling, (2) information aggregation, and (3) sparse representation of the signal landscape. These methods utilize mathematical techniques from geometry, topology, statistics, and distributed signal processing.

The network monitoring tools enable better designed, more robust, trustworthy, and longer-lived sensor networks in operation. That, in turn lowers costs and enlarges the community of users as well as the set of potential commercial applications for networked sensing.

The research output of this project includes novel algorithms, software tools, and their empirical evaluation using testbeds.

CCF-0702798

Mimir: A Geometric Approach to Multi-dimensional Program Profiling Architectures

Timothy P. Sherwood

While mixed static-dynamic program analysis can be done completely in software through binary instrumentation, the amount of analysis that can be done at test-time is bounded by the performance impact that can be tolerated. The end goal of the Mimir project is to enable a new breed of hardware/software analysis tools, for researchers and system builders that can sift through on-line profile data at unprecedented speeds, yielding a highly accurate and timely image of computer system execution. The cross-layer approach to be investigated combines the raw computational ability of custom architectures with the formal guarantees provided by carefully crafted stream algorithms. At a high level, the proposed algorithmic approach to profiling is grounded in geometry, implicitly motivated by the belief that many profiling patterns, trends, or anomalies have natural geometric representations that become discernible under a geometric lens. At a low level, novel programmable hardware methods will provide a scalable and high performance substrate onto which these stream algorithms can be mapped. The combination of these two methods will allow online monitors to make streaming queries over live data at unprecedented speeds with the goal of enabling a new class of previously intractable dynamic analysis methods.

Proliferation of wireless networks has dramatically changed the way we live and work. However, wireless innovation and deployment has been blocked by the spectrum shortage problem as a result of today's static spectrum assignment. While most spectrum bands have been allocated to existing wireless networks and technologies, they are severely under-utilized.
This research will seek to improve spectrum utilization using dynamic spectrum access. In this new system, components of future wireless networks no longer have statically assigned spectrum. Instead, they request spectrum on-demand matching their time-varying demand and pay for what they use. To exploit the full potential of dynamic spectrum access, this research will focus on developing an efficient spectrum auction system which auctions spectrum periodically to wireless nodes and dynamically assign spectrum to minimize interference. Moving away from traditional centralized solutions, this project focuses on distributed auction system to manage large volume of spectrum requests across large geographic areas.
The success of this project will advance understanding in dynamic spectrum access systems, and impact development of cognitive radios and future wireless networks. The educational impacts of the project include integration of research with interdisciplinary training programs at both undergraduate and graduate levels.

Proposal Title: RI: Medium Collaborative Research: Minimalist Mapping and
Monitoring
Institution: University of Illinois at Urbana-Champaign
Abstract Date: 05/05/09
"This award is funded under the American Recovery and Reinvestment Act of 2009
(Public Law 111-5)."
This project addresses fundamental and challenging questions that are common to
robotic systems that build their own maps and solve monitoring tasks. In particular, the
work contributes to our general understanding of the interplay between sensing, control,
and computation as people attempt to design systems that minimize costs and
maximize robustness.
Powerful new abstractions, planning algorithms, and control laws that accomplish basic
mapping and monitoring operations are being developed in this effort. This is expected
to lead to improved technologies in numerous settings where mapping and monotoring
are basic components.
Ample motivation is provided by technological challenges that involve searching,
tracking, and monitoring the behavior of people, wildlife, and robots. Examples include
search-and-rescue, security sweeps, mapping abandoned mines, scientific study of
endangered species, assisted living, ground-based military operations, and even
analysis of shopping habits.
The work is particularly transformative because it lives outside of the traditional
boundaries of algorithms, computational geometry, sensor networks, control theory, and
robotics. Furthermore, national interest continues to grow in the direction of developing
distributed robotic systems that combine sensing, actuation, and computation. By
helping to break down traditional academic and scientific barriers, it is expected that the
work will transform the way we think about robotics algorithms, the engineering design
process, and the education of students across the robotics, computational geometry,
and control disciplines.
NATIONAL SCIENCE FOUNDATION
Proposal Abstract
Proposal:0905523 PI Name:LaValle, Steven
Printed from eJacket: 05/06/09 Page 1 of 1

The objective of this research is the design of innovative routing,
planning and coordination strategies for robot networks, and their
application to oceanography. The approach is organized in three
synergistic thrusts: (1) the application of queueing theory and
combinatorial techniques to networked robots performing sequential tasks,
(2) the design of novel distributed optimization and coordination schemes
relying only on asynchronous and asymmetric communication, (3) the design
of practical routing and coordination algorithms for the USC Networked
Aquatic Platforms. In collaboration with oceanographers and marine
biologists, the project aims to design motion, communication and
interaction protocols that maximize the amount of scientific information
collected by the platforms.

This proposal addresses multi-dimensional problems of relevance in
Engineering and Computer Science by unifying fundamental concepts from
multiple cyberphysical domains (robotics, autonomy, combinatorics, and
network science). Our team has expertise in a broad range of scientific
disciplines, including control theory and theoretical computer science and
their applications to multi-agent systems, robotics and sensor networks.

The proposed research will have a positive impact on the emerging
technology of autonomous and reliable robotic networks, performing a broad
range of environmental monitoring and logistic tasks. Our educational and
outreach objectives are manifold and focus on (1) integrating the proposed
research themes into undergraduate education and research, e.g., via the
existing NSF REU site at the USC Computer Science Department, and (2)
mounting a vigorous program of outreach activities, e.g., via a
well-developed collaboration with the UCSB Center for Science and
Engineering Partnerships.

Most scientific and engineering disciplines today have enormous opportunities for creation of knowledge from massive quantities of data available to them. But the lack of appropriate algorithms and analysis tools for processing, organizing, and querying this data deluge makes this task extremely challenging. A large portion of the data being acquired today has a geometric character, and even non-geometric data are often best analyzed by embedding them in a multi-dimensional feature space and exploiting the geometry of that space. This data is invariably full of noise, inaccuracies, outliers, is often incomplete and approximate, yet most of the existing geometric algorithms are unable to cope with any data uncertainty in relating their output to their input.

The project aims to fill this void by investigating uncertainty-aware geometric computing, with an express goal of designing algorithmic techniques and foundations that will help extract ``knowledge'' from large quantities of geometric data in the presence of various non-idealities and uncertainties. It focuses on a number of fundamental geometric problems, all dealing with uncertain data. A unified set of models will be developed for modeling uncertainty that can deal with multiple uncertainty types, and attention will be paid to handling noise/outliers in heterogeneous and dynamic data. Algorithms will be investigated for understanding how input uncertainty carries over to output uncertainty (e.g. by associating a confidence level or likelihood with each output, or computing certain statistics of the output) and how the input uncertainty impacts the quality of the output (e.g. by defining and computing the stability of the output in terms of the input uncertainty). Since exact solutions are likely to be computationally infeasible, the emphasis will be on simple, efficient approximation techniques (e.g. computing a compact, approximate distribution of geometric/topological structures such as Delaunay triangulations and their subcomplexes of uncertain data).

A key ingredient of the award is to address a variety of computational issues that arise in the presence of uncertainty using a few key problems, and to develop a core set of techniques that illuminate algorithmic design under uncertainty not only on these key problems but that can also be transferred to other geometric problems, as needed. This research touches upon many topics in theoretical computer science and applied mathematics including discrete and computational geometry, discrete and continuous optimization, estimation theory, and machine learning. This study will strengthen connections of computational geometry with a variety of disciplines, including machine learning, probabilistic databases, statistics, and GIS. Since so many problems require geometric data analysis, the project has the potential of enhancing the capability of various government, commercial, and civic units to make informed decisions that impact the society at large.

This Integrative Graduate Education and Research Traineeship (IGERT) award provides Ph.D. students at the University of California at Santa Barbara with the skills to design more efficient and robust empirical networks based on their analyses of large data sets derived from existing networks. By training students to examine multiple types of networks, such as genetic, economic, and social networks, this program aims to advance the field of Network Science.

Intellectual Merit: This traineeship program is a collaboration among seven graduate departments (Computer Science, Communication, Ecology, Evolution & Marine Biology, Electrical & Computer Engineering, Geography, Mechanical Engineering, and Sociology), which will enable trainees to learn computational methods to engineer, control, measure, and predict the dynamics of large networks. Through the program?s Network Science Laboratory, trainees will participate in team-based modules and obtain hands-on experience with software, empirical data sets, and interdisciplinary science. Additionally, trainees will participate in weekly seminars, summer internships, workshops, and an innovation program focused on problem solving and creative thinking.

Broader Impacts: By providing students with interdisciplinary training in Network Science, this program will advance the emerging field of Network Science and will serve as a model for similar academic programs across the nation. Moreover, this program aims to recruit, retain, and mentor 70% women and underrepresented minority students from University of California at Santa Barbara undergraduates as well as students from four partner institutions: California State University at San Bernardino, California State University at Los Angeles, University of California at Merced, and University of New Mexico, all of which are Hispanic Serving Institutions.

IGERT is an NSF-wide program intended to meet the challenges of educating U.S. Ph.D. scientists and engineers with the interdisciplinary background, deep knowledge in a chosen discipline, and the technical, professional, and personal skills needed for the career demands of the future. The program is intended to establish new models for graduate education and training in a fertile environment for collaborative research that transcends traditional disciplinary boundaries, and to engage students in understanding the processes by which research is translated to innovations for societal benefit.

Analyzing the spread of an epidemic, evaluating the vulnerability of Internet-based infrastructures, modeling dynamics of opinion in online social networks, understanding interconnections in the brain, and interactions between genes -- all these tasks are, in an abstract setting, struggling to understand large-scale, complex networks of interlinked nodes. These networks are complex not only because of their scale---social networks and the Internet-of-Things span billions of nodes and even coarse information maps of the brain involve many millions of voxels and pathways---but also because they entail complex, noisy, and time-varying behavior---the structure of links in social networks or connections in brain is poorly understood, and virtually all real networks are subject to non-linear dynamics. The abstraction of graph theory, in which any nodes can be linked, leads to algorithms that become computational bottlenecks on the graphs for these large and messy networks. This project advocates that embedding complex networks in a geometric space gives a framework to apply the use of geometric methods for fast, scalable and approximate analysis of complex networks.

The project has three research thrusts:
(1) theoretical investigation of geometric embeddings for 'scalable network analysis:' to better understand theoretically why certain graphs appear (empirically) to embed nicely in low-dimensional spaces, discover natural graph properties that cause large distortions, and design efficient and scalable algorithms for constructing low-distortion embeddings.
(2) probabilistic embeddings for 'uncertain graphs:' to evaluate how the spatial richness of geometric embeddings capture the link uncertainties inherent in virtually all practical graph models, and
(3) embedding of graphs in two-dimensional plane for 'information cartography:' to embed complex graphs in the two-dimensional plane to reveal important structural themes.
These thrusts complement each other, since network analysis invariably requires both an initial quantitative part---estimating various network statistics by highly efficient algorithms that are enabled by the embedding of the entire network---followed by a qualitative presentation---displaying those network aggregates and substructrures in a visual context to create an informational cartogram.

The results of this project will significantly broaden the applicability of geometric algorithms to network science, and to modern data sets in general. The project touches upon many topics in theoretical computer science and mathematics including discrete and computational geometry, non-Euclidean geometry, probability theory, graph drawing, and information cartography.

Shortest paths and reachability are fundamental problems with a long and distinguished history in computer science and mathematics. Due to growing integration of cyber and physical worlds through the Internet-of-Things (IoT), an increasing amount of data processing entails geometric models, and an ever growing set of smart mobile devices can interact with, and affect, the environment in which they operate - from self-driving cars to autonomous robots. Addressing the needs of these applications, this project explores new directions for shortest paths in geometric domains, organized around the following two broad themes: (1) improving shortest paths by removal of some path-blocking obstacles, and (2) searching for a randomized prize. The specific research topics of the project are novel, yet the general theme touches on many classical problems in geometry, combinatorial optimization, probability theory, decision science and search. The project significantly broadens the scope, applicability and relevance of geometric algorithms to search and planning in continuous spaces, by incorporating strategic intervention and planning under uncertainty. The fundamental nature of topics addressed in this project is likely to appeal to a broad set of students with diverse backgrounds, both graduate and undergraduate. The material generated from this project will be integrated into multiple courses on algorithms and computational geometry, including the investigator's newly launched Foundations of Data Science course.

The project is centered around two research topics. The first topic deals with the following question of reachability: can one reach a target position from an initial position. When this is possible, the goal is to compute a feasible path, or perhaps the shortest one. The focus of the project is the "if not" side of this question, which is often left unattended. Specifically, if no feasible path exists, or the shortest path is unacceptably long, how many and which obstacles should be removed? This form of reachability augmentation in geometric domains is both fundamental and intellectually exciting, with many surprising twists and turns. The solution quality and the algorithmic efficiency critically depend on the geometry of the workspace and model assumptions: are obstacles convex or non-convex? Are obstacles disjoint or overlapping? Is the removal cost the same for all obstacles or different? The second topic proposes a novel framework for problems in which one tries a sequence of alternatives in search for a prize (favorable outcome), where each outcome is determined by a random trial. Computing combinatorial structures, such as shortest paths, in the presence of such random events poses significant intellectual challenges, and the project research contributes to an important body of knowledge.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.