Stanford InfoLab InfoQual 2018

InfoQual consists of an oral exam where a committee of three faculty asks questions on five different topics. The oral exam requires passing all five topics. The topics from past exams are listed below; more topics can be added, subject to approval of the InfoLab faculty. The oral exam takes 1.5 hours and covers all five chosen topics. It is conducted by a committee of 3 faculty (InfoLab or otherwise). Details of the oral exam -- faculty involved, scheduling, and topics -- are coordinated by the student and student's advisor. The student is expected to be able to explain and critique in detail the readings for each topic, including the premises, contributions, impact, and shortcomings of the work. The outcome of the entire oral exam is a simple pass or fail; it is not a score, and it is not possible to pass some topics and fail others.

If you have any questions about the InfoQual talk to Jure Leskovec (jure@cs.stanford.edu).

How to register for the InfoQual

In the table below please fill in the time, exam location, the topics and a professor for each of the 5 oral topics. Students check with the committee members about their availability and topics they will quiz them on. Students also need to book a room for the oral exam. After the exam is over one of the faculty should email Jure the outcome (pass/fail).

Topics for the oral exam

These topics were used by previous students who took the InfoQual. Adding/customizing topics is easy. If students want to do that, students have to find a professor who will prepare and approve the list of papers and then quiz the student on them.

Web Search  (Approved  by Hector)

• The Impact of Caching on Search Engines -- Baeza-Yates et al., SIGIR 2007
• Efficient Crawling Through URL Ordering -- Cho, Garcia-Molina, & Page, WWW 1998
• The Anatomy of a Large-Scale Hypertextual Web Search Engine -- Brin & Page, Computer Networks 1998

Small-world networks and Decentralized search (Approved by Jure)

• Wayfinding in Social Networks -- Liben-Nowell, Algorithms for Next Generation Networks 2010
• The Small-world Phenomenon: An Algorithmic Perspective -- Kleinberg, STOC 2000
• How Do Networks Become Navigable? -- Clauset and Moore, arXiv:cond-mat/0309415v2, 2003
• An Experimental Study of the Small World Problem -- Travers and Milgram, Sociometry 1969

Power-laws and Preferential attachment (Approved by Jure)

• M.E.J. Newman. Power laws, Pareto distributions and Zipf's law. Contemporary Physics 46(5), 323-351, 2005.
• A. Clauset, C.R. Shalizi, and M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009.
• A.L. Barabasi, R. Albert. Emergence of scaling in random networks. Science, 286, 1999.

Link Analysis (Approved by Jure)

• A Survey on PageRank Computing -- Berkhin, Internet Mathematics 2005
• Combating Web Spam with TrustRank -- Gyöngyi et al., VLDB 2004

Community structure in networks (Approved by Jure)

• M. Granovetter. The strength of weak ties. American Journal of Sociology, 78(6):1360-1380, 1973.
• S. Fortunato. Community detection in graphs. http://arxiv.org/abs/0906.0612
• Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach by J. Yang, J. Leskovec. ACM International Conference on Web Search and Data Mining (WSDM), 2013.

Cascading Behavior in Networks (Approved by Jure)

• Jon Kleinberg. Cascading Behavior in Networks: Algorithmic and Economic Issues. In Algorithmic Game Theory, Eds. Nisan, et al. 2007
• Centola, Macy: Complex contagions and the weakness of long ties, American Journal of Sociology, 113:702–734, 2007
• J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, N. Glance. Cost-effective Outbreak Detection in Networks. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2007.

Frequent Itemsets (Approved by Jeff)

• Frequent Itemsets -- Ullman book chapter 6
• Mining Frequent Patterns without Candidate Generation, Han et al., SIGMOD 2000
• Discovering Frequent Episodes in Sequences. Mannila et al., ICDM 1995

Finding similar items (Approved by Jeff)

• Finding Similar Items -- Ullman book chapter 3
• Finding Near-duplicate Web Pages: a Large-scale Evaluation of Algorithms -- Henzinger, SIGIR 2006
• Similarity Search in High Dimensions via Hashing -- Gionis et al., VLDB 1999

Distributed Graph Computation Systems  -- Jennifer, Peter, Matei

• Pregel: a System for Large-Scale Graph Processing -- Malewicz et al., SIGMOD 2010
• Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud – Low et al., VLDB 2012 (pdf)
• PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations -- Kang, Tsourakakis, & Faloutsos, ICDM 2009

MapReduce, Pig, Hive  -- Hector or Jennifer

• MapReduce: A Flexible Data Processing Tool -- Dean & Ghemawat, CACM 2010

• Bigtable: A Distributed Storage System for Structured Data – Chang et al., OSDI 2006 (pdf)

• Pig Latin: a Not-so-Foreign Language for Data Processing -- Olston et al., SIGMOD 2008
• Hive - A Petabyte Scale Data Warehouse Using Hadoop -- Thusoo et al., ICDE 2010

Parallel Database Systems  -- Hector, Peter, Matei

• Parallel Database Systems: Open Problems and New Issues -- Valduriez, DAPD 1993
• Parallel Database Systems: The Future of High Performance Database Systems -- CACM 1992

Theory of MapReduce  -- Jeff

• A Model of Computation for MapReduce -- Karloff, Suri, & Vassilvitskii, SODA 2010
• Counting Triangles and the Curse of the Last Reducer -- Suri & Vassilvitskii, WWW 2011
• Optimizing Joins in a Map-Reduce Environment -- Afrati & Ullman, EBDT 2010

Conjunctive Query Containment  -- Jeff

• Conjunctive Queries -- Ullman lecture notes
• Extended Conjunctive Queries -- Ullman lecture notes
• Answering Queries Using Views -- Levy et al., PODS 1995

Graph Query Languages and Data Models – Jennifer

• Query Languages for Graph Databases – Wood, SIGMOD Record 2012 (pdf)
• Survey of Graph Database Models – Angles & Gutierrez, CSUR 2008 (pdf)
• Semantics and Complexity of SPARQL – Pérez et al., ISWC 2006 (pdf)

Visual Data Analytics – Andreas

• 30 Years of Multidimensional Multivariate Visualization – Wong & Bergeron, Scientific Visualization, Overviews, Methodologies, and Techniques 1997 (pdf)
• A Tour through the Visualization Zoo – Heer et al., ACM Queue 2010 (pdf)
• Profiler: Integrated Statistical Analysis and Visualization for Data Quality Assessment – Kandel et al., AVI 2012 (pdf)

Interactive Data Analysis Systems – Hector, Matei, Peter

• Dremel: Interactive Analysis of Web-Scale Datasets – Melnik et al., VLDB 2010 (pdf)
• Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing – Zaharia et al., NSDI 2012 (pdf)

Crowdsourcing Algorithms  -- Hector

• Decision-Theoretic Control of Crowd-Sourced Workflows -- Dai, Mausam, & Weld, AAAI 2010
• Human-Assisted Graph Search: It's Okay to Ask Questions -- Parameswaran et al., VLDB 2010
• Get Another Label? Improving Data Quality and Data Mining Using Multiple, Noisy Labelers -- Sheng, Provost, & Ipeirotis, KDD 2008

Crowdsourcing Systems  -- Jennifer

• CrowdDB: Answering Queries with Crowdsourcing -- Franklin et al., SIGMOD 2011
• Turkit: Human Computation Algorithms on Mechanical Turk -- Little et al., UIST 2010
• Labeling Images with a Computer Game -- von Ahn & Dabbish, CHI 2004

Peer to Peer  -- Hector, Matei, Peter

• Designing a Super-Peer Network -- Yang & Garcia-Molina, ICDE 2003
• Routing Indices For Peer-to-Peer Systems -- Crespo & Garcia-Molina, ICDCS 2002
• Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications -- Stoica et al., SIGCOMM 2001

Distributed Transactions -- Peter, Matei

• The dangers of replication and a solution -- Gray et al., SIGMOD 1996
• Spanner: Google's Globally-Distributed Database -- Corbett et al., OSDI 2012
• Coordination Avoidance in Database Systems -- Bailis et al., VLDB 2015

Streaming Analytics Engines -- Peter, Matei

• TelegraphCQ: continuous dataflow processing -- Chandrasekaran et al., CIDR 2003
• Continuous analytics over discontinuous streams -- Krishnamurthy et al., SIGMOD 2010
• Discretized streams: Fault-tolerant streaming computation at scale -- Zaharia et al., SOSP 2013

Parallel Model Training -- Peter, Matei

• Dimmwitted: A study of main-memory statistical analytics -- Zhang and Re, VLDB 2014
• Scaling Distributed Machine Learning with the Parameter Server -- Li et al., OSDI 2014
• TensorFlow: A system for large-scale machine learning -- Abadi et al., OSDI 2016

Resource-Constrained Query Processing -- Peter, Matei

• TAG: A tiny aggregation service for ad-hoc sensor networks -- Madden et al., OSDI 2002
• Model-driven data acquisition in sensor networks -- Deshpande et al., VLDB 2004
• Global Analytics in the Face of Bandwidth and Regulatory Constraints -- Vulimiri et al., NSDI 2015

Sketching and Synopses -- Peter, Matei

• Synopses for massive data: Samples, histograms, wavelets, sketches -- Cormode et al., Foundations and Trends in Databases, 2012
• Finding frequent items in data streams -- Cormode and Hadjieleftheriou, VLDB 2008
• BlinkDB: Queries with Bounded Errors and Bounded Response Times on Very Large Data, Agarwal et al., EuroSys 2013

Model Serving and Fast Inference -- Peter, Matei

• The missing piece in complex analytics: Low latency, scalable model management and serving with Velox -- Crankshaw et al., CIDR 2015
• MauveDB: supporting model-based user views in database systems -- SIGMOD 2006
• Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding -- Han et al., ICLR 2016

Design of Parallel Dataflow Engines -- Peter, Matei

• Encapsulation of parallelism in the Volcano query processing system -- Graefe, SIGMOD 1990
• Dryad: distributed data-parallel programs from sequential building blocks -- Isard et al., SOSP 2007
• Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing -- Zaharia et al., NSDI 2012

Replication, Consensus, Distributed Agreement -- Peter, Matei

• Implementing fault-tolerant services using the state machine approach: A tutorial -- Schneider, ACM CSUR, 1990
• Paxos; suggested reading: The part-time parliament -- Lamport, ACM TOCS, 1998; Paxos made moderately complex -- Van Renesse and Altinbuken, ACM CSUR, 2015
• How Fast Can a Distributed Transaction Commit? -- Guerraoui and Wang, SIGMOD 2017

Internet + Information Integration -- Peter, Matei

• Combining systems and databases: A search engine retrospective -- Brewer, Readings in Database Systems, Fourth Edition, 2005.
• WebTables: exploring the power of tables on the web -- Cafarella et al., VLDB, 2008
• SLiMFast: Guaranteed Results for Data Fusion and Source Reliability -- Joglekar et al., SIGMOD 2017

Languages for Analytics -- Peter, Matei

• DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a High-Level Language -- Yu et al., OSDI 2008
• The CQL Continuous Query Language: Semantic Foundations and Query Execution -- Arasu et al., VLDB Journal, 2006
• Spark SQL: Relational data processing in Spark -- Armbrust et al., SIGMOD 2015

Materialized Views -- Peter, Matei

• Efficiently updating materialized views -- Blakeley et al., SIGMOD 1986
• Automated Selection of Materialized Views and Indexes in SQL Databases -- Agrawal et al., SIGMOD 2000
• Mesa: Geo-replicated, near real-time, scalable data warehousing -- Gupta et al., SIGMOD 2014

Additional non-core InfoLab topics

Networking

Quizzer: Keith Winstein

Quizzees: John Emmons

• V. Jacobson and M. J. Karels, Congestion Avoidance and Control, SIGCOMM 1988.
• R. Ensafi, Examining How the Great Firewall Discovers Hidden Circumvention, ICM 2015.
• J. Sherry et al., BlindBox: Deep Packet Inspection over Encrypted Traffic, SIGCOMM 2015.

Data Compression

Quizzer: Keith Winstein

Quizzees: John Emmons

• Valin et al., "High-Quality, Low-Delay Music Coding in the Opus Codec", AES 135
• D. Horn et al. "The Design, Implementation, and Deployment of a System to Transparently Compress Hundreds of Petabytes of Image Files for a File-Storage Service", NSDI 2017
• Chapters 4, 8-9, 12-13, and 18 from "Introduction to Data Compression" (Sayood 3rd Edition)

Inference surrounding linear regression models (approved by Lester Mackey)

Quizzer: Lester Mackey

Quizzees: Hima

• Chapter 3 of An Introduction to Statistical Learning

• Linear regression, accuracy of coefficients, testing for variable association

• Chapters 2, 3, 4 of "Applied Linear Regression" by Weisberg

• Covers Simple Linear Regression, Multiple Linear Regression, and Drawing Conclusions (from linear regression models)

Feature selection and variable importance (approved by Lester Mackey)

Quizzer: Lester Mackey

Quizzees: Hima

• Sections 6.1, 6.2, 6.4 of An Introduction to Statistical Learning

• Covers best subset, stepwise regression, and Lasso for model selection

• ESL Section 15.3

• Random forest variable importance

• Regression Shrinkage and Selection via the Lasso http://www.jstor.org/stable/2346178?seq=1#page_scan_tab_contents
• Random Forests http://link.springer.com/article/10.1023/A:1010933404324

Sentiment Analysis (approved by Dan Jurafsky)

Quizzer: Dan Jurafsky

Quizzees: Bob, Hima

- Bing Liu. "Sentiment Analysis and Subjectivity." In the Handbook of

Natural Language Processing, Second Edition. March, 2010.

http://www.cs.uic.edu/~liub/FBS/NLP-handbook-sentiment-analysis.pdf

- Danescu-Niculescu-Mizil, Cristian, Gueorgi Kossinets, Jon Kleinberg, Lillian Lee. 2009. How opinions are received by online communities: A case study on Amazon.com helpfulness votes. Proceedings of WWW, 141-150.

- Pang, Bo, Lee, Lillian, and Vaithyanathan, Shivakumar. 2002. Thumbs up? Sentiment classification using machine learning techniques. EMNLP 2002.

Information Extraction (approved by Dan Jurafsky)

Quizzer: Dan Jurafsky

Quizzees: Bob

- IE chapter in Dan J’s NLP book

- Banko, M. and Etzioni, O. The tradeoffs between traditional and open relation extraction. In ACL 2008.

- Weld, D., Wu, F., Adar, E., Amershi, S., Fogarty, J., Hoffmann, R., Patel, K. and Skinner, M. Intelligence in Wikipedia. In AAAI 2008.

Social Choice Theory (Approved by Ashish Goel)

Quizzer: Ashis Goel

Quizzees: Christie, Peter

-- Y. Shoham and K. Leyton-Brown, Aggregating Preferences: Social Choice, Chapter in Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations.

-- A. Altman and M. Tennenholtz,  Ranking Systems: The PageRank Axioms (EC 2005).

-- K. Arrow, A Difficulty in the Concept of Social Welfare (Journal of Political Economy 1950). 

Network Formation (approved by Ashish Goel)

Quizzee: Christie

--Venkatesh Bala and Sanjeev Goyal.  A Noncooperative Model of Network Formation. Econometrica , Vol. 68, No. 5 (Sep., 2000), pp. 1181-1229          http://www.jstor.org/stable/2999447

--M. Jackson and Brian W. Rogers. "Search and the strategic formation of large networks: when and why do we see power laws and small worlds." Proceedings of the Second Workshop on the Economics of Peer-to-Peer Systems (Cambridge, MA. 2004.)

--Jackson, Matthew O., and Brian W. Rogers. "Meeting strangers and friends of friends: How random are social networks?." The American economic review (2007): 890-915.

--Dandekar, Pranav, et al. "Strategic formation of credit networks." Proceedings of the 21st international conference on World Wide Web. ACM, 2012.

Regularization (Approved by Mohsen Bayati)

Quizzer: Mohsen Bayati

Quizzees: Chenguang

-- Review: Trevor Hastie, Robert Tibshirani, Jerome Friedman. Chapter 3 of The Elements of Statistical Learning.

-- Review 2: Friedman,  J. H., Hastie, T. and Tibshirani, R. Regularized Paths for Generalized Linear Models via Coordinate Descent, Journal of Statistical Software, 33(1) (2008).

Review: F. Girosi, M. Jones and T. Poggio, Regularization Theory and Neural Networks Architectures, In Neural Computation, pp. 219-269, 1995

-- M. W. Mahoney and L. Orecchia, Implementing Regularization Implicitly Via Approximate Eigenvector Computation, In Proc. ICML 2011

-- P. Perry and M. Mahoney, Regularized Laplacian Estimation and Fast Eigenvector Approximation, In Proc. NIPS 2011

Social Choice Theory (Approved by Yoav)

Quizzer: Yoav Shoham

Quizzees: Ashton

-- Y. Shoham and K. Leyton-Brown, Aggregating Preferences: Social Choice, Chapter in Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations.

-- A. Altman and M. Tennenholtz,  Ranking Systems: The PageRank Axioms (EC 2005).

-- K. Arrow, A Difficulty in the Concept of Social Welfare (Journal of Political Economy 1950).

Mechanism Design (Approved by Yoav)

Quizzer: Yoav Shoham

Quizzees: Ashton

-- Y. Shoham and K. Leyton-Brown, Protocols for Strategic Agents: Mechanism Design, Chapter in Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations.

-- T. Roughgarden, Lecture Notes on Combinatorial Auctions.

Graph Layout and Network Visualization (Jeff Heer):

Survey: Herman, et al. Graph Visualization and Navigation in Information Visualization: A Survey. IEEE TVCG 2000.

Articles:

• Ghoniem, et al. A Comparison of the Readability of Graphs Using Node-Link and Matrix-Based Representations. InfoVis 2004.

• Dwyer, et al. Dig-cola: Directed graph layout through constrained energy minimization. InfoVis 2005.
• Dwyer #2

Text Visualization (Jeff Heer):

Survey: Hearst. Information Visualization for Text Analysis. Search User Interfaces (Chap. 11).

Articles:

• van Ham, et al. Mapping Text with Phrase Nets. InfoVis 2009.

Articles:

• Viegas, et al. Visualizing Email Content: Portraying Relationships from Conversational Histories. CHI 2006.
• Stasko, et al. Jigsaw: supporting investigative analysis through interactive visualization. Information Visualization (2008) 7, 118-132.
• Chuang, et al. TOCHI paper on Keyphrases Generation.

Crowds and Human Computation (Scott):

Survey:

• Quinn, et al. Human Computation: A Survey and Taxonomy of a Growing Field. CHI 2011.
• (Selections from): Law & von Ahn. Human Computation.

Articles:

• Kittur, et al. Harnessing the Wisdom of Crowds in Wikipedia: Quality through Coordination. CSCW 2008.
• von Ahn, et al. Peekaboom: A Game for Locating Objects in Images. CHI 2006.
• Bernstein, et al. Soylent: A Word Processor with a Crowd Inside. UIST 2010.

Alternate:

• von Ahn, et al. Designing Games with a Purpose. CACM 2008.
• Huberman, et al. Crowdsourcing, Attention and Productivity. Journal of Information Science, 2009.

Social Systems (Scott):

Survey: Some chapter from: Kraut & Resnick. Building Successful Online Communities: Evidence-Based Social Design. (In Press).

Articles:

• Gilbert, et al. Predicting Tie Strength with Social Media. CHI 2009
• Resnick, et al. Recommender Systems. CACM 40(3). 1997, p.56-58.

Alternate:

• Kittur, et al. Harnessing the Wisdom of Crowds in Wikipedia: Quality through Coordination. CSCW 2008.
• The Benefits of Facebook "Friends:" Social Capital and College Students' Use of Online Social Network Sites by Ellison, Steinfield & Lampe
• Is It Really About Me?: Message Content in Social Awareness Streams by Naaman, Boase & Lai
• Peaks and Persistence: Modeling the Shape of Microblog Conversations
• by Shamma, Kennedy & Churchill

Social Computing (Michael):

• Ling, K., Beenen, G., Ludford, P., Wang, X., Chang, K., Li, X., ... & Kraut, R. (2005). Using social psychology to motivate contributions to online communities. Journal of Computer‐Mediated Communication, 10(4), 00-00.
• Kittur, A., & Kraut, R. E. (2008, November). Harnessing the wisdom of crowds in wikipedia: quality through coordination. In Proceedings of the 2008 ACM conference on Computer supported cooperative work (pp. 37-46). ACM.
• Gilbert, E., & Karahalios, K. (2009, April). Predicting tie strength with social media. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (pp. 211-220). ACM.

Social Systems (Michael):

• Grudin, J. (1994). Groupware and social dynamics: Eight challenges for developers. Communications of the ACM, 37(1), 92-105.
• Horowitz, D., & Kamvar, S. D. (2010, April). The anatomy of a large-scale social search engine. In Proceedings of the 19th international conference on World wide web (pp. 431-440). ACM.
• Lasecki, W., Miller, C., Sadilek, A., Abumoussa, A., Borrello, D., Kushalnagar, R., & Bigham, J. (2012, October). Real-time captioning by groups of non-experts. In Proceedings of the 25th annual ACM symposium on User interface software and technology (pp. 23-34). ACM.

Info Qual 2012

Info Qual 2013

InfoQual 2014: