Incremental Updates of Inverted Lists for Text Document Retrieval

Summary: Dual-structure index separates long and short inverted lists to optimize incremental updates, retrieval, and storage. Evaluates engineering trade-offs with real data and simulation to identify the best algorithm for various update/query criteria. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2796
Venue: SIGMOD
Year: 1994
Pagerank: 9.3486136e-05
Overall Rank: 1,989 | 86.36%
DOI: 10.1145/191839.191896

Incoming Non-self Citations Over Time

Authors

1. Anthony Tomasic (Stanford University)
2. Hector Garcia-Molina (Stanford University)
3. Kurt Shoens (IBM)

BibTeX Citation

@inproceedings{tomasic_sigmod94,
        title = {{Incremental Updates of Inverted Lists for Text Document Retrieval}},
        author = {Tomasic, Anthony and Garcia-Molina, Hector and Shoens, Kurt},
        series = {{SIGMOD} '94},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/191839.191896},
        url = {https://dl.acm.org/doi/10.1145/191839.191896},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
77	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00037048607
1,407	Fast Incremental Indexing for Full-Text Information Retrieval	1994	VLDB	0.00010856546
3,058	Comparing Hybrid Peer-to-Peer Systems	2001	VLDB	7.8069146e-05
4,254	GraphJet: Real-Time Content Recommendations at Twitter	2016	VLDB	6.8024576e-05
6,479	Wave-Indices: Indexing Evolving Databases	1997	SIGMOD	5.8671916e-05
12,428	Pay-As-You-Go - An Adaptive Approach to Provide Full Context-Aware Text Search over Document Content	2010	SIGMOD	5.093636e-05
12,695	Trustworthy Keyword Search for Regulatory-Compliant Records Retention	2006	VLDB	5.093636e-05
12,923	A Multi-Similarity Algebra	1998	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,059	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00012377809
1,587	An Efficient Indexing Technique for Full-Text Database Systems	1992	VLDB	0.00010269584
2,574	The Rufus System: Information Organization for Semi-Structured Data	1993	VLDB	8.3995947e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,896	Optimizing Index for Taxonomy Keyword Search	2012	SIGMOD
2	9,472	Indexing for Keyword Search with Structured Constraints	2023	PODS
3	3,421	Updates for Structure Indexes	2002	VLDB
4	7,492	Scalable Distributed Inverted List Indexes in Disaggregated Memory	2024	SIGMOD
5	13,756	Query-based Partitioning of Documents and Indexes for Information Lifecycle Management	2008	SIGMOD
6	10,315	Fast Indexing for Temporal Information Retrieval	2026	SIGMOD
7	4,359	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD
8	11,888	Document Reordering for Faster Intersection	2019	VLDB
9	1,587	An Efficient Indexing Technique for Full-Text Database Systems	1992	VLDB
10	1,407	Fast Incremental Indexing for Full-Text Information Retrieval	1994	VLDB