D 2008

Detecting Co-Derivative Documents in Large Text Collections

POMIKÁLEK, Jan a Pavel RYCHLÝ

Základní údaje

Originální název

Detecting Co-Derivative Documents in Large Text Collections

Název česky

Detekce blízkých dokumentů ve velkých textových kolekcích

Autoři

Vydání

Marrakech, Morocco, Proceedings of the Sixth International Language Resources and Evaluation (LREC'08), od s. 132-135, 3 s. 2008

Nakladatel

European Language Resources Association (ELRA)

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Maroko

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/08:00024198

Organizační jednotka

Fakulta informatiky

ISBN

2-9517408-4-0

UT WoS

Klíčová slova anglicky

Detecting; Large Text Collections

Štítky

Příznaky

Mezinárodní význam
Změněno: 27. 6. 2008 13:56, Ing. Dana Komárková

Anotace

ORIG CZ

V originále

We have analyzed the SPEX algorithm by Bernstein and Zobel (2004) for detecting co-derivative documents using duplicate n-grams. Although we totally agree with the claim that not using unique n-grams can greatly increase the efficiency and scalability of the process of detecting co-derivative documents, we have found serious bottlenecks in the way SPEX finds the duplicate n-grams. While the memory requirements for computing co-derivative documents can be reduced to up to 1% by only using duplicate n-grams, SPEX needs about 40 times more memory for computing the list of duplicate n-grams itself. Therefore the memory requirements of the whole process are not reduced enough to make the algorithm practical for very large collections. We propose a solution for this problem using an external sort with the suffix array in-memory sorting and temporary file compression. The proposed algorithm for computing duplicate n-grams uses a fixed amount of memory for any input size.

Česky

Analyzovali jsme algoritmus SPEX (Bernstein a Zobel, 2004) pro detekci blízkých dokumentů s použitím duplicitních n-gramů. Přestože zcela souhlasíme s tvrzením, že zanedbání unikátních n-gramů může vést ke značenému zvýšení efektivity a škálovatelnosti procesu detekce blízkých dokumentů, objevili jsme závažné nedostatky ve způsobu, kterým SPEX vyhledává duplicitní n-gramy. Paměťové nároky na výpočet blízkých dokumentů mohou být sníženy až na 1%, použijeme-li pouze duplicitní n-gramy, avšak SPEX potřebuje přibližně 40x více paměti pro výpočet samotného seznamu duplicitních n-gramů. Celkové paměťové nároky tedy nejsou dostatečně nízké na to, aby byl algoritmus prakticky použitelný pro velmi velké kolekce. Navrhli jsme řešení tohoto problému s použitím externího řazení s řazením v paměti pomocí sufixového pole a komprese dočasných souborů. Navržený algoritmus pro výpočet duplicitních n-gramů vyžaduje pevné množství paměti pro vstup libovolné velikosti.

Návaznosti

LC536, projekt VaV
Název: Centrum komputační lingvistiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Centrum komputační lingvistiky
1ET100300419, projekt VaV
Název: Inteligentní modely, algoritmy, metody a nástroje pro vytváření sémantického webu
Investor: Akademie věd ČR, Inteligentní modely, algoritmy, metody a nástroje pro vytváření sémantického webu
2C06009, projekt VaV
Název: Prostředky tvorby komplexní báze znalostí pro komunikaci se sémantickým webem v přirozeném jazyce (Akronym: COT-SEWing)
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Prostředky tvorby komplexní báze znalostí pro komunikaci se sémantickým webem v přirozeném jazyce