Vi studerar problemet med domänsökning där en domän är en uppsättning skilda värden från ett ospecificerat universum. Vi använder Jaccard set inneslutning score, definierat som  tillQ  med X och/eller Q, som ett mått på relevansen av en domän X för en frågedomän Q. Vårt val av Jaccard uppsättning inneslutning över Jaccard likhet som ett mått på relevans gör vårt arbete särskilt lämpligt för att söka Open Data och data på webben, eftersom Jaccard likhet är känd för att ha dålig prestanda över uppsättningar med stora skillnader i deras domänstorlekar. Vi visar att domänerna som finns i flera öppna data- och webbdatabaser i verkligheten visar en power-law-distribution över deras domänstorlekar. Vi presenterar en ny indexstruktur, Locality Sensitive Hashing (LSH) Ensemble, som löser problemet med domänsökning med hjälp av set inneslutning på Internet skala. Vår indexstruktur och sökalgoritm klarar av datavolym och skev med hjälp av dataskisser med Minwise Hashing och domänpartitionering. Vår indexstruktur utgår inte från en föreskriven uppsättning datavärden. Vi konstruerar en kostnadsmodell som beskriver noggrannheten hos LSH Ensemble med en given partitionering. Detta gör att vi kan formulera datapartitioneringen för LSH Ensemble som ett optimeringsproblem. Vi bevisar att det finns en optimal partitionering för all datadistribution. Dessutom, för dataset efter en powerlaw-distribution, som observerats i Open Data och Web data corpora, visar vi att den optimala partitioneringen kan approximeras med hjälp av liksidiga, vilket gör det särskilt effektivt att använda i praktiken. Vi utvärderar vår algoritm med hjälp av verkliga data (Canadian Open Data och WDC Web Tables) som innehåller upp till tre miljoner domäner. Experimenten visar att vårt index konsekvent överträffar andra ledande alternativ i noggrannhet och prestanda. Förbättringarna är mest dramatiska för data med stor skev i domänstorlekarna. Även på tre miljoner domäner, vårt index upprätthåller frågeprestanda med under 50 millisekunders svarstid. Detta är en utökad version.
Dessutom, för att hitta fogbara tabeller, Zhu el al. REF studerade domänsökningen som är problemet med att hitta attribut som i hög grad innehåller värdena för en frågeattribut.
LSH Ensemble: Internet Scale Domain Search
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}