Similarity Search on Bregman Divergence: Towards Non-Metric Indexing

Summary: Enables nearest-neighbor and range indexing for non-metric Bregman divergences, including KL and Itakura–Saito, without symmetry or triangle inequality. Maps points to an extended space, adapting R-trees/VA-files with tighter bounds and distribution-aware optimization. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10091
Venue: VLDB
Year: 2009
Pagerank: 5.5628618e-05
Overall Rank: 7,708 | 47.12%
DOI: 10.14778/1687627.1687630

Incoming Non-self Citations Over Time

Authors

1. Zhenjie Zhang (National University of Singapore)
2. Beng Chin Ooi (National University of Singapore)
3. Srinivasan Parthasarathy (Ohio State University)
4. Anthony K.H. Tung (National University of Singapore)

BibTeX Citation

@article{zhang_vldb09,
        title = {{Similarity Search on Bregman Divergence: Towards Non-Metric Indexing}},
        author = {Zhang, Zhenjie and Ooi, Beng Chin and Parthasarathy, Srinivasan and Tung, Anthony K.H.},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687630},
        url = {https://doi.org/10.14778/1687627.1687630},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.649474e-05
4,112	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.8944534e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
12,366	Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables	2011	SIGMOD	5.093636e-05
12,371	Effective Data Co-Reduction for Multimedia Similarity Search	2011	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
2,509	Foundations of Probabilistic Answers to Queries	2005	SIGMOD	8.4857765e-05
6,483	Similarity Search: A Matching Based Approach	2006	VLDB	5.8667204e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,259	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
2	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
3	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
4	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
5	10,454	Fast-Convergent Proximity Graphs for Approximate Nearest Neighbor Search	2026	SIGMOD
6	10,447	Efficient and Robust Out-Of-Distribution Vector Similarity Search with Cross-Distribution Monotonic Graph	2026	SIGMOD
7	3,710	Efficient Reverse k-Nearest Neighbor Search in Arbitrary Metric Spaces	2006	SIGMOD
8	592	Distance-Based Indexing For High-Dimensional Metric Spaces	1997	SIGMOD
9	8,655	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD
10	9,334	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB