De Liu
Gatton College of Business and Economics, University of Kentucky
Keyword advertising, including sponsored links and contextual
advertising, powers many of today's online information services
such as search engines and Internet-based emails. This paper
examines the design of keyword auctions, a novel mechanism that
keyword advertising providers such as Google and Yahoo! use to
allocate advertising slots. In our keyword auction model,
advertisers bid their willingness-to-pay per click on their
advertisements, and the advertising provider can weight
advertisers' bids differently and require different minimum bids
based on advertisers' click-generating potential. We study the
impact and design of such weighting schemes and minimum-bids
policies. We find that weighting scheme determines how advertisers
with different click-generating potential match in equilibrium.
Minimum bids exclude low-valuation advertisers and at the same
time may distort the equilibrium matching. The efficient design of
keyword auctions requires weighting advertisers' bids by their
expected click-through-rates, and requires the same minimum
weighted bids. The revenue-maximizing weighting scheme may or may
not favor advertisers with low click-generating potential. The
revenue-maximizing minimum-bid policy differs from those
prescribed in the standard auction design literature. Keyword
auctions that employ the revenue-maximizing weighting scheme and
differentiated minimum bid policy can generate higher revenue than
standard fixed-payment auctions. We draw managerial implications
for pay-per-click and other pay-for-performance auctions and
discuss potential applications to other areas.
(joint work with Jianqing Chen, and Andrew Whinston)
Host: Professor J. Goldsmith.
Samson Cheung
Electrical and Computer Engineering Department, University of Kentucky
A treasure map, drawn with invisible ink,
Gradually reveals itself by putting a candle
light underneath a famous painting ...
Such a plotline can be found in many adventure stories and just about every Nicholas Cage's movie. While the arts of hiding secret information can be traced back two thousand years ago to the ancient Greeks, the serious study of the science of modern digital information hiding did not begin until the late eighties. Since then, we have applied information hiding techniques in a great variety of applications ranging from anti-counterfeiting, covert communication to error correction and multimedia privacy. Also we have developed sophisticated models to better understand the fundamental limits on the capacity of hiding information in various data sources, the robustness against both benign and malicious attacks as well as the detectability of the hidden messages. In this installment of the seminar series in computer security, I will survey some of these applications and provide an overview on the mathematical modeling of information hiding. My focus will be on hiding information in digital signals like images and videos. I will review a number of information hiding techniques including the earlier spread spectrum schemes and the more recent binning-based quantization schemes. I will also discuss practical designs that enables fully reversible hiding and public-key hiding.
John Franco
EECSE Department, University of Cincinnati
We examine the structure of CNF representations of common problems, such as bounded model checking, in Formal Verification. We observe that this structure arises in a variety of other difficult problems as well. We show why such structures are difficult for current Satisfiability solvers: namely, that inferences typically can be discovered only after a large number of variables have been set. Thus, for example, clause learning is not as effective on such structures as we would like it to be. We propose some ideas which may lead to significantly reduced solution times for these and other problems. These have have to do with guessing inferences a priori BASED ON SOLUTION STRUCTURE and not formula structure as is typically done in preprocessing. That is, the structure of solutions that can be found for smaller versions of a problem are examined for necessary patterns of variable values - either to support or reject the solutions - and constraints are added to the original formula to enforce inclusion or rejection of these patterns. Adding guessed constraints can reduce search enormously but may eliminate some solution traces, so at some search depth these guessed constraints are removed and search continues to the end. The trick is to prevent all solutions from being lost if at least one exists. For Formal Verification problems this means, at worst, getting a result with a certain confidence. Some other problems can be solved more directly. For example, this idea was used to find a van der Waerden number W(2,6) = 1132 by first getting a bound then using solution patterns to reduce a full search to something manageable. We are still refining this technique.
Host: Professor V. Marek.
Craig Partridge
BBN Corp.
We are in the early years of a revolution in wireless communications and the future holds many possibilities. Central to this revolution is the ability to dynamically program (and reprogram) radios, so that innovation in radios will come at the speed of software releases rather than hardware releases. But programmability is only part of the story. There are regulatory issues. There are potential innovations in energy use. In this talk I sketch how how research innovations in wireless are likely to unfold over the next dozen years or so with some (naive) discussions of how the innovations will affect the marketplace. I'll follow this talk with a brief talk on the current status of GENI.
Dr. Craig Partridge is Chief Scientist for Networking Research at BBN Technologies and Outreach Director for the GENI Project Office. Craig's been doing data communications research since 1983 and his contributions include designing how Internet email is routed and co-developing the world's first 40 Gbps Internet router. He's an IEEE and ACM fellow and a former editor-in-chief of both IEEE Network Magazine and ACM Computer Communication Review. He received his A.B., M.Sc. and Ph.D. degrees from Harvard University.
Host: Professor J. Griffioen.
Abstract of Professor Hayes' talk:
Undocumented software systems are a common challenge for developers
performing maintenance and/or reuse. The challenge is two-fold: (1)
when no comments or documentation exist, it is difficult for developers
to understand how a system works; (2) when no requirements exist, it is
difficult to know what the system actually does. We present a
method, named ReORe (Reuse or Rewrite) that assists developers in
recovering requirements for a competitor system and in deciding if they
should reuse parts of their existing system or rewrite it from scratch.
Our method requires source code and executable for the system and assumes
that requirements are preliminarily recovered. We apply ReORe to Lynx,
a Web browser written in C. We provide evidence of ReORe accuracy: 56%
for validation based on textual and static analysis and 94% for the
final validation using dynamic analysis.
Abstract of Professor Griffioen's talk:
In the current Internet architecture, functions such as addressing, routing,
and forwarding are entangled. Among other consequences, this makes it
difficult to modify one without affecting the others, and obscures the role of
policy at various places in the architecture. This talk describes a network
layer designed as a set of separable component mechanisms that work together
to provide a best-effort datagram service. Our thesis is that separating
concerns makes the architecture more flexible and robust.
After presenting the functions that make up the recursive (hierarchical) routing and forwarding service, we will consider the issue of network management and auto-configuration. The separation and delegation of functions, along with the use of flat, topology-independent identifiers, allows the architecture to be self-configuring as much as possible, leaving only the components whose function is affected by policy to be configured.
Dr. Krish Muralidhar
Gatton Research Professor
School of Management
University of Kentucky
Recent advances in information technology have made it possible for organizations to gather and store large quantities of data regarding individuals and other organizations. In many cases, such data include sensitive confidential information about the respondents. With the increase in the ability to gather and store such data, there has also been an increase in the demand to protect the sensitive attributes that may be present in the data. This has limited the ability of organizations to analyze, share, or disseminate data containing sensitive attributes. There are techniques that make it possible to analyze, share, or disseminate data without compromising the confidentiality of the sensitive attributes within the data. Referred to as "data masking", these techniques attempt to provide "masked data" which retains its analytical usefulness while simultaneously protecting the confidentiality of sensitive data regarding the respondents. The purpose of this presentation is to provide an introduction to the techniques that can be used to "mask" numerical confidential data.
Dr. Hong Qin
Department of Computer Science
SUNY Stony Brook (Stony Brook University)
With the rapid advances of 3D surface scanning technologies and medical modalities for volumetric objects, high-fidelity surface models and volumetric datasets of tremendous size have been routinely acquired through the state-of-the-art hardware systems. This presentation concentrates on the challenging research issues of how to build the best possible (surface and volume) mapping and registration between different objects of arbitrarily complicated topological types and how to further broaden application scopes in visual computing beyond the traditional boundary of Computer Aided Design and Computer Graphics. Our most recent research activities seek accurate and efficient solutions to this fundamental and important problem. In particular, we have articulated a general and powerful data modeling paradigm based on shape mapping for objects in different dimensions with arbitrary topologies: in the 1D curve case, we devise the conformal invariants as curve signatures; in the 2D surface case, we exploit techniques of topological decomposition and quasi-conformal mapping; and in the 3D volumetric case, we focus on harmonic map based on Green function theory. The great potential of our shape mapping and registration framework will be highlighted through many valuable applications such as shape analysis, deformation editing, animation morphing, information transfer and reuse, meshing, texture synthesis, and physics-based modeling. Furthermore, we envision much broader application scopes in many visual computing fields including computational vision, shape data base and content-driven information retrieval, digital medicine, virtual environments, etc.
Dr. Hong Qin is a Professor of Computer Science in Department of Computer Science at State University of New York at Stony Brook (Stony Brook University). He received his B.S. degree and his M.S. degree in Computer Science from Peking University. He received his Ph.D. degree in Computer Science from the University of Toronto. He was a recipient of NSF CAREER Award from the National Science Foundation (NSF), Honda Initiation Award, and Alfred P. Sloan Research Fellow by the Sloan Foundation. At present, he is an associate editor for IEEE Transactions on Visualization and Computer Graphics (IEEE TVCG), The Visual Computer, and Journal of Computer Science & Technology. In 2008, he served as the Conference Chair for for ACM Solid and Physical Modeling Symposium and IEEE International Conference on Shape Modeling and Applications. His research interests include geometric and solid modeling, graphics, physics-based modeling and simulation, computer aided geometric design, human-computer interaction, visualization, and scientific computing. For more details, please visit http://www.cs.sunysb.edu/~qin
Abstract of Professor Liu' talk:
eQTL analysis is essential to determine how genes control each other,
specifically, whether some genetic makeup of one gene influences the
expression of other genes. Underlying the eQTL analysis is the traditional
Quantitative trait (QTL) analysis. Most existing Bayesian linkage methods
are prohibitive for high-throughput eQTL analysis because of the
time-consuming Monte Carlo sampling procedure. We present a Bayesian
linkage model that offers highly interpretable posterior densities for
linkage, without the need for Bayes factors in model selection. For this
model, we develop Laplace approximations for integration over nuisance
parameters in backcross data. Our approach is highly accurate and is fast
enough so that the computation of linkage posterior densities for over
30,000 transcripts becomes feasible. In addition, the ability in computing
the probability of data at each transcript makes it possible to estimate
the global cis-acting and trans-acting probabilities, which maximizes the
probability of data.
Abstract of Professor Yang' talk:
Video is ubiquitous in our life. While almost all of them are captured and
visualized in 2D, the interests for 3D contents have been raising. My
research focuses on the acquisition and visualization of 3D contents. I will
first present a 3D display that simulates the flow of light in the real
world. The result is an autosterescopic -- 3D without glasses -- display
that provides full color, full parallax, and proper occlusion. Then I will
talk about several techniques we have developed to create 3D contents using
from an array of cameras to a single one.
Dr. Neil Yorke-Smith
Artificial Intelligence Center
SRI International
To have value for an individual who is arranging an event, a scheduling tool must actively account for your scheduling preferences, especially when the meeting request constraints must be relaxed. We develop a preference model designed to capture user scheduling preferences for overconstrained meeting requests between multiple people, and a methodology for preference elicitation to initially populate this model. The model is built around a 2-order Choquet integral representation. We explain a natural-language-based elicitation of the meeting request details and constraints, and outline the solving of the resulting constrained scheduling problem (with preferences). We describe the display of solutions to the scheduling problem to the user, as candidate scheduling options with explanations, and detail unobtrusive learning of revisions to the preference model from the user's choices among the candidates. We report on initial assessment of the efficacy of such a preference model in terms of elicitation, learning, and reasoning.
Neil Yorke-Smith is a Computer Scientist at SRI's Artificial Intelligence Center. His research focuses on technologies that assist human decision making, with interests including planning and scheduling, preferences, constraint programming, advisable agents, and intelligent user interfaces, and their real-world applications. He received his Ph.D. from Imperial College London in 2004. Publications and further information are available at: http://www.ai.sri.com/~nysmith
Host: Professor J. Goldsmith.
Jinwei Gu, Columbia University (Faculty Candidate)
Over the last decade, we have seen the beginnings of a successful merging of computer graphics and computer vision for tackling many difficult research problems in both fields, such as photo-realistic rendering with data-driven methods, scene reconstruction with novel computational imaging systems, and image enhancement with computational photography methods.
In this talk, I will discuss how to employ this hybrid approach of vision and graphics for studying the visual appearance of a variety of complex natural phenomena. First, I will present our work on time-varying appearance of opaque surfaces (e.g., the burning of wood, the wetting and drying of rocks and fabrics, the decay of fruit skins, and the rusting of steel and copper), in which we have conducted the first comprehensive data-driven study of such dynamic phenomena with a novel nonlinear space-time appearance factorization model. Second, I will discuss our work on modeling and rendering the weathering effects of transparent objects, in which a phenomenological model is derived by aggregating single-scattering events over the transparent surfaces. This model is used for both real-time rendering as well as building acquisition systems to measure parameters from real samples. Finally, I will discuss our recent work on recovering the volume density of dynamic inhomogeneous participating media (e.g., fog, smoke, milk clouds) using a novel computational imaging system --- compressive structured light --- in which light patterns are emitted to obtain a line integral measurement of the volume density at each camera pixel. In addition to its use for graphics applications, this method can also be viewed from the perspective of computer vision as extending the applicable domain of structured light methods from opaque surfaces to volumes.
Jinwei Gu received his B.S. degree and M.S. degree from Department of Automation at Tsinghua University, China, in 2002 and 2005, respectively. He is currently a doctoral candidate in the Computer Science department at Columbia University. His research interests are in both computer graphics and vision, and especially at the intersection of the two. In particular, his current research focuses on understanding and modeling the physical image formation mechanism and the intrinsic structure of the visual appearance of complex natural phenomena, and applying them in data-driven computer graphics, physics-based computer vision, and computational photography.
Dr. Huamin Wang, Georgia Institute of Technology (Faculty Candidate)
Modeling realistic natural phenomena is an important and active research topic in both graphics and computer vision. Physically-based simulation approaches generate plausible animations by following physical laws from an initial state. In contrast, image-based reconstruction techniques try to directly acquire models from real-world data. In my own work, I seek to combine the best aspects of both of these approaches by starting with image-based data and improve upon it based on physics. Specifically, I will present my work on fluid modeling that first begins with depth information of flowing water that is created using stereo video input. From this, I use physics-guided optimization to improve the spatial and time-based smoothness of the water motion in order to produce more realistic motion. The result of this process is a 3D description of moving fluids that we use to create animations from any camera position. I will show results for pouring water, a splashing object and a fountain.
My hybrid work on physics and image-based modeling draws upon my earlier experiences in physical simulation and computer vision. I will show some results of this earlier work, starting with my virtual surface method of modeling small-scale fluid effects. I will show animations of water beading on surfaces, drop pinch-off, and rivulets on surfaces. I will then demonstrate my approach for analyzing images for repeated content, which then can be used for image and video compression. I will conclude by describing extensions of my current research to other kinds of natural phenomena such as fire, cloth, plants and fire, and how additional considerations such as repetitiveness and perception might be used in creating such animations.
Dr. Tingjian Ge, Brown University (Faculty Candidate)
The need to manage uncertain data arises in many applications. Some examples include data cleaning, data integration, sensor networks, pervasive computing, and scientific data management. Uncertainty can arise in both measured and predicted values, thus, requiring a statistical treatment. Predictive queries based on historic data are also useful in a range of domains like proactive system management, inventory planning, adaptive query processing, sensor data management, and financial planning. In this talk, I describe a series of techniques that I developed to answer various kinds of queries, including JOIN and top-k queries, on uncertain data. I also explore methods for effectively processing predictive queries. For example, I discuss the use of skip-lists for building models that answer predictive queries on different time horizons. I show experimental results that indicate that these techniques are practical. (Speaker's personal page: http://www.cs.brown.edu/~tige/)
Dr. Feng Pan, University of North Carolina (Faculty Candidate)
The goal of genome wide association (GWA) mapping in modern genetics is to identify genes or narrow regions in the genome which contribute to genetically complex phenotypes such as morphology or disease. Existing methods include single-marker, haplotype and phylogeny-based association mapping. Phylogeny-based association mapping utilizes phylogenetic trees which are rich yet compact representations of the genetic relationships between samples. Thus phylogeny-based methods show obvious advantages over single marker-based and haplotype-based methods by incorporating richer information of the evolutionary history. However, most of the existing phylogeny-based methods are time-consuming and not scalable to genome-wide analysis. I developed two efficient phylogeny-based association mapping methods, TreeQA and TreeQA+, which utilize local perfect phylogenies constructed in genomic regions exhibiting no evidence of historical recombination. TreeQA is highly efficient because it uses linear-time algorithm to construct local perfect phylogeny trees, conducts effective permutation tests and maximizes the reuse of intermediate computation. Moreover, TreeQA is more robust and effective than previous phylogeny-based methods due to its ability to remove outliers induced by the tree topology and search for associations in sample subspaces. TreeQA+ inherits all advantages of TreeQA. Moreover, it improves TreeQA by utilizing the Brownian motion and maximum likelihood model to incorporate sample correlations induced by the topology of the phylogenetic trees (The correlations violate the sample independence assumption and are ignored by previous association methods.).
The method is also extended and applied to association analysis in high
dimensional data of any domains, which is a general data mining problem.
(Speaker's personal page: http://www.cs.unc.edu/~panfeng/)
Dr. Jan-Michel Frahm, University of North Carolina (Faculty Candidate)
In recent years photo/video sharing web sites like Flickr and YouTube
have become increasingly popular. Nowadays, every day terra bytes of
photos and videos are uploaded. These data survey large parts of the
world throughout the different seasons, various weather conditions and
all times of the day. In the talk I will present my work on the highly
efficient reconstruction of 3D models from these data. It addresses a
variety of the current challenges that have to be addressed to achieve a
concurrent 3D model from these data. The challenges are: estimation of
the geometric and radiometric camera calibration from videos and photos,
efficient robust camera motion estimation for (quasi-)degenerate
estimation problems, high performance stereo estimation from multiple
views, automatic selection of correct views from noisy image/video
collections, image based location recognition for topology detection. In
the talk I will discuss the details of our real-time camera motion
estimation from video using our Adaptive Real-Time Random Sample
Consensus (ARRSAC) and our high performance salient feature tracker,
which simultaneously estimates the radiometric camera calibration and
tracks the motion of the salient feature points. Furthermore our
technique to achieve robustness against (quasi-) degenerate data will be
introduced. It allows to detect and overcome the case of data, which
under-constrain the camera motion estimation problem. Additionally our
optimal stereo technique for determining the scene depths with constant
precision throughout the scene volume will be explained during the
talk. It allows to perform the scene depth estimation from a large set
of views with optimal computational effort while obtaining the depth
with constant precision throughout the reconstruction volume. I also
discuss our fast technique for the image based location recognition,
which uses commodity graphics processors to achieve real-time
performance while providing high recognition rates. Furthermore in the
talk I present our work on 3D reconstruction from internet photo
collections. It combines image based recognition with geometric
constraints to efficiently perform the simultaneous selection of correct
views and the 3D reconstruction from large collections of photos. The
talk will also explain the future challenges in all the mentioned
areas.
(Speaker's personal page: http://www.cs.unc.edu/~jmf/)
Dr. Remco Chang, Research Scientist, UNC Charlotte / Charlotte Visualization Center
Interaction is becoming an integral part in using visualization for
analysis. When interaction is tightly and appropriately coupled with
visualization, it can transform the visualization from displaying static
imageries to assisting comprehensive analysis of data at all scales. In
this relationship, a deeper understanding of the role of interaction,
its effects, and how visualization relates to interaction is necessary
for designing systems in which the two components complement
each other.
In this talk, I will be presenting various examples of the different
aspects of this relationship. The three main areas that I will focus on
are: interactive urban visualization and analysis, application of
interaction techniques in coordinated visualizations, and capturing and
storing interactions (provenance) in visualization for the purpose of
understanding a user's analysis process.
(Speaker's personal page: http://coitweb.uncc.edu/~rchang/)
Host: Professor R. Yang.