Maximal intersection queries in randomized input models

DOI10.1007/S00224-008-9154-6MaRDI QIDQ2268345zbMATH OpenOpenAlexFDO

Authors Benjamin Hoffmann, Yury Lifshits, Dirk Nowotka, M. A. Lifshits

Publication date 5 March 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1004.0092

zbMATH Keywords

algorithms for large data setsmaximal intersection problemnearest neighbor problemrandomized input modelsZipf's law

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: Consider a family of sets and a single set, called the query set. How can one quickly find a member of the family which has a maximal intersection with the query set? 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. 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 which is logarithmic in the size of the family. Moreover, we point out a threshold phenomenon on the probabilities of intersecting sets in each of our two input models which leads to the efficient algorithms mentioned above.

Recommendations

• Maximal Intersection Queries in Randomized Graph Models
• Stochastic Algorithms: Foundations and Applications
• A Linear Time Approach to the Set Maxima Problem
• Lower bounds for set intersection queries
• scientific article; zbMATH DE number 2119687

Cites work

• A new method for approximate indexing and dictionary lookup with one error
• Dictionary matching and indexing with errors and don't cares
• Estimation of the Click Volume by Large Scale Regression Analysis
• Finding nearest neighbors in growth-restricted metrics
• scientific article; zbMATH DE number 1559575 (Why is no real title available?)
• scientific article; zbMATH DE number 1408945 (Why is no real title available?)
• scientific article; zbMATH DE number 6469222 (Why is no real title available?)
• Maximal Intersection Queries in Randomized Graph Models
• Similarity search. The metric space approach.
• The hardness of decoding linear codes with preprocessing
• The Structure and Function of Complex Networks

Cited in

(4)

• Maximal Intersection Queries in Randomized Graph Models
• Probabilistic Properties of Zipf Sets and Their Maximal Intersections
• Intersections of Zipf random sets: maximal weighted relevance
• Two limit theorems on the intersections of random Zipf sets

This page was built for publication: Maximal intersection queries in randomized input models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268345)