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: 3178
Venue: SIGMOD
Year: 1999
Pagerank: 7.5841142e-05
Overall Rank: 3,264 | 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
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
468	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017986163
4,325	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	6.7605683e-05
5,490	XWAVE: Optimal and Approximate Extended Wavelets for Streaming Data	2004	VLDB	6.200262e-05
5,650	Extended Wavelets for Multiple Measures	2003	SIGMOD	6.1337629e-05
8,655	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD	5.3910353e-05
11,957	Efficient Haar+ Synopsis Construction for the Maximum Absolute Error Measure	2018	VLDB	5.093636e-05
12,350	The Filter-Placement Problem and its Application to Minimizing Information Multiplicity	2012	VLDB	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
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00050347119
353	The Query By Image Content (QBIC) System	1995	SIGMOD	0.00020370587

Semantically Similar Papers

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