S4: Top-k Spreadsheet-Style Search for Query Discovery

Summary: S4 proposes top-k project-join query discovery with approximate containment of user-provided example tuples. It enables spreadsheet-style, incremental search that returns results as users type or edit a cell, delivering substantial efficiency gains over prior state-of-the-art. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5131
Venue: SIGMOD
Year: 2015
Pagerank: 8.6482009e-05
Overall Rank: 2,387 | 83.63%
DOI: 10.1145/2723372.2749452

Incoming Non-self Citations Over Time

Authors

1. Fotis Psallidas (Columbia University)
2. Bolin Ding (Microsoft)
3. Kaushik Chakrabarti (Microsoft)
4. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@inproceedings{psallidas_sigmod15,
        title = {{S4: Top-k Spreadsheet-Style Search for Query Discovery}},
        author = {Psallidas, Fotis and Ding, Bolin and Chakrabarti, Kaushik and Chaudhuri, Surajit},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2749452},
        url = {https://dl.acm.org/doi/10.1145/2723372.2749452},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,198	Overview of Data Exploration Techniques	2015	SIGMOD	0.00011706307
2,025	Data Market Platforms: Trading Data Assets to Solve Data Problems	2020	VLDB	9.2903125e-05
2,048	Duoquest: A Dual-Specification System for Expressive SQL Queries	2020	SIGMOD	9.2560185e-05
3,677	Example-Driven Query Intent Discovery: Abductive Reasoning using Semantic Similarity	2019	VLDB	7.2076465e-05
6,200	New Trends on Exploratory Methods for Data Analytics	2017	VLDB	5.9457282e-05
6,461	Explain3D: Explaining Disagreements in Disjoint Datasets	2019	VLDB	5.8718966e-05
6,523	Combining Design and Performance in a Data Visualization Management System	2017	CIDR	5.8518572e-05
7,093	DICE: Data Discovery by Example	2021	VLDB	5.7056625e-05
8,358	Exploring the Data Wilderness through Examples	2019	SIGMOD	5.4446041e-05
8,362	EQUI-VOCAL: Synthesizing Queries for Compositional Video Events from Limited User Interactions	2023	VLDB	5.4432545e-05
8,987	Constructing Expressive Relational Queries with Dual-Specification Synthesis	2020	CIDR	5.3387464e-05
9,368	SQuID: Semantic Similarity-Aware Query Intent Discovery	2018	SIGMOD	5.2778771e-05
10,486	Qualitative Join Discovery in Data Lakes using Examples	2026	SIGMOD	5.093636e-05
11,787	SPARQL Rewriting: Towards Desired Results	2020	SIGMOD	5.093636e-05
12,072	Exploring Databases via Reverse Engineering Ranking Queries with PALEO	2016	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
37	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00048017193
128	Efficient and Extensible Algorithms for Multi Query Optimization	2000	SIGMOD	0.0003072825
212	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB	0.000247733
517	Query by Output	2009	SIGMOD	0.00017169735
796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD	0.00013932561
930	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.0001312728
1,262	Discovering Queries based on Example Tuples	2014	SIGMOD	0.00011427456
1,313	Reverse Engineering Complex Join Queries	2013	SIGMOD	0.00011186284
1,751	Sample-Driven Schema Mapping	2012	SIGMOD	9.838446e-05
1,883	ReStore: Reusing Results of MapReduce Jobs	2012	VLDB	9.5421713e-05
3,163	Multi-Query Optimization in MapReduce Framework	2014	VLDB	7.6784171e-05
4,048	Efficient Type-Ahead Search on Relational Data: a TASTIER Approach	2009	SIGMOD	6.9372074e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,048	Efficient Type-Ahead Search on Relational Data: a TASTIER Approach	2009	SIGMOD
2	635	Evaluating Top-k Selection Queries	1999	VLDB
3	37	DISCOVER: Keyword Search in Relational Databases	2002	VLDB
4	212	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB
5	12,331	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB
6	3,317	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB
7	8,378	Discovering the Skyline of Web Databases	2016	VLDB
8	12,308	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
9	7,550	Processing Top-k Join Queries	2010	VLDB
10	1,262	Discovering Queries based on Example Tuples	2014	SIGMOD