×

zbMATH — the first resource for mathematics

Practical compact indexes for top-\(k\) document retrieval. (English) Zbl 1369.68171

MSC:
68P05 Data structures
68P20 Information storage and retrieval of data
Software:
Wumpus
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] D. Arroyuelo, R. Cánovas, G. Navarro, and K. Sadakane. 2010. Succinct trees in practice. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX’10). 84–97. · doi:10.1137/1.9781611972900.9
[2] R. Baeza-Yates and B. Ribeiro-Neto. 2011. Modern Information Retrieval (2nd ed.). Addison-Wesley.
[3] D. Belazzougui, G. Navarro, and D. Valenzuela. 2013. Improved compressed indexes for full-text document retrieval. Journal of Discrete Algorithms 18, 3–13. · Zbl 1268.68075 · doi:10.1016/j.jda.2012.07.005
[4] D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman, and S. S. Rao. 2005. Representing trees of higher degree. Algorithmica 43, 4, 275–292. · Zbl 1086.68034 · doi:10.1007/s00453-004-1146-6
[5] N. Brisaboa, G. de Bernardo, R. Konow, G. Navarro, and D. Seco. 2016. Aggregated 2D range queries on clustered points. Information Systems 60, 34–49. · doi:10.1016/j.is.2016.03.004
[6] N. Brisaboa, S. Ladra, and G. Navarro. 2013. DACs: Bringing direct access to variable-length codes. Information Processing and Management 49, 1, 392–404. · doi:10.1016/j.ipm.2012.08.003
[7] N. Brisaboa, S. Ladra, and G. Navarro. 2014. Compact representation of Web graphs with extended functionality. Information Systems 39, 1, 152–174. · doi:10.1016/j.is.2013.08.003
[8] S. Büttcher, C. Clarke, and G. Cormack. 2010. Information Retrieval: Implementing and Evaluating Search Engines. MIT Press, Cambridge, MA. · Zbl 1211.68176
[9] D. R. Clark. 1996. Compact Pat Trees. Ph.D. Dissertation. Waterloo, Ontario, Canada.
[10] B. Croft, D. Metzler, and T. Strohman. 2009. Search Engines: Information Retrieval in Practice. Pearson Education.
[11] J. S. Culpepper, M. Petri, and F. Scholer. 2012. Efficient in-memory top-k document retrieval. In Proceedings of the 35th International ACM Conference on Research and Development in Information Retrieval (SIGIR’12). 225–234. · doi:10.1145/2348283.2348317
[12] S. Culpepper, G. Navarro, S. Puglisi, and A. Turpin. 2010. Top-k ranked document search in general text databases. In Algorithms—ESA 2010. Lecture Notes in Computer Science, Vol. 6347. Springer, 194–205. · Zbl 1287.68035 · doi:10.1007/978-3-642-15781-3_17
[13] H. Ferrada and G. Navarro. 2014. Efficient compressed indexing for approximate top-k string retrieval. In String Processing and Information Retrieval. Lecture Notes in Computer Science, Vol. 8799. Springer, 18–30. · Zbl 06400028 · doi:10.1007/978-3-319-11918-2_3
[14] P. Ferragina and G. Manzini. 2005. Indexing compressed text. Journal of the ACM 52, 4, 552–581. · Zbl 1323.68261 · doi:10.1145/1082036.1082039
[15] J. Fischer and V. Heun. 2011. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM Journal on Computing 40, 2, 465–492. · Zbl 1222.05024 · doi:10.1137/090779759
[16] T. Gagie, G. Navarro, and S. J. Puglisi. 2012. New algorithms on wavelet trees and applications to information retrieval. Theoretical Computer Science 426–427, 25–41. · Zbl 1243.68161
[17] S. Gog. 2011. Compressed Suffix Trees: Design, Construction, and Applications. Ph.D. Dissertation. University of Ulm, Germany.
[18] S. Gog, T. Beller, A. Moffat, and M. Petri. 2014. From theory to practice: Plug and play with succinct data structures. In Proceedings of the 13th International Symposium on Experimental Algorithms (SEA’14). 326–337. · Zbl 06349909 · doi:10.1007/978-3-319-07959-2_28
[19] S. Gog and G. Navarro. 2015. Improved single-term top-k document retrieval. In Proceedings of the 17th Workshop on Algorithm Engineering and Experiments (ALENEX’15). 24–32. · doi:10.1137/1.9781611973754.3
[20] S. Gog and M. Petri. 2014. Optimized succinct data structures for massive data. Software —Practice and Experience 44, 11, 1287–1314. · doi:10.1002/spe.2198
[21] R. Grossi, A. Gupta, and J. Vitter. 2003. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’03). 841–850. · Zbl 1092.68584
[22] W.-K. Hon, M. Patil, R. Shah, and S.-B. Wu. 2010. Efficient index for retrieving top-k most frequent documents. Journal of Discrete Algorithms 8, 4, 402–417. · Zbl 1215.68095 · doi:10.1016/j.jda.2010.08.003
[23] W.-K. Hon, R. Shah, and J. S. Vitter. 2009. Space-efficient framework for top-k string retrieval problems. In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS’09). 713–722. · Zbl 1292.68182 · doi:10.1109/FOCS.2009.19
[24] J. Karkkainen, D. Kempa, and S. J. Puglisi. 2014. Hybrid compression of bitvectors for the FM-index. In Proceedings of the 24th Data Compression Conference (DCC’14). 302–311. · doi:10.1109/DCC.2014.87
[25] R. Konow and G. Navarro. 2013. Faster compact top-k document retrieval. In Proceedings of the 23rd Data Compression Conference (DCC’13). 351–360. · doi:10.1109/DCC.2013.43
[26] N. J. Larsson and A. Moffat. 2000. Off-line dictionary-based compression. Proceedings of the IEEE 88, 11, 1722–1732. · doi:10.1109/5.892708
[27] T.-Y. Liu. 2009. Learning to rank for information retrieval. Foundations and Trends in Information Retrieval 3, 3, 225–331. · doi:10.1561/1500000016
[28] V. Mäkinen and G. Navarro. 2006. Position-restricted substring searching. In LATIN 2006: Theoretical Informatics. Lecture Notes in Computer Science, Vol. 3887. Springer, 703–714. · Zbl 1145.68392 · doi:10.1007/11682462_64
[29] U. Manber and E. W. Myers. 1993. Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing 22, 5, 935–948. · Zbl 0784.68027 · doi:10.1137/0222058
[30] I. Munro. 1996. Tables. In Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, Vol. 1180. Springer, 37–42. · doi:10.1007/3-540-62034-6_35
[31] J. I. Munro and V. Raman. 2002. Succinct representation of balanced parentheses and static trees. SIAM Journal on Computing 31, 3, 762–776. · Zbl 1017.68037 · doi:10.1137/S0097539799364092
[32] S. Muthukrishnan. 2002. Efficient algorithms for document retrieval problems. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’02). 657–666. · Zbl 1093.68588
[33] G. Navarro. 2014. Spaces, trees and colors: The algorithmic landscape of document retrieval on sequences. ACM Computing Surveys 46, 4, Article No. 52. · Zbl 1305.68078 · doi:10.1145/2535933
[34] G. Navarro. 2016. Compact Data Structures: A Practical Approach. Cambridge University Press. · doi:10.1017/CBO9781316588284
[35] G. Navarro and V. Mäkinen. 2007. Compressed full-text indexes. ACM Computing Surveys 39, 1, Article No. 2. · doi:10.1145/1216370.1216372
[36] G. Navarro and Y. Nekrich. 2012. Top-k document retrieval in optimal time and linear space. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). · Zbl 1359.68053 · doi:10.1137/1.9781611973099.84
[37] G. Navarro, Y. Nekrich, and L. Russo. 2013. Space-efficient data-analysis queries on grids. Theoretical Computer Science 482, 60–72. · Zbl 1291.68155 · doi:10.1016/j.tcs.2012.11.031
[38] G. Navarro, S. J. Puglisi, and J. Sirén. 2014a. Document retrieval on repetitive collections. In Algorithms—ESA 2014. Lecture Notes in Computer Science, Vol. 8737. Springer, 725–736. · Zbl 1425.68099 · doi:10.1007/978-3-662-44777-2_60
[39] G. Navarro, S. J. Puglisi, and D. Valenzuela. 2014b. General document retrieval in compact space. ACM Journal of Experimental Algorithmics 19, 2, Article No. 3. · Zbl 1347.68103
[40] G. Navarro and K. Sadakane. 2014. Fully-functional static and dynamic succinct trees. ACM Transactions on Algorithms 10, 3, Article No. 16. · Zbl 1333.68084 · doi:10.1145/2601073
[41] D. Okanohara and K. Sadakane. 2007. Practical entropy-compressed rank/select dictionary. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX’07). 60–70. · doi:10.1137/1.9781611972870.6
[42] M. Patil, S. V. Thankachan, R. Shah, W.-K. Hon, J. S. Vitter, and S. Chandrasekaran. 2011. Inverted indexes for phrases and strings. In Proceedings of the 34th International ACM Conference on Research and Development in Information Retrieval (SIGIR’11). 555–564. · doi:10.1145/2009916.2009992
[43] R. Raman, V. Raman, and S. S. Rao. 2007. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Transactions on Algorithms 3, 4, Article No. 43. · Zbl 1093.68582 · doi:10.1145/1290672.1290680
[44] W. Szpankowski. 1993. A generalized suffix tree and its (un)expected asymptotic behaviors. SIAM Journal on Computing 22, 6, 1176–1198. · Zbl 0799.68050 · doi:10.1137/0222070
[45] S. Vigna. 2008. Broadword implementation of rank/select queries. In Proceedings of the 7th International Conference on Experimental Algorithms (WEA’08). 154–168. · Zbl 05288393 · doi:10.1007/978-3-540-68552-4_12
[46] P. Weiner. 1973. Linear pattern matching algorithms. In Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT’73). 1–11. · doi:10.1109/SWAT.1973.13
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.