Papers

Papers

Raw index is at bottom. Newer entries categorized below. Old notes are at Reading.Work.

Categories

Approximation Algorithms

• Geometry, Flows, and Graph-Partitioning Algorithms (CACM 2008)
  • Surveys approaches to approximate graph partitioning, mostly based on network flow and congested links.

Bloom Filters

• Space/Time Trade-Offs in Hash Coding with Allowable Errors (CACM 1970)
  • Original paper introducing Bloom filters.
• Network Applications of Bloom Filters: A Survey (Internet Mathematics 2004)
  • Excellent review of many applications of Bloom filters to networking topics, including resource routing, measurement, duplicate detection, and others.
• PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities (HPDC 2003)
  • Overviews a P2P system for keyword search document retrieval built on gossiping and Bloom filters.
• Implementation Results of Bloom Filters for String Matching (FCCM 2004)
  • Brief poster paper on a network intrusion detection system based around matching signatures against a set of parallel Bloom filters implemented in an FPGA.

Constraint Optimization

• A Decentralized Approach to the Art Gallery Problem (FWCG 2007)
  • Casts and solves variations of the art gallery problem as distributed constraint optimization problems.
• Agent Technologies for Sensor Networks (IEEE IS 2009)
  • Brief, high overview of several sensor systems utilizing agent based approaches, including DCOPs for coordination, and model estimation

Data Archiving/Preservation

• Got Data? A Guide to Data Preservation in the Information Age (CACM 2008)
  • Overviews problems in data preservation and archiving, changing trends, basics of a data stewardship plan.

Data Structures

• Scalable Synchronous Queues (CACM 2009)
  • Presents two algorithms for lock free synchronous queues, since adopted for thread scheduling in Java 6. Synchronous queues pair producers with consumers, synchronizing their activities and eliminating the need for a work product buffer.

Databases

• Breaking the Memory Wall in MonetDB (CACM 2008)
  • Overviews changes in computer architecture and database usage hindering previous architectures, describes MonetDB's column store architecture, cache aware algorithms, reduced algebra, and memory access cost models.

Description Logics

• Pushing the EL Envelope (IJCAI 2005)
  • Discusses tractability of several extensions of the EL description logic.
• Bubo---Implementing OWL in Rule-Based Systems (WWW 2003)
  • Translation of OWL DL semantics to logic programming, relational databases.
• On Logics with Two Variables (TCS 1999)
  • Survey of decidability results for various logics of two variables, formalization of logics with two variables.
• On the Decision Problem for Two-Variable First-Order Logic (Symbolic 1997)
  • Lowers the complexity bound of satisfiability for logics with two variables.
• On the Relative Expressiveness of Description Logics and Predicate Logics (AIJ 1996)
  • Relates several common, overarching DL languages into L2 and L3 fragments of first order logic, implying expressiveness and decidability bounds

Distributed Computing

• Scalable Synchronous Queues (CACM 2009)
  • Presents two algorithms for lock free synchronous queues, since adopted for thread scheduling in Java 6. Synchronous queues pair producers with consumers, synchronizing their activities and eliminating the need for a work product buffer.
• Eventually Consistent (CACM 2009)
  • Describes different forms of consistency, and the changing approaches taken from early database systems to Internet scale services.

Epidemic and Gossip Protocols

• Epidemic Algorithms for Replicated Database Maintenance (PDC 1987)
  • Introduces and analyzes dissemination and consistency maintenance protocols based on epidemiology.
• Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks (NSDI 2004)
  • Introduces Trickle, a gossip protocol for data consistency maintenance on sensor networks which takes advantage of the broadcast medium and eavesdropping.
• Eventually Consistent (CACM 2009)
  • Describes different forms of consistency, and the changing approaches taken from early database systems to Internet scale services.

Fault Detection/Management

• On the Design of a Self-Managed Wireless Sensor Network (IEEE Communications 2005)
  • Very high level overview of an autonomic control system for a fire detecting wireless sensor network.
• Self-Managed Fault Management in Wireless Sensor Networks (UBICOMM 2008)
  • High level discussion of hardware monitoring and failure detection in a hierarchical sensor network.
• Exterminator: Automatically Correcting Memory Errors with High Probability (CACM 2008)
  • Buffer overflow and dangling pointer detection and correction via analysis of multiple randomized heaps.
• Fault Localization and Self-Healing with Dynamic Domain Configuration (MILCOM 2003)
  • Applying Bayesian models and incremental hypothesis updating to detecting faults, resolving them by reconfiguring network to isolate problems or start new services.
• Active Probing Approach for Fault Localization in Computer Networks (E2EMON 2006)
  • Selecting probe stations, types, and strategies to detect and localize faults on a network.
• Diagnosis of Sensor Networks (ICC 2001)
  • Several basic approaches to collect information from sensor networks to discover faulty nodes.
• Distributed Fault Detection of Wireless Sensor Networks (DIWANS 2006)
  • Voting among neighbors to determine faulty sensors based on reported values.
• HYWINMARC: An Autonomic Management Architecture for Hybrid Wireless Networks (LNCS 2006)
  • Policy managing mobile agents on wireless mesh network with MANET clusters.

Game AI

• Terrain Analysis for Realtime Strategy Games (Gamasutra 2000)
  • Discusses basic mechanisms used in providing input to AI players.

Graph Theory

• Geometry, Flows, and Graph-Partitioning Algorithms (CACM 2008)
  • Surveys approaches to approximate graph partitioning, mostly based on network flow and congested links.

Graphics/3D/CAD

• 3D Media and the Semantic Web (IEEE IS 2009)
  • High level discussion of applicability and problems of annotating 3D data with Semantic Web markup.

Image Manipulation

• Seam Carving for Media Retargeting (CACM 2009)
  • Applies dynamic programming and graph cuts to determine low energy seams in images and videos which can be safely removed or interpolated between to shrink or expand the media and change the aspect ratio without unduly affecting the content.
• Scene Completion Using Millions of Photographs (CACM 2008)
  • Completes photographs with missing components by extracting from photos taken from huge database of photos.

Information Extraction

• Open Information Extraction from the Web (CACM 2008)
  • Short history of information extraction, developments in large scale, Web-based information extraction for general querying.

Memory Allocation

• Exterminator: Automatically Correcting Memory Errors with High Probability (CACM 2008)
  • Buffer overflow and dangling pointer detection and correction via analysis of multiple randomized heaps.
• Flash Storage Memory (CACM 2008)
  • Discusses using flash memory as an intermediary between cache and persistent storage.

Mobile Ad Hoc and Mesh Networks

• Exploring Mesh and Tree Based Multicast Routing Protocols for MANETs (IEEE Mobile Computing 2006)
  • Evaluates ODMRP and MAODV protocols in various settings---ODMRP shown to have better delivery, MAODV less overhead; looks at variations on flooding to enable alternately reduced redundancy or improved reliability
• HYWINMARC: An Autonomic Management Architecture for Hybrid Wireless Networks (LNCS 2006)
  • Policy managing mobile agents on wireless mesh network with MANET clusters.
• A High-Throughput Path Metric for Multi-Hop Wireless Routing (Wireless 2005)
  • Introduces ETX, estimated transmission count, for choosing higher quality paths of more hops versus inferior paths of less hops.
• Architecture and Evaluation of an Unplanned 802.11b Mesh Network (MobiCom 2005)
  • Overviews and evaluates Roofnet algorithms and implementation.
• A High-Throughput Path Metric for Multi-Hop Wireless Routing (MobiCom 2003)
  • Introduces ETX link quality estimation.
• Challenges and Lessons in Developing Middleware on Smart Phones (IEEE Computer 2008)
  • Overviews limitations of current smart phone platforms, middleware requirements.

Natural Language Processing

• Open Information Extraction from the Web (CACM 2008)
  • Short history of information extraction, developments in large scale, Web-based information extraction for general querying.

Network and Graph Characteristics, Construction

• Emergence of Scaling in Random Networks (Science 1999)
  • Demonstrates existence of power law degree distribution in several real networks, and shows that mechanisms not based on continuous growth and preferential attachment do not result in such a system (including ER and Watts-Strogatz small world graphs)
• Classes of Small-World Networks (PNAS 2000)
  • Many real world networks actually fall into one of three classes of small-world networks: Scale-free, broad-scale, single-scale; adding aging and capacity to small-world growth models introduces distribution cutoffs seen in broad-scale and single-scale
• Emergence of Tempered Preferential Attachment from Optimization (PNAS 2007)
  • Demonstrates that real world data may be more realistically fit via a preferential attachment model including saturation and viability; shows how that model may arise from an optimization process
• Evolving Networks with Distance Preferences (PR-E 2002)
  • Looks at networks where nodes are added via a distance preference function for connecting to existing nodes; can produce power law degree distribution as in scale free construction, but differs in other characteristics such as clustering coefficient

Network Intrusion Detection

• Implementation Results of Bloom Filters for String Matching (FCCM 2004)
  • Brief poster paper on a network intrusion detection system based around matching signatures against a set of parallel Bloom filters implemented in an FPGA.

Network Management

• Performance Analysis of DRAMA: A Distributed Policy-Based System for MANET Management (MILCOM 2006)
  • Very high level overview of DRAMA agent-based management scheme; focus on software-in-the-loop evaluation on emulated MANET compared to SNMP.
• Active Probing Approach for Fault Localization in Computer Networks (E2EMON 2006)
  • Selecting probe stations, types, and strategies to detect and localize faults on a network.
• Diagnosis of Sensor Networks (ICC 2001)
  • Several basic approaches to collect information from sensor networks to discover faulty nodes.
• HYWINMARC: An Autonomic Management Architecture for Hybrid Wireless Networks (LNCS 2006)
  • Policy managing mobile agents on wireless mesh network with MANET clusters.

Parallel Computing

• The Revolution Inside the Box (CACM 2008)
  • Multi-core processors in changing both hardware and software in radical ways.

Peer to Peer

• An Analysis of Internet Content Delivery Systems (OSDI 2002)
  • Analyzes network traffic at UW to look at P2P vs Web behavior, discusses applicability of P2P caches
• An Introduction to Communication Network Analysis, Chapter 7 (Wiley-IEEE 2007)
  • Quickly overviews several basic, common elements in P2P search
• RDFPeers: A Scalable Distributed {RDF} Repository Based on a Structured Peer-to-peer Network (WWW 2004)
  • Presents a scheme for distributing RDF triple stores through a reasonably simple scheme of pushing three copies, one each for pred/sub/obj, into a DHT, and querying in a straightforward way based on that
• PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities
  • Overviews a P2P system for keyword search document retrieval built on gossiping and Bloom filters.
• Eventually Consistent (CACM 2009)
  • Describes different forms of consistency, and the changing approaches taken from early database systems to Internet scale services.

Process Modeling

• A Computer Scientists's Guide to Business Process Management (BPM) (ACM Crossroads 2009)
  • Quick overview of business process management, modeling, etc. Decent terminology guide, good references.

Publish/Subscribe ^pubsub

• The Many Faces of Publish/Subscribe (ACM CS 2003)
  • Looks at several variants of pub/sub (e.g. topic, content, type) as well as similar schemes (e.g. RPC) and looks at how they enable decoupling participants in time/space/synchronization
    • These slides seem largely based on this paper & have some good figures/tables: http://www.extreme.indiana.edu/~gannon/b649/IntroToPublishSubscribe.ppt
• Disseminating Information to Mobile Clients Using Publish–Subscribe (IEEE IC 2004)
  • Overviews the Rebeca pub/sub system, which incorporates several mechanisms to support mobile users, including filter aggregation, reliable and persistent delivery, and several levels of QoS policies
• An Ontology-Based Publish/Subscribe System (Middleware 2004)
  • Uses a simple homed graph pattern matching scheme on central registrar to compare pubs to subs; no use of inference
• PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities
  • Overviews a P2P system for keyword search document retrieval built on gossiping and Bloom filters.
• Semantic Email Addressing (IEEE IC 2009)
  • Sending emails to queries over Semantic Web data which database resolves to sets of users.

Publishing/Peer Review

• Program Committee Overload in Systems (CACM 2009)
  • Describes several mechanisms that could be instituted to improve the peer review process---both motivating more researchers to review papers and reducing the number of papers submitted.
• Scaling the Academic Publication Process to Internet Scale (CACM 2009)
  • Describes several mechanisms that could be instituted to improve the peer review process---both motivating more researchers to review papers and reducing the number of papers submitted.

Robotics

• Intelligence without Representation (AIJ 1991)
  • AIs and robots must be situated in world, constructed through continual connection of smaller but complete behaviors.
• Fast, Cheap and Out of Control: A Robot Invasion of the Solar System (BIS 1989)
  • Swarms of small, simpler robots offer many advantages for interplanetary exploration.

Security

• Lest We Remember: Cold-Boot Attacks on Encryption Keys (CACM 2009)
  • Describes a process for finding keys in memory for several common algorithms, which is then applied to breaking encrypted disks after the machine has been physically stolen and its memory frozen to prevent state decay when the power is cut and transplanted to another machine for sifting.
• Exterminator: Automatically Correcting Memory Errors with High Probability (CACM 2008)
  • Buffer overflow and dangling pointer detection and correction via analysis of multiple randomized heaps.

Semantic Web/RDF/OWL

• RDFPeers: A Scalable Distributed {RDF} Repository Based on a Structured Peer-to-peer Network (WWW 2004)
  • Presents a scheme for distributing RDF triple stores through a reasonably simple scheme of pushing three copies, one each for pred/sub/obj, into a DHT, and querying in a straightforward way based on that.
• Ontologies and the Semantic Web (CACM 2008)
  • Overviews Semantic Web, RDF, OWL; good examples of reasoning and solid applications (mostly medical); highlights some ongoing developments.
• Bubo---Implementing OWL in Rule-Based Systems (WWW 2003)
  • Translation of OWL DL semantics to logic programming, relational databases.
• Semantic Sensor Web (IEEE IC 2008)
  • Annotating sensor network data with Semantic Web ontology markup to better facilitate querying and data fusion; no real discussion of architecture, but clearly centralized.
• 3D Media and the Semantic Web (IEEE IS 2009)
  • High level discussion of applicability and problems of annotating 3D data with Semantic Web markup.
• Semantic Email Addressing (IEEE IC 2009)
  • Sending emails to queries over Semantic Web data which database resolves to sets of users.

Sensor Networks

• Trickle: A Self-Regulating Algorithm for Code Propagation and Maintenance in Wireless Sensor Networks (NSDI 2004)
  • Introduces Trickle, a gossip protocol for data consistency maintenance on sensor networks which takes advantage of the broadcast medium and eavesdropping.
• On the Design of a Self-Managed Wireless Sensor Network (IEEE Communications 2005)
  • Very high level overview of an autonomic control system for a fire detecting wireless sensor network.
• Self-Managed Fault Management in Wireless Sensor Networks (UBICOMM 2008)
  • High level discussion of hardware monitoring and failure detection in a hierarchical sensor network.
• Irisnet: An Architecture for a Worldwide Sensor Web (IEEE Pervasive 2003)
  • Discussion of Irisnet, a framework for large scale integration of many sensors and users, employing service based computing and distributed databases.
• TAG: A Tiny Aggregation Service for Ad-Hoc Sensor Networks (OSDI 2002)
  • Introduces TAG, a system for aggregating readings in a sensor network.
• Diagnosis of Sensor Networks (ICC 2001)
  • Several basic approaches to collect information from sensor networks to discover faulty nodes.
• Distributed Fault Detection of Wireless Sensor Networks (DIWANS 2006)
  • Voting among neighbors to determine faulty sensors based on reported values.
• A High-Throughput Path Metric for Multi-Hop Wireless Routing (Wireless 2005)
  • Introduces ETX, estimated transmission count, for choosing higher quality paths of more hops versus inferior paths of less hops.
• Semantic Sensor Web (IEEE IC 2008)
  • Annotating sensor network data with Semantic Web ontology markup to better facilitate querying and data fusion; no real discussion of architecture, but clearly centralized.
• Agent Technologies for Sensor Networks (IEEE IS 2009)
  • Brief, high overview of several sensor systems utilizing agent based approaches, including DCOPs for coordination, and model estimation
• Challenges and Lessons in Developing Middleware on Smart Phones (IEEE Computer 2008)
  • Overviews limitations of current smart phone platforms, middleware requirements.

Social Networking

• Voyagers and Voyeurs: Supporting Asynchronous Collaborative Visualization (CACM 2009)
  • Describes sense.us, a Web-based system for asynchronous, distributed, collaborative data investigation incorporating doubly-linked comments, annotations, view indexing, and several clever implementation details.
• Semantic Email Addressing (IEEE IC 2009)
  • Sending emails to queries over Semantic Web data which database resolves to sets of users.

Software Engineering

• Intelligence without Representation (AIJ 1991)
  • AIs and robots must be situated in world, constructed through continual connection of smaller but complete behaviors.
• Fast, Cheap and Out of Control: A Robot Invasion of the Solar System (BIS 1989)
  • Swarms of small, simpler robots offer many advantages for interplanetary exploration.

Streams and Event Processing/Continuous Queries

• Cayuga: A General Purpose Event Monitoring System (CIDR 2007)
  • Outlines the Cayuga system for stream processing, which focuses on matching patterns over multiple events (tuples)

Visualization

• Voyagers and Voyeurs: Supporting Asynchronous Collaborative Visualization (CACM 2009)
  • Describes sense.us, a Web-based system for asynchronous, distributed, collaborative data investigation incorporating doubly-linked comments, annotations, view indexing, and several clever implementation details.

Grants

• NSF Community-based Data Interoperability Networks (INTEROP)
  • Group development of ontologies, protocols, other frameworks for science and engineering data exchange, archiving
• NSF Networking Technology and Systems (NeTS)
  • Wide ranging support for all manner of novel network architecture, protocol, etc.
• NIST Recovery Act Measurement Science and Engineering Research Grants
  • Pretty broad set of topics; CS related includes network measurement & management, testbeds

Raw