Geodesic
Proximity full-text search with response time guarantee by means of three component keys
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 1, pp. 60-77 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: full-text search, search engines, inverted files, additional indexes, proximity search. 
@article{VYURV_2018_7_1_a4,
     author = {A. B. Veretennikov},
     title = {Proximity full-text search with response time guarantee by means of three component keys},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {60--77},
     year = {2018},
     volume = {7},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2018_7_1_a4/}
}
TY  - JOUR
AU  - A. B. Veretennikov
TI  - Proximity full-text search with response time guarantee by means of three component keys
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2018
SP  - 60
EP  - 77
VL  - 7
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURV_2018_7_1_a4/
LA  - ru
ID  - VYURV_2018_7_1_a4
ER  - 
%0 Journal Article
%A A. B. Veretennikov
%T Proximity full-text search with response time guarantee by means of three component keys
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2018
%P 60-77
%V 7
%N 1
%U http://geodesic.mathdoc.fr/item/VYURV_2018_7_1_a4/
%G ru
%F VYURV_2018_7_1_a4
A. B. Veretennikov. Proximity full-text search with response time guarantee by means of three component keys. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 1, pp. 60-77. http://geodesic.mathdoc.fr/item/VYURV_2018_7_1_a4/

[1] R. B. Miller, “Response Time in Man-Computer Conversational Transactions”, Proceedings: AFIPS Fall Joint Computer Conference, AFIPS '68 (San Francisco, California, December 09–11), v. 33, 1986, 267–277

[2] J. Zobel, A. Moffat, “Inverted Files for Text Search Engines”, AFIPS '68 (San Francisco, California, December 09–11), ACM Computing Surveys, 38, no. 2(6), 2006 | DOI

[3] A. Tomasic, H. Garcia-Molina, K. Shoens, “Incremental Updates of Inverted Lists for Text Document Retrieval”, Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, SIGMOD ’94 (Minneapolis, Minnesota, May 24–27), v. 33, 1994, 289–300 | DOI

[4] E. W. Brown, J. P. Callan, W. B. Croft, “Fast Incremental Indexing for Full-Text Information Retrieval”, Proceedings of the 20th International Conference on Very Large Data Bases, VLDB ’94 (Santiago de Chile, Chile, September 12–15), 1994, 192–202

[5] G. Zipf, “Relative Frequency as a Determinant of Phonetic Change”, Harvard Studies in Classical Philology, 40 (1929), 1–95 | DOI

[6] H. E. Williams, J. Zobel, D. Bahle, “Fast Phrase Querying with Combined Indexes”, ACM Transactions on Information Systems (TOIS), 22:4 (2004), 573–594 | DOI

[7] D. Bahle, H. E. Williams, J. Zobel, “Efficient Phrase Querying with an Auxiliary Index”, Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’02 (Tampere, Finland, August 11–15), 2002, 215–221 | DOI

[8] V. N. Anh, A. Moffat, “Pruned Query Evaluation Using Pre-computed Impacts”, Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’06 (Seattle, Washington, USA, August 06–11), ACM Press, 2006, 372–379 | DOI

[9] V. N. Anh, O. de Kretser, A. Moffat, “Vector-Space Ranking with Effective Early Termination”, Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’01 (New Orleans, Louisiana, USA, September 9–12), 2001, 35–42 | DOI

[10] S. Garcia, H. E. Williams, A. Cannane, “Access-Ordered Indexes”, Proceedings of the 27th Australasian Conference on Computer Science, ACSC ’04 (Dunedin, New Zealand, January 18–22), 2004, 7–14

[11] H. Yan, S. Shi, F. Zhang, T. Suel, J.-R. Wen, “Efficient Term Proximity Search with Term-Pair Indexes”, Proceedings of the 19th ACM International Conference on Information and Knowledge Management, CIKM ’10 (Toronto, ON, Canada, October 26–30), 2010, 1229–1238 | DOI

[12] A. B. Veretennikov, “Using Additional Indexes for Fast Full-Text Searching Phrases that Contains Frequently Used Words”, Control Systems and Information Technologies, 52:2 (2013), 61–66

[13] A. B. Veretennikov, “Efficient Full-Text Search by Means of Additional Indexes of Frequently Used Words”, Control Systems and Information Technologies, 66:4 (2016), 52–60

[14] J. W. J. Williams, “Algorithm 232 — Heapsort”, Communications of the ACM, 7:6 (1964), 347–348

[15] R. Schenkel, A. Broschart, S. Hwang, M. Theobald, G. Weikum, “Efficient Text Proximity Search”, Lecture Notes in Computer Science., String Processing and Information Retrieval. 14th International Symposium. SPIRE 2007 (Santiago de Chile, Chile, October 29–31), v. 4276, Springer, Berlin, Heidelberg, 2007, 287–299 | DOI