About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Krátký, Michal ; Skopal, Tomáš ; Snášel, Václav
Multidimensional term indexing for efficient processing of complex queries. (English). Kybernetika, vol. 40 (2004), issue 3, pp. [381]-396
MSC: 14Q15, 68P05, 68P10, 68P20 | Zbl 1249.68042
Keywords:
term indexing; complex queries; multidimensional data structures; BUB-forest
Summary:
The area of Information Retrieval deals with problems of storage and retrieval within a huge collection of text documents. In IR models, the semantics of a document is usually characterized using a set of terms. A common need to various IR models is an efficient term retrieval provided via a term index. Existing approaches of term indexing, e. g. the inverted list, support efficiently only simple queries asking for a term occurrence. In practice, we would like to exploit some more sophisticated querying mechanisms, in particular queries based on regular expressions. In this article we propose a multidimensional approach of term indexing providing efficient term retrieval and supporting regular expression queries. Since the term lengths are usually different, we also introduce an improvement based on a new data structure, called BUB-forest, providing even more efficient term retrieval.
References:
[1] Baeza-Yates R., Ribeiro-Neto B.: Modern Information Retrieval. Addison Wesley, New York 1999
[2] Bayer R.: The iniversal B-tree for multidimensional indexing: General concepts. In: Proc. World-Wide Computing and its Applications’97, WWCA’97, Tsukuba 1997
[3] Beckmann N., Kriegel H., Schneider, R., Seeger B.: The R*-tree: An effcient and robust access method for points and rectangles. In: Proc. 1990 ACM SIGMOD Internat. Conference on Management of Data, Atlantic City, NJ 1990, pp. 322–331
[4] Böhm C., Berchtold, S., Keim D. A.: Searching in high-dimensional spaces – Index structures for improving the performance of multimedia databases. ACM, 2002
[5] Crochemore M., Rytter W.: Text Algorithms. Oxford University Press, Oxford 1994 MR 1307378 | Zbl 1078.68151
[6] Deppisch U.: S-tree: a dynamic balanced signature index for office retrieval. In: Proc. 9th ACM SIGIR Conference, Pisa 1986, pp. 77–87
[7] Dvorský J., Krátký M., Skopal, T., Snášel V.: Term indexing in information retrieval systems. In: Proc. CIC’03, CSREA Press, Las Vegas 2003
[8] Faloutsos C.: Gray codes for partial match and range queries. IEEE Trans. Software Engrg. 14 (1988), 10, xxx–xxx DOI 10.1109/32.6184 | MR 0962343 | Zbl 0659.68125
[9] Fenk R.: The BUB-Tree. In: Proc. 28rd VLDB Internat. Conference on VLDB. Hongkong 2002
[10] Fenk R., Markl, V., Bayer R.: Improving multidimensional range queries of non rectangular volumes specified by a query box set. In: Proc. Internat. Symposium on Database, Web and Cooperative Systems (DWACOS), Baden-Baden 1999
[11] Ferragina P., Grossi R.: A fully-dynamic data structure for external substring search. In: Proc. ACM Symposium on Theory of Computing, 1995 Zbl 0978.68513
[12] Guttman A.: R-Trees: A dynamic index structure for spatial searching. In: Proc. ACM SIGMOD 1984, ACM Press, Boston 1984, pp. 47–57
[13] Manolopoulos Y., Theodoridis, Y., Tsotras V.: Advanced Database Indexing. Kluwer, Dordrecht 2001 Zbl 0943.68049
[14] Markl V.: Mistral: Processing Relational Queries using a Multidimensional Access Technique. Ph.D. Thesis. Technical University München 1999, http://mistral.in.tum.de/results/publications/Mar99.pdf
[15] NIST: Text REtrieval Conference (TREC). 2003, http://trec.nist.gov/
[16] Ramsak F., Markl V., Fenk R., Zirkel M., Elhardt, K., Bayer R.: Integrating the UB-tree into a database system kernel. In: Proc. 26th VLDB Internat. Conference, Morgan Kaufmann, Cairo 2000
[17] Roman S.: Advanced Linear Algebra. Springer Verlag, Berlin 1995 Zbl 1132.15002
[18] Salton G., McGill M. J.: Introduction to Modern Information Retrieval. First edition. McGraw Hill, New York 1983 Zbl 0523.68084
[19] Skopal T., Krátký M., Snášel, V., Pokorný J.: On Range Queries in Universal B-trees. Technical Report No. ARG-TR-01-2003, Department of Computer Science, VŠB-Technical University of Ostrava 2003, http://www.cs.vsb.cz/arg/techreports/range.pdf
[20] Stephen G. A.: String Searching Algorithms. Lecture Notes Series on Computing, World Scientific, 1998 MR 1313914 | Zbl 0831.68028
[21] Wirth N.: Algorithms and Data Structures. Prentice Hall, Englewood Cliffs, N. J. 1984 MR 0808586 | Zbl 0910.68053
[22] Witten I. H., Moffat, A., Bell T. C.: Managing Gigabytes, Compressing and Indexing Documents and Images. Van Nostrand Reinhold, New York 1994 Zbl 0821.68051
[23] Consortium, W3: Extensible Markup Language (XML) 1. 0. 1998, http://www.w3.org/ TR/REC-xml
Partner of
EuDML logo