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.4163853e-05
Overall Rank: 3,332 | 77.60%
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
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021384073
478	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017631293
4,416	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.6089486e-05
5,622	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.0614658e-05
5,785	Extended Wavelets for Multiple Measures	2003	SIGMOD	5.9961546e-05
8,818	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	5.2700772e-05
12,255	Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure	2018	VLDB	4.9793485e-05
12,641	The Filter-Placement Problem and its Application to Minimizing Information Multiplicity	2012	VLDB	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
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
32	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00049737458
353	The Query By Image Content (QBIC) System	1995	SIGMOD	0.00020222998

Semantically Similar Papers

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