WALRUS: A Similarity Retrieval Algorithm for Image Databases

Summary: WALRUS: region-based image similarity, robust to scaling and translation, by matching regions rather than global signatures. Regions from sliding windows; wavelet-based signatures computed by DP; similarity equals area fraction of matching regions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h05985606a58283c9
Venue: SIGMOD
Year: 1999
Pagerank: 7.3884891e-05
Overall Rank: 3,341 | 77.61%
DOI: 10.1145/304182.304217

Incoming Non-self Citations Over Time

Authors

1. Apostol Natsev (Duke University)
2. Rajeev Rastogi (AT&T)
3. Kyuseok Shim (AT&T)

BibTeX Citation

@inproceedings{natsev_sigmod99,
        title = {{WALRUS: A Similarity Retrieval Algorithm for Image Databases}},
        author = {Natsev, Apostol and Rastogi, Rajeev and Shim, Kyuseok},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304217},
        url = {https://dl.acm.org/doi/10.1145/304182.304217},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
311	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021315058
481	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017567157
4,438	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.5840202e-05
5,636	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.0385837e-05
5,800	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.9735022e-05
8,844	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	5.2501688e-05
12,304	Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure	2018	VLDB	4.9605343e-05
12,690	The Filter-Placement Problem and its Application to Minimizing Information Multiplicity	2012	VLDB	4.9605343e-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
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
32	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00049559562
350	The Query By Image Content (QBIC) System	1995	SIGMOD	0.0002018411

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,144	Similarity Search for Web Services	2004	VLDB
2	5,558	Earth Mover’s Distance based Similarity Search at Scale	2014	VLDB
3	361	A Retrieval Technique for Similar Shapes	1991	SIGMOD
4	1,996	WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases	1998	VLDB
5	6,167	An Information Retrieval Approach for Image Databases	1992	VLDB
6	13,201	An Extendible Hash for Multi-Precision Similarity Querying of Image Databases	2001	VLDB
7	1,825	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB
8	13,281	Algorithms for Querying by Spatial Structure	1998	VLDB
9	9,372	Qcluster: Relevance Feedback Using Adaptive Clustering for Content-Based Image Retrieval	2003	SIGMOD
10	13,351	Similarity based Retrieval of Pictures Using Indices on Spatial Relationships	1995	VLDB