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: hdbfeee02e81c7947
Venue: SIGMOD
Year: 1994
Pagerank: 9.1527591e-05
Overall Rank: 2,035 | 86.32%
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
81	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00036346781
1,448	Fast Incremental Indexing for Full-Text Information Retrieval	1994	VLDB	0.00010627619
3,110	Comparing Hybrid Peer-to-Peer Systems	2001	VLDB	7.6386801e-05
4,177	GraphJet: Real-Time Content Recommendations at Twitter	2016	VLDB	6.757191e-05
6,607	Wave-Indices: Indexing Evolving Databases	1997	SIGMOD	5.736384e-05
12,719	Pay-As-You-Go - An Adaptive Approach to Provide Full Context-Aware Text Search over Document Content	2010	SIGMOD	4.9793485e-05
12,985	Trustworthy Keyword Search for Regulatory-Compliant Records Retention	2006	VLDB	4.9793485e-05
13,213	A Multi-Similarity Algebra	1998	SIGMOD	4.9793485e-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,085	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00012112632
1,624	An Efficient Indexing Technique for Full-Text Database Systems	1992	VLDB	0.00010045219
2,622	The Rufus System: Information Organization for Semi-Structured Data	1993	VLDB	8.2118212e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,058	Optimizing Index for Taxonomy Keyword Search	2012	SIGMOD
2	9,653	Indexing for Keyword Search with Structured Constraints	2023	PODS
3	3,490	Updates for Structure Indexes	2002	VLDB
4	7,631	Scalable Distributed Inverted List Indexes in Disaggregated Memory	2024	SIGMOD
5	14,067	Query-based Partitioning of Documents and Indexes for Information Lifecycle Management	2008	SIGMOD
6	10,525	Fast Indexing for Temporal Information Retrieval	2026	SIGMOD
7	4,439	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD
8	12,188	Document Reordering for Faster Intersection	2019	VLDB
9	1,624	An Efficient Indexing Technique for Full-Text Database Systems	1992	VLDB
10	1,448	Fast Incremental Indexing for Full-Text Information Retrieval	1994	VLDB