UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Probably Approximately Correct Search

Cox, IJ; Fu, RX; Hansen, LK; (2009) Probably Approximately Correct Search. In: Azzopardi, L and Kazai, G and Robertspm, S and Ruger, S and Shokouhi, M and Song, D and Yilmaz, E, (eds.) ADVANCES IN INFORMATION RETRIEVAL THEORY. (pp. 2 - 16). SPRINGER-VERLAG BERLIN

Full text not available from this repository.


We consider the problem of searching a document collection using a set of independent computers. That is, the computers do not cooperate with one another either (i) to acquire their local index of documents or (ii) during the retrieval of a document. During the acquisition phase, each computer is assumed to randomly sample a subset of the entire collection. During retrieval, the query is issued to a random subset of computers, each of which returns its results to the query-issuer, who consolidates the results. We examine how the number of computers, and the fraction of the collection that each computer indexes, affects performance in comparison to a traditional deterministic configuration. We provide analytic formulae that, given the number of computers and the fraction of the collection each computer indexes, provide the probability of an approximately correct search, where a "correct search" is defined to be the result of a deterministic search on the entire collection. We show that the randomized distributed search algorithm can have acceptable performance under a range of parameters settings. Simulation results confirm our analysis.

Type: Proceedings paper
Title: Probably Approximately Correct Search
Event: 2nd International Conference on Theory of Information Retrieval
Location: Cambridge, ENGLAND
Dates: 2009-09-10 - 2009-09-12
ISBN-13: 978-3-642-04416-8
URI: http://discovery.ucl.ac.uk/id/eprint/135594
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item