Maximal Intersection Queries in Randomized Graph Models.

Hoffmann, Benjamin, Lifshits, Yury and Nowotka, Dirk (2007) Maximal Intersection Queries in Randomized Graph Models. [Paper] In: Computer Science Russia (CSR). , 3 - 7 Sep 2007, Ekaterinburg, Russia . Computer Science – Theory and Applications. ; pp. 227-236 . DOI 10.1007/978-3-540-74510-5_24. Lecture Notes in Computer Science .

[thumbnail of MaxIntJ.pdf]
Preview
Text
MaxIntJ.pdf

Download (203kB) | Preview

Supplementary data:

Abstract

Consider a family of sets and a single set, called query set. How can one quickly find a member of the family which has a maximal intersection with the query set? Strict time constraints on the query and on a possible preprocessing of the set family make this problem challenging. Such maximal intersection queries arise in a wide range of applications, including web search, recommendation systems, and distributing on-line advertisements. In general, maximal intersection queries are computationally expensive. Therefore, one need to add some assumptions about input in order to get an efficient solution. We investigate two well-motivated distributions over all families of sets and propose an algorithm for each of them. We show that with very high probability an almost optimal solution is found in time logarithmic in the size of the family. In particular, we point out a threshold phenomenon on the probabilities of intersecting sets in each of our two input models which leads to efficient algorithms mentioned above.

Document Type: Conference or Workshop Item (Paper)
Keywords: maximum intersection problem nearest neighbour problem randomized graph models large scale algorithms
Research affiliation: Kiel University
Publisher: Springer
Date Deposited: 15 Feb 2013 21:27
Last Modified: 23 Sep 2019 21:29
URI: https://oceanrep.geomar.de/id/eprint/20533

Actions (login required)

View Item View Item