Top-k-frågor baserade på rankning element av flerdimensionella datauppsättningar är en grundläggande byggsten för många typer av information upptäckt. Den mest kända general-purpose algoritmen för att utvärdera top-k frågor är Fagin tröskel algoritm (TA). Eftersom användarens mål bakom top-k-frågor är att identifiera en eller några relevanta och nya dataobjekt, är det intressant att använda ungefärliga varianter av TA för att minska kostnaderna för körning. Detta dokument introducerar en familj av ungefärliga topk-algoritmer baserade på probabilistiska argument. När scanning index listor av den underliggande multidimensionella datautrymme i fallande ordning av lokala poäng, olika former av konvolution och härledda gränser används för att förutsäga när det är säkert, med hög sannolikhet, att släppa kandidat objekt och att beskära indexet skannar. De utvecklade metodernas precision och effektivitet utvärderas experimentellt utifrån en stor webbkorpus och en strukturerad datainsamling.
Ännu ett verk av Theobald et al. REF införde en ungefärlig TA-algoritm baserad på probabilistiska argument: När du skannar postlistorna i fallande ordning på lokala poäng används olika former av härledda gränser för att förutsäga när det är säkert, med stor sannolikhet, att hoppa över kandidatposter och därmed handla av noggrannhet för sorterad åtkomst.
Top-k Query Evaluation with Probabilistic Guarantees
{'venue': 'In VLDB', 'journal': None, 'mag_field_of_study': ['Computer Science']}