Implementation Notes for the Soft Cosine Measure

NOVOTNÝ, Vít. Implementation Notes for the Soft Cosine Measure. Online. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM '18). Torino, Italy: Association for Computing Machinery, 2018, s. 1639-1642. ISBN 978-1-4503-6014-2. Dostupné z: https://dx.doi.org/10.1145/3269206.3269317.

Základní údaje

Originální název

Implementation Notes for the Soft Cosine Measure

Autoři

NOVOTNÝ, Vít (203 Česká republika, garant, domácí)

Vydání

Torino, Italy, Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM '18), od s. 1639-1642, 4 s. 2018

Nakladatel

Association for Computing Machinery

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Itálie

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

Postprint DOI

Kód RIV

RIV/00216224:14330/18:00101853

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4503-6014-2

DOI

http://dx.doi.org/10.1145/3269206.3269317

UT WoS

000455712300190

Klíčová slova anglicky

Vector Space Model; computational complexity; similarity measure

Štítky

core_A, firank_A, information retrieval, ranking, SCM, similarity search, soft cosine measure

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

The standard bag-of-words vector space model (VSM) is efficient, and ubiquitous in information retrieval, but it underestimates the similarity of documents with the same meaning, but different terminology. To overcome this limitation, Sidorov et al. proposed the Soft Cosine Measure (SCM) that incorporates term similarity relations. Charlet and Damnati showed that the SCM is highly effective in question answering (QA) systems. However, the orthonormalization algorithm proposed by Sidorov et al. has an impractical time complexity of O(n^4), where n is the size of the vocabulary. In this paper, we prove a tighter lower worst-case time complexity bound of O(n^3). We also present an algorithm for computing the similarity between documents and we show that its worst-case time complexity is O(1) given realistic conditions. Lastly, we describe implementation in general-purpose vector databases such as Annoy, and Faiss and in the inverted indices of text search engines such as Apache Lucene, and ElasticSearch. Our results enable the deployment of the SCM in real-world information retrieval systems.

---

Návaznosti

MUNI/A/1038/2017, interní kód MU	Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 18 Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 18, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
MUNI/A/1213/2017, interní kód MU	Název: Aplikovaný výzkum na FI: bezpečnost počítačových systémů, SW architektury kritických infrastruktur, zpracování velkých dat, vizualizace dat a virtuální realita Investor: Masarykova univerzita, Aplikovaný výzkum na FI: bezpečnost počítačových systémů, SW architektury kritických infrastruktur, zpracování velkých dat, vizualizace dat a virtuální realita, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty
TD03000295, projekt VaV	Název: Inteligentní software pro sémantické hledání dokumentů (Akronym: ISSHD) Investor: Technologická agentura ČR, Inteligentní software pro sémantické hledání dokumentů

Přiložené soubory

1808.09407.pdf

Vyhledat podobné dokumenty