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.9605343e-05
Overall Rank: 12,277 | 17.71%
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.0004024707
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00032945275
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027077763
202	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025244506
359	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00019963275
934	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00012973416
966	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012777679
1,068	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012170201
1,424	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010694144
2,158	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	8.9272802e-05
2,235	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.7832223e-05
2,514	An Empirical Evaluation of Set Similarity Join Techniques	2016	VLDB	8.3446573e-05
2,933	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.827041e-05
2,957	Spatio-Textual Similarity Joins	2013	VLDB	7.799694e-05
3,270	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4613275e-05
3,359	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	7.3640394e-05
3,412	Benchmarking Declarative Approximate Selection Predicates	2007	SIGMOD	7.3073062e-05
3,695	Exploiting MapReduce-based Similarity Joins	2012	SIGMOD	7.0720169e-05
4,462	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	6.5751733e-05
6,617	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.7150599e-05
7,241	OASSIS: Query Driven Crowd Mining	2014	SIGMOD	5.5620382e-05
9,152	A Probabilistic Model for Linking Named Entities in Web Text with Heterogeneous Information Networks	2014	SIGMOD	5.2058483e-05

Semantically Similar Papers

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