Применение трехкомпонентных ключей для полнотекстового поиска с учетом расстояния с гарантированным временем отклика
Автор: Веретенников Александр Борисович
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 1 т.7, 2018 года.
Бесплатный доступ
Рассматриваются задачи поиска фраз и наборов слов в большом объеме текстов. В результате поиска получаем список документов, содержащих заданные слова, при этом документы, где слова располагаются ближе друг к другу, считаются более релевантными. Поскольку эта задача требует сохранения в индексе информации о каждом вхождении каждого слова в текстах, запросы, включающие часто встречающиеся слова, требуют для своего выполнения длительного времени. В некоторых поисковых системах предлагается ввести список стоп слов, которые не учитываются при поиске, но этот подход снижает качество поиска. В данной работе при поиске обрабатываются все слова и применяются дополнительные индексы. С помощью дополнительных индексов время выполнения поискового запроса, включающего часто встречающиеся слова, может быть снижено в десятки раз. Разработан новый вид индекса с трехкомпонентными ключами. Приведены алгоритмы поиска и результаты экспериментов поиска в сравнении с обычными индексами. Эксперименты показывают, что при применении разработанных индексов для определенного класса запросов, состоящих из самых часто встречающихся слов, скорость поиска возрастает более чем в 90 раз.
Полнотекстовый поиск, поисковые системы, инвертированные файлы, дополнительные индексы, поиск с учетом близости слов
Короткий адрес: https://sciup.org/147160640
IDR: 147160640 | УДК: 519.683.5 | DOI: 10.14529/cmse180105
Proximity full-text search with response time guarantee by means of three component keys
Searches for phrases and word sets in large text arrays by means of additional indexes are considered. A search result is a list of documents that contain specified words. A document which contains the query words near each other is more important. Such a tack required to store one posting per any word occurrence in a document. Some search systems use a list of stop words and exclude any information about a stop word from the index thus reducing search quality. In our paper we store information about all words to ensure search quality and build additional indexes for most frequently used words. Use of the additional indexes may reduce the query processing time by an order of magnitude and more in comparison with standard indexes. A new three component key based index has described. Results of search experiments are given and new search algorithm is provided. The results of the experiments shows 90 times improvement of search time for a class of queries containing most frequently used words in comparison with default inverted file.
Список литературы Применение трехкомпонентных ключей для полнотекстового поиска с учетом расстояния с гарантированным временем отклика
- 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. P. 267-277 DOI: 10.1145/1476589.1476628
- Zobel J., Moffat A. Inverted Files for Text Search Engines//ACM Computing Surveys, 2006. Vol. 38, No. 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. P. 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. P. 192-202.
- Zipf G. Relative Frequency as a Determinant of Phonetic Change//Harvard Studies in Classical Philology. 1929. Vol. 40. P. 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. P. 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, P. 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. P. 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. P. 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. P. 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. P. 1229-1238 DOI: 10.1145/1871437.1871593
- Веретенников А.Б. Использование дополнительных индексов для более быстрого полнотекстового поиска фраз, включающих часто встречающиеся слова//Системы управления и информационные технологии. 2013. № 2(52). С. 61-66.
- Веретенников А.Б. Эффективный полнотекстовый поиск с использованием дополнительных индексов часто встречающихся слов//Системы управления и информационные технологии. 2016. № 4(66). С. 52-60.
- Williams J.W.J. Algorithm 232 -Heapsort//Communications of the ACM. 1964. Vol. 7, No. 6. P. 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. P. 287-299 DOI: 10.1007/978-3-540-75530-2_26
