ZigZag: Supporting Similarity Queries on Vector Space Models

Summary: ZigZag uses inverted-index based methods for similarity search in vector-space models where records are token bags with token weights and per-record degrees. Pruning bounds with formal correctness and iterative tightening enable exact filtering of dissimilar records, scalable to disks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h71db90f8e8d7d4ed
Venue: SIGMOD
Year: 2018
Pagerank: 4.9793485e-05
Overall Rank: 12,228 | 17.79%
DOI: 10.1145/3183713.3196936

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Wenhai Li (Wuhan University)
2. Lingfeng Deng (Wuhan University)
3. Yang Li (Wuhan University)
4. Chen Li (University of California Irvine)

BibTeX Citation

@inproceedings{li_sigmod18,
        title = {{ZigZag: Supporting Similarity Queries on Vector Space Models}},
        author = {Li, Wenhai and Deng, Lingfeng and Li, Yang and Li, Chen},
        series = {{SIGMOD} '18},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3183713.3196936},
        url = {https://dl.acm.org/doi/10.1145/3183713.3196936},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040370171
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025331535
360	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020009936
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013020115
963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012816649
1,061	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012213729
1,421	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010726757
2,144	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	8.9608583e-05
2,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8146984e-05
2,513	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	8.3679178e-05
2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.8519256e-05
2,944	Spatio-Textual Similarity Joins	2013	VLDB	7.828107e-05
3,255	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4890984e-05
3,350	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	7.3910669e-05
3,403	Benchmarking Declarative Approximate Selection Predicates	2007	SIGMOD	7.3300953e-05
3,691	Exploiting MapReduce-based Similarity Joins	2012	SIGMOD	7.0935524e-05
4,439	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	6.5998035e-05
6,605	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.7367357e-05
7,228	OASSIS: Query Driven Crowd Mining	2014	SIGMOD	5.5805857e-05
9,122	A Probabilistic Model for Linking Named Entities in Web Text with Heterogeneous Information Networks	2014	SIGMOD	5.2255929e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,871	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD
2	12,784	Skip-and-Prune: Cosine-based Top-K Query Processing for Efficient Context-Sensitive Document Retrieval	2009	SIGMOD
3	7,856	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB
4	6,973	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
5	10,635	Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph	2026	SIGMOD
6	7,030	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
7	10,443	Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search	2026	SIGMOD
8	13,084	Efficiency-Quality Tradeoffs for Vector Score Aggregation	2004	VLDB
9	8,110	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD
10	2,060	Similarity search in the blink of an eye with compressed indices	2023	VLDB