We introduce a wait-free, multi-reader, single-writer, "kill -9" durable, indexing structure for in-memory social graph databases. This structure requires no communication from the readers back to the writer, allowing for trivial read scalability and isolation. We support online updates without compromising availability or read performance. Our structure supports looking up small subgraphs in 80 nanoseconds and a materialization rate of 12 nanoseconds per edge. Storage takes 7 bytes per edge per index and supports almost 1 million online writes per second.

In order to efficiently serve a high volume of queries, LinkedIn's distributed graph service caches computationally-expensive materialized views. Despite this, even basic view maintenance has been a scalability bottleneck. In this paper, we introduce Partial Update, which efficiently applies incremental view maintenance in the absence of deletions in a materialized view. Without expensive transaction handling, Partial Update guarantees eventual consistency across source of truth databases, materialized views and base relations stores. By design, its delta change computation logic only produces lightweight queries, reducing any need to augment the underlying data storage systems. This allows Partial Update to seamlessly integrate on top of traditional eventually consistent systems. In LinkedIn's production systems, Partial Update achieves up to a 50% reduction in both maintenance time and network bandwidth utilization. The improved view maintenance scalability allows us to improve the quality of cached data by a factor of 20. We consider that Partial Update is general enough to be applicable to the majority of select-project-join view maintenance strategies in eventually consistent distributed data stores.

Many Online Social Networks horizontally partition data across data stores. This allows the addition of server nodes to increase capacity and throughput. For single key lookup queries such as computing a member's 1st degree connections, clients need to generate only one request to one data store. However, for multi key lookup queries such as computing a 2nd degree network, clients need to generate multiple requests to multiple data stores. The number of requests to fulfill the multi key lookup queries grows in relation to the number of partitions. Increasing the number of server nodes in order to increase capacity also increases the number of requests between the client and data stores. This may increase the latency of the query response time because of network congestion, tail-latency, and CPU bounding. Replication based partitioning strategies can reduce the number of requests in the multi key lookup queries. However, reducing the number of requests in a query can degrade the performance of certain queries where processing, computing, and filtering can be done by the data stores. A better system would provide the capability of controlling the number of requests in a query. This paper presents Moolle, a system of controlling the number of requests in queries to scalable distributed data stores. Moolle has been implemented in the LinkedIn distributed graph service that serves hundreds of thousands of social graph traversal queries per second. We believe that Moolle can be applied to other distributed systems that handle distributed data processing with a high volume of variable-sized requests.

Computer-assisted photo album creation continues to be a challenging application as it requires integrated technical solutions to many difficult problems. Effective solutions must leverage both design knowledge and image understanding algorithms to automate time-consuming tasks like image selection, grouping, cropping, layout and background selection. At the same time, they should allow the user to cater to personal tastes by fine-tuning aspects of album appearance. MagicPhotobook is a photobook authoring system that takes steps in these directions by providing advances over prior solutions in the following areas: automatic image selection and theme-based image grouping; dynamic page layout; automatic cropping; automatic background selection; design-preserving background artwork transformation; and a simple yet powerful user interface for personalization.