TITLES IN DEVELOPMENT

Information Retrieval technology powers a lot of the search functionality that runs the Web. As different web properties evolve over time and new services become mainstream, the ability to search for pages, people, music, messages, posts, and other objects is an essential part of our daily digital life. This text describes the new techniques which have emerged to ensure said functionality works from any device at scale. The book should be of interest to researchers, practitioners, and graduate students who want to understand the latest advances in this area.

Structural bioinformatics is the field related to the development and application of computational models for the prediction and analysis of macromolecular structures. The unique nature of protein and nucleotide structures has presented many computational challenges over the last three decades.

The book is intended as a user's guide for key algorithms to solve problems related to macromolecular structure, with emphasis on protein structure, function and dynamics. It can be used as a textbook for a one-semester graduate course in algorithms in bioinformatics.

The collection of essays on Artificial Intelligence and Society provides the first systematic and comprehensive coverage of how the field of Artificial Intelligence (AI) has impacted society. The book is centered around five sections---sustainability, health, smart cities and urban planning, privacy and security, and fairness, accountability, and transparency. Each section will consist of several tutorial-style essays discussing specific societal challenges, relevant background material (mathematical and algorithmic), a brief literature review, the core algorithmic content, and a description of how the societal challenge has been addressed. The ultimate aim of this edited volume is to enlighten students about how AI algorithms and data-driven modeling have impacted society from a diverse range of perspectives and impact areas.

ACM Books is pleased to announce the signing of a new book in our Turing Award series, Birth of the Database: The Work of Charles W. Bachman, edited by Gary Rector of Salt River Project.

Bachman received the prestigious ACM Turing Award in 1973 “for his outstanding contributions to database technology.” The book will feature a short biography of Bachman, the history of the creation of Bachman diagrams and IDS (the first direct-access database), and an analysis of Bachman’s influence on today's leading computer scientists.

This book in the ACM Turing Award series focuses on the life and contributions of Jim Gray. Jim was dedicated to the mentoring, nurturing, and development of individuals and the scientific community with a special emphasis on computer science education, and his curiosity and passion for learning led him into new and uncharted areas within systems computing. The book follows Jim’s exploration of eight major areas of systems computing: systems, transactions, databases, availability, performance, sort, scale, and eScience.

Formal Methods for Safe Autonomy: Data-Driven Verification, Synthesis, and Applications makes foundational contributions to the verification of embedded and cyber-physical systems, and demonstrates applicability of the developed verification technologies in industrial-scale systems. It also advances the theory for sensitivity analysis and symbolic reachability, develops verification algorithms and software tools (DryVR, Realsyn), and demonstrates applications in industrial-scale autonomous systems.

ACM Books is pleased to announce the signing of a new book in our Turing Award series, Foundations of Computation and Machine Learning: The Work of Leslie Valiant, edited by Rocco Servedio of Columbia University.

Valiant received the prestigious ACM Turing Award in 2010 for "transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing." The book will feature a short biography of Valiant, as well as analysis of his seminal works by today's leading computer scientists.

From Algorithms to Thinking Machines uses an informative style to present the concepts of algorithms, data and computation and discuss the role of algorithms and computers in ruling and shaping the world in which we live and work. The main goal is to help readers to clearly understand the power and impact of pervasive use of algorithms on human lives. The book combines a popular approach with a well-founded scientific description aiming at discussing both principles and applications of algorithms, Big Data, and machine intelligence.

Geospatial data science is the science of collecting, organizing, analyzing, and visualizing geospatial data. The book introduces a new generation of geospatial technologies based on the Semantic Web and the Linked Data paradigms, and shows how data scientists can use them to build environmental applications easily. The book is aimed at researchers and practitioners who would like to know more about this research area and can also be used as a textbook for a last year undergraduate or graduate course. Every chapter of the book contains exercises that can help the readers master the material covered by the chapter.

The topics covered by the book in detail are: geospatial data modeling, geospatial data and metadata, geospatial data formats and OGC standards, geospatial ontologies and linked geospatial data models, querying geospatial data expressed in RDF, querying evolving linked geospatial data, visualizing linked geospatial data, transforming geospatial data into RDF, interlinking geospatial data sources, geospatial ontology-based data access and incomplete geospatial information.

Online advertising has grown from almost nothing at the end of last century to an annual spend of over 200B dollars globally. Today, online advertising garners the most advertising dollars of any advertising channel including TV. Online advertising is computational advertising since most the decisions of which ads to show to a user in a given context are determined by algorithms. Indeed, computational advertising was one of the first big data applications. For this reason, the problems behind computational advertising have driven research into large-scale machine learning and algorithmic game theory and is responsible for many advances in those areas as well as in parallel computing architectures. This book covers the current state of the art of computational advertising. That includes the economics of online advertising, understanding and modeling consumer behavior, matching ads and consumers, user response prediction and measurement of ad effectiveness. We also cover ad allocation, campaign management and optimization, as well as fraud and privacy issues. Today, computational advertising intersects computer science, economics marketing and psychology. Hence, after 20 years of advances in this field we hope this book fills the needs of researchers, practitioners and graduate students who want to understand the state of the art in this multidisciplinary area.

Sir Tim Berners-Lee was awarded the 50th anniversary ACM Turing Award "For inventing the World Wide Web, the first web browser, and the fundamental protocols and algorithms allowing the Web to scale." This new book, one in a series dedicated to Turing Award winners, looks at the life and work of Berners-Lee. It features a short biography, seminal research, and commentary from leading computer scientists on the evolution and impact of his work.

Stephen A. Cook was awarded the ACM Turing Award in 1982, in recognition of "his advancement of our understanding of the complexity of computation in a significant and profound way." Cook's theory of NP-completeness is one of the most fundamental and enduring contributions in computer science, and has a singificant impact outside the field. This volume will present works on NP-completeness and other contributions which, while perhaps not as well known, has also had a significant impact on computing theory and practice, as well as mathematical logic. With additional material, including a biographical chapter, Professor Cook's Turing Award address, and a full bibliography of his work, the volume will provide an excellent resource for anyone wishing to understand the foundations of Cook's work as well as its ongoing significance and relevance to current research problems in computing and beyond.

This book provides a comprehensive study of the many ways to interact with computers and computerized devices. An “interaction technique” starts when the user performs an action that causes an electronic device to respond, and includes the direct feedback from the device to the user. Examples include physical buttons and switches, on-screen menus and scrollbars operated by a mouse, touchscreen widgets and gestures such as flick-to-scroll, text entry on computers and touchscreens, consumer electronic controls such as remote controls, game controllers, input for virtual reality systems like waving a Nintendo Wii wand or your hands in front of a Microsoft Kinect, interactions with conversational agents such as Apple Siri, Google Assistant, Amazon Alexa or Microsoft Cortana, and adaptations of all of these for people with disabilities. The book starts with a history of the invention and development of these techniques, discusses the various options used today, and continues on to the future with the latest research on interaction techniques such as presented at academic conferences. Sections also cover how to use, model, implement, and evaluate new interaction techniques. The goal of the book is to be useful for anyone interested in why we interact with electronic devices the way we do, and designers creating the interaction techniques of tomorrow who need to know the options and constraints and what has been tried, also for implementers and consumers who want to get the most out of their interaction techniques.

Pointer analysis provides information to disambiguate indirect reads and writes of data through pointers and indirect control flow through function pointers or virtual functions. Thus it enables application of other program analyses to programs containing pointers. There is a large body of literature on pointer analysis. However, there is no material that brings out a uniform coherent theme by separating fundamental concepts from advanced techniques and tricks. This book fills this void.

The book focuses on fundamental concepts instead of trying to cover the entire breadth of the literature on pointer analysis. Bibliographic notes point the reader to relevant literature for more details.
Rather than being driven completely by pointer analysis’s practical effectiveness, the book evolves the concepts from the first principles based on the language features, brings out the interactions of different abstractions at the level of ideas, and finally, relates them to practical observations and the nature of practical programs.

Principles of Graph Data Management and Analytics is the first textbook on the subject for upper-level undergraduates, graduate students and data management professionals who are interested in the new and exciting world of graph data management and computation. The book blends together the two thinly connected disciplines – a database-minded approach to managing and querying graphs, and an analytics-driven approach to perform scalable computation on large graphs. It presents a detailed treatment of the underlying theory and algorithms, and prevalent techniques and systems; it also presents textbook use cases and real-world problems that can be solved by combining database-centric and analysis-centric approaches. The book will enable students to understand the state of the art in graph data management, to effectively program currently available graph databases and graph analytics products, and to design their own graph data analysis systems.To help this process, the book supplements its textual material with several data sets, small and large, that will be made available through the book’s website. Several free and contributed software will also be provided for readers for practice.

The process of creating 3D graphics – adding surfaces, texture and lighting to a bare wireframe – inspires Rendering History: The Women of ACM-W (Association for Computing Machinery’s Council on Women in Computing). To create a history of ACM-W, the book separates into three main parts and leverages an analogy to rendering 3D graphics. Developing the history of ACM-W (or creating a 3D graphic) requires surfaces; the anchor (or surface) of Rendering History is the traditional retelling of ACM-W’s story based on annual reports, newsletters and interviews. The texture of the book emerges as an annotated bibliography that outlines the major literature involving ACM-W’s purview: K-16 computing education and the girls and women in this school range. A 3D rendering finishes with lighting. A history of ACM-W is also incomplete without lighting – an accounting of the nearly 100 women who served ACM from 1993 to the present. The women of ACM-W co-founded some of the most influential institutions that recruit, retain and celebrate women in computing. They launched projects to broaden participation in computing. The women work in industry, in academia; some author books; a few are now retired. The women conduct research; they teach; they lead organizations. The women of ACM-W received millions of dollars in grant funding; they won prominent awards. Rendering History allows a sample of ACM-W members to inspire and motivate by narrating accounts of their lives. The description of ACM-W’s projects, an annotated bibliography and the personal stories comprise a fully-formed history of ACM-W.

Static program analysis studies the behavior of programs under all possible inputs. It is an area with a wealth of applications, in virtually any tool that processes programs. A compiler needs static analysis in order to detect errors (e.g., undefined variables) or to optimize code (e.g., eliminate casts or devirtualize calls). A refactoring or a program understanding tool need global program analysis in order to answer useful questions such as “where could this program variable have been set?” or “which parts of the program can influence this value?'' A security analyzer needs program analysis to determine “can the arguments of this private operation ever be affected by untrusted user input?” A concurrency bug detector needs program analysis in order to tell whether a program can ever deadlock or have races. Static program analysis is practically valuable, but it is also hard. It is telling that the quintessential undecidable computing problem, the “halting problem”, is typically phrased as a program analysis question: “can there be a program that accepts another program as input and determines whether the latter always terminates?” Other program analysis problems have given rise to some of the best known techniques and algorithms in computer science (e.g., data-flow frameworks). This book offers a comprehensive treatment of the principles, concepts, techniques and applications of static program analysis, illustrated and explained. The emphasis is on understanding the tradeoffs of different kinds of static program analysis algorithms and on appreciating the main factors for critically evaluating a static analysis and its suitability for practical tasks.

Algorithms are used to make decisions in an ever-increasing number of socially consequential domains. From risk assessment tools in the criminal justice system to content moderation tools to assessments in hiring, algorithms play a key role in shaping the lives of people around the world. Algorithms offer many potential benefits: they are consistent, scalable, and can leverage more data than any human could reasonably consume. However, without careful consideration algorithmic decision-making also carries a number of risks, like replicating human biases, creating perverse incentives, and propagating misinformation. This thesis seeks to develop principles for the responsible deployment of algorithms in applications of societal concern, realizing their benefits while addressing their potential harms. What does it mean to make decisions fairly? How do theoretical ideas about societal impacts manifest in practice? How do existing legal protections apply in algorithmic settings, and how can technical insights inform policy?

In this thesis, we explore these questions from a variety of perspectives. Part II leverages theoretical models to surface challenges posed by algorithmic decision-making and potential avenues to overcome them. Part III incorporates models of behavior to better understand the interplay between algorithms and humans decisions. In Part IV, we explore how these insights manifest in practice, studying applications in employment and credit scoring contexts. We conclude in Part V with open directions for future research.

Modern trends in networking, such as the rise of cloud computing and progressive rollout of large datacenter networks, have complicated network management and created a great need in practice for tools that can ensure reliability of our physical networks. To address this need, in recent years many researchers, including myself, have explored how to apply formal methods techniques, including verification and synthesis, to validate the correctness of networks at scale. However, despite a lot of recent interest in the fields of network verification and synthesis, the topics remain inscrutable to most practitioners and researchers, requiring strong backgrounds in both networking principles and formal methods techniques. Moreover, the fields are relatively new and most of the knowledge is locked away in the heads of a small number of people.

The goal of this publication is the provide an in-depth exploration of the recent advances in formal methods as applied specifically to the area of network routing (layer 3). The monograph aims to also provide suitable background to be accessible to those lacking background in either networking or formal methods. The target audiences would be (1) researchers and new graduate students looking to work in the fields of either network verification or network synthesis, and (2) industrial practitioners looking to build practical tools to improve network reliability.