Load Balancing Query Processing in Metric-Space Similarity Search

GIL COSTA G. VERONICA; MAURICIO MARÍN

Conferencia; CCGrid; 2012

Metric-space similarity search has been provensuitable for searching large collections of complex objectssuch as images. A number of distributed index data struc-tures and respective parallel query processing algorithms havebeen proposed for clusters of distributed memory processors.Previous work has shown that best performance is achievedwhen using global indexing as opposed to local indexing.However global indexing is prone to performance degradationwhen query load becomes unbalanced across processors. Thispaper proposes a query scheduling algorithm that solves thisproblem. It adaptively load balances processing of user queriesthat are dynamically skewed towards particular sections ofthe distributed index. Sections highly hit by queries can bekept replicated. Experimental results show that with 1%–10% replication performance improves signi cantly (e.g., 35%)under skewed work-loads.