Hash-Samples

Wir untersuchen Techniken zur Schätzung der Selektivität für Abfragen zur Ähnlichkeit von Mengen. In der Vergangenheit wurden eine Vielzahl von Ähnlichkeitsmaßen für Mengen vorgeschlagen. In diesem Werk konzentrieren wir uns auf die Klasse von gewichteten Ähnlichkeitsmaßen (z. B. TF/IDF und BM25 Kosinusähnlichkeit und Varianten) und entwerfen Selektivitätsschätzer, die auf a priori konstruierten Stichproben basieren. Zunächst untersuchen wir die Fallstricke, die mit einfachen Anwendungen der Zufallsstichprobe verbunden sind, und argumentieren, dass Vorsicht geboten ist, wie die Stichproben konstruiert werden; gleichmäßige Zufallsstichproben führen zu sehr niedriger Genauigkeit, während abfrageempfindliche Echtzeitstichproben teurer sind als exakte Lösungen (sowohl in Bezug auf CPU- als auch I/O-Kosten). Wir zeigen, wie man robuste Stichproben a priori basierend auf bestehenden Synopsen für die Schätzung verschiedener Werte aufbaut. Wir beweisen die Genauigkeit unserer Technik theoretisch und überprüfen ihre Leistung experimentell. Unser Algorithmus ist um Größenordnungen schneller als exakte Lösungen und hat einen sehr geringen Speicheraufwand.