Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki:

Personal entry:
Save password
Forgotten password?

Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2019, Volume 29, Issue 1, Pages 117–132 (Mi vuu671)  

This article is cited in 1 scientific paper (total in 1 paper)


An efficient algorithm for three-component key index construction

A. B. Veretennikov

Ural Federal University, pr. Lenina, 51, Yekaterinburg, 620083, Russia

Abstract: Proximity full-text searches in large text arrays are considered. A search query consists of several words. The search result is a list of documents containing these words. In a modern search system, documents that contain search query words that are near each other are more relevant than other documents. To solve this task, for each word in each indexed document, we need to store a record in the index. In this case, the query search time is proportional to the number of occurrences of the queried words in the indexed documents. Consequently, it is common for search systems to evaluate queries that contain frequently occurring words much more slowly than queries that contain less frequently occurring, ordinary words. For each word in the text, we use additional indexes to store information about nearby words at distances from the given word of less than or equal to $MaxDistance$, which is a parameter. This parameter can take a value of 5, 7, or even more. Three-component key indexes can be created for faster query execution. Previously, we presented the results of experiments showing that, when queries contain very frequently occurring words, the average time of the query execution with three-component key indexes is 94.7 times less than that required when using ordinary inverted indexes. In the current work, we describe a new three-component key index building algorithm. We prove the correctness of the algorithm. We present the results of experiments of the index creation depending on the value of $MaxDistance$.

Keywords: full-text search, search engines, inverted files, additional indexes, proximity search, three-component key indexes.

Funding Agency Grant Number
Ministry of Education and Science of the Russian Federation 02.A03.21.0006
The work was supported by Act 211 Government of the Russian Federation, contract № 02.A03.21.0006


Full text: PDF file (789 kB)
Full text:
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.683.5
MSC: 68P20, 68P10
Received: 01.07.2018

Citation: A. B. Veretennikov, “An efficient algorithm for three-component key index construction”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 29:1 (2019), 117–132

Citation in format AMSBIB
\by A.~B.~Veretennikov
\paper An efficient algorithm for three-component key index construction
\jour Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki
\yr 2019
\vol 29
\issue 1
\pages 117--132

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. B. Veretennikov, “Ranzhirovanie dokumentov pri polnotekstovom poiske s uchetom rasstoyaniya s ispolzovaniem indeksov s mnogokomponentnymi klyuchami”, Vestn. Udmurtsk. un-ta. Matem. Mekh. Kompyut. nauki, 31:1 (2021), 132–148  mathnet  crossref
  • Вестник Удмуртского университета. Математика. Механика. Компьютерные науки
    Number of views:
    This page:165
    Full text:106

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021