Применение трехкомпонентных ключей для полнотекстового поиска с учетом расстояния с гарантированным временем отклика

Александр Борисович Веретенников

Аннотация


Рассматриваются задачи поиска фраз и наборов слов в большом объеме текстов. В результате поиска получаем список документов, содержащих заданные слова, при этом документы, где слова располагаются ближе друг к другу, считаются более релевантными. Поскольку эта задача требует сохранения в индексе информации о каждом вхождении каждого слова в текстах, запросы, включающие часто встречающиеся слова, требуют для своего выполнения длительного времени. В некоторых поисковых системах предлагается ввести список стоп слов, которые не учитываются при поиске, но этот подход снижает качество поиска. В данной работе при поиске обрабатываются все слова и применяются дополнительные индексы. С помощью дополнительных индексов время выполнения поискового запроса, включающего часто встречающиеся слова, может быть снижено в десятки раз. Разработан новый вид индекса с трехкомпонентными ключами. Приведены алгоритмы поиска и результаты экспериментов поиска в сравнении с обычными индексами. Эксперименты показывают, что при применении разработанных индексов для определенного класса запросов, состоящих из самых часто встречающихся слов, скорость поиска возрастает более чем в 90 раз.

Ключевые слова


полнотекстовый поиск; поисковые системы; инвертированные файлы; дополнительные индексы; поиск с учетом близости слов

Полный текст:

PDF

Литература


Miller R.B. Response Time in Man-Computer Conversational Transactions. Proceedings: AFIPS Fall Joint Computer Conference. San Francisco, California, December 09-11, 1968. vol. 33. pp. 267-277. DOI: 10.1145/1476589.1476628.

Zobel J., Moffat A. Inverted Files for Text Search Engines. ACM Computing Surveys, 2006, 38(2), Article 6. DOI: 10.1145/1132956.1132959.

Tomasic A., Garcia-Molina H., Shoens K. Incremental Updates of Inverted Lists for Text Document Retrieval. SIGMOD '94 Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. Minneapolis, Minnesota, May 24-27, 1994. pp. 289-300. DOI: 10.1145/191839.191896.

Brown E.W., Callan J.P., Croft W.B. Fast Incremental Indexing for Full-Text Information Retrieval. VLDB '94 Proceedings of the 20th International Conference on Very Large Data Bases. Santiago de Chile, Chile, September 12-15, 1994. pp. 192-202.

Zipf G. Relative Frequency as a Determinant of Phonetic Change. Harvard Studies in Classical Philology. 1929. vol. 40. pp. 1-95. DOI: 10.2307/408772.

Williams H.E., Zobel J., Bahle D. Fast Phrase Querying with Combined Indexes. ACM Transactions on Information Systems (TOIS). 2004. vol. 22, no. 4. pp. 573-594. DOI: 10.1145/1028099.1028102.

Bahle D., Williams H.E., Zobel J. Efficient Phrase Querying with an Auxiliary Index. SIGIR '02 Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Tampere, Finland, August 11-15, 2002, pp. 215-221. DOI: 10.1145/564376.564415.

Anh V.N., Moffat A. Pruned Query Evaluation Using Pre-computed Impacts. SIGIR '06 Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Seattle, Washington, USA, August 06-11, 2006. pp. 372-379. ACM Press. DOI: 10.1145/1148170.1148235.

Anh V.N., de Kretser O., Moffat A. Vector-Space Ranking with Effective Early Termination. SIGIR '01 Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New Orleans, Louisiana, USA, September 9-12, 2001. pp. 35-42. DOI: 10.1145/383952.383957.

Garcia S, Williams H.E., Cannane A. Access-Ordered Indexes. ACSC '04 Proceedings of the 27th Australasian Conference on Computer Science. Dunedin, New Zealand, January 18-22, 2004. pp. 7-14.

Yan H., Shi S., Zhang F., Suel T., Wen J.-R. Efficient Term Proximity Search with Term-Pair Indexes. CIKM '10 Proceedings of the 19th ACM International Conference on Information and Knowledge Management. Toronto, ON, Canada, October 26-30, 2010. pp. 1229-1238. DOI: 10.1145/1871437.1871593.

Veretennikov A.B. Using Additional Indexes for Fast Full-Text Searching Phrases that Contains Frequently Used Words. Sistemy upravleniya i informatsionnye tekhnologii [Control Systems and Information Technologies]. 2013. vol. 52, no. 2. pp. 61-66.

Veretennikov A.B. Efficient Full-Text Search by Means of Additional Indexes of Frequently Used Words. Sistemy upravleniya i informatsionnye tekhnologii [Control Systems and Information Technologies]. 2016. vol. 66, no. 4. pp. 52-60.

Williams J.W.J. Algorithm 232 - Heapsort. Communications of the ACM. 1964. vol. 7, no. 6. pp. 347-348.

Schenkel R., Broschart A., Hwang S., Theobald M., Weikum G. Efficient Text Proximity Search. String Processing and Information Retrieval. 14th International Symposium. SPIRE 2007. Lecture Notes in Computer Science. Santiago de Chile, Chile, October 29-31, 2007. vol. 4726. Springer, Berlin, Heidelberg. pp. 287-299. DOI: 10.1007/978-3-540-75530-2_26.




DOI: http://dx.doi.org/10.14529/cmse180105