Similarity Search: A Matching Based Approach

Summary: Recasts similarity search as k-n-match, dynamically selecting n of d attributes to expose partial matches and avoid domination by highly dissimilar dimensions. A frequent variant aggregates answers across n, with attribute-optimal, disk-based algorithms outperforming kNN empirically. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9668
Venue: VLDB
Year: 2006
Pagerank: 5.8667204e-05
Overall Rank: 6,483 | 55.53%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Anthony K. H. Tung (National University of Singapore)
2. Rui Zhang (University of Melbourne)
3. Nick Koudas (University of Toronto)
4. Beng Chin Ooi (National University of Singapore)

BibTeX Citation

@article{tung_vldb06,
        title = {{Similarity Search: A Matching Based Approach}},
        author = {Tung, Anthony K. H. and Zhang, Rui and Koudas, Nick and Ooi, Beng Chin},
        journal = {PVLDB},
        series = {{VLDB} '06},
        pages = {631--642},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,572	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010329197
7,708	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB	5.5628618e-05
8,485	Diversity based Relevance Feedback for Time Series Search	2014	VLDB	5.4155551e-05
12,677	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
85	The X-tree: An Index Structure for High-Dimensional Data	1996	VLDB	0.00035405879
170	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00027376361
350	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00020425134
690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.0001492934
1,384	Content-Based Image Indexing	1994	VLDB	0.00010957733
2,158	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.0622995e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
2	1,776	Efficient User-Adaptable Similarity Search in Large Multimedia Databases	1997	VLDB
3	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
4	6,746	Flexible Aggregate Similarity Search	2011	SIGMOD
5	3,353	Efficient EMD-based Similarity Search in Multimedia Databases via Flexible Dimensionality Reduction	2008	SIGMOD
6	796	Optimal Multi-Step k-Nearest Neighbor Search	1998	SIGMOD
7	3,866	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
8	12,371	Effective Data Co-Reduction for Multimedia Similarity Search	2011	SIGMOD
9	13,724	Techniques for Similarity Searching in Multimedia Databases	2010	VLDB
10	3,363	Efficient k-NN Search on Vertically Decomposed Data	2002	SIGMOD