zbMATH — the first resource for mathematics

Fast set intersection and two-patterns matching. (English) Zbl 1207.68270
Summary: We present a new problem, the fast set intersection problem, which is to preprocess a collection of sets in order to efficiently report the intersection of any two sets in the collection. In addition we suggest new solutions for the two-dimensional substring indexing problem and the document listing problem for two patterns by reduction to the fast set intersection problem.

68T10 Pattern recognition, speech recognition
68P20 Information storage and retrieval of data
68W05 Nonnumerical algorithms
Full Text: DOI
[1] Demaine, E.D.; López-Ortiz, A.; Munro, J.I., Adaptive set intersections, unions, and differences, (), 743-752 · Zbl 0957.68124
[2] Baeza-Yates, R.A., A fast set intersection algorithm for sorted sequences, (), 400-408 · Zbl 1103.68485
[3] Barbay, J.; López-Ortiz, R.; Lu, T., Faster adaptive set intersections for text searching, (), 146-157, URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=
[4] P. Bille, A. Pagh, R. Pagh, Fast evaluation of union-intersection expressions, CoRR abs/0708.3259. · Zbl 1193.68081
[5] Ferragina, P.; Koudas, N.; Srivastava, D.; Muthukrishnan, S., Two-dimensional substring indexing, (), 282-288, URL http://dx.doi.org/10.1145/375551.375610 · Zbl 1054.68043
[6] Muthukrishnan, S., Efficient algorithms for document retrieval problems, (), 657-666 · Zbl 1093.68588
[7] Fredman, M.L.; Komlós, J.; Szemerédi, E., Storing a sparse table with 0(1) worst case access time, J. ACM, 31, 3, 538-544, (1984) · Zbl 0629.68068
[8] Pagh, R., Faster deterministic dictionaries, (), 487-493 · Zbl 0954.68062
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.